MATH 414 Lecture 25

« previous | Friday, March 21, 2014 | next »

Fast Fourier Transform

Developed by Cooley (CS) and Tukey (STAT/MATH) ca. 1965 at Bell Labs.

Discrete Fourier Transform involves multiplication of an $n\times n$ matrix, around $4n^{2}$ real multiplications.

DFT for powers of $2$ : $n=2^{L}$ for $L\in \mathbb {Z} ^{+}$ . (In practice, we have $n=2N$ , where $N=2^{L-1}$ ).

${\begin{aligned}{\mathcal {F}}_{2N}\left[y_{0},\ldots ,y_{2N-1}\right]&=\sum _{j=0}^{2N-1}y_{j}\,{\overline {\omega }}^{j\,k}\\&=\sum _{{\mbox{even}}\ j}y_{j}\,{\overline {\omega }}^{j\,k}+\sum _{{\mbox{odd}}\ j}y_{j}\,{\overline {\omega }}^{j\,k}\\&=\sum _{\ell =0}^{N_{1}}y_{2\ell }\,{\overline {\omega }}^{2\ell \,k}+\sum _{\ell =0}^{N-1}y_{2\ell +1}\,{\overline {\omega }}^{(2\ell +1)\,k}\end{aligned}}$

In the even case,

${\begin{aligned}{\overline {\omega }}^{2\ell \,k}&=\mathrm {e} ^{-{\frac {2\pi \,i}{n}}\cdot 2\ell \,k}\\&=\mathrm {e} ^{-{\frac {2\pi \,i}{2N}}\cdot 2\ell \,k}\\&=\mathrm {e} ^{-{\frac {2\pi \,i}{N}}\,\ell \,k}\end{aligned}}$

Let $W=\mathrm {e} ^{\frac {2\pi \,i}{N}}$ . Then

${\begin{aligned}\mathrm {e} ^{-{\frac {2\pi \,i}{2N}}\cdot 2\ell \,k}&={\overline {W}}^{\ell \,k}\end{aligned}}$

In the odd case,

${\begin{aligned}{\overline {\omega }}^{(2\ell +1)\,k}&={\overline {\omega }}^{k}\,{\overline {\omega }}^{2\ell \,k}\\&={\overline {\omega }}^{k}\,{\overline {W}}^{\ell \,k}\end{aligned}}$

Hence

${\mathcal {F}}_{2N}\left[y_{0},\ldots ,y_{2N-1}\right]_{k}={\mathcal {F}}_{N}\left[y_{0},y_{2},y_{4},\ldots ,y_{2N-2}\right]+{\overline {\omega }}^{k}\,{\mathcal {F}}_{N}\left[y_{1},y_{3},y_{5},\ldots ,y_{2N-1}\right]$