FAST FOURIER TRANSFORM METHOD AND DEVICE THEREOF

摘要

A fast Fourier transform method disclosed in an embodiment of this invention enables not only the prevention of a collision, wherein one bank reads out at least 2 pieces of data from a memory at one time, but also the consistent application of low complex addressing in each stage. The disclosed fast Fourier transform method using an in-place method and an N-point radix-M method is characterized by comprising the steps of: (a) determining, when M pieces of data are inputted, a memory address which includes M number of banks having N/M number of addresses, to store N pieces of data and then determining a starting bank index based on the determined address; (b) storing the inputted M pieces of data at the determined address from the bank corresponding to the first start bank index circularly; (c) converting the memory address to determine a new memory address whenever data after the M pieces of data are inputted until N pieces of data are inputted at the memory and repeating the steps (b) and (c); and (d) performing butterfly arithmetic by using the data stored in the memory.