DIMENSIONLESS FAST FOURIER TRANSFORM METHOD AND APPARATUS

摘要

A method and apparatus for calculating fast Fourier transforms FFTs. An FFT of a given size is formatted using tensor product principles for implementation in apparatus or by software such that the same reconfigurable hardware or software can calculate FFTs of any dimension for the selected FFT size. The FFT is factored into an input permutation and successive stages for computing tensor products of dimensionless Fourier transforms of a relatively small base size and twiddle factors, with load-stride permutations between computation stages. The basic building blocks of the circuitry can be reconfigurable for maximizing use-flexibility of the hardware or software. Examples of digital circuit apparatus configured to compute dimensionless formatted FFTs are presented.