VLSI systolic array architectures for the one-dimensional and two-dimensional discrete Fourier transform.

Abstract

In this thesis, we propose efficient systolic array architectures for the 1-D and the 2-D discrete Fourier transforms (DFT) using the second-order Goertzel algorithm. For the 1-D DFT, two 1-D and one 2D systolic arrays are proposed. The two 1-D structures, a semi-systolic array and a pure-systolic array, are characterized by regular, modular cell interconnections, thus making the arrays compatible with VLSI design principles. These arrays perform at an effective throughput rate of one DFT sample per clock cycle. The proposed 2-D array structure obtains a higher throughput rate of one DFT transform per clock cycle. As for the 2-D DFT, a 2-D systolic array architecture is developed which does not require a row-column transposition while some delay units are needed between the two stages. All the above proposed systolic arrays can process continuous flow of input data and perform at 100% efficiency. These structures are compared to other DFT systolic arrays regarding complexity and real-time implementation. (Abstract shortened by UMI.)