<< Chapter < Page Chapter >> Page >

As bases, we choose b = ( 1 , x ) , c = ( 1 ) , d = ( 1 ) . Δ ( 1 ) = ( 1 , 1 ) with the same coordinate vector in c d = ( 1 , 1 ) . Further, because of x 1 mod ( x - 1 ) and x - 1 mod ( x + 1 ) , Δ ( x ) = ( x , x ) ( 1 , - 1 ) with the same coordinate vector. Thus, Δ in matrix form is the so-called butterfly matrix, which is a DFT of size 2: DFT 2 = [ 1 1 1 -1 ] .

Polynomial transforms

Assume P ( s ) C [ s ] has pairwise distinct zeros α = ( α 0 , , α N - 1 ) . Then the CRT can be used to completelydecompose C [ s ] / P ( s ) into its spectrum :

Δ : C [ s ] / P ( s ) C [ s ] / ( s - α 0 ) C [ s ] / ( s - α N - 1 ) , X ( s ) ( X ( s ) mod ( s - α 0 ) , , X ( s ) mod ( s - α N - 1 ) ) = ( s ( α 0 ) , , s ( α N - 1 ) ) .

If we choose a basis b = ( P 0 ( s ) , , P N - 1 ( s ) ) in C [ s ] / P ( s ) and bases b i = ( 1 ) in each C [ s ] / ( s - α i ) , then Δ , as a linear mapping, is represented by a matrix. The matrix is obtained by mappingevery basis element P n , 0 n < N , and collecting the results in the columns of the matrix. The result is

P b , α = [ P n ( α k ) ] 0 k , n < N

and is called the polynomial transform for A = C [ s ] / P ( s ) with basis b .

If, in general, we choose b i = ( β i ) as spectral basis, then the matrix corresponding to the decomposition [link] is the scaled polynomial transform

diag 0 k < N ( 1 / β n ) P b , α ,

where diag 0 n < N ( γ n ) denotes a diagonal matrix with diagonal entries γ n .

We jointly refer to polynomial transforms, scaled or not, as Fourier transforms.

Dft as a polynomial transform

We show that the DFT N is a polynomial transform for A = C [ s ] / ( s N - 1 ) with basis b = ( 1 , s , , s N - 1 ) . Namely,

s N - 1 = 0 k < N ( x - W N k ) ,

which means that Δ takes the form

Δ : C [ s ] / ( s N - 1 ) C [ s ] / ( s - W N 0 ) C [ s ] / ( s - W N N - 1 ) , X ( s ) ( X ( s ) mod ( s - W N 0 ) , , X ( s ) mod ( s - W N N - 1 ) ) = ( X ( W N 0 ) , , X ( W N N - 1 ) ) .

The associated polynomial transform hence becomes

P b , α = [ W N k n ] 0 k , n < N = DFT N .

This interpretation of the DFT has been known at least since [link] , [link] and clarifies the connection between the evaluation points in [link] and the circular convolution in [link] .

In [link] , DFTs of types 1–4 are defined, with type 1 being the standard DFT. In the algebraic framework, type 3 is obtainedby choosing A = C [ s ] / ( s N + 1 ) as algebra with the same basis as before:

P b , α = [ W N ( k + 1 / 2 ) n ] 0 k , n < N = DFT -3 N ,

The DFTs of type 2 and 4 are scaled polynomial transforms [link] .

Algebraic derivation of the cooley-tukey fft

Knowing the polynomial algebra underlying the DFT enables us to derive the Cooley-Tukey FFT algebraically . This means that instead of manipulating the DFT definition, we manipulate the polynomial algebra C [ s ] / ( s N - 1 ) . The basic idea is intuitive. We showed that the DFT is the matrix representation of the complete decomposition [link] . The Cooley-Tukey FFT is now derived by performing this decomposition in steps as shown in [link] . Each step yields a sparse matrix; hence, the DFT N is factorized into a product of sparse matrices, which will be the matrix representation ofthe Cooley-Tukey FFT.

Basic idea behind the algebraic derivation of Cooley-Tukey type algorithms

This stepwise decomposition can be formulated generically for polynomial transforms [link] , [link] . Here, we consider only the DFT.

We first introduce the matrix notation we will use and in particular the Kronecker product formalism that became mainstream for FFTsin [link] , [link] .

Then we first derive the radix-2 FFT using a factorization of s N - 1 . Subsequently, we obtain the general-radix FFT using a decomposition of s N - 1 .

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