A new systolic architecture for pipeline prime factor DFT-algorithm

The paper shows how a rectangular array of N=N _{1spl times}N ₂ processing elements (PE), where N ₁ and N ₂ are relatively prime, can be used do carry out efficient two-dimensional systolic implementation of N-point DFT, offering highly attractive throughput rates in relation to other N-processor solutions, such as the conventional linear systolic array. The systematic approach allows one to choose, among all possible systolic processors for the 2D-DFT algorithm, an optimal design which has the minimum number of locally connected PE´s, good coordination between the processes of computation and communication, a small number of I/O pins, the minimum possible time of processing and the minimum amount of input data.<>