Triple-Matrix Product-Based 2D Systolic Implementation of Discrete Fourier Transform

TitleTriple-Matrix Product-Based 2D Systolic Implementation of Discrete Fourier Transform
Publication TypeJournal Article
Year of Publication2015
AuthorsMamatha, I., TSB. Sudarshan, S.. Tripathi, and N. Bhattar
JournalCircuits, Systems, and Signal Processing
Volume34
Issue10
Pagination3221-3239
ISBN Number0278-081X
KeywordsDept. of Electronics and communication Engineering.
Abstract

Realization of NN -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 NN into smaller lengths. Triple-matrix product form of representation enables to map the NN -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 NN for an application where NN is a composite number. The total time required to compute NN -point DFT is 2(N1−1)+N2+N2(N1−1)+N2+N for any N=N1N2N=N1N2 . 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.