Methods and apparatus for reordering data signals in fast fourier transform systems

摘要

Data signal items output by a radix 4n2m fast Fourier transform (“FFT”) operation may not be in the order desired for further use of those data items (e.g., they may be output in a non-natural order rather than in a desired natural order). Memory circuitry (e.g., dual-port memory circuitry) may be used in conjunction with circuitry for addressing the memory circuitry with address signals that are reordered in a particular way for each successive set of N data items. This allows use of memory circuitry with fewer data item storage locations than would otherwise be required to reorder the data items from non-natural to natural order. In particular, the memory circuitry only needs to be able to store N data items at any one time, which is more efficient memory utilization than would otherwise be possible.

主权项

1. Circuitry for reordering at least three successive sets of data items in a radix 4n2m fast Fourier transform (“FFT”) operation comprising:
circuitry for producing at least three successive sets of addresses in synchronism with the at least three successive sets of data items, wherein: the data items in each successive set of the data items are produced one after another in succession, the addresses in each successive set of the addresses are produced one after another in succession in synchronism with production of an associated one of the data items, and the order of pairs of adjacent bits in each address in each successive set of the addresses is reversed as compared to the order of the said pairs of adjacent bits in a corresponding address in an immediately preceding one of the sets of addresses; memory circuitry; circuitry for applying each successive set of the data items to a data input port of the memory circuitry; and circuitry for applying each successive set of the addresses to read and write address ports of the memory circuitry so that the data items of each successive set of the data items are stored in the memory circuitry as data items of an immediately preceding set of the data items are read out from a data output port of the memory circuitry.