Computing the DFT: how is the number of operations reduced by splitting the signal into even and odd parts?

Question

On page 137 of "Understanding Digital Signal Processing" by R.G. Lyons I found that if I separate the standard DFT form:

$$X(m)=\sum_{n=0}^{N-1}x(n)e^{-j2\pi nm/N}\tag{4-11}$$

by odd and even components, with $W_{N}^{nm} = e^{-j(2\pi/N) mn}$:

$$X(m)=\sum_{n=0}^{(N/2)-1}x(2n)W_{N/2}^{nm}+W_{N}^m\sum_{n=0}^{(N/2)-1}x(2n+1)W_{N/2}^{nm}.\tag{4-15}$$ So we now have two $N/2$ summations whose results can be combined to give us the $N$-point DFT. We've reduced some of the necessary number crunching in Eq. (4-15) relative to Eq. (4-11) because the $W$ terms in the two summations of Eq. (4-15) are identical. There's a further benefit in breaking the $N$-point DFT into two parts because the upper half of the DFT outputs is easy to calculate. Consider the $X(m+N/2)$ output. If we plug $m+N/2$ in for $m$ in Eq. (4-15), then [followed by equation for $X(m + N/2)$]

I can "reduce some of the necessary number crunching, because the $W$ terms in the two summations are identical", which is not clear. It looks like changing the order of the addends does not change the sum, so the "number crunching" should be the same, isn't it?

Answer 1

In the original formula you need (approximately) $N^2$ complex multiplications and additions to compute all values of $X[m]$. In the second formula you have two DFTs of length $N/2$, which results in (approximately) $2(N/2)^2$ complex multiplications and additions. Furthermore, you need $N$ complex multiplications due to the term $W_N^m$ in the second sum, and you need $N$ complex additions to add the two terms. Consequently, the total number of complex multiplications and additions necessary to evaluate the second formula is (approximately) $N+2(N/2)^2=N+N^2/2$. Hence, for $N>2$ it is more efficient to split up the sum into two sums.

Note that we didn't take into account the computation of the twiddle factors $W$. We can assume that they are pre-computed and stored.

It's instructive to look at the combination of the two length $N/2$ DFT in vector notation. Let $\mathbf{X}$ denote the vector containing the elements $X[k]$, $k=0,\ldots,N-1$. Similarly, define the length $N/2$ vectors $\mathbf{X}_1$ and $\mathbf{X}_2$ containing the elements of the two length $N/2$ DFTs ($\mathbf{X}_1$ for the DFT of the even elements of $x[n]$, and $\mathbf{X}_2$ for the DFT of the odd elements of $x[n]$). The length $N$ DFT is then computed from the two length $N/2$ DFTs as follows:

$$\mathbf{X}=\left[\begin{array}{l}\mathbf{X}_1\\\mathbf{X}_1\end{array}\right]+\left[\begin{array}{l}W_N^0\\\vdots\\W_N^{N-1}\end{array}\right]\odot\left[\begin{array}{l}\mathbf{X}_2\\\mathbf{X}_2\end{array}\right]$$

where $\odot$ denotes element-wise multiplication. Note that the length $N/2$ DFTs are reused to compute the first and second halves of the length $N$ DFT.

For $N$ a power of $2$, the decimation-in-time FFT algorithm continues to split up the problem into smaller subproblems until we're left with length $2$ DFTs, which need to be combined appropriately to compute the original length $N$ DFT. The details can be found in any DSP textbook.

Answer 2

Your computation is reduced because $N$ is even, $(N/2)$ is an integer and $W_N^{(N/2)}=-1$, $W_N^2=W_{N/2}$, which implies $W_{(N/2)}^{(N/2)}=1$, so that the partial sums can be seen as DFT of half the length. This allows to decompose the DFT sums of length $M$ into parts that are DFT sums of length $N/2$, \begin{alignat}{1} X(m+(N/2))&=&&\sum_{n=0}^{(N/2)-1}x(2n)W_{N/2}^{nm}\\&&-W_{N}^m&\sum_{n=0}^{(N/2)-1}x(2n+1)W_{N/2}^{nm} \end{alignat} This computes an extra value using the same partial sums as used for $X(m)$.

If this is recursively continued, one gets the complexity equation $$T(N)=2T(N/2)+c\cdot(N/2),$$ where $T(N)$ is the time or complexity of transforming an array of size $N$ and $c$ some small constant collecting the operations outside the sums. This gives $$T(N)=(c/2)⋅N\log_2(N)$$ if $N$ is a power of $2$. There are other FFT algorithms for small factors other than 2 that allow to extend this pattern to general sizes $N$.

Answer 3

If you calculate the DFT naively, you do a lot of duplicate work. Here is the DFT formula again

$$X(m)=\sum_{n=0}^{N-1}x(n)\omega^{nm}$$ where ω is a Nth complex root of unity, meaning $$\begin{align*} \omega=e^\frac{-j2\pi }{N} && \text{with} && \omega^N = 1 && \text{and} && \omega^{nm} = \omega^{N+nm} = \omega^{2N+nm} = \space ...\\ \end{align*}$$

That means you have lots of {n,m} tuples that result in the same power of ω. For N=20, for example, there is:

$$ \omega^{3\cdot5} = \omega^{5\cdot3} = \omega^{5\cdot7} = \omega^{7\cdot5} = \omega^{5\cdot11} = \omega^{11\cdot5}= \omega^{3\cdot25} =\space...\space= \omega^{kN+15} = \omega^{15} $$

All FFT algorithms re-use intermediate results to avoid duplication. There's a lot of duplication (N² {n,m} tuples, but only N distinct powers of ω) and that's why the non-naive algorithms are much faster.

Answer 4

Looking just at the formulas and not jumping ahead deeper into FFT, I got to agree with you that there are no direct savings in computation due to the coefficients being identical in the two sums. Let's try to combine two multiplications by identical coefficients into a single multiplication:

$$\begin{eqnarray}X(m)&=&\sum_{n=0}^{(N/2)-1}x(2n)W_{N/2}^{nm}+W_{N}^m\sum_{n=0}^{(N/2)-1}x(2n+1)W_{N/2}^{nm}\\ &=&\sum_{n=0}^{(N/2)-1}x(2n)W_{N/2}^{nm}+\sum_{n=0}^{(N/2)-1}W_{N}^mx(2n+1)W_{N/2}^{nm}\\ &=&\sum_{n=0}^{(N/2)-1}\left(x(2n)W_{N/2}^{nm}+W_{N}^mx(2n+1)W_{N /2}^{nm}\right)\\ &=&\sum_{n=0}^{(N/2)-1}\left(x(2n)+W_{N}^mx(2n+1)\right)W_{N /2}^{nm},\end{eqnarray}$$

which for a single value of $m$ would be going from $N/2 + N/2 + 1 = N + 1$ multiplications and $(N/2 - 1) + (N/2 - 1) + 1 = N-1$ additions on the first row to $2\,N/2 = N$ multiplications and $N/2 + N/2 - 1 = N-1$ additions on the last row. But that's the same as $N$ multiplications and $N-1$ additions in the original formula that we were comparing against:

$$X(m)=\sum_{n=0}^{N-1}x(n)W_N^{nm}.$$

I don't know if Rick just refers to needing to (pre)calculate less values of $W$.