Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Patent
1997-01-06
1999-12-14
Moise, Emmanuel L.
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
708406, G06F 1500
Patent
active
060030569
ABSTRACT:
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.
REFERENCES:
patent: 4456877 (1984-06-01), Brown
patent: 4858164 (1989-08-01), Schildhorn
patent: 5293330 (1994-03-01), Sayegh
patent: 5365470 (1994-11-01), Smith
patent: 5724278 (1998-03-01), Ohgose et al.
Frontiers in Applied Mathematics; Computational Frameworks for the Fast Fourier Transform; Charles Van Loan; 1992 by the Society for Industrial and Applied Mathematics; (entire book, 273 pages).
How the FFT Gained Acceptance; James W. Cooley; Jan. 1992, IEEE SP Magazine, pp. 10-13.
Fast Fourier Transforms--For Fun and Profit; W.M. Gentleman; AFIPS Proceedings -- Fall Joint Computer Conference, 1966, pp. 333-348.
Vector Radix Fast Fourier Transform; David B. Harris et al, 1977 IEEE Int. Conf. on Acoustics, Speech and Signal Processing, May 9-11, 1977, Hartford, Conn.; pp. 548-551.
Direct Fast Fourier Transform of Bivariate Functions; Glen E. Rivard; IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-25, No. 3, Jun. 1977, pp. 250-252.
A Unified Treatment of Cooley-Tukey Algorithms for the Evaluation of the Multidimensional DFT; Russell M. Mersereau, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-29, No. 5, Oct. 1981; pp. 1011-1018.
Kronecker Products and Shuffle Algebra, Marc Davio; IEEE Transactions on Computers, vol. C-30, No. 2, Feb. 1981; pp. 116-125.
An Adaptation of the Fast Fourier Transform for Parallel Processing; Marshall C. Pease; Journal of the Association for Computing Machinery, vol. 15, No. 2, Apr. 1968, pp. 252-264.
Short Notes; The Relationship Between Two Fast Fourier Transforms; IEEE Transactions on Computers, Mar. 1971; pp. 310-317.
Al Algorithm for the Machine Calculation of Complex Fourier Series by James W. Cooley and John W. Tukey; Math, Comp. vol. 19, No. 90 (1965); pp. 297-301.
What is the Fast Fourier Transform?; William T. Cochran et al.; IEEE Transactions on Audio and Electroacoustics, vol. AU-15, No. 2, Jun. 1967; pp. 45-55.
Short Notes, On the Fast Fourier Transform on Finite Abelian Groups; Thomas W. Cairns; IEEE Transactions on Computers, May 1971, pp. 569-571.
On the Twiddling Factors; C.K. Yuen, IEEE Transactions on Computers, May 1973; pp. 544-545.
Properties of the Multidimensional Generalized Discrete Fourier Transform; Paolo Corsini and Graziano Frosini; IEEE Transactions on Computers, vol. c-28, No. 11, Nov. 1979; pp. 819-830.
Correspondence; A New Technique for Twiddle-Factor Elimination in Multidimensional FFT's; R. Bernardini et al.; IEEE Transactions on Signal Processing, vol. 42, No. 9, Aug. 1994; pp. 2176-2178.
The Structure of Vector Radix Fast Fourier Transforms; Hong Ren Wu and Frank John Paoloni; IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, No. 9, Sep. 1989; pp. 1415-1424.
Fast Hardware Fourier Transformation Through Counting; Shalhav Zohar; IEEE Transactions on Computers, vol., C-22, No. 5, May 1973; pp. 433-441.
A Pipeline Processor for Mixed-Size FFT's; Soheil I. Sayegh; IEEE Transactions on Signal Processing, vol. 40, No. 8, Aug. 1992; pp. 1892-1900.
A Bus-Oriented Multiprocessor Fast Fourier Transform; Douglas L. Jones and Henrik V. Sorensen, IEEE Transactions on Signal Processing, vol. 39, No. 11, Nov. 1991; pp. 2547-2551.
Access and Alignment of Data in an Array Processor; Duncan H. Lawrie; IEEE Truncations on Computers, vol. c-24, No. 12, Dec. 1975; pp. 1145-1155.
Fixed-Pipeline Two-Dimensional Hadamard Transform Algorithms; Chih-Peng Fan and Jar-Ferr Yang; IEEE Transactions on Signal Processing, vol. 45, No. 6, Jun. 1997; pp. 1669-1674.
Organization of Large Scale Fourier Processors; Marshall C. Pease; Journal of the Association for Computing Machinery, vol. 16, No. 3, Jul. 1969, pp. 474-482.
A Fast Fourier Transform for High-Speed Signal Processing; Michael H. Corinthios; IEEE Transactions on Computers, vol. c-20, No. 8, Aug. 1971; pp. 843-846.
Very Fast Fourier Transform Algorithms Hardware for Implementation; Alvin M. Depain; IEEE Transactions on Computers, vol. c-28, No. 5, May 1979; pp. 333-341.
A Parallel Radix-4 Fast Fourier Transform Computer; Michael J. Corinthios et al.; IEEE Transactions on Computers, vol. c-24, No. 1, Jan.; pp. 80-92.
On Generating Multipliers for a Cellular Fast Fourier Transform Processor; W.R. Cyre and G.J. Lipovski; IEEE Transactions on Computers, Jan. 1972; pp. 83-87.
A pipeline Fast Fourier Transform; Herbert L. Groginsky and George A. Works; IEEE Transactions on Computers, vol. c-19, No. 11, Nov. 1970; pp. 1015-1019.
Fourier Transform Computers Using CORDIC Iterations; Alvin M. Despain, IEEE Transactions on Computers, vol, c-23, No. 10, Oct. 1974; pp. 993-1001.
Constant Geometry Fast Fourier Transforms on Array Processors, George Miel; IEEE Transactions on Computers, vol. 42, No. 3, Mar. 1993; pp. 371-375.
Correspondence; Modular Architecture for High Performance Implementation of the FFT Algorithm, K. Sapiecha and R. Jarocki, IEEE Transactions on Computers, vol. 39, No. 12, Dec. 1990; pp. 1464-1468.
Pipeline and Parallel-Pipeline FFT Processors for VLSI Implementations; Erling H. Wold and Alvin M. Despain; IEEE Transactions on Computers, vol. c-33, No. 5, May 1984; pp. 414-425.
Fault-Tolerant FFT Networks; Jing-Yang Jou and Jacob A. Abraham; IEEE Transactions on Computers, vol. 37, No. 5, May 1988; pp. 548-561.
Parallelism in Fast Fourier Transform Hardware; Ben Gold and Theodore Bially; Copyright .COPYRGT. 1973 by the Institute of Electrical and Electronics Engineers, Inc., Reprinted from IEEE Trans. Audio Electroacoustics, AU-21(1), 5-16 (1973); pp. 357-368.
Some New Realizations of Dedicated Hardware Digital Signal Processors; Abraham Peled and Bede Liu; pp. 171-175; Copyright .COPYRGT. 1974 by the Institute of Electrical and Electronics Engineers, Inc., Reprinted from Proc. 1974 IEEE EASCON, Institute of Electrical and Electronics Engineers, Inc., 1974, pp. 464-468.
Fast Fourier Transform Hardware Implementations--A Survey; Glenn D. Bergland; IEEE Transactions on Audio and Electroacoustics, vol. Au-17, No. 2, Jun. 1969; pp. 109-119.
Architectures for Multiplierless Fast Fourier Transform Hardware Implementation in VLSI; Wirendre a. Perera; IEEE Transactions on Acoustics, Speech, and Signal Procesing, vol. ASSP-35, No. 12, Dec. 1987; pp. 1750-1760.
A New Hardware Realization of High-Speed Fast Fourier Transformers; Bede Liu and Abraham Peled; IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-23, No. 6, Dec. 1975; pp. 543-579.
An Architecture for a Video Rate Two-Dimensional Fast Fourier Transform Processor;; G.F. Taylor, R.H. Steinvorth and J.F. McDonald; IEEE Transactions on Computers, vol. 37, No. 9, Sep. 1988; pp. 1145-1148.
Parallel Processing with the Perfact Shuffle, Harold S. Stone; IEEE Transactions on Computers, vol. c-20, No. 2, Feb. 1971; pp. 153-161.
The Design of a Class of Fast Fourier Transform Computers, Michael J. Corinthios; IEEE Transactions on Computers, vol. c-20, No. 6, Jun. 1971; pp. 617-622.
Continuous Shading of Curved Surfaces, Henry Gouraud; IEEE Transactions on Computers, vol. c-20, No. 6, Jun. 1971; p. 623.
A VLSI Network for Variable Size FFT's; G. Bongiovanni; IEEE Transactions on Computers, vol. c-32, No. 8, Aug. 1983; pp. 756-760.
Notes on Shuffle/Exchange-Type Switching Networks; D. Stott Parker, Jr.; IEEE Transactions on Computers, vol. c-29, No. 3, Mar. 1980; pp. 213-222.
Fourier Transf
Auslander Lewis
Johnson Jeremy R.
Johnson Robert W.
LandOfFree
Dimensionless fast fourier transform method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dimensionless fast fourier transform method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dimensionless fast fourier transform method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-873803