Browse Prior Art Database

Computing Multidimensional Discrete Fourier Transforms by Polynomial Transforms

IP.com Disclosure Number: IPCOM000056040D
Original Publication Date: 1980-Oct-01
Included in the Prior Art Database: 2005-Feb-13

Publishing Venue

IBM

Related People

Authors:
Nussbaumer, H [+details]

Abstract

In this article we introduce an improved technique for computing multi-dimensional discrete Fourier transforms (DFTs) by polynomial transforms. We show that a DFT of size NxN, with N=2/t/, can be computed by a single polynomial transform, N DFTs of N terms plus N/2/ multiplications. (See Original for pages 1972-1974 top).