1
$\begingroup$

I am confused regarding the complexity of the Fast Fourier Transform (FFT). The Discrete Fourier Transform is:

$$\qquad X\left [ k \right ]=\sum_{n=0}^{N-1}x[n]W_{N}^{kn}\quad \text{where}\quad W_{N}=e^{\frac{-j2\pi}{N}}\tag{1}$$

The first step in deriving the FFT is to express $(1)$ as the sum of even and odd inputs

$$\qquad X[k]=\sum_{n\ \rm even}x[n]W_{N}^{nk}\ +\ \sum_{n\ \rm odd}x[n]W_{N}^{nk}\tag{2}$$

And after many other derivations the final equation $(3)$ is obtained as

$$\qquad X[k]=\sum_{r=0}^{N/2-1}x[2r]W_{N/2}^{rk}\ +W_{N}^{k}\ \sum_{r=0}^{N/2-1}x[2r+1]W_{N/2}^{rk}\tag{3}$$

Equation $(3)$ consists of $2$ length $N/2$ FFTs, which is more computationally efficient than performing one big length $N$ FFT.

My question is: isn't equation $(2)$ also $2$ length $N/2$ FFTs? In other words, why all the bother about deriving equation $(3)$? Isn't equation $(2)$ already more computationally efficient than equation $(1)$? Or perhaps I'm missing something?

Any help is greatly appreciated.

$\endgroup$
2
$\begingroup$

Remember that the Cooley–Tukey algorithm seeks to calculate the original DFT recursively, partitioning each DFT into two of half the length in each recursion step. Therefore, it is necessary to express the DFT of length $N$ as two DFTs of length $N/2$.

The notation you used may be the cause of your confusion. Let me avoid using $W_N$. The second equation you wrote is then:

$$ X[k]= \sum_{m=0}^{\frac N 2 -1}x[2m]e^{-\frac{j2\pi}{N}(2m)k} + \sum_{m=0}^{\frac N 2 -1}x[2m+1]e^{-\frac{j2\pi}{N}(2m+1)k} \qquad(2) $$

The third one would be:

$$ X[k]= \sum_{m=0}^{\frac N 2 -1}x[2m]e^{-\frac{j2\pi}{N/2}mk} + e^{-\frac{j2\pi}{N}k} \sum_{m=0}^{\frac N 2 -1}x[2m+1]e^{-\frac{j2\pi}{N/2}mk} \qquad(3) $$

This way it's easier to see that in $(2)$ you do not have two DFTs. The second summation has the factor $(2m+1)$ in the exponential, which is different from the definition of DFT. If you factor it out, leading to that $\left(e^{-\frac{j2\pi}{N}k}\right)$ multiplying the second summation in $(3)$, then you have two DFTs: the one corresponding to the even-indexed part and the one corresponding to the odd-indexed one. That's why that additional step is made.

$\endgroup$
4
$\begingroup$

No, Equation (2) is not the sum of 2 FFTs (of lengths $N/2$) as you claim, and it is not computationally more efficient. The canonical way of evaluating Equation (1) is via Horner's method:

$$X[k] = (((\cdots (x[N-1]\cdot\omega + x[N-2])\cdot\omega + x[N-3])\cdot\omega + \ldots)\cdot\omega + x[0]\tag{a}$$

where $\omega = W_N^k$ which requires $N-1$ multiplications and $N$ additions: lather, rinse, and repeat for for other values of $k$. Equation (2) just splits this Horner's rule computation into two parts with no change in complexity. That is, we compute $\sum_{n\ even}x[n]W_{N}^{nk}$ as $$(((\cdots (x[N-1]\cdot\Omega + x[N-3])\cdot\Omega + x[N-5])\cdot\Omega + \ldots)\cdot\Omega + x[0]\tag{b}$$ where $\Omega = \omega^2$ and $\sum_{n\ odd}x[n]W_{N}^{nk}$ as $$(((\cdots (x[N-2]\cdot\Omega + x[N-4])\cdot\Omega + x[N-6])\cdot\Omega + \ldots)\cdot\Omega + x[1])\cdot\omega.\tag{c}$$ Each computation requires $N/2$ multiplications and $N/2$ additions with no savings in computation over the standard brute-force Horner's method applied to a vector of length $N$ in $(a)$.

Equation (3), however, is the core of the FFT butterfly; the two sums in Equation (3) are DFTs of two shorter length sequences. Define \begin{align}x_{\text{even}}[k] &= x[2k], &k = 0, 1, \ldots, N/2-1,\\ x_{\text{odd}}[k] &= x[2k+1], &k = 0, 1, \ldots, N/2-1, \end{align} and let the DFTs of these shorter sequences be denoted by $X_{\text{even}}[k]$ and $X_{\text{odd}}[k]$ respectively. Then the computation of Equation (1) has been re-written in Equation (3) as $$X[k] = X_{\text{even}}[k] + W_N^kX_{\text{odd}}[k] \tag{**}$$ which requires one multiplication and one addition per bin. Note that $k$ varies from $0$ to $N-1$ in $(**)$, and the shorter DFTs in $(**)$ are assumed to be periodic functions of period $N/2$ (where's rb-j when I need him?) But, now note that $X_{\text{even}}[k]$ and $X_{\text{odd}}[k]$ are DFTs of length $N/2$, and so, if $N/2$ is an even number (hint: this means that $N$ is a multiple of $4$), we can use the idea behind $(**)$ to express $X_{\text{even}}[k]$ as $$X_{\text{even}}[k] = X_{\text{even, even}}[k] + W_{N/2}^kX_{\text{even, odd}}[k]$$ and $X_{\text{odd}}[k]$ as $$X_{\text{odd}}[k] = X_{\text{odd, even}}[k] + W_{N/2}^kX_{\text{odd, odd}}[k]$$ that is, both DFTs of length $N/2$ have been expressed in terms of 2 DFTs of length $N/4$, and so on. If $N = 2^m$, we can proceed in this way to where we have $N/2$ DFTs of length $2$ that we compute using one multiplication and addition per DFT bin. So, $N$ multiplications and additions total to compute these $N/2$ DFTs. (Purists whining that a length $2$ DFT needs only one addition and one subtraction are kindly requested to go jump in the lake!). Next, we combine these $N/2$ DFTs of length $2$ into $N/4$ DFTs of length $4$ using one multiplication and one addition per DFT bin for a total of $N$ multiplications and additions to do the combination. Next, we combine these $N/4$ DFTs of length $4$ into $N/8$ DFTs of length $8$ using one multiplication and one addition per DFT bin for a total of $N$ multiplications and additions to do the combination..... Ultimately, we arrive at $(**)$. This iterative procedure for computing the DFT of length $N$ is (one of the many versions of) the FFT algorithm for computing the Discrete Fourier transform. It has $m=\log_2N$ stages requiring $N$ multiplications and $N$ additions at each stage for a total of $Nm = N\log_2N$ multiplications and additions. In contrast, the use of Horner's rule would need $N(N-1)$ multiplications and $N^2$ additions. Hence the soubriquet FAST for this kind of algorithm.

Purists who have survived their jumps into the lake can now start their cacophony about radix-2 versus radix-4 versus radix-8 transforms and the exact number of multiplications and additions needed for implementing an FFT algorithm.

$\endgroup$
1
$\begingroup$

A DFT is equivalent to multiplying by a square matrix. Multiplying by a matrix double in size requires, not double the multiplies, but quadruple. And 4 is bigger than 2

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.