Multidimensional Systolic Arrays for Computing Discrete Fourier Transforms and Discrete Cosine Transforms

This chapter presents a new approach for computing the multidimensional discrete Fourier transform (DFT) and the multidimensional discrete cosine transform (DCT) in a multidimensional systolic array. There are extensive applications of fast Fourier transform (FFT) and fast cosine transform (FDCT) algorithms. From the basic principle of fast transform algorithms (breaking the computation in successively smaller computations), we find that the multidimensional systolic architecture is efficiently used for implementing FFT algorithms and FDCT algorithms. The essence of the multidimensional systolic array is to combine different types of semi-systolic arrays into one array so that the resulting array becomes truly systolic. This systolic array does not require any preloading of input data and it generates output data only from boundary PEs. No networks for transposition between intermediate constituent 1-D transforms are required; therefore the entire processing is fully pipelined. This approach is well suited for VLSI implementation by providing simple and regular structures. Complexity estimation of area*time2 shows our multidimensional systolic array is within a factor of logk of the lower bound for an M-dimensional k-point DFT (k=NM).