<< Chapter < Page Chapter >> Page >
Three squares with a 4x4 array of dots on each. The square in the back is labeled x(n1,n2) and has lines extending from the top four dots. The next square is labeled x(k1,n2)xTF and has lines extending from the left column of dots extending to the next square which is labeled X(k1,k2)
Uncoupling of the Row and Column Calculations (Rectangles are Data Arrays)

The left 4-by-4 array is the mapped input data, the center array has the rows transformed, and the right array is the DFTarray. The row DFTs and the column DFTs are independent of each other. The twiddle factors (TF) which are the center W in [link] , are the multiplications which take place on the center array of [link] .

This uncoupling feature reduces the amount of arithmetic required and allows the results of each row DFT to be writtenback over the input data locations, since that input row will not be needed again. This is called “in-place" calculationand it results in a large memory requirement savings.

An example of the type-two map used when the factors of N are relatively prime is given for N = 15 as

n = 5 n 1 + n 2
k = k 1 + 3 k 2

The residue reduction is again not explicitly needed. Although the factors 3 and 5 are relatively prime, use of the type-two mapsets only one of the terms in [link] to zero. The DFT in [link] becomes

X = n 2 = 0 4 n 1 = 0 2 x W 3 n 1 k 1 W 15 n 2 k 1 W 5 n 2 k 2

which has the same form as [link] , including the existence of the twiddle factors (TF). Here the inner sum is five length-3DFTs, one for each value of k 1 . This is illustrated in [link] where the rectangles are the 5 by 3 data arrays and the system is called a ``mixed radix" FFT.

Three rectangles with a 3x5 array of dots. The first rectangle is labeled x(n_1,n_2) with lines extending from the first row of dots to the next rectangle. This rectangle is labeled x(k_1,n_2). Lines extend from the left-most column and end at the third rectangle labeled X(k_1,k_2).
Uncoupling of the Row and Column Calculations (Rectangles are Data Arrays)

An alternate illustration is shown in [link] where the rectangles are the short length 3 and 5 DFTs.

This image contains five rectangles that are laying horizontal and are stacked vertically. Each of the rectangles has three lines extending through themselves and then intersecting one of three vertical rectangles.
Uncoupling of the Row and Column Calculations (Rectangles are Short DFTs)

The type-one map is illustrated next on the same length-15 example. This time the situation of [link] with the “and" condition is used in [link] using an index map of

n = 5 n 1 + 3 n 2

and

k = 10 k 1 + 6 k 2

The residue reduction is now necessary. Since the factors of N are relatively prime and the type-one map is being used, both terms in [link] are zero, and [link] becomes

X ^ = n 2 = 0 4 n 1 = 0 2 x ^ W 3 n 1 k 1 W 5 n 2 k 2

which is similar to [link] , except that now the type-one map gives a pure two-dimensional DFT calculation with no TFs, and thesums can be done in either order. Figures [link] and [link] also describe this case but now there are no Twiddle Factor multiplications in the center and the resulting system is called a ``prime factor algorithm" (PFA).

The purpose of index mapping is to improve the arithmetic efficiency. For example a direct calculation of a length-16 DFTrequires 16^2 or 256 real multiplications (recall, one complex multiplication requires 4 real multiplications and 2 real additions) and an uncoupled version requires 144. A direct calculation of a length-15 DFT requires225 multiplications but with a type-two map only 135 and with a type-one map, 120. Recall one complex multiplication requiresfour real multiplications and two real additions.

Algorithms of practical interest use short DFT's that require fewer than N 2 multiplications. For example, length-4 DFTs require no multiplications and, therefore, for the length-16DFT, only the TFs must be calculated. That calculation uses 16 multiplications, many fewer than the 256 or 144 required forthe direct or uncoupled calculation.

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