Apparatus and method for recursive parallel and pipelined fast fourier transform

摘要

A circuit for performing Fast Fourier Transform (FFT) with minimum number of clock cycles and minimum complexity. One-dimensional FFT of size N=N₀×N₁× . . . ×N_M−1, N_mm=0, 1, . . . , M−1, positive numbers, is computed recursively, through a sequence of two-dimensional row-column transform computations of sizes, N₀×N₁, (N₀×N₁)×N₂, (N₀×N₁×N₂)×N₃, . . . , (N₀×N₁× . . . ×N_M−2)×N_M−1 with twiddle factors. The complexity of the circuit is reduced by elimination of butterfly computation structure and adaptation of transposeless 2-D transform architecture.