Publication

Abstract : Realization of \(N\) -point discrete Fourier transform (DFT) using one-dimensional or two-dimensional systolic array structures has been developed for power of two DFT sizes. DFT algorithm, which can be represented as a triple-matrix product, can be realized by decomposing \(N\) into smaller lengths. Triple-matrix product form of representation enables to map the \(N\) -point DFT on a 2D systolic array. In this work, an algorithm is developed and is mapped to a two-dimensional systolic structure where DFT size can be non-power of two. The proposed work gives flexibility to choose \(N\) for an application where \(N\) is a composite number. The total time required to compute \(N\) -point DFT is \(2(N_{1}-1)+N_{2}+N\) for any \(N=N_{1}N_{2}\) . The array can be used for matrix-matrix multiplication and also to compute the diagonal elements of triple-matrix multiplication for other applications. The proposed architecture produces in-order stream of DFT sequence at the output avoiding need for reordering buffer. Large sized DFT can be computed by repeatedly using the proposed systolic array architecture.