Radix-4 FFT Algorithms 1.4 2004/05/17 17:29:49 GMT-5 2006/09/18 21:51:22.487 GMT-5 Douglas L. Jones dl-jones@uiuc.edu Douglas L. Jones dl-jones@uiuc.edu Harika Basana ilsai@rice.edu Kyle Evan Clarkson kclarks@rice.edu decimation-in-frequency decimation-in-time DFT FFT radix-4 The decimation-in-time (DIT) radix-4 FFT recursively partitions a DFT into four quarter-length DFTs of groups of every fourth time sample. The outputs of these shorter FFTs are reused to compute many outputs, thus greatly reducing the total computational cost. The radix-4 decimation-in-frequency FFT groups every fourth output sample into shorter-length DFTs to save computations. The radix-4 FFTs require only 75% as many complex multiplies as the radix-2 FFTs. The radix-4 decimation-in-time and decimation-in-frequency fast Fourier transforms (FFTs) gain their speed by reusing the results of smaller, intermediate computations to compute multiple DFT frequency outputs. The radix-4 decimation-in-time algorithm rearranges the discrete Fourier transform (DFT) equation into four parts: sums over all groups of every fourth discrete-time index n 0 4 8 … N 4 , n 1 5 9 … N 3 , n 2 6 10 … N 2 and n 3 7 11 … N 1 as in . (This works out only when the FFT length is a multiple of four.) Just as in the radix-2 decimation-in-time FFT, further mathematical manipulation shows that the length-N DFT can be computed as the sum of the outputs of four length- N 4 DFTs, of the even-indexed and odd-indexed discrete-time samples, respectively, where three of them are multiplied by so-called twiddle factors W N k 2 k N , W N 2 k , and W N 3 k . X k n N 1 0 x n 2 n k N n N 4 1 0 x 4 n 2 4 n k N n N 4 1 0 x 4 n 1 2 4 n 1 k N n N 4 1 0 x 4 n 2 2 4 n 2 k N n N 4 1 0 x 4 n 3 2 4 n 3 k N DFT N 4 x 4 n W N k DFT N 4 x 4 n 1 W N 2 k DFT N 4 x 4 n 2 W N 3 k DFT N 4 x 4 n 3 This is called a decimation in time because the time samples are rearranged in alternating groups, and a radix-4 algorithm because there are four groups. graphically illustrates this form of the DFT computation.

Radix-4 DIT structure Decimation in time of a length-N DFT into four length-N4 DFTs followed by a combining stage.

Due to the periodicity with N 4 of the short-length DFTs, their outputs for frequency-sample k are reused to compute X k , X k N 4 , X k N 2 , and X k 3 N 4 . It is this reuse that gives the radix-4 FFT its efficiency. The computations involved with each group of four frequency samples constitute the radix-4 butterfly, which is shown in . Through further rearrangement, it can be shown that this computation can be simplified to three twiddle-factor multiplies and a length-4 DFT! The theory of multi-dimensional index maps shows that this must be the case, and that FFTs of any factorable length may consist of successive stages of shorter-length FFTs with twiddle-factor multiplications in between. The length-4 DFT requires no multiplies and only eight complex additions (this efficient computation can be derived using a radix-2 FFT).

The radix-4 DIT butterfly can be simplified to a length-4 DFT preceded by three twiddle-factor multiplies.

If the FFT length N 4 M , the shorter-length DFTs can be further decomposed recursively in the same manner to produce the full radix-4 decimation-in-time FFT. As in the radix-2 decimation-in-time FFT, each stage of decomposition creates additional savings in computation. To determine the total computational cost of the radix-4 FFT, note that there are M 4 N 2 N 2 stages, each with N 4 butterflies per stage. Each radix-4 butterfly requires 3 complex multiplies and 8 complex additions. The total cost is then Radix-4 FFT Operation Counts 3 N 4 2 N 2 3 8 N 2 N complex multiplies (75% of a radix-2 FFT) 8 N 4 2 N 2 N 2 N complex adds (same as a radix-2 FFT) The radix-4 FFT requires only 75% as many complex multiplies as the radix-2 FFTs, although it uses the same number of complex additions. These additional savings make it a widely-used FFT algorithm.The decimation-in-time operation regroups the input samples at each successive stage of decomposition, resulting in a "digit-reversed" input order. That is, if the time-sample index n is written as a base-4 number, the order is that base-4 number reversed. The digit-reversal process is illustrated for a length- N 64 example below. N = 64 = 4^3 Original Number Original Digit Order Reversed Digit Order Digit-Reversed Number 0 000 000 0 1 001 100 16 2 002 200 32 3 003 300 48 4 010 010 4 5 011 110 20 ⋮ ⋮ ⋮ ⋮ It is important to note that, if the input signal data are placed in digit-reversed order before beginning the FFT computations, the outputs of each butterfly throughout the computation can be placed in the same memory locations from which the inputs were fetched, resulting in an in-place algorithm that requires no extra memory to perform the FFT. Most FFT implementations are in-place, and overwrite the input data with the intermediate values and finally the output. A slight rearrangement within the radix-4 FFT introduced by Burrus allows the inputs to be arranged in bit-reversed rather than digit-reversed order. A radix-4 decimation-in-frequency FFT can be derived similarly to the radix-2 DIF FFT, by separately computing all four groups of every fourth output frequency sample. The DIF radix-4 FFT is a flow-graph reversal of the DIT radix-4 FFT, with the same operation counts and twiddle factors in the reversed order. The output ends up in digit-reversed order for an in-place DIF algorithm. How do we derive a radix-4 algorithm when N 4 M 2 ? Perform a radix-2 decomposition for one stage, then radix-4 decompositions of all subsequent shorter-length DFTs. C.S. Burrus Unscrambling for fast DFT algorithms IEEE Transactions on Acoustics, Speech, and Signal Processing 1988 ASSP-36 7 1086-1089 July