<< Chapter < Page Chapter >> Page >
A = k G : 9 | k } = { 4 , 12 }
B = k G : 9 | k } = { 36 }

This yields the two intermediate polynomials,

s 6 + 1 , and s 12 - s 6 + 1

In the notation used above,

X ' X ' ' = I 6 - I 6 I 6 I 6 I 6 - I 6 I 6 X

entailing 24 additions. Continuing this process results in a factorization in steps

In order to see the number of additions this scheme uses for numbers of the form N = P - 1 (which is relevant to prime length FFT algorithms) figure 4 shows the number of additions the reduction process uses when the polynomialX(s) is real.

Figure 4: Number of Additions for Reduction Stage

The polynomial product stage

The iterated convolution algorithm can be used to construct an N point linear convolution algorithm from shorter linear convolution algorithms [link] . Suppose the linear convolution y , of the n point vectors x and h ( h known) is described by

y = E n T D E n x

where E n is an “expansion" matrix the elements of which are ± l 's and 0's and D is an appropriate diagonal matrix. Because the only multiplications in thisexpression are by the elements of D , the number of multiplications required, M ( n ) , is equal to the number of rows of E n . The number of additions is denoted by A ( n ) .

Given a matrix E n 1 and a matrix E n 2 , the iterated algorithm gives a method for combining E n 1 and E n 2 to construct a valid expansion matrix, E n , for N n 1 n 2 . Specifically,

E n 1 , n 2 = ( I M ( n 2 ) E n 1 ) ( E n 2 × I n 1 )

The product n 1 n 2 may be greater than N , for zeros can be (conceptually) appended to x . The operation count associated with E n 1 , n 2 is

A ( n 1 , n 2 ) = n ! A ( n 2 ) + A ( n 1 ) M n 2 )
M ( n 1 , n 2 ) = M ( n 1 ) M ( n 2 )

Although they are both valid expansion matrices, E n 1 , n 2 E n 2 , n 1 and A n 1 , n 2 A n 2 , n 1 Because M n 1 , n 2 M n 2 , n 1 it is desirable to chose an ordering of factors to minimize the additions incurred by the expansion matrix.The following [link] , [link] follows from above.

Multiple factors

Note that a valid expansion matrix, E N , can be constructed from E n 1 , n 2 and E n 3 , for N n 1 n 2 n 3 . In general, any number of factors can be used to create larger expansion matrices.The operation count associated with E n 1 , n 2 , n 3 is

A ( n 1 , n 2 , n 3 ) = n 1 n 2 A ( n 3 ) + n 1 A ( n 2 ) M ( n 3 ) + A ( n 1 ) M ( n 2 ) M ( n 3 )
M ( n 1 , n 2 , n 3 ) = M ( n 1 ) M ( n 2 ) M ( n 3 )

These equations generalize in the predicted way when more factors are considered. Because the ordering of the factors is relevant in the equation for A ( . ) but not for M ( . ) , it is again desirable to order the factors to minimize the number of additions. By exploiting the following property of the expressionsfor A ( . ) and M ( . ) , the optimal ordering can be found [link] .

reservation of Optimal Ordering. Suppose A ( n 1 , n 2 , n 3 ) min { A ( n k 1 , n k 2 , n k 3 ) : k 1 , k 2 , k 3 { 1 , 2 , 3 } and distinct}, then

  1. A ( n 1 , n 2 ) A ( n 2 , n 1 )
  2. A ( n 2 , n 3 ) A ( n 3 , n 2 )
  3. A ( n 1 , n 3 ) A ( n 3 , n 1 )

The generalization of this property to more than two factors reveals that an optimal ordering of { n 1 , , n L - i } is preserved in an optimal ordering of { n 1 , n L } . Therefore, if ( n 1 , n L ) is an optimal ordering of { n 1 , n L } , then ( n k , n k + 1 ) is an optimal ordering of { n k , n k + 1 } and consequently

A ( n k ) M ( n k ) - n k A ( n k + 1 ) M ( n k + 1 ) - n k + 1

for all k = 1 , 2 , , L - 1 .

This immediately suggests that an optimal ordering of { n 1 , n L } is one for which

A ( n 1 ) M ( n 1 ) - n 1 A ( n L ) M ( n L ) - n L

is nondecreasing. Hence, ordering the factors, { n 1 , n L } , to minimize the number of additions incurred by E n 1 , , n L simply involves computing the appropriate ratios.

Discussion and conclusion

We have designed prime length FFTs up to length 53 that are as good as the previous designs that only went up to 19. Table 1 gives theoperation counts for the new and previously designed modules, assuming complex inputs.

It is interesting to note that the operation counts depend on the factorability of P - 1 . The primes 11, 23, and 47 are all of the form 1 + 2 P 1 making the design of efficient FFTs for these lengths more difficult.

Further deviations from the original Winograd approach than we have made could prove useful for longer lengths. We investigated, for example,the use of twiddle factors at appropriate points in the decomposition stage; these can sometimes be used to divide the cyclic convolutioninto smaller convolutions. Their use means, however, that the 'center* multiplications would no longer be by purely real or imaginary numbers.

Operation counts for prime length DFTs
N Mult Adds
7 16 72
11 40 168
13 40 188
17 82 274
19 88 360
23 174 672
29 190 766
31 160 984
37 220 920
41 282 1140
43 304 1416
47 640 2088
53 556 2038

The approach in writing a program that writes another program is a valuable one for several reasons. Programming the design process for the design ofprime length FFTs has the advantages of being practical, error-free, and flexible. The flexibility is important because it allows for modificationand experimentation with different algorithmic ideas. Above all, it has allowed longer DFTs to be reliably designed.

More details on the generation of programs for prime length FFTs can be found in the 1993 Technical Report.

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