DIT FFT: Algorithm and Complexity Analysis

1. The Computational Cost of the Direct DFT

Before we can appreciate the "fast" in FFT, we must first understand the "slow" in DFT. The DFT is defined by the analysis equation:

$X[k]={\sum }_{n=0}^{N-1}x[n]e^{-j\frac{2\pi kn}{N}}\text{for }k=0,1,\dots ,N-1$

Let's analyze the number of calculations needed to compute this directly.

• For a single DFT coefficient $X[k]$, we need to perform $N$ complex multiplications (each $x[n]$ by its corresponding complex exponential) and $N-1$ complex additions to sum the results.
• Since we need to do this for all $N$ values of $k$ (from 0 to $N-1$), the total number of operations is on the order of $N\times N=N^2$.

We say the direct DFT has a computational complexity of $O(N^2)$. This might not seem so bad for small $N$, but as $N$ grows, the computational cost becomes prohibitive very quickly.

To get a feel for the numbers and the historical context behind the FFT's development, please watch the beginning of the following video.

The difference between $O(N^2)$ and the FFT's $O(N\log N)$ is not just an incremental improvement; it's a revolutionary leap that made real-time spectral analysis and complex digital filtering feasible.

2. The Core Idea: Divide and Conquer

The key to the FFT algorithm, first published in its modern form by James Cooley and John Tukey in 1965 (though rediscovered from the work of Gauss), is a "divide and conquer" strategy. We break a large problem into smaller, easier-to-solve subproblems and then combine their results.

The most common variant of this is the radix-2 decimation-in-time (DIT) algorithm, which we'll derive now. It works on signals where the length $N$ is a power of 2 (e.g., 1024, 4096).

The derivation starts by splitting the DFT summation into two smaller sums: one over the even-indexed samples of $x[n]$ and one over the odd-indexed samples.

This derivation is the heart of the lesson. The following video segment walks through it step-by-step. As you watch, I will provide the key mathematical expressions here for your reference.

Derivation Summary

Let's formalize the steps shown in the video.

1. Define the Twiddle Factor: To simplify notation, we define $W_N=e^{-j\frac{2\pi }{N}}$. The DFT is then $X[k]={\sum }_{n=0}^{N-1}x[n]W_N^{kn}$.

2. Split the Sum: We separate the sum over $n$ into even and odd indices. Let $n=2r$ for the even terms and $n=2r+1$ for the odd terms. Both sums now go from $r=0$ to $N/2-1$.

   $X[k]={\sum }_{r=0}^{N/2-1}x[2r]W_N^{k(2r)}+{\sum }_{r=0}^{N/2-1}x[2r+1]W_N^{k(2r+1)}$

3. Factor and Simplify: We can factor out terms that don't depend on $r$.

   $X[k]={\sum }_{r=0}^{N/2-1}x[2r](W_N^2{)}^{kr}+W_N^k{\sum }_{r=0}^{N/2-1}x[2r+1](W_N^2{)}^{kr}$

4. Recognize the Smaller DFTs: The key insight is that $W_N^2=(e^{-j\frac{2\pi }{N}}{)}^2=e^{-j\frac{2\pi }{N/2}}=W_{N/2}$. Substituting this in, we see two familiar forms emerge:

   $X[k]=\underset{\text{N/2-point DFT of even part}}{\underbrace{\sum _{r=0}^{N/2-1}{x}_{even}[r]W_{N/2}^{kr}}}+W_N^k\underset{\text{N/2-point DFT of odd part}}{\underbrace{\sum _{r=0}^{N/2-1}{x}_{odd}[r]W_{N/2}^{kr}}}$

   Let's call the DFT of the even part $X_e[k]$ and the DFT of the odd part $X_o[k]$. The equation is now:

   $X[k]=X_e[k]+W_N^k{X}_o[k]$

This is a remarkable result! We have expressed an $N$-point DFT in terms of two $N/2$-point DFTs. This equation computes the first half of the output, for $k=0,1,\dots ,N/2-1$.

But what about the second half? For $k\ge N/2$, we can substitute $k+N/2$ for $k$:

$X[k+N/2]=X_e[k+N/2]+W_N^{k+N/2}{X}_o[k+N/2]$

Using the periodicity properties $X_e[k+N/2]=X_e[k]$, $X_o[k+N/2]=X_o[k]$, and $W_N^{k+N/2}=W_N^k{W}_N^{N/2}=-W_N^k$, we get:

$X[k+N/2]=X_e[k]-W_N^k{X}_o[k]$

These two equations define the fundamental DIT butterfly computation:

For $k=0,1,\dots ,N/2-1$:
$X[k]=X_e[k]+W_N^k{X}_o[k]$
$X[k+N/2]=X_e[k]-W_N^k{X}_o[k]$

