Automatic generation of prime length FFT programs

Ivan W. Selesnick, C. Sidney Burrus

Research output: Contribution to journalArticle

Abstract

We describe a set of programs for circular convolution and prime length fast Fourier transforms (FFT's) that are relatively short, possess great structure, share many computational procedures, and cover a large variety of lengths. The programs make clear the structure of the algorithms and clearly enumerate independent computational branches that can be performed in parallel. Moreover, each of these independent operations is made up of a sequence of suboperations that can be implemented as vector/parallel operations. This is in contrast with previously existing programs for prime length FFT's: They consist of straight line code, no code is shared between them, and they cannot be easily adapted for vector/parallel implementations. We have also developed a program that automatically generates these programs for prime length FFT's. This code-generating program requires information only about a set of modules for computing cyclotomic convolutions.

Original languageEnglish (US)
Pages (from-to)14-24
Number of pages11
JournalIEEE Transactions on Signal Processing
Volume44
Issue number1
DOIs
StatePublished - 1996

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Automatic generation of prime length FFT programs'. Together they form a unique fingerprint.

  • Cite this