Multidimensional Fourier transforms by systolic architectures

A method of formal transformation of a multidimensional DFT (discrete Fourier transform) algorithm to a form suitable for implementation with a systolic macropipeline is discussed. The suggested transformation of the original form of the DFT algorithm consists of one or several rotationlike transfor...

Full description

Saved in:
Bibliographic Details
Main Author: Roziner, T.D.
Format: Conference Proceeding
Language:English
Subjects:
Circuits
Computer architecture
Design for testability
Discrete Fourier transforms
Fourier transforms
Laboratories
Multidimensional systems
Systolic arrays
Throughput
Very large scale integration
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A method of formal transformation of a multidimensional DFT (discrete Fourier transform) algorithm to a form suitable for implementation with a systolic macropipeline is discussed. The suggested transformation of the original form of the DFT algorithm consists of one or several rotationlike transforms applied to the index set. The resulting 'completely systolized' form of the algorithm makes it possible to implement the N/sup M/-point (m-dimensional) DFT with a macropipeline containing M or (M-1) cascaded systolic/semisystolic arrays. Each array is an M-dimensional hypercube of the processing elements (PEs) of the multiply-add type; the internal structure of PEs in different arrays is slightly different. For given values of N and M, several design options exist, with hardware complexity of about the same value. The proposed systolic architecture makes it possible to obtain the throughput of N (one set of spectrum values every N array clocks) for any number of dimensions M.< >
DOI:10.1109/PARBSE.1990.77153