Optimal VLSI complexity design for high speed pipeline FFT using RNS
In this study a logic design, based on RNS units, to perform the N point FFT on a continuous data stream is proposed, and its performance is evaluated in terms of asymptotic VLSI complexity. Such a structure is based on quadratic residue number systems (QRNS), which allow a simplified processing of complex numbers. It is known in the literature that a lower bound on complexity for a single instance of the FFT problem is A(N)T2(N)=?(N2 log2N), and that optimal constructive designs were proposed with T(N)=?(log2N). The architecture proposed here is based on a very high degree of processing parallelism and on a communication parallelism tailored to the response time of adders and multipliers used in the design; furthermore, pipelining data it performs as a single FFT instance optimal design and features an upper bound for the mean service timeTm(N)=?(log log log N) for each FFT instance. The approach has been also applied in the design of a structure performing 1024-point FFT, with 23 bit data.
vlsi complexity pipeline fft quadratic residue number systems (qrns)