A novel pipeline design for the realization of the prime factor FFT

An extremely efficient pipeline architecture is proposed for the realization of the prime factor algorithm (PFA). Using the extended diagonal feature of the Chinese remainder theorem mapping, it is shown that data transactions during the computation can be efficiently carried out with the simplest control strategy. Thus, the approach has the least hardware requirement as compared to previous methods. In the case of multidimensional PFA computation, it does not require the computation to be split up into a number of two-dimensional ones. Consequently, the overhead for data loading and data retrieval in each two-dimensional stage can be saved. All these savings are achieved by using just one more link, which connects all the memory buffers via the extended diagonal of a multidimensional array