# Computing M Sample DFT by Hand

• Number2Pencil
In summary, the M sample DFT of f(m) = cos(2*pi*(f*m)) for 0 <= m <= M-1, where M = 128 and f = 1/16, can be simplified using Euler's identity and a geometric series identity. The result is a function that depends on the values of f and M, and can be further simplified if f is a multiple of M.
Number2Pencil

## Homework Statement

Compute the M sample DFT of:

f(m) = cos(2*pi*(f*m)) for 0 <= m <= M-1

where M = 128, f = 1/16

This should be done by hand, and the solution will reduce to a very simple form.

## The Attempt at a Solution

I slaved through this problem and got an answer that seems to have the same shape and magnitude as the dft function in MATLAB, but it is not what I'd consider a "very simple form." Could you please check my work and see if there is any major simplifications I missed?

First, we look at the generic formula for the DFT:

$$\tilde{x(k)} = \sum_{n=0}^{N-1} x(n) e^{\frac{-j 2 \pi k n}{N}}$$

where x(k) is the frequency values at normalized frequency k, x(n) is the input sample, and N is the number of samples taken. For this problem, this formula is:
$$\tilde{f(k)} = \sum_{n=0}^{M-1} cos(2 \pi f_x n) e^{\frac{-j 2 \pi k n}{M}}$$

We can utilize Euler's identity:

$$cos(x) = \frac {e^{jx}+e^{-jx}}{2}$$

$$\tilde{f(k)} = \sum_{n=0}^{M-1} (\frac{e^{j2 \pi f_x n}+e^{-j 2 \pi f_x n}}{2}) e^{\frac{-j 2 \pi k n}{M}}$$

Distributing the outside exponential, separating into two summations:

$$\tilde{f(k)} = \sum_{n=0}^{M-1} \frac {e^{j 2 \pi f_x n}e^{-j 2 \pi k \frac{1}{M}n}} {2} + = \sum_{n=0}^{M-1} \frac {e^{-j 2 \pi f_x n}e^{-j2 \pi k \frac{1}{M}n}} {2}$$

Combine terms:

$$\tilde{f(k)} = \sum_{n=0}^{M-1} \frac{1}{2} e^{j 2 \pi n (f-\frac{1}{M}k)} + = \sum_{n=0}^{M-1} \frac{1}{2} e^{-j 2 \pi n (f+\frac{1}{M}k)}$$

The form of a geometric sum:

$$\sum_{n=0}^{M-1} a^n = \frac{1-a^M}{1-a}$$

In this case:

$$a = e^{j 2 \pi (f-\frac{1}{M}k)}$$

Resulting in:

$$\tilde{f(k)} = \frac{1}{2} \frac {1 - e^{j2 \pi (f-\frac{1}{M}k)M}} {1-e^{j2 \pi (f - \frac{1}{M}k)}} + \frac{1}{2} \frac {1-e^{-j 2 \pi (f+\frac{1}{M}k)M}} {1-e^{-j 2 \pi (f+\frac{1}{M}k)}}$$

There is a specific identity to be used:

$$\frac{1-e^{jaN}}{1-e^{ja}} = \frac{e^{\frac{ja(N-1)}{2}}sin(\frac{aN}{2})}{sin(\frac{a}{2})}$$

In our case:

$$\tilde{x(k)} = \frac{1}{2} \frac{ e^{\frac{[j2 \pi (f-\frac{1}{M}k)][M-1]}{2}} sin(\frac{[2 \pi (f-\frac{1}{M}k)]M}{2})} { sin(\frac{2 \pi (f-\frac{1}{M}k)}{2}) } + \frac{1}{2} \frac{ e^{\frac{[-j2 \pi (f+\frac{1}{M}k)][M-1]}{2}} sin(\frac{[-2 \pi (f+\frac{1}{M}k)]M}{2})} { sin(\frac{-2 \pi (f+\frac{1}{M}k)}{2}) }$$

Plugging in the original values:

$$\tilde{f(x)} = \frac{1}{2}e^{127 j \pi (\frac{1}{16}-\frac{1}{128}k)} \frac {sin[128 \pi (\frac{1}{16} - \frac{1}{128}k)]} {sin[\pi (\frac{1}{16} - \frac{1}{128}k)]} + \frac{1}{2}e^{-j 127 \pi (\frac{1}{16}+\frac{1}{128}k)} \frac {sin[128 \pi (\frac{1}{16}+\frac{1}{128}k)]} {sin[\pi (\frac{1}{16}+\frac{1}{128}k]}$$

Return to the sum of the geometric series. Consider the case that $f = \frac{\ell}{M}$ where $\ell$ is an integer.

## 1. What is a DFT and why is it important in computing?

A DFT (Discrete Fourier Transform) is a mathematical algorithm used to convert a signal from its original domain (usually time or space) to a representation in the frequency domain. This is important in computing because it allows us to analyze and manipulate signals in the frequency domain, which can be more intuitive and useful for certain applications.

## 2. How do you compute a DFT by hand?

To compute a DFT by hand, you will need to follow a series of steps that involve multiplication, addition, and complex number operations. First, you will need to convert your signal into a series of complex numbers. Then, you will apply the DFT formula, which involves multiplying each complex number by a series of complex exponential functions and summing the results. Finally, you will need to convert the resulting complex numbers back into their original form in the frequency domain.

## 3. What are the benefits of computing a DFT by hand?

Computing a DFT by hand can be beneficial for understanding the underlying principles and operations involved in the transformation process. It can also be useful for small-scale or educational purposes, where using a computer may not be necessary or practical.

## 4. What are some common applications of DFT?

DFT has a wide range of applications in various fields such as signal processing, image processing, audio processing, data compression, and more. Some examples include analyzing and manipulating audio signals in music production, filtering and noise reduction in images, and data compression in telecommunications.

## 5. Are there any limitations to computing a DFT by hand?

Computing a DFT by hand can be time-consuming and prone to human error, especially for larger signals. It also requires a good understanding of complex numbers and mathematical operations, which may be challenging for some individuals. Therefore, for practical applications, it is often more efficient to use a computer to compute the DFT.

### Similar threads

• Calculus and Beyond Homework Help
Replies
3
Views
617
• Calculus and Beyond Homework Help
Replies
1
Views
515
• Calculus and Beyond Homework Help
Replies
1
Views
386
• Calculus and Beyond Homework Help
Replies
1
Views
683
• Calculus and Beyond Homework Help
Replies
16
Views
748
• Calculus and Beyond Homework Help
Replies
1
Views
574
• Calculus and Beyond Homework Help
Replies
5
Views
782
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
7
Views
983
• Calculus and Beyond Homework Help
Replies
9
Views
1K