APPARATUS AND METHOD FOR FAST FOURIER TRANSFORM

摘要

A device and a method for fast Fourier transform are provided to offer a simple binary reverse output order and reduce complexity while minimizing the number of hardware elements by having a structure formed with only the adders without any multiplier, as a mixed radix 4-2 butterfly structure is used. The first radix-4 butterfly operation module(110) generates the first output data according to the simple binary reverse output order by performing the radix-4 butterfly operation after decomposing input and output data according to an index decomposition method. The first radix-2 butterfly operation module(120) generates the second output data according to the simple binary reverse output order by performing the radix-2 butterfly operation with the first output data according to the index decomposition method.