3. Complexity Analysis: From $O(N^2)$ to $O(N\log N)$

The "divide and conquer" step reduced the problem, but how much does that save us? And how do we turn this into a full algorithm?

The key is to apply the decomposition recursively. The two $N/2$-point DFTs can each be broken down into two $N/4$-point DFTs, and so on, until we are left with trivial 1-point DFTs (where the DFT of a single point is just the point itself).

Let's see how this recursive splitting leads to the $O(N\log N)$ complexity.

To summarize the analysis:

• We have ${\log }_{2}N$ stages of decomposition. (e.g., for N=8, we have 8 -> 4 -> 2 -> 1, which is 3 stages, and ${\log }_{2}8=3$).
• At each stage, we perform $N/2$ butterfly computations to combine the results from the previous stage.
• Each butterfly involves one complex multiplication and two complex additions.
• Therefore, each of the ${\log }_{2}N$ stages requires $O(N)$ operations.
• The total complexity is the number of stages times the work per stage: $O(N{\log }_{2}N)$.

4. The Algorithm in Practice: Signal Flow and Bit Reversal

When we implement this recursive algorithm, an interesting pattern emerges in the ordering of the input data. To perform the computations efficiently "in-place" (i.e., overwriting the input buffer with intermediate results to save memory), the input data $x[n]$ must be reordered first.

This reordering is called bit reversal. If you take the index of a sample, write it in binary, and then reverse the bits, you get its new position in the input array for the DIT-FFT.

The entire process is visualized using a signal flow graph, which shows the butterfly computations at each stage.

The canonical DIT-FFT algorithm can be summarized in pseudocode:

// N is a power of 2
// x is an array of N complex numbers

procedure dit_fft(x, N):
    // 1. Reorder the input array by bit-reversal
    bit_reverse_copy(x)

    // 2. Perform log2(N) stages of butterfly computations
    for stage from 1 to log2(N):
        M = 2^stage  // Size of DFTs being combined
        W_m = exp(-2*pi*j / M)
        for k from 0 to M/2 - 1:
            twiddle = (W_m)^k
            for j from 0 to N-1 by M:
                // Perform butterfly
                t = twiddle * x[j + k + M/2]
                u = x[j + k]
                x[j + k] = u + t
                x[j + k + M/2] = u - t

This iterative, in-place structure is how most high-performance FFT libraries are implemented.

5. A Deeper Perspective: Why Does This Work?

We have successfully derived the algorithm and analyzed its complexity. For your interest, given your preference for deeper mathematical insights, there is a beautiful alternative perspective from computer science and algebra that explains why a fast algorithm like this is even possible.

The key is to view the DFT as the evaluation of a polynomial, whose coefficients are the signal values $x[n]$, at $N$ specific points on the complex plane—the $N$-th roots of unity. The DIT-FFT algorithm is a manifestation of a fast polynomial evaluation algorithm. The "divide and conquer" strategy works because the set of $N$-th roots of unity has a special "collapsing" property: if you square all of them, you get the $(N/2)$-th roots of unity, repeated twice. This allows the problem size to shrink at each stage of the recursion.

This is a more abstract but powerful way to understand the FFT. If you're curious, the MIT OpenCourseWare lecture "Divide & Conquer: FFT" provides a fantastic explanation of this viewpoint.

Conclusion

In this lesson, we demystified the Fast Fourier Transform. You now understand that it is not a different transform, but a remarkably efficient algorithm for computing the DFT.

Key Takeaways:

• Direct computation of the DFT has a complexity of $O(N^2)$, which is too slow for large $N$.
• The FFT is a divide-and-conquer algorithm that reduces this complexity to $O(N\log N)$.
• The radix-2 Decimation-In-Time (DIT) algorithm works by recursively splitting an $N$-point signal into its even and odd indexed samples, computing their $N/2$-point DFTs, and combining them.
• The core computation is the butterfly, which combines results from smaller DFTs using "twiddle factors" ($W_N^k$).
• An efficient, in-place implementation of the DIT-FFT algorithm involves an initial bit-reversal of the input data, followed by ${\log }_{2}N$ stages of butterfly computations.

This understanding of the FFT's mechanics completes our deep dive into the fundamental tools of discrete-time signal analysis.

Preview of the Next Module:

We now possess a comprehensive toolkit for analyzing and manipulating signals in the frequency domain. Our next major topic is to use these tools for a practical purpose: designing digital filters. In the first lesson of the next module, we will explore the historical context of digital filter design, examining how engineers first ingeniously adapted decades of analog filter theory to the digital domain before developing the direct digital design methods we use today. This will set the stage for designing our own IIR and FIR filters to meet specific frequency-response requirements.