Browse Prior Art Database

Fast Discrete Fourier Transform

IP.com Disclosure Number: IPCOM000068568D
Original Publication Date: 1978-Jan-01
Included in the Prior Art Database: 2005-Feb-20

Publishing Venue

IBM

Related People

Authors:
Nussbaumer, H [+details]

Abstract

A discrete Fourier transform (DPT) of dimension N = N(1).N(2), where N(1), N(2)...N(d) are relative primes, can be viewed as a multidimensional transform of dimension N(1) x N(2)... x N(d). Moreover, if N(1), N(2)... N(2) are primes or powers of primes, the individual DFTs of dimension N(1), N(2)... N(2) can be computed by correlations. In this article, it is shown that the bulk of the calculations required to evaluate a DFT of dimension N(1).N(2)... N(d) corresponds to computing multidimensional correlations, which can in turn, be computed efficiently by polynomial transforms.