<< Chapter < Page Chapter >> Page >

Matrix notation

We denote the N × N identity matrix with I N , and diagonal matrices with

diag 0 k < N ( γ k ) = γ 0 γ N - 1 .

The N × N stride permutation matrix is defined for N = K M by the permutation

L M N : i K + j j M + i

for 0 i < K , 0 j < M . This definition shows that L M N transposes a K × M matrix stored in row-major order. Alternatively, we can write

L M N : i iM mod N - 1 , for 0 i < N - 1 , N - 1 N - 1 .

For example ( · means 0),

L 2 6 = 1 · · · · · · · 1 · · · · · · · 1 · · 1 · · · · · · · 1 · · · · · · · 1 .

L N / 2 N is sometimes called the perfect shuffle.

Further, we use matrix operators; namely the direct sum

A B = A B

and the Kronecker or tensor product

A B = [ a k , B ] k , , for A = [ a k , ] .

In particular,

I n A = A A = A A

is block-diagonal.

We may also construct a larger matrix as a matrix of matrices, e.g.,

A B B A .

If an algorithm for a transform is given as a product of sparse matrices built from the constructs above, then an algorithm for the transpose orinverse of the transform can be readily derived using mathematical properties including

( A B ) T = B T A T , ( A B ) - 1 = B - 1 A - 1 , ( A B ) T = A T B T , ( A B ) - 1 = A - 1 B - 1 , ( A B ) T = A T B T , ( A B ) - 1 = A - 1 B - 1 .

Permutation matrices are orthogonal, i.e., P T = P - 1 . The transposition or inversion of diagonal matrices is obvious.

Radix-2 fft

The DFT decomposes A = C [ s ] / ( s N - 1 ) with basis b = ( 1 , s , , s N - 1 ) as shown in [link] . We assume N = 2 M . Then

s 2 M - 1 = ( s M - 1 ) ( s M + 1 )

factors and we can apply the CRT in the following steps:

C [ s ] / ( s N - 1 ) C [ s ] / ( s M - 1 ) C [ s ] / ( s M + 1 )
0 i < M C [ s ] / ( x - W N 2 i ) 0 i < M C [ s ] / ( x - W M 2 i + 1 )
0 i < N C [ s ] / ( x - W N i ) .

As bases in the smaller algebras C [ s ] / ( s M - 1 ) and C [ s ] / ( s M + 1 ) , we choose c = d = ( 1 , s , , s M - 1 ) . The derivation of an algorithm for DFT N based on [link] - [link] is now completely mechanical by reading off the matrix for each of the threedecomposition steps. The product of these matrices is equal to the DFT N .

First, we derive the base change matrix B corresponding to [link] . To do so, we have to express the base elements s n b in the basis c d ; the coordinate vectors are the columns of B . For 0 n < M , s n is actually contained in c and d , so the first M columns of B are

B = I M * I M * ,

where the entries * are determined next. For the base elements s M + n , 0 n < M , we have

s M + n s n mod ( s M - 1 ) , s M + n - s n mod ( s M + 1 ) ,

which yields the final result

B = I M - I M I M - I M = DFT 2 I M .

Next, we consider step [link] . C [ s ] / ( s M - 1 ) is decomposed by DFT M and C [ s ] / ( s M + 1 ) by DFT -3 M in [link] .

Finally, the permutation in step [link] is the perfect shuffle L M N , which interleaves the even and odd spectral components (even and odd exponents of W N ).

The final algorithm obtained is

DFT 2 M = L M N ( DFT M DFT -3 M ) ( DFT 2 I M ) .

To obtain a better known form, we use DFT -3 M = DFT M D M , with D M = diag 0 i < M ( W N i ) , which is evident from [link] . It yields

DFT 2 M = L M N ( DFT M DFT M D M ) ( DFT 2 I M ) = L M N ( I 2 DFT M ) ( I M D M ) ( DFT 2 I M ) .

The last expression is the radix-2 decimation-in-frequency Cooley-Tukey FFT. The corresponding decimation-in-time version isobtained by transposition using [link] and the symmetry of the DFT:

DFT 2 M = ( DFT 2 I M ) ( I M D M ) ( I 2 DFT M ) L 2 N .

The entries of the diagonal matrix I M D M are commonly called twiddle factors .

The above method for deriving DFT algorithms is used extensively in [link] .

General-radix fft

To algebraically derive the general-radix FFT, we use the decomposition property of s N - 1 . Namely, if N = K M then

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