Page 385 - Matrix Analysis & Applied Linear Algebra

5.8 Discrete Fourier Transform 381

r
(a) If n =2 , and if P n is the even–odd permutation matrix
described in (5.8.15), explain why
R n =(I 2 r−1 ⊗ P 2 1)(I 2 r−2 ⊗ P 2 2) ··· (I 2 1 ⊗ P 2 r−1)(I 2 0 ⊗ P 2 r)
is the permutation matrix associated with the bit reversing (or
perfect shuffle) permutation described in (5.8.19) and Table
5.8.1. Hint: Work it out for n =8 by showing
   
x 0 x 0
 x 1   x 4 
   
 x 2   x 2 
   
 x 3   x 6 
R 8   =   ,
 x 4   x 1 
   
 x 5   x 5 
   
x 6 x 3
x 7 x 7
and you will see why it holds in general.
r
(b) Suppose n =2 , and set

I n/2 D n/2
B n = .
I n/2 −D n/2
According to (5.8.15), the Fourier matrix can be written as
F n = B n (I 2 ⊗ F n/2 )P n .
Expand on this idea by proving that F n can be factored as
F n = L n R n
in which
L n =(I 2 0 ⊗ B 2 r)(I 2 1 ⊗ B 2 r−1) ··· (I 2 r−2 ⊗ B 2 2)(I 2 r−1 ⊗ B 2 1),
and where R n is the bit reversing permutation
R n =(I 2 r−1 ⊗ P 2 1)(I 2 r−2 ⊗ P 2 2) ··· (I 2 1 ⊗ P 2 r−1)(I 2 0 ⊗ P 2 r).
Notice that this says F n x = L n R n x, so the discrete Fourier
transform of x is obtained by first performing the bit revers-
ing permutation to x followed by r applications of the terms
(I r−k ⊗ B k) from L n . This in fact is the FFT algorithm in
2
2
factored form. Hint: Define two sequences by the rules
L k =(I r−k ⊗ B k) L k−1 and R k = R k−1 (I r−k ⊗ P k) ,
2
2
2
2
2
2
2
2
where
L 1 =1, R 1 = I n , B 2 = F 2 , P 2 = I 2 ,
and use induction on k to prove that
for k =1, 2,...,r.
2
I r−k ⊗ F k = L kR k
2
2
2