Bottom     Previous     Contents

Definition of DFT and Inverse DFT (IDFT).

Given a sequence of N samples f(n), indexed by n = 0..N-1, the Discrete Fourier Transform (DFT) is defined as F(k), where k=0..N-1:

equation

F(k) are often called the 'Fourier Coefficients' or 'Harmonics'.

The sequence f(n) can be calculated from F(k) using the Inverse Discrete Fourier Transform (IDFT):

equation

In general, both f(n) and F(k) are complex.

Annex A shows that the IDFT defined above really is an inverse DFT.

Conventionally, the sequences f(n) and F(k) is referred to as 'time domain' data and 'frequency domain' data respectively. Of course there is no reason why the samples in f(n) need be samples of a time dependant signal. For example, they could be spatial image samples (though in such cases a 2 dimensional set would be more common).

Although we have stated that both n and k range over 0..N-1, the definitions above have a periodicity of N:

equation

So both f(n) and F(k) are defined for all (integral) n and k respectively, but we only need to calculate values in the range 0..N-1. Any other points can be obtained using the above periodicity property.

For the sake of simplicity, when considering various Fast Fourier Transform (FFT) algorithms, we shall ignore the scaling factors and simply define the FFT and Inverse FFT (IFFT) like this:

equation

equation

In fact, we shall only consider the FFT algorithms in detail. The inverse FFT (IFFT) is easily obtained from the FFT.

Some Simple Transforms.

Here are some simple DFT's expressed as matrix multiplications.

1 point DFT:

equation

2 point DFT:

equation

4 point DFT:

equation

3 point DFT:

equation

equation

Note that each of the matrix multipliers can be inverted by conjugating the elements. This what we would expect, given that the only difference between the DFT and IDFT is the sign of the complex exponential argument.

Here's another couple of useful transforms:

If..

equation

equation

equation

This is the 'Delta Function'. The usual implied periodicity has been made explicit by using MOD N. The DFT is therefore:

equation

This gives us the DFT of a unit impulse at n=n0. Less obvious is this DFT:

If..

equation

equation

Given the relationship between the DFT and IDFT, perhaps this isn't so surprising after all. (See Annexes A and B for proof of this.)

©1999 - Engineering Productivity Tools Ltd.


Next     Top