A Fast Fourier Transform(FFT) hardware implementation and method provides efficient FFT processing while minimizing the die area needed in an Integrated Circuit(IC). The FFT hardware can implement an N point FFT, where N = rn is a function of a radix(r). The hardware implementation includes a sample memory having N/r rows, each storing r samples. A twiddle factor memory can store k twiddle factors per row, where 0 < k<r represents the number of complex twiddle multipliers available. An FFT module reads r rows from memory, performs an r-point complex FFT on the samples, followed by twiddle multiplication, and writes the results into an r x r register bank. The contents of the register bank are written in transposed order back to the sample memory. This operation is repeated N/r2 times for each stage and then repeated for n- stages to produce the N point FFT. |