Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Multi-dimensional FFT with Improved Data Flow

IP.com Disclosure Number: IPCOM000122022D
Original Publication Date: 1991-Oct-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 82K

Publishing Venue

IBM

Related People

Karp, AH: AUTHOR

Abstract

A program is disclosed that combines the small stride Pease FFT (Fast Fourier Transform) with a small stride matrix transposition scheme to eliminate a separate transpose step used in most implementations of multi-dimensional FFTs.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Multi-dimensional FFT with Improved Data Flow

      A program is disclosed that combines the small stride
Pease FFT (Fast Fourier Transform) with a small stride matrix
transposition scheme to eliminate a separate transpose step used in
most implementations of multi-dimensional FFTs.

      The Fourier transform of a multi-dimensional array is done by
computing the Fourier transform of each column, then of each row, and
so on for each dimension.  While the data can be accessed
contiguously in memory for the first set of transforms over the
columns (assuming Fortran style column major ordering), it must be
accessed at large stride for the subsequent ones.  Since the
performance of machines with hierarchical memories is substantially
degraded when data is accessed at large stride, the array is
typically transposed between sets of transforms.  Unfortunately,
these transposes necessarily access the data at large stride or
require multiple passes over the array.

      In (1) it was shown how to transpose a two-dimensional array
using one pass over the data for each prime factor of the leading
dimension using only sequential access methods. This idea was
extended to multiply dimensioned arrays in (2) which showed that the
method is efficient on machines with hierarchical memories.  The
invention described here uses the fact that the data access pattern
used to perform the transpose is exactly that used by the
one-dimensional Pease FFT algorithm (3).

      We start by performing a digit reversal permutation on each
column.  Next, we compute the FFT.  For a radix-2 FFT, at each stage
we multiple each odd numbered element by a proper "twiddle factor"
and form the sum and difference with the corresponding even numbered
term.  The sum is stored in the top half of the output array, and the
difference is stored in the bottom half.  We exchange the input and
output arrays and continue until we have finished the FFT on the
columns.  At this point, the indices of the array have been
circularly permuted so that...