Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-08-07
2004-04-27
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06728742
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to Fast Fourier Transforms and, more particularly, to methods of data storage that are particularly useful in VLSI implementations of in-place FFT algorithms.
Since its rediscovery by Cooley and Tukey in 1965, the Fast Fourier Transform (FFT) has found wide application in fields such as digital signal processing. A general review of the state of the art in FFTs is found in P. Duhamel and M. Vetterli, “Fast Fourier Transforms: a tutorial review and a state of the art”,
Signal Processing
vol. 19, pp. 259-299 (1990), which is incorporated by reference for all purposes as if fully set forth herein.
One particular class of FFTs is the in-place Cooley-Tukey FFT.
FIG. 1
, which is adapted from
FIG. 1
of Duhamel and Vetterli, illustrates this style of FFT. This particular example shows the implementation of a 15-point FFT as a succession of radix-5 and radix-3 Discrete Fourier Transforms (DFTs). An input sequence of 15 complex numbers x
0
through x
14
is stored in column order in an array
10
of 3 rows and 5 columns, as shown. The first step of the FFT is three radix-5 DFTs
12
of the three rows of array
10
. DFTs
12
are performed in place: the numbers stored in each row of array
10
are read and transformed, and the transformed numbers replace the original numbers in array
10
. The second step of the FFT is the multiplication, also in place, of each number now stored in array
10
by a corresponding “twiddle factor” from a 3 row, 5 column array
14
of twiddle factors w that are integral powers of exp(−2&pgr;j/15), where j is the square root of −1. (In general, the twiddle factors are integral powers of exp(−2&pgr;j/N), where N is the length of the FFT.) The third step of the FFT is five radix-3 DFTs
16
of the five columns now stored in array
10
. This third step also is performed in place: the numbers stored in each column of array
10
are read and transformed, and the transformed numbers replace the numbers stored in array
10
prior to the radix-3 DFTs. The final output sequence of the transform, 15 complex numbers x
0
through x
14
, is read from array
10
in row order, as shown.
As noted by Duhamel and Vetterli, most of the effort invested in optimizing the implementation of FFTs has been directed towards reducing the number of arithmetic operations performed. The net speed of an FFT implementation also depends on the speed at which numbers are retrieved from memory and stored in memory. This is particularly true in the case of very large scale integration (VLSI) implementations, in which the DFTs are performed by dedicated hardware.
There is thus a widely recognized need for, and it would be highly advantageous to have, an efficient method for storing and retrieving the numbers used in an in-place FFT.
SUMMARY OF THE INVENTION
According to the present invention there is provided a method of performing a FFT of a sequence of N=B
n
numbers, where B is a power of 2 and n is a positive integer, including the steps of: (a) recursively selecting a pattern of storage locations for the B
n
numbers in M in-place memories, M being a power of 2 that is less than B, wherein, if n=1, each in-place memory has storage locations for a different B/M of the B numbers, and wherein, if n is greater than 1, the pattern for storing B
n
numbers is a concatenation of B the patterns for storing B
n−1
numbers, there being B/M successive sets of the patterns for storing B
n−1
numbers in the pattern for storing B
n
numbers when n is greater than 1, the patterns, for storing B
n−1
numbers, within each of the B/M successive sets, being mutually identical and being different from the patterns, for storing B
n−1
numbers, of any other the set; (b) storing the numbers in the storage locations; (c) performing an in-place radix-B DFT on each of N/B groups of values stored in the storage locations; and (d) if n is greater than 1, performing a length N/B DFT on each of B groups of N/B values stored in the storage locations, each group including N/(MB) values stored in each of the in-place memories.
According to the present invention there is provided a device for performing an FFT of a sequence of N=B
n
numbers, where B is a power of 2 and n is a positive integer, including: (a) M in-place memories, M being a power of 2 that is less than B; (b) a software module including a plurality of instructions for storing the N numbers in corresponding storage locations in the in-place memories according to one of a recursively derived plurality of patterns of the storage locations, the pattern for n=1 being such that a different B/M of the N numbers is stored in each in-place memories, and the pattern for n greater than 1 being a concatenation of B of the patterns for n−1, there being B/M successive sets of the patterns for n−1 in the pattern for n greater than w, the patterns for n−1 within each of the B/M successive sets being mutually identical and being different from the patterns for N−1 of any other the set; (c) a master processor for executing the instructions, thereby storing N values in N the storage locations; and (d) at least one FFT processor for performing a radix-B FFT on the N values taken B at a time.
According to the present invention there is provided a method of providing a plurality of complex numbers of unit modulus to a computational process, including the steps of: (a) factoring each complex number into a most significant factor and a least significant factor; (b) storing the most significant factors in a most significant factor memory; and (c) storing at least a part of each least significant factor in a least significant factor memory.
According to the present invention there is provided a method of performing a FFT of a sequence of N=CB
n
numbers, where B is a power of 2, C is a power of 2 that is less than B, and n is a positive integer, including the steps of: (a) recursively selecting a pattern of storage locations for B
n+1
numbers in M in-place memories, M being a power of 2 that is less than B, starting from a base storage pattern, for B numbers, wherein each in-place memory has storage locations for a different B/M of the B numbers, each subsequently selected pattern for storing B
m
numbers, where m is an integer greater than 1, being a concatenation of B the patterns for storing B
m−1
numbers, there being B/M successive sets of the patterns for storing B
m−1
numbers in the pattern for storing B
m
numbers, the patterns, for storing B
m−1
numbers, within each of the B/M successive sets, being mutually identical and being different from the patterns, for storing B
m−1
numbers, of any other set; (b) storing the N numbers in N of the storage locations for B
n+1
numbers; (c) performing an in-place radix-C DFT on each of N/C groups of values stored in the N storage locations; and (d) performing a length B
n
DFT on each of C groups of B
n
values stored in the N storage locations, each group including B
n
/M values stored in each of the in-place memories.
According to the present invention there is provided a device for performing an FFT of a sequence of N=CB
n
numbers, where B is a power of 2, C is a power of 2 that is less than B, and n is a positive integer, including: (a)M in-place memories, M being a power of 2 that is less than B; (b) a software module including a plurality of instructions for storing the N numbers in corresponding storage locations in the in-place memories according to a recursively derived pattern of storage locations for storing B
n+1
numbers, a base pattern of the recursive derivation being a pattern for storing B numbers, such that a different B/M of the B numbers is stored in each of the in-place memories, and each subsequently derived pattern for storing B
m
numbers, where m is an integer greater than 1, being a concatenation of B of the patterns for storing B
m−1
numbers, there being B/M successive sets of the
Friedman Mark M.
Ngo Chuong Dinh
LandOfFree
Data storage patterns for fast fourier transforms does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data storage patterns for fast fourier transforms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data storage patterns for fast fourier transforms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3261844