Abstract
In this paper, we propose a two-dimensional (2-D) systolic array for performing the 2-D N×N-point discrete Fourier transform (DFT). The new array is constructed based on the use of the Goertzel algorithm to realize the 2-D DFT in a row-column-wise or column-row-wise format. Unlike the conventional row-column decomposition method, the proposed system involves no matrix transposition problems. In addition, the system possesses the features of regularity, modularity, and concurrency. As a consequence, it is well suited to VLSI implementation and has a very high throughput of one 2-D transform per N cycles. Moreover, the utilization efficiency of the proposed system is 100 percent, and the latency (processing time for a single 2-D transform) is 4N-1 cycles. In terms of the area-time complexity, the proposed approach is a fast design and reaches the lower bound (AT p 2 = O (N 4 log 2 2 N 2 )).