Fast fourier transform circuit having partitioned memory for minimal latency during in-place computation

摘要

An FFT circuit is implemented using a radix-4 butterfly element and a partitioned memory 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, each stage including a prescribed number of in-place computation operations 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 for the FFT circuit are divided equally for storage in the first and second memory portions in a manner that ensures that each in-place computation operation is based on retrieval of an equal number of data values retrieved from each of the first and second memory portions.