Patent ID: 6792441
Filing Date: 2004-09-14
Classification: G06F

Abstract:
A Fourier transform processor responsive to N input data points to compute N data output points, said Fourier transform processor comprising:a plurality of r parallel processing elements, each of said plurality of r parallel processing elements having N/r input data points and N/r output data points, said N/r input data points of said plurality of r parallel processors being coupled to respective ones of said N input data points, each of said plurality of r parallel processing elements being independent of each other and having at least two stages of butterfly computing elements; and a combination phase computing element having N output points forming said N data output data points of said Fourier transform processor, said combination phase computing element having N input data points coupled to respective ones of said N/r output data points from said plurality of r processing elements, said combination phase computing element including a single stage of butterfly computing elements, wherein each of said r parallel processing elements includes a butterfly processing element for use in a decimation in frequency radix-r butterfly responsive to a plurality of input data points, said radix-r butterfly providing a plurality of output a points, said butterfly processing element comprising: a plurality of multipliers, each of said multipliers having a respective first and second input terminals and a respective output terminal; and an adder having a plurality of input terminals and an output terminal, each of said plurality of input terminals of said adder being coupled to a respective on of said output terminals of said plurality of multipliers; said plurality of first input terminals of said plurality of multiple each being respectively coupled to one of said plurality of input data points, said output terminal of said adder being coupled to one of said plurality of output data points said plurality of second input terminals of said plurality of multipliers being coupled to a set of coefficients derived from the product of an adder matrix Tr and a twiddle factor matrix wNr wherein said coefficients derived from the product of said adder matrix Tr and said twiddle factor matrix wNr, are substantially given by Tr=[w0w0w0-w0w0wN/rw2&it;N/r-w(r-1)&it;N/rw0w2&it;N/rw4&it;N/r-w2&it;(r-1)&it;N/r-----w0w(r-1)&it;N/r--w(r-1)2&it;N/r]=[T(l,m)],(5A)where T(l,m)=w((l&it;â€ƒ&it;m&it;Nr))&it;N,(6A)â€ƒand defining w(r, k, i) the set of the twiddle factor matrices wNr as: W(r,k,i)=[w(0,k,i)0-00w(1,k,i)-0----00-w((r-1),k,i)]=[w(l,m)(k,i)],(8A)â€ƒin which, w(l,m)(k,i)=w((N~&af;(kri)&it;lri))&it;N&it;â€ƒ&it;for&it;â€ƒ&it;1=m,and&it;â€ƒ&it;0&it;â€ƒ&it;elsewhere,(9A)â€ƒwherein, Br DIF=w(r,k,i)Ã—Tr=[Br DIF(l,m)(k,i)]â€ƒâ€ƒ(10A), with Br DIF(l,m)(k,i)=w((lmN/r+Ã‘(k/ri)/ri))Nâ€ƒâ€ƒ(11A), â€ƒ1=m=0, . . . , râˆ’1, i=0,1 . . . , nâˆ’1, k=0,1 . . . ,1 (N/r)âˆ’1, ((x))N denotes x modulo N and Ã‘ (k/ri) is defined as the integer part of the division of k and ri, whereby the operation of said butterfly processing element for said decimation in frequency radix-r butterfly is: the colon vector X(r,k,i)=Br DIFÃ—x=[X(l)(k,i)]â€ƒâ€ƒ(12A), where the 1th output X(l)(k,i)=&Sum;m=0r-1&it;â€ƒ&it;x(m)&it;w((l&it;â€ƒ&it;mN/r+N~&af;(k/ri)&it;lri))&it;N.(13A)