FAST FOURIER TRANSFORM CIRCUIT HAVING PARTITIONED MEMORY FOR MINIMAL LATENCY DURING IN-PLACE COMPUTATION

摘要

An FFT circuit (10) is implemented using a radix-4 butterfly element (12) and a partitioned memory (16a, 16b) for storage of a prescribed number of data values. The radix-4 butterfly element is configured for performing an FFT operation in a prescribed number of stages (30a, 30b, 30c), each stage including a prescribed number of in-place computation operations (32) relative to the prescribed number of data values. The partitioned memory includes a first memory portion and a second memory portion, and the data values (34, 36) for the FFT circuit are divided equally for storage in the first and second memory portions in a manner that ensures that each I-place computation operation is based on retrieval of an equal number of data values retrieved from each of the first and second memory portions.