| 摘要 |
A circuit and a method for implementing Fast Fourier Transform (FFT)/Inverse Fast Fourier Transform (IFFT) are provided. The method includes: determining the number m of iterations, depth d1 of the first and second Random Access Memories (RAMs), depth d2 of a Read Only Memory (ROM); storing the first and second n/2 parts of the input data to be Transformed into the second and first RAMs respectively; performing the iterative butterfly operations m times; in the first iteration, reading the first and second RAMs in a reverse bit order, writing the results of the even-numbered butterfly operations into the first RAM, writing the results of the odd-numbered butterfly operations into the second RAM; during the second to the (m-1)th iterations, reading the first and second RAMs in a normal bit order, wherein the way to write back to the RAM is the same as that of the first time; in the m-th iteration, reading the first and second RAMs in a normal bit order, wherein the location in the RAM to be written back is the same as the location for reading. |
