The purpose of this week is to finish up orthogonal frequency division multiplexing (OFDM) and discuss the fast fourier transform (FFT) algorithm.

1. OFDM

2. Fast Fourier Transform

In order to understand the FFT, we must discuss the discrete fourier transform (DFT) that we will discuss more thoroughly in the next few articles. The basic idea of the DFT is that we are sampling the DTFT of a signal so that we can store it in memory. Recall the DTFT:

$$X(\omega)=DTFT\{x[n]\}=\sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}$$

We sample $X(\omega)$ as such:

$$X_N(k)=X(\omega_k = \frac{2\pi k}{N})=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N} n}$$

Which is called the N-point DFT of $x$.

The radix-2 flavor of FFT is when $N=2^v$, aka N is radix-2 (or base-2 as it is more commonly known). When we use the FFT algorithm, we achieve HUGE savings in computation for the DFT.

The general takeaway from the following is this: choosing the right the order in which you (1) compute/loop through the summation and (2) read out the DFT values can greatly improve efficiency in the calculation of DFTs.

2.1. Radix-2

2.1.1. Radix-2 Decimation in Time

We start with the DFT:

$$X_N(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N} n}$$

We wish to split the sum into even and odd components for $n$. Thus,

$$X_N(k)=\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi k}{N} 2n}+\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi k}{N} (2n+1)}$$

We take out the extra exponential term in the odd-term sum:

$$X_N(k)=\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi k}{N} 2n}+e^{-j\frac{2\pi k}{N}}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi k}{N} 2n}$$

We now wish to express each sum as a $N/2$-pt DFT as so:

$$X_N(k)=\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi k}{N/2} n}+e^{-j\frac{2\pi k}{N}}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi k}{N/2} n}$$

So, we have now expressed this $N$-pt DFT as two $N/2$-pt DFT’s. This does not necessarily save us computation, however. The key step is to observe $X_N(k+N/2)$.

$$X_N(k+N/2)=\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi (k+N/2)}{N/2} n}+e^{-j\frac{2\pi (k+N/2)}{N}}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi (k+N/2)}{N/2} n}$$

$$X_N(k+N/2)=e^{-j 2\pi n}\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi k}{N/2} n}+(e^{-j\frac{2\pi k}{N}}e^{-j \pi})e^{-j2\pi n}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi k}{N/2} n}$$

$$X_N(k+N/2)=\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi k}{N/2} n}-e^{-j\frac{2\pi k}{N}}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi k}{N/2} n}$$

In summary:

$$X_N(k)=\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi k}{N/2} n}+e^{-j\frac{2\pi k}{N}}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi k}{N/2} n}$$

$$X_N(k+N/2)=\sum_{n=0}^{N/2-1}x[2n]e^{-j\frac{2\pi k}{N/2} n}-e^{-j\frac{2\pi k}{N}}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j\frac{2\pi k}{N/2} n}$$

Let $F_{N/2}^{(1)}(k)$ be the $N/2$-pt DFT of $x[2n]$, and $F_{N/2}^{(2)}(k)$ be the $N/2$-pt DFT of $x[2n+1]$. Let $W_N^k = e^{-j\frac{2\pi k}{N}}$. Then,

$$\boxed{X_N(k)=F_{N/2}^{(1)}(k)+W_N^kF_{N/2}^{(2)}(k)}$$

$$\boxed{X_N(k+N/2)=F_{N/2}^{(1)}(k)-W_N^kF_{N/2}^{(2)}(k)}$$

As can be seen, this allows us to compute two different values for $X_N(k)$ for the same price.

Bill:

1. $F_{N/2}^{(1)}(k)$ (decimation, DFT)
2. $F_{N/2}^{(2)}(k)$ (decimation, DFT)
3. $W_N^k$ (stored, basically free)

This can futher be observed with a butterfly diagram:

This is the first big computation save that the FFT provides, but it is not nearly all. As can be seen, two non-trivial DFTs are required to be computed.

The next step allows us to dramatically improve computational efficiency: we can decimate $f^{(1)}[n]$, $f^{(2)}[n]$ futher until we only compute 2-pt DFTs (only works because $N=2^v$).

In block diagram form:

As can be seen, the ordering of the inputs is a bit interesting. The below figure describes how the ordering maps, from natural to bit-reversed order:

2.1.2. Radix-2 Decimation in Frequency

This is very similar to the decimation in time algorithm.

We start with the DFT:

$$X_N(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N} n}$$

We wish to split the sum into two halves, as such:

$$X_N(k)=\sum_{n=0}^{N/2-1}x[n]e^{-j\frac{2\pi k}{N} n} + \sum_{n=N/2}^{N-1}x[n]e^{-j\frac{2\pi k}{N} n}$$

