<< Chapter < Page Chapter >> Page >

The prime factor algorithm

If the DFT is calculated directly using [link] , the algorithm is called a prime factor algorithm [link] , [link] and was discussed in Winograd’s Short DFT Algorithms and Multidimensional Index Mapping: In-Place Calculation of the DFT and Scrambling . When the short DFT's are calculated by the very efficient algorithms of Winograddiscussed in Factoring the Signal Processing Operators , the PFA becomes a very powerful method that is as fast or faster than the best Cooley-Tukey FFT's [link] , [link] .

A flow graph is not as helpful with the PFA as it was with the Cooley-Tukey FFT, however, the following representation in [link] which combines Figures Multidimensional Index Mapping: Figure 1 and Winograd’s Short DFT Algorithms: Figure 2 gives a good picture of the algorithm with the example of Multidimensional Index Mapping: Equation 25

This is a three-dimensional figure of five flat rectangles stacked together and rotated horizontally, and three flat shapes stacked together and rotated vertically with flat side facing front, and numerous lines passing through the shapes from left to right. The lines from top to bottom are spread out sporadically in no discernible pattern, and are labeled from top to bottom on the left side of the figure, 10, 5, 0, 8, 3, 11, 6, 14, 9, 2, 12. On the right side of the figure, they are labeled from top to bottom, 5, 10, 11, 0, 1, 2, 6, 7, 8, 12, 13, 14, 3, 4, 9. Each shape, both the vertical and horizontally oriented shapes, are divided into three sections with lines perpendicular to the numbered lines across the page. These sections are labeled from left to right, +, x, +, on each shape. This is a three-dimensional figure of five flat rectangles stacked together and rotated horizontally, and three flat shapes stacked together and rotated vertically with flat side facing front, and numerous lines passing through the shapes from left to right. The lines from top to bottom are spread out sporadically in no discernible pattern, and are labeled from top to bottom on the left side of the figure, 10, 5, 0, 8, 3, 11, 6, 14, 9, 2, 12. On the right side of the figure, they are labeled from top to bottom, 5, 10, 11, 0, 1, 2, 6, 7, 8, 12, 13, 14, 3, 4, 9. Each shape, both the vertical and horizontally oriented shapes, are divided into three sections with lines perpendicular to the numbered lines across the page. These sections are labeled from left to right, +, x, +, on each shape.
A Prime Factor FFT for N = 15

If N is factored into three factors, the DFT of [link] would have three nested summations and would be a three-dimensional DFT.This principle extends to any number of factors; however, recall that the Type-1 map requires that all the factors be relativelyprime. A very simple three-loop indexing scheme has been developed [link] which gives a compact, efficient PFA program for any number of factors. The basic program structure is illustrated in [link] with the short DFT's being omitted for clarity. Complete programs are given in [link] and in the appendices.

C---------------PFA INDEXING LOOPS-------------- DO 10 K = 1, MN1 = NI(K) N2 = N/N1I(1) = 1 DO 20 J = 1, N2DO 30 L=2, N1 I(L) = I(L-1) + N2IF (I(L .GT.N) I(L) = I(L) - N 30 CONTINUEGOTO (20,102,103,104,105), N1 I(1) = I(1) + N120 CONTINUE 10 CONTINUERETURN C----------------MODULE FOR N=2-----------------102 R1 = X(I(1)) X(I(1)) = R1 + X(I(2))X(I(2)) = R1 - X(I(2)) R1 = Y(I(1))Y(I(1)) = R1 + Y(I(2)) Y(I(2)) = R1 - Y(I(2))GOTO 20 C----------------OTHER MODULES------------------103 Length-3 DFT 104 Length-4 DFT105 Length-5 DFT etc.
Part of a FORTRAN PFA Program

As in the Cooley-Tukey program, the DO 10 loop steps through the M stages (factors of N) and the DO 20 loop calculates the N/N1 length-N1DFT's. The input index map of [link] is implemented in the DO 30 loop and the statement just before label 20. In the PFA, each stageor factor requires a separately programmed module or butterfly. This lengthens the PFA program but an efficient Cooley-Tukey program willalso require three or more butterflies.

Because the PFA is calculated in-place using the input index map, the output is scrambled. There are five approaches to dealingwith this scrambled output. First, there are some applications where the output does not have to be unscrambled as in the case ofhigh-speed convolution. Second, an unscrambler can be added after the PFA to give the output in correct order just as thebit-reversed-counter is used for the Cooley-Tukey FFT. A simple unscrambler is given in [link] , [link] but it is not in place. The third method does the unscrambling in the modules while they arebeing calculated. This is probably the fastest method but the program must be written for a specific length [link] , [link] . A fourth method is similar and achieves the unscrambling by choosingthe multiplier constants in the modules properly [link] . The fifth method uses a separate indexingmethod for the input and output of each module [link] , [link] .

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