Butterfly-processing element for efficient fast fourier transform method and apparatus

摘要

A Fast Fourier Transformation (FFT) method and apparatus is implemented using a radix-r butterfly design based on a reduced single phase of calculation, termed a butterfly-processing element (BPE). Butterfly calculations are each executed in the same number of iterations, and comprised of substantially identical butterfly-processing elements. The resulting algorithm, in which a number of parallel processors operate simultaneously by a single instruction sequence, reduces both the computational burden and the communication burden. The use of substantially identical butterfly-processing elements, repeated in combination to form a radix-r butterfly, enables the design of FFT butterflies containing identical structures and a systematic means of accessing the corresponding multiplier coefficients stored in memory. The butterfly-processing element substantially reduces the complexity of the radix-r butterfly, particularly for higher order radices. In particular, starting from the basic DFT equations, the adder matrix is factored and combined with the twiddle matrix to form a single phase of calculation. By grouping all the multiply calculations into one calculation phase and all the addition calculations into the remaining calculation phases, the total number of calculations is reduced and the degree of parallelism is increased. Trivial multiplications, encountered during the execution of particular butterflies, are avoided by simple checks on the coefficient addresses. An efficient address generator is provided to access or store the twiddle factors, the input data and the output data.