A new systolic array algorithm for discrete Fourier transform

Author

Liu, Chi-Min ; Jen, Chein-Wei

Author_Institution

Dept. of Electron. Eng., Nat. Chiao Tung Univ., Hsinchu, Taiwan

fYear

1991

fDate

11-14 Jun 1991

Firstpage

2212

Abstract

A new systolic algorithm for computing the discrete Fourier transform (DFT) is presented. The algorithm exhibits the minimum required time O(Nt_a) and the computational complexity O(2N²), which are much better than the time O(Nt_a+Nt_m) and the complexity O(4N²) in existing systolic algorithms, where t_a and t_m are the computation time for a complex addition and a complex multiplication, respectively, and N is the DFT length. By exerting the benefits of the algorithm and adopting the scheme of tag control, a systolic array and a two-level pipelined systolic array are designed. The resulting arrays have outstanding performance on computing speeds, hardware cost, and the number of input/output (I/O) channels

Keywords

computational complexity; digital signal processing chips; fast Fourier transforms; parallel processing; systolic arrays; DFT; I/O channels; computational complexity; computing speeds; discrete Fourier transform; hardware cost; minimum required time; performance; systolic array; systolic array algorithm; tag control; two-level pipelined systolic array; Bandwidth; Computational complexity; Concurrent computing; Costs; Discrete Fourier transforms; Hardware; Parallel processing; Power generation; Systolic arrays; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1991., IEEE International Sympoisum on

Print_ISBN

0-7803-0050-5

Type

conf

DOI

10.1109/ISCAS.1991.176739

Filename

176739