Architectural design of array processors for multi-dimensional discrete Fourier transform
Stanislav G. Sedukhin, S. Peng · WIT Press eBooks · 2001
In this chapter, the design of systolic array processors (SAPs) for computing multi-dimensional discrete Fourier transform (r-D DFT) is considered. We introduce two approaches of design: one uses the data For the first approach, we investigated three different computational schemes for designing SAPs for 2-D DFT. The systematic method guarantees to find optimal SAPs from a large solution space in terms of the number of processing elements and I/O channels, the processing time, topology, pipeline period, etc. This approach is difficult to extend to the 3-D case since the 6-D data dependency graph for the 3-D DFT cannot be reduced easily. Therefore, for the 3-D DFT we propose another approach: the dimensional splitting method. Using this method, computing of the r-D DFT with r ≥ 2 is done iteratively with each iteration handling the 1-D DFTs of different dimensions. Finally, an application of the proposed SAPs to the prime-factor DFT is presented.