# Urgent: Problem with Discrete Fourier transform

• Jun 28th 2012, 12:28 AM
al289
Urgent: Problem with Discrete Fourier transform
Hi all,

I'm a student and learning Fourier transform by myself. I want to learn Fast Fourier Transform ans Wavelet Transform but I was advised to begin with Discrete Fourier transform because it's very basic.

I'm reading "understanding digital signal processing" and I don't know how the following figure was drawn. As I understood, in order to draw these figures equations of amplitude response as a function of bin index m, and magnitude response as a function of freq. in Hz (sth like Amplitude=f(m) and Magnitude=f(freq.) ) are needed, right?

But I don't understand how these equations were established?
Attachment 24180
• Jun 28th 2012, 03:43 AM
niaren
Re: Urgent: Problem with Discrete Fourier transform
I can not spit out the equations right now but maybe this can help you find the equations yourself.

The lower figure shows the magnitude of the curve in the upper plot. So everywhere the the curve in the upper plot goes negative the lower plot reverses the sign to positive.

What you see in the upper plot is a solid curve and you see some points.

The solid line shows the Discrete-Time Fourier Transform (DTFT) of the truncated cosine sequence. This is so to speak the 'true' result. To derive the expression for this curve you have to evaluate a sum that looks something like this

$C(\omega) = \sum_{n=-N}^N \cos(\omega_0 n) w(n) e^{-j\omega n} = \sum \frac{1}{2}[e^{j\omega_0}+e^{-j\omega_0}] w(n) e^{-j\omega n}$
$= \frac{1}{2} \sum e^{j\omega_0} w(n) e^{-j\omega n} + \frac{1}{2} \sum e^{-j\omega_0} w(n)e^{-j\omega n}$
$= \frac{1}{2} \sum w(n) e^{-j(\omega-\omega_0) n} + \frac{1}{2} \sum w(n)e^{-j(\omega + \omega_0) n}$
$= \frac{1}{2} W(\omega) * \delta(\omega-\omega_0) + \frac{1}{2} W(\omega) * \delta(\omega +\omega_0)$
$= \frac{1}{2} W(\omega-\omega_0) + \frac{1}{2} W(\omega+\omega_0)$

So the result is a sum of two convolutions (that is the meaning of *). Each of the two terms 'moves' the $W(\omega)$ spectrum, one term moves it to $-\omega_0$ and the other moves it to $+\omega_0$. We consider the term that moves $W(\omega)$ spectrum to $+\omega_0$ which is what they do in the figure. We thus have to consider

$\frac{1}{2} W(\omega -\omega_0)$

Because nothing else is stated in the figure or in your post we assume that the window function $w(n)$ is the rectangular window function. The DTFT of $w(n)$ is a sinc function $\frac{sin \pi n}{\pi n}$ for which I can't write the exact expression right off my mind. So end of the line is that the solid curve in the upper plots is a sinc function moved to $\omega_0$.
Also note the the DTFT transform of the truncated cosine sequency is real (because it is symmetric).

The points in the upper plot represents samples of the sinc function. In other words, the points represent a sinc sequence. Because there is a whole number of cosine periods inside your window the samples of the sinc function happen to be precisely at the maximum and at zero-crossings. If there isn't a whole number of periods inside your window you will see samples of a shifted sinc function.

So solid line is shifted sinc function.
Points represents sinc sequence.

Hope this helps