0.1 Algorithms  (Page 2/5)

where the two sums are now DFTs of the even indexed terms ( $x_{2n_2}$ ) and the odd indexed terms ( $x_{2n_2+1}$ ), which are combined with twiddle factor ${\omega }_N^k$ .

In order to compute the transform more efficiently, the Cooley-Tukey algorithm divides $X_k$ into two halves, and exploits the periodicity of sub-transforms and symmetries in the trigonometric coefficients. Firstly, [link] is rewritten as two halves with $E_k$ substituted for the even sub-transform, and $O_k$ substituted for the odd sub-transform:

where $k=0,\cdots ,N/2-1$ . Because of the periodicity property of the outputs of a DFT, $E_k=E_{k+N/2}$ and $O_k=O_{k+N/2}$ , [link] simplifies thus:

And finally, by exploiting symmetries in the complex exponential function, namely that ${\omega }_N^{k+N/2}=-{\omega }_N^k$ , the radix-2 DIT FFT can be expressed as:

which makes it clear that each pair of outputs share common computation, approximately halving the number of arithmetic operations when compared tothe DFT. But since the even and odd terms in [link] are themselves DFTs that can be computed with the FFT, the savings compound with each stage of recursion. The total number of realarithmetic operations required to compute the radix-2 FFT can be expressed with the following recurrencerelation:

which is in $\Theta (nlogn)$ .

Split-radix

In 1968 a derivitive of the Cooley-Tukey algorithm broke the record for the lowest number of arithmetic operations for computing theDFT  [link] , [link] , [link] . The algorithm was initially discovered by Yavne  [link] , but was not widely cited until 1984 when it was rediscovered by Duhamel and Hollman  [link] and became known as the split-radix algorithm.

The split-radix algorithm improves the arithmetic complexity of the Cooley-Tukey algorithm by further decomposing the odd parts into odd-odd andodd-even parts, while the even parts are left alone because they have no multiplicative factor. More formally, [link] can be re-written as three sums:

where $n=4n_4=2n_2$ . As with the Cooley-Tukey radix-2 example in "Cooley-Tukey" , the trigonometric coefficients are expanded and simplified, and the termsconstant with respect to the index variables factored out:

By substituting the even sum with $U_k$ (where $k=0,\cdots ,N/2-1$ ) and the odd sums with $Z_k$ and $Z_k^{\text{'}}$ (where $k=0,\cdots ,N/4-1$ ), [link] is simplified:

Computation can be factored out of [link] by again exploiting periodicity in the sub-transforms and symmetries in the twiddlefactors. [link] is first expressed as an equation of four parts:

where $k=0,\cdots ,N/4-1$ . The periodicity properties of the sub-transforms can be expressed with the relationships $U_k=U_{k+N/2}$ , $Z_k=Z_{k+N/4}$ and $Z_k^{\text{'}}=Z_{k+N/4}^{\text{'}}$ . These are used to simplify [link] thus: