<< Chapter < Page Chapter >> Page >

The h ( n ) terms are fixed for a digital filter, or they represent the W terms from Multidimensional Index Mapping: Equation 1 if the convolution is being used to calculate a DFT. Because of this, d = B H in [link] can be precalculated and only the A and C operators represent the mathematics done at execution of the algorithm. In order toexploit this feature, it was shown [link] , [link] that the properties of [link] allow the exchange of the more complicated operator C with the simpler operator B . Specifically this is given by

Y = C [ A X o B H ]
Y ' = B T [ A X o C T H ' ]

where H ' has the same elements as H , but in a permuted order, and likewise Y ' and Y . This very important property allows precomputing the more complicated C T H ' in [link] rather than B H as in [link] .

Because B H or C T H ' can be precomputed, the bilinear form of [link] and [link] can be written as a linear form. If an M x M diagonal matrix D is formed from d = C T H , or in the case of [link] , d = B H , assuming a commutative property for o , [link] becomes

Y ' = B T D A X

and [link] becomes

Y = C D A X

In most cases there is no reason not to use the same reduction operations on X and H , therefore, B can be the same as A and [link] then becomes

Y ' = A T D A X

In order to illustrate how the residue reduction is carried out and how the A matrix is obtained, the length-5 DFT algorithmstarted in The DFT as Convolution or Filtering: Matrix 1 will be continued. The DFT is first converted to a length-4 cyclic convolution by theindex permutation from The DFT as Convolution or Filtering: Equation 3 to give the cyclic convolution in The DFT as Convolution or Filtering . To avoid confusion from the permuted order of the data x ( n ) in The DFT as Convolution or Filtering , the cyclic convolution will first be developed without thepermutation, using the polynomial U ( s )

U ( s ) = x ( 1 ) + x ( 3 ) s + x ( 4 ) s 2 + x ( 2 ) s 3
U ( s ) = u ( 0 ) + u ( 1 ) s + u ( 2 ) s 2 + u ( 3 ) s 3

and then the results will be converted back to the permuted x ( n ) . The length-4 cyclic convolution in terms of polynomials is

Y ( s ) = U ( s ) H ( s ) mod ( s 4 - 1 )

and the modulus factors into three cyclotomic polynomials

s 4 - 1 = ( s 2 - 1 ) ( s 2 + 1 )
= ( s - 1 ) ( s + 1 ) ( s 2 + 1 )
= P 1 P 2 P 3

Both U ( s ) and H ( s ) are reduced modulo these three polynomials. The reduction modulo P 1 and P 2 is done in two stages. First it is done modulo ( s 2 - 1 ) , then that residue is further reduced modulo ( s - 1 ) and ( s + 1 ) .

U ( s ) = u 0 + u 1 s + u 2 s 2 + u 3 s 3
U ' ( s ) = ( ( U ( s ) ) ) ( s 2 - 1 ) = ( u 0 + u 2 ) + ( u 1 + u 3 ) s
U 1 ( s ) = ( ( U ' ( s ) ) ) P 1 = ( u 0 + u 1 + u 2 + u 3 )
U 2 ( s ) = ( ( U ' ( s ) ) ) P 2 = ( u 0 - u 1 + u 2 - u 3 )
U 3 ( s ) = ( ( U ( s ) ) ) P 3 = ( u 0 - u 2 ) + ( u 1 - u 3 ) s

The reduction in [link] of the data polynomial [link] can be denoted by a matrix operation on a vector which has the data asentries.

1 0 1 0 0 1 0 1 u 0 u 1 u 2 u 3 = u 0 + u 2 u 1 + u 3

and the reduction in [link] is

1 0 - 1 0 0 1 0 - 1 u 0 u 1 u 2 u 3 = u 0 - u 2 u 1 - u 3

Combining [link] and [link] gives one operator

1 0 1 0 0 1 0 1 1 0 - 1 0 0 1 0 - 1 u 0 + u 2 u 1 + u 3 u 0 - u 2 u 1 - u 3 = u 0 + u 2 u 1 + u 3 u 0 - u 2 u 1 - u 3 = w 0 w 1 v 0 v 1

Further reduction of v 0 + v 1 s is not possible because P 3 = s 2 + 1 cannot be factored over the rationals. However s 2 - 1 can be factored into P 1 P 2 = ( s - 1 ) ( s + 1 ) and, therefore, w 0 + w 1 s can be further reduced as was done in [link] and [link] by

1 1 w 0 w 1 = w 0 + w 1 = u 0 + u 2 + u 1 + u 3
1 - 1 w 0 w 1 = w 0 - w 1 = u 0 + u 2 - u 1 - u 3

Combining [link] , [link] and [link] gives

1 1 0 0 1 - 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 - 1 0 0 1 0 - 1 u 0 u 1 u 2 u 3 = r 0 r 1 v 0 v 1

The same reduction is done to H ( s ) and then the convolution of [link] is done by multiplying each residue polynomial of X ( s ) and H ( s ) modulo each corresponding cyclotomic factor of P ( s ) and finally a recombination using the polynomial Chinese RemainderTheorem (CRT) as in Polynomial Description of Signals: Equation 9 and Polynomial Description of Signals: Equation 13 .

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Fast fourier transforms. OpenStax CNX. Nov 18, 2012 Download for free at http://cnx.org/content/col10550/1.22
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?

Ask