US 12,754,969 B2Granted

Method and apparatus for efficient multidimensional fast Fourier transforms

OwnerSeung Pil Kiminventor

Life of this patent

Estimating the term…

Abstract

A method and apparatus for calculating multidimensional Fast Fourier Transforms (FFTs) efficiently without transpose data flow and with in-place computations. If higher throughput computations are desired, computations are done in pipelined stages with parallel computing devices. A wide range of trade-offs can be made between the computation speed and the hardware complexity. This is based on an extension of the Cooley-Tuckey algorithm to n-dimensional data. A mathematical derivation of the algorithm has been provided. This invention makes it possible to perform n-dimensional FFTs, n>1 without relying on one-dimensional FFT computations.

Claims6

Dependent claims

A method, comprising:

reading an n-dimensional input data of a size N1×N2× . . . ×Nn from an input buffer, the n-dimensional input data having a size Ni along each of an axis i=1, 2, . . . , n, wherein n is an integer greater than or equal to 2;
performing an n-dimensional fast Fourier transform (FFT) using one or more n-dimensional radix butterfly computing elements referred to as n-D-fly computation blocks, and the performing further comprises:
computing an n-dimensional output of a size r1×r2× . . . ×rn from an input of the same size by using one or more of a plurality of one-dimensional butterfly blocks or one or more of a plurality of one-dimensional quad-fly blocks along each of the axis i=1, 2, . . . , n, in a sequential manner, depending on whether the radix ri of the axis i is 2 or 4;
and
computing an intermediate n-dimensional FFTs of progressively increasing sizes in an S number of stages, wherein S is a total number of the stages, wherein:
at a first stage, Stage-1, the n-D-fly blocks compute a plurality of n-dimensional outputs of a size
r
1
(
1
)
×
r
2
(
1
)
×
…
×
r
n
(
1
)
;
after receiving a corresponding plurality of inputs of a same size from an input ping-pong buffer, the plurality of n-dimensional outputs being equivalent to n-dimensional discrete Fourier Transforms (DFTs), wherein the first stage radix
r
i
(
1
)
=
2
⁢
or
⁢
4
depending on a radix decomposition selected for the axis i=1, 2, . . . , n;
at Stage-s, where s=2, 3, . . . , S, the intermediate n-dimensional FFTs of increased size are computed using the plurality of n-dimensional outputs computed from the previous stage and received from a ping-pong buffer, and a plurality of twiddle factors computed from a plurality of locations of the n-dimensional input data at a current stage, Stage-s, wherein a transform size along the axis i is increased by a factor
r
i
(
s
)
=
2
⁢
or
⁢
4
wherein an n-dimensional radix at Stage-s is
r
1
(
s
)
×
r
2
(
s
)
×
…
×
r
n
(
s
)
;
and
at a final stage, Stage-S, computing a final n-dimensional FFT of a size N1×N2× . . . ×Nn corresponding to the n-dimensional input data of the size N1×N2× . . . ×Nn and outputting to an output ping-pong buffer.

71 more elements

An apparatus, comprising:

an input buffer configured to store an n-dimensional input data of a size N1×N2× . . . ×Nn wherein n is an integer greater than or equal to 2;
an output buffer configured to store an n-dimensional FFT result of the n-dimensional input data;
and
an Stage-s computation pipeline, wherein s=1, 2, . . . , S and S is a total number of the stages, having an n-dimensional radix
r
1
(
s
)
×
r
2
(
s
)
×
…
×
r
n
(
s
)
at Stage-s,
wherein each stage in Stage-s comprises one or more n-D-fly computation blocks implemented using a plurality of processors or a plurality of programmable logic devices, wherein each n-D-fly computation block further comprises:
a plurality of n sequential sub-stages, wherein each sub-stage is configured to compute along a corresponding data axis i=1, 2, . . . , n in a sequential manner,
wherein each sub-stage comprises one or more of a plurality of one-dimensional butterfly blocks or one or more of a plurality of one-dimensional quad-fly blocks, depending on a radix
r
i
(
s
)
=
2
or 4 selected for the data axis i at Stage-s,
wherein each stage further comprises a ping-pong buffer;
wherein each stage further comprises a storage for a plurality of twiddle factors and the plurality of twiddle factors computed from a plurality of locations of the n-dimensional input data at each Stage-s;
the Stage-s computation pipeline configured at each Stage-s to increase a transform size along each axis i by the corresponding radix factor
r
i
(
s
)
,
producing an intermediate n-dimensional FFTs of progressively increasing sizes;
and
at Stage-S, computing a final n-dimensional FFT of size N1×N2× . . . ×Nn corresponding to the n-dimensional input data of the size N1×N2× . . . ×Nn and outputting to an output ping-pong buffer.

44 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

A method, comprising:

reading an n-dimensional input data of a size N1×N2× . . . ×Nn from an input buffer, the n-dimensional input data having a size Ni along each of an axis i=1, 2, . . . , n, wherein n is an integer greater than or equal to 2;
performing an n-dimensional fast Fourier transform (FFT) using one or more n-dimensional radix butterfly computing elements referred to as n-D-fly computation blocks, and the performing further comprises:
computing an n-dimensional output of a size r1×r2× . . . ×rn from an input of the same size by using one or more of a plurality of one-dimensional butterfly blocks or one or more of a plurality of one-dimensional quad-fly blocks along each of the axis i=1, 2, . . . , n, in a sequential manner, depending on whether the radix ri of the axis i is 2 or 4;
and
computing an intermediate n-dimensional FFTs of progressively increasing sizes in an S number of stages, wherein S is a total number of the stages, wherein:
at a first stage, Stage-1, the n-D-fly blocks compute a plurality of n-dimensional outputs of a size
r
1
(
1
)
×
r
2
(
1
)
×
…
×
r
n
(
1
)
;
after receiving a corresponding plurality of inputs of a same size from an input ping-pong buffer, the plurality of n-dimensional outputs being equivalent to n-dimensional discrete Fourier Transforms (DFTs), wherein the first stage radix
r
i
(
1
)
=
2
⁢
or
⁢
4
depending on a radix decomposition selected for the axis i=1, 2, . . . , n;
at Stage-s, where s=2, 3, . . . , S, the intermediate n-dimensional FFTs of increased size are computed using the plurality of n-dimensional outputs computed from the previous stage and received from a ping-pong buffer, and a plurality of twiddle factors computed from a plurality of locations of the n-dimensional input data at a current stage, Stage-s, wherein a transform size along the axis i is increased by a factor
r
i
(
s
)
=
2
⁢
or
⁢
4
wherein an n-dimensional radix at Stage-s is
r
1
(
s
)
×
r
2
(
s
)
×
…
×
r
n
(
s
)
;
and
at a final stage, Stage-S, computing a final n-dimensional FFT of a size N1×N2× . . . ×Nn corresponding to the n-dimensional input data of the size N1×N2× . . . ×Nn and outputting to an output ping-pong buffer.

71 more elements