A unified treatment of compact symmetric FFT code generation

Author

Seguel, Jaime

Author_Institution

Dept. of Electr. & Comput. Eng., Puerto Rico Univ., Mayaguez, Puerto Rico

Volume

50

Issue

11

fYear

2002

fDate

11/1/2002 12:00:00 AM

Firstpage

2789

Lastpage

2797

Abstract

A method for the automatic generation of compact symmetric fast Fourier transforms (FFTs) from high-level specifications is presented. The generated code eliminates all redundant computations induced by the symmetries in the FFT data flow, minimizing storage requirements, input/output and arithmetic operations, and preserves the attractive computational feature of FFT algorithms. The code-generating method can be expressed as a simple and well-structured meta-algorithm whose inputs are the dimension and edge size of the data array and a matrix representation of the data symmetries

Keywords

computational complexity; fast Fourier transforms; mathematics computing; program compilers; signal processing; FFT data flow; arithmetic operations; automatic generation; code-generating method; compact symmetric FFT code generation; compact symmetric fast Fourier transforms; computational feature; data array; data symmetries; edge size; high-level specifications; input/output; matrix representation; meta-algorithm; redundant computations; storage requirements; unified treatment; Arithmetic; Data flow computing; Discrete Fourier transforms; Fast Fourier transforms; Flexible printed circuits; Fourier transforms; Helium; History; Multidimensional systems; Pervasive computing;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/TSP.2002.804318

Filename

1041036