Patent ID: 6073154
Filing Date: 2000-06-06
Classification: G06F

Abstract:
A method for computing multidimensional discrete Fourier transforms (DFTs) using a field programmable gate array (FPGA) comprising the steps of:a. ordering a set of polynomial data in a two dimensional matrix;b. 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, where In indicates the natural logarithm),j=.sqroot.-1, n.sub.2 =the column index number in the matrix, andN=the transform length) to produce a premultiplication product;c. performing a polynomial transform (PT) on the premultiplication product to produce a polynomial transform result;d. performing N reduced DFTs of N terms on the polynomial transform result to produce a permuted output; ande. reordering the permuted output to a natural order.