Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Patent
1998-06-26
2000-06-06
Mai, Tan V.
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
G06F 1714
Patent
active
060731540
ABSTRACT:
An FPGA configured for computation of an N.times.N discrete Fourier transform (DFT) using polynomial transforms defined in modified rings of transforms, comprising a first buffer for ordering a set of polynomial data in a two dimensional matrix, a multiplier for multiplying each element of the two dimensional matrix by .omega..sup.-n.sbsp.2 (where .omega.=e.sup.-j.pi./N, e is a constant (ln(e)=1),
j=.sqroot.-1, n.sub.2 =the column index number in the matrix, and N=the transform length) to produce a premultiplication product, a polynomial transform circuit for performing a polynomial transform (PT) modulo (z.sup.N +1), size N, root z.sup.2 on the premultiplication product to produce a polynomial transform result, where z represents the unit delay operator, a reduced DFT calculator for performing N reduced DFTs of N terms on the polynomial transform result to produce a permuted output, and an address generator for reordering the permuted output to a natural order.
REFERENCES:
patent: 3952186 (1976-04-01), Speiser et al.
patent: 4060850 (1977-11-01), Speiser
patent: 4328555 (1982-05-01), Nussbaumer
Quandalle, "Multidimensional Discrete Fourier Transform Calculated Through Polynomial Transform", IBM Technical Disclosure Bulletin, vol. 21, No. 7, Dec. 1978, pp. 2859-2861.
James W. Cooley and John W. Tukey, in "An Algorithm for the Machine Calculation of Complex Fourier Series", Math of Comput., vol. 19, pp. 297-301, Apr. 1965.
H. J. Nussbaumer and P. Quandelle, in "Computation of Convolutions and Discrete Fourier Transforms by Polynomial Transforms", J. Res. Develop., vol. 22, No. 2, pp. 134-144, Mar. 1978.
Kai Hwang, in Computer Arithmetic Principles Architecture and Design, John Wiley & Sons, New York, 1979, Chapter 5, pp. 152-155.
Mai Tan V.
Xilinx , Inc.
Young Edel M.
LandOfFree
Computing multidimensional DFTs in FPGA does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computing multidimensional DFTs in FPGA, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing multidimensional DFTs in FPGA will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2223412