Then, we wish to again obtain each sum as a $N/2$-pt DFT:

$$X_N(k)=\sum_{n=0}^{N/2-1}x[n]e^{-j\frac{2\pi k}{N} n} + e^{-j \pi k}\sum_{n=0}^{N/2-1}x[n+\frac{N}{2}]e^{-j\frac{2\pi k}{N} n}$$$$X_N(k)=\sum_{n=0}^{N/2-1}(x[n] + (-1)^kx[n+\frac{N}{2}])e^{-j\frac{2\pi k}{N} n}$$

We now wish to decimate in frequency to obtain the odd and even $k$ values:

$$X_N(2k)=\sum_{n=0}^{N/2-1}(x[n] + x[n+\frac{N}{2}])e^{-j\frac{2\pi k}{N/2} n}$$

$$X_N(2k+1)=\sum_{n=0}^{N/2-1}\{(x[n] - x[n+\frac{N}{2}])e^{-j\frac{2\pi}{N} n}\}e^{-j\frac{2\pi k}{N/2} n}$$

Now let $g^{(1)}[n]=x[n] + x[n+\frac{N}{2}]$ and $g^{(2)}[n]=(x[n] - x[n+\frac{N}{2}])e^{-j\frac{2\pi}{N} n}$. Then

$$\boxed{X_N(2k)=\sum_{n=0}^{N/2-1}g^{(1)}[n]W_{N/2}^{kn}=G_{N/2}^{(1)}(k)}$$

$$\boxed{X_N(2k+1)=\sum_{n=0}^{N/2-1}g^{(2)}[n]W_{N/2}^{kn}=G_{N/2}^{(2)}(k)}$$

In block diagram form:

2.1.3. Efficiency

First, we must decimate $v=log_2(N)$ times. Each decimation involves $N/2$ butterflies, and each butterfly requires 1 multiplication and 2 additions. Therefore, we obtain $\frac{N}{2}log_2(N)$ multiplcations and $Nlog_2(N)$ additions.

Without the FFT algorithm we have $N^2$ multiplcations and $N(N-1)$ additions.

2.2. Divide and Conquer: Non-Prime-pt FFTs

2.2.1. Formulation

Now we move onto the more general case, where $N$ can be factored by two numbers, $M$ and $L$ for $N=ML$. Recall DFT:

$$X_N(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N}n}$$

We can first decimate in time, as the decimation in time FFT:

$$X_N(k)=\sum_{l=0}^{L-1}\sum_{m=0}^{M-1}x[l+mL]e^{-j\frac{2\pi k}{N}(l+mL)}$$

We can then decimate in frequency, as the decimation in frequency FFT:

$$X_N(q+pM)=\sum_{l=0}^{L-1}\sum_{m=0}^{M-1}x[l+mL]e^{-j\frac{2\pi}{N}(q+pM)(l+mL)}$$

(The order of the above, obviously, does not matter).

Simplifying:

$$e^{-j\frac{2\pi}{N}(q+pM)(l+mL)}=e^{-j\frac{2\pi}{N}ql}e^{-j\frac{2\pi}{M}mq}e^{-j\frac{2\pi}{L}lp}e^{-j 2\pi pm}$$

$$X_N(q+pM)=\sum_{l=0}^{L-1}\{e^{-j\frac{2\pi}{N}ql}[\sum_{m=0}^{M-1}x[l+mL]e^{-j\frac{2\pi}{M}mq}]\}e^{-j\frac{2\pi}{L}lp}$$

In plain english:

1. Take $L$ $M$-pt DFTs of $x$ decimated at different points according to $x[l+mL]$.
2. Multiply each $M$-pt DFT generated in the previous step by the “twiddle factor” $e^{-j\frac{2\pi}{N}ql}$
3. Take the $L$-pt DFT of the quantity generated in the last step. Do this $M$ times to get all values.

Take the example below of a 15-pt FFT:

2.2.2. Efficiency

Count:

1. $L$ $M$-pt DFTs -> $LM^2$ multiplications.
2. N=ML multiplications by twiddle factor.
3. $M$ $L$-pt DFTs -> $ML^2$ multiplications.

Total:

$$LM^2+ML+ML^2=N(M+L+1) < N^2=N(ML)$$

Because $M+L+1 < ML$.

2.3. Inverse FFT

Recall the DFT and IDFT:

$$X_N(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N}n}$$

$$x[n]=\frac{1}{N}\sum_{n=0}^{N-1}X_N(k)e^{j\frac{2\pi k}{N}n}$$

Take the conjugate of the IDFT formula:

$$x^*[n]=\frac{1}{N}\sum_{n=0}^{N-1}X_N^*(k)e^{-j\frac{2\pi k}{N}n}$$

So IFFT is calculated by the FFT.