Discrete Fourier Transforms

Some of my classmates freak out on this subject Digital Signal Processing. I think it’s rather FUN!

Let me get you to a very simple and elegant topic that you may need to study under DSP, it’s called DFT.

The definition of Discrete Fourier Transform,

X_k =\sum_{n=0}^{N-1}x_n e^{-j k n / N}

Now, if you are trained then you can easily find similarity between this relationship with Z-transform. It’s simple z on unit circle, i.e z=e^{j\omega}.

In more general terms, it means if x_n is a sequence of a sampled signal then the frequency spectrum of this signal is X_k. Neat little formula where j=\sqrt{-1}=i. Now, this N is the sampling rate and k is the angular frequency in radians/second. If you are doing manual calculations you can simply consider N as a arbitrary number and multiply the frequency axis with the ratio <real sampling rate>/<your N>.

When I first encountered this definition I thought it is so damn simple to get the phase and amplitude spectrum. All you need to do is find the amplitude and the argument of the numbers in X_k and you get the amplitude and phase spectra respectively.

Now there is another neat tool that can make out your and computers’ life even easier. Well, the MATRIX. Not the movie! 😉

With a little brainstorming you can figure is out too, we are summing up over n and calculating the function with multiple values of k. GET IT?

This matrix form is also known as Vandermonde matrix,

Where w = e^{- j/ N}, and you get can simply put the sequence as the column matrix [x], use this relationship below,

[X] = [W][x]

and get X_k as the [X].

And suppose you want to make some (linear) filter, what will you do? Don’t bother with that word linear, it’s related to linear systems. You can simply multiply X_k with H_k, where h_n is the impulse response of that filter, or rather the transfer function in disguise. You can use the same DFT technique to get H_k from h_n.

Let’s write that as,

F_k = X_k \cdot H_k

And viola! You do a Inverse DFT and get the time sequence, FILTERED!

And the easiest way to do a IDFT? MATRIX again…

[f_n] = [W]^{-1} [F_k]

Here f_n is the filtered sequence. But you wanna know the coolest part? You don’t need to do all the calculations to figure out [W]^{-1}. With a little mathematics, it can be proved that, [W]^{-1} = \frac{1}{N} [W]^{*}. Isn’t that easy? 🙂

What I figured out from other texts and articles, people have been using Fourier Transforms for sequences which are not time-sequences. Well, then what do I call the spectra? I don’t know. Think it out yourself. 🙂

And another thing, there is another thing call DTFT which is similar to DFT, but you can put any frequency resolution you want. With a little time and thought, you can modify DFT techniques into DTFT. Have at it, if’s FUN!

P.S. I could not get neat relationship between w and w^{*}, if I get it, I would post it.