Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-02
2003-12-02
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06658441
ABSTRACT:
OTHER PUBLICATIONS
Oppenheim et al, “Discrete-time Signal Processing” Prentice-Hall, N.J., 1989, pp609-618.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
“Not Applicable”
REFERENCE TO A MICROFICHE APPENDIX
“Not Applicable”
BACKGROUND OF THE INVENTION
The usefulness of the Fast Fourier Transform (FFT) is often limited by the computation speed and power consumption. Many researches have been done in order to improve the speed through parallel and pipelined architecture implementation [U.S. Pat. Nos. 5,163,017, 5,034,910, 4,821,224, 4,241,411]. However, all previously known efforts are based on the so called ‘butterfly structure’ [Oppenheim, 1989] or some variations of it. As the FFT transform size increases, the butterfly size increases, i.e., the locations of input and output data become farther apart. In high speed hardware implementations, this puts a limit on the computation speed since data propagation can not be done at a faster clock rate without added hardware for pipelining. This results in higher complexity circuit with higher power consumption. The current invention does not use the butterfly architecture, and data propagation during the computation is minimized, while the number of computing elements is kept minimal. As a result, the present invention improves FFT computation efficiency over prior arts in terms of speed, hardware complexity and power consumption.
BRIEF SUMMARY OF THE INVENTION
The circuit performs one dimensional (1-D) FFT of size N=N
0
×N
1
× . . . ×N
M−1
where, N
m
m=0, 1, . . . M−1, and M are positive numbers, by implementing 1-D FFTs with progressively increasing sizes, N
0
, N
0
×N
1
, N
0
×N
1
×N
2
, . . . , N
0
×N
1
× . . . ×N
M−1
, using two dimensional computation devices and methods recursively. First, an 1-D FFT of size N
0
×N
1
is achieved by a two-dimensional transform device with a twiddle factor multiplier between row and column transform stages, where each transform sizes are N
0
and N
1
, respectively. This is based on the algorithm described by Oppenheim [Oppenheim, pp609-618]. Once 1-D FFT of a size N
0
×N
1
is computed, one can continue to compute a larger size 1-D FFT using a two-dimensional transform of an increased size (N
0
×N
1
)×N
2
where only column transforms of N
2
-point DFTs need be further computed following a prior transform of size N
0
×N
1
. New twiddle factors need be multiplied element by element before the new column transform. This process can be continued for a next size ((N
0
×N
1
)×N
2
×N
3
, and so on, until 1-D FFT of a desired size N
0
×N
1
× . . . ×N
M−1
is achieved.
The complexity of the system is especially minimized if N
m
=4 or 2, m=0, 1, . . . M−1, since nontrival multiplications are required only for twiddle factor multiplications. As a result, the number of multiplication nodes in the signal flow is significantly reduced. Since a recursive two-dimensional transform data flow replaces prior art butterfly data flow in the FFT computation, the control circuit for computing butterfly memory address is removed. The combined effect of smaller number of multiplication nodes and simpler control makes the current FFT architecture and algorithm suitable for high-speed operation. Furthermore, by adopting a transpose-less pipelined 2-D transform architecture by Kim (U.S. Pat. No. 5,528,736), a preferred embodiment in the current invention, one output per clock computation throughput rate is achieved.
REFERENCES:
patent: 3662161 (1972-05-01), Bergland et al.
patent: 4060850 (1977-11-01), Speiser
patent: 4241411 (1980-12-01), Krasner et al.
patent: 4275452 (1981-06-01), White
patent: 4293921 (1981-10-01), Smith, Jr.
patent: 4344151 (1982-08-01), White
patent: 4471357 (1984-09-01), Wu et al.
patent: 4534009 (1985-08-01), McGee
patent: 4821224 (1989-04-01), Liu et al.
patent: 4839844 (1989-06-01), Watari
patent: 4929954 (1990-05-01), Elleaume
patent: 4970674 (1990-11-01), White
patent: 5034910 (1991-07-01), Whelchel et al.
patent: 5163017 (1992-11-01), Wong et al.
patent: 5365470 (1994-11-01), Smith
patent: 5528736 (1996-06-01), Kim
patent: 5535291 (1996-07-01), Spencer et al.
patent: 5805106 (1998-09-01), Baum
patent: 5805485 (1998-09-01), Ito et al.
patent: 6061705 (2000-05-01), Hellberg
patent: 6081821 (2000-06-01), Hopkinson et al.
patent: 6247034 (2001-06-01), Nakai et al.
patent: 6366936 (2002-04-01), Lee et al.
Lang et al., The multidimensional Phase-Rotation FFT: A New Parallel Architecture, 1991, IEEE Transactions on Signal Processing, CH2977-7, 2889-2892.*
Soheil I. Sayegh, A Pipeline Processor for Mixed-Size FFT's, Aug. 8 1992, IEEE Transactions on Signal Processing, vol. 40, 1892-1900.*
Oppenheim and Shafer, Discrete-time signal processing, 1989, pp. 609-613, 1st Ed., Prenticce-Hall Inc., Englwood Cliffs, New Jersey USA.*
Sungwook Yu et al., A new pipelined implementation of the Fast Fourier Transform, IEEE 2000, pp. 423-427.
Do Chat C
Kim Seung Pil
LandOfFree
Apparatus and method for recursive parallel and pipelined... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for recursive parallel and pipelined..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for recursive parallel and pipelined... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3137839