An RNS discrete Fourier transform implementation

A novel discrete Fourier transform (DFT) implementation is described. It is based on the union of number theoretic transforms, modular arithmetic, and distributed arithmetic. In order to achieve megahertz-class transform rates with a limited amount of hardware, several new technologies are integrated. To accelerate complex arithmetic speed, a new body of knowledge called the quadratic residue number system (QRNS) is employed. To overcome the overflow management problem introduced by the QRNS, a finite impulse response form of the DFT, known as the prime factor transform (PFT), is used. In order to implement the PFT and the required QRNS overflow scaling units, a fast and compact distributed arithmetic filter (DAF) and number system converter is designed. The integrated system is developed and analyzed in the context of existing semiconductor technology. The resulting machine is shown to potentially possess megahertz-class performance, over a 16- to 24-bit data dynamic range, in a limited amount of hardware