NOTES ON STATISTICS, PROBABILITY and MATHEMATICS

Fast Fourier Transform (FFT):

In the decimation in time FFT a big DFT is build from smaller ones. The assumption is \(N = 2^m\) with \(N\) being the number of sampled points. The sampled points (in the time domain), i.e. \(x[n]\) are separate into even and odd-indexed sequences. \(k\) corresponds to the harmonic number or frequency parameter:

Remembering that \(\large\color{blue}{\large W_N \equiv e^{-i\frac{2\pi}{N}}}\) corresponds to the twiddle factor:

\[\large X[k]=\sum_{n=0}^{N-1}\,x[n]\,W_N^{kn}=\sum_{n\text{ even}}\,x[n]\,W_N^{kr}\,+\,\sum_{n\text{ odd}}\,x[n]\,W_N^{kr}\]

where \(n = 2r\) for even indices, and \(n = 2r +1\) for odd indices, and \(r = 0,1,\cdots,\frac{N}{2}-1.\)

So we can re-write the eqution as:

\[\large\begin{align}\large X[k]&=\sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_N^{k2r} + \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_N^{k(2r+1)}\\[2ex]\ &= \sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_N^{k2r} + \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_N^{k}W_N^{k2r}\\[2ex] &=\sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_N^{k2r} +W_N^{k} \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_N^{k2r}\\[2ex] &=\sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,(W_N^2)^{kr} +W_N^{k} \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,(W_N^2)^{kr}\\[2ex] &\underset{*}= \sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_{N/2}^{kr} +W_N^{k} \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_{N/2}^{kr}\\[2ex] &\underset{**}= X_e[k] + W_N^k\,X_o[k] \end{align}\]

\(*\) because \(\color{blue}{W_N^2=e^{-i\frac{2\dot2\pi}{N}}=e^{-i\frac{2\pi}{N/2}}=W_{N/2}}\)

\(**\) the sum of two \(N/2\) point DFTs.

But \(k\) runs from 0 to \(N-1\) while there are only \(N/2\) odd numbers and \(N/2\) even numbers. So how can it be… Let’s try with an \(8\)-point DFT:

For \(k=0\):

\[\begin{align}X[0]&=\sum_{r=0}^{3}\,x[2r]\,W_{4}^{0r} +W_8^{0} \sum_{r=0}^{3}\,x[2r+1]\,W_{4}^{0r}\\[2ex] &=\sum_{r=0}^{3}\,x[2r] +W_8^{0} \sum_{r=0}^{3}\,x[2r+1]\\[2ex] &=X_e[0] + X_o[0] \end{align}\]

For \(k=1\):

\[\begin{align}X[1]&=\sum_{r=0}^{3}\,x[2r]\,W_{4}^{1r} +W_8^{1} \sum_{r=0}^{3}\,x[2r+1]\,W_{4}^{1r}\\[2ex] &=X_e[1] + W_8^1\,X_o[1] \end{align}\]

\(\vdots\)

For \(k = 4\), though, this reasoning, runs into a “problem” because summarizing the corresponding expression as a sum of DFT of even and odd numbers, such as

\[\begin{align}X[\color{red}{4}]&\overset{?}=X_e[\color{red}{4}]+W_8^4\,X_o[\color{red}{4}]\tag{1}\\[2ex] &\overset{?}=\sum_{r=0}^{\color{red}{3}}\,x[2r]\,W_{4}^{\color{red}{4}r} +W_8^{4} \sum_{r=0}^{\color{red}{3}}\,x[2r+1]\,W_{4}^{\color{red}{4}r} \end{align}\]

makes apparently no sense, since \(k\) in DFT runs from \(0,1,2,\cdots,r-1=3\).

However,

\[\large W_4^{4r}=e^{-i\frac{2\pi}{4}4r}=1=W_{4}^{0r}\].

Hence \(X[\color{red}{4}]= X[0]\).

What about \(X[5]\)… well

\[\begin{align}\large W_4^{5r} &= e^{-i\frac{2\pi}{4}5r}\\[2ex] &= e^{-i\frac{2\pi}{4}4r}\,e^{-i\frac{2\pi}{4}r}\\[2ex] &= e^{-i\frac{2\pi}{4}r}\\[2ex] &= W_4^{1r} \end{align}\]

Going back to Eq. \(1\):

\[X[\color{red}{4}]=X_e[\color{red}{4}]+W_8^4\,X_o[\color{red}{4}]=X_e[\color{red}{0}]+W_8^1\,X_o[\color{red}{0}]\]

\[X[\color{red}{5}]=X_e[\color{red}{5}]+W_8^5\,X_o[\color{red}{5}]=X_e[\color{red}{1}]+W_8^5\,X_o[\color{red}{1}]\]

\[X[\color{red}{6}]=X_e[\color{red}{6}]+W_8^6\,X_o[\color{red}{6}]=X_e[\color{red}{2}]+W_8^6\,X_o[\color{red}{2}]\]

\[\begin{align}X[\color{red}{7}]&=X_e[\color{red}{7}]+W_8^7\,X_o[\color{red}{7}]=X_e[\color{red}{3}]+W_8^7\,X_o[\color{red}{3}]\\[2ex] &=\underset{X_e[3]}{\underbrace{\sum_{r=0}^{\color{red}{3}}\,x[2r]\,W_{\color{blue}{4}}^{\color{red}{3}r}}} +W_8^{7} \underset{X_o[3]}{\underbrace{\sum_{r=0}^{\color{red}{3}}\,x[2r+1]\,W_{\color{blue}{4}}^{\color{red}{3}r}}} \end{align}\]

Explaining the plot in this youtube video:

So regularly calculated DFTs take \(O( N^2)\), but splitting the \(2^N\) signals into even and odd results in \(\left(\frac{N}{2}\right)^2\cdot 2\) plus the multiplication by the \(W_8\) factors in the example above, resulting in \(O\left(\frac{N}{2}\right)^2 +N\)

since we started off with a number of the form \(2^N\) we can split each \(\frac{N}{2}\)-point DFTs into \(2\frac{N}{4}\)-point DFTs:

\[\frac{N}{2}, \frac{N}{4},\cdots,\frac{N}{2^{p-1}}, \frac{N}{2^{p}}\]

where \(p = \log_2 N\), such that \(\frac{N}{2^{p}}=1\). Hence we end up with a \(1\)-point DFT at the end. And we’ll end up with \(O(N\log_2 N)\) for large \(N\).

The resultant idea is:

Home Page

NOTE: These are tentative notes on different topics for personal use - expect mistakes and misunderstandings.