FFT Algorithms

Algorithms

For DFT & FFT

Look at the aforementioned formula for DFT. The term W^k_N

(= exp(-j(2πk/N))) can be represented as follows:

In the above figure the values for N = 2, 4, and 8 are shown in the complex plane, where ‘N’ denotes N-point DFT.

For example,

For a 2-point DFT

W₂ = e^-2jπ/N = e^-2jπ/2 = e^-jπ = -1

Now, discrete Fourier transform for complex numbers a₁ and a₂ is

Aₖ = Σₙ aₙ W₂^(kn)
    = Σₙ aₙ (-1)^(kn)
    = a₀ (-1)^(k·0) + a₁ (-1)^(k·1)
    

As K = 0 and 1 (for 2-point DFT):

A₀ = a₀ + a₁

A₁ = a₀ − a₁

Similarly for a 4-point DFT

W₄ = e^-2jπ/4 = e^-jπ/2 = -j

Now, discrete Fourier transform for complex numbers a₁, a₂, a₃, and a₄ is:

Aₖ = Σₙ aₙ W₄^(kn)
    = a₀ (-j)^(k·0)
    + a₁ (-j)^(k·1)
    + a₂ (-j)^(k·2)
    + a₃ (-j)^(k·3)
    

Hence,

A₀ = a₀ + a₁ + a₂ + a₃

A₁ = a₀ - j a₁ - a₂ + j a₃

A₂ = a₀ - a₁ + a₂ - a₃

A₃ = a₀ + j a₁ - a₂ - j a₃

To compute A quickly, we can pre-compute common sub-expressions:

A₀ = (a₀ + a₂) + (a₁ + a₃)
A₁ = (a₀ - a₂) − j(a₁ − a₃)
A₂ = (a₀ + a₂) − (a₁ + a₃)
A₃ = (a₀ − a₂) + j(a₁ − a₃)
    

Then we can diagram the 4-point like so (diagram removed).

Matrix Relations in DFT

The DFT samples are defined by

Xₖ = Σₙ xₙ W_N^(kn)
where W_N = e^(-j 2π/N)
    

W_N^kn can be expanded as an N × N DFT matrix:

| 1        1        1        ...      1       |
| 1      W_N      W_N²      ...   W_N^(N-1)  |
| 1    W_N²    W_N⁴        ...   W_N^(2(N-1))|
| ...                                      ...|
| 1  W_N^(N-1) W_N^(2(N-1)) ... W_N^((N-1)²) |
    

In the matrix, the elements in the first row and first column are all W_N⁰ = 1. In the third row powers are multiplied by 2, in the fourth row by 3, and so on.

So,

X = W · x
where W = DFT matrix
    

Oppositely, to find the inverse DFT, we replace j with −j in the matrix (i.e., take complex conjugates of the matrix elements).

x = (1/N) W* X
where W* = conjugate transpose of DFT matrix
    

The effective determinant of above is 1/4.

For an 8-point FFT

The FFT is a fast algorithm for computing the DFT. If we take the 2-point DFT and 4-point DFT and generalize them to 8-point, 16-point, ..., 2ʳ-point, we get the FFT algorithm.

N = 8-point radix-4 DIT-FFT

Where, −W⁴ = W⁰ = 1 −W⁵ = W¹ = a = (1 − j)/√2 −W² = W⁶ = j −W³ = W⁷ = b = (1 + j)/√2

The above diagram is the same as illustrated in section ‘Fast Fourier Transform’ under ‘Basics of Fourier Transform’.

N = 8-point radix-2 DIT-FFT

Wˣ = W₈ˣ = e^(-j 2πx / 8) 

Further Reading