EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-10Calculating DFT ( )∑∑−=−−=−==10/210/2)()()(NnnkNjNnNknjenxenxkXππ Denote NjNeW/2π−= , then ∑−==10)()(NnnkNWnxkX Each X(k) requires N complex multiplications and N complex additions. Each complex multiplication needs 4 real multiplications and 2 real addition because (a+jb)*(c+jd) = (ac-bd)+j(bc+ad) There are N different X(k), so we need a total of 4N2 real multiplications 4N2 real additions However, by taking advantages of some properties of mNW , we can significantly speed out the calculations ⇒ Fast Fourier Transform Interesting Properties of mNW : (1) 1,1)(200/20=====−−ππjNNNjNeWeeW (2) mNmNNWW =+ (periodic) (3) Assume N is a multiple of 4 1/)2//(22/−===−−ππjNNjNNeeW jeeWjNNjNN−===−− 2//)4//(24/ππ jeeWjNNjNN===−− 2/3/)4/3/(24/3ππ (4) Assume N is even krNkrNjkrNjkrNWeeW2)2//(22/22)()( ===−−ππ Real Imaginary 0NW 1NW N0360EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-11Example 10-3: Two-Point DFT x(0), x(1): 1,0)()(102==∑=kWnxkXnnk )1()0()()()0(101002xxnxWnxXnnn+===∑∑== )1()0( )1)(1()0( )1()0( )()()1(12021021012xxxxWxWxWnxWnxXnnnn−=−+=+===∑∑== Example 10-4: Four-point DFT of x(0), x(1), x(2), x(3) ,3,2,1,0)()(304==∑=kWnxkXnnk )3()2()1()0()()()0(303004xxxxnxWnxXnnn+++===∑∑== )3()2()1()0( )3()2()1()0()()1(34241404304jxxjxxWxWxWxWxWnxXnn+−−=+++==∑= )3()2()1()0( )3()1)(2()1)(1()0( )3()2()1()0()()2(24644424043024xxxxWxxxxWxWxWxWxWnxXnn−+−=++−+=+++==∑=EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-12)3()2()1()0( )3()()2()1()1()0( )3()1)(2()1()0( )3()2()1()0()()3(142434946434043034jxxjxxxjxjxxWxWxWxxWxWxWxWxWnxXnn−−+=−+−++=+++=+++==∑= )]3()1([)]2()0([)3()]3()1([)]2()0([)2()]3()1()[()]2()0([)1()]3()1([)]2()0([)0(xxjxxXxxxxXxxjxxXxxxxX−+−=+−+=−−+−=+++= If we denote z(0) = x(0), z(1) = x(2) => Z(0) = z(0) + z(1) = x(0) + x(2) Z(1) = z(0) - z(1) = x(0) - x(2) v(0) = x(1), v(1) = x(3) => V(0) = v(0) + v(1) = x(1) + x(3) V(1) = v(0) - v(1) = x(1) - x(3) Our four – point DFT: X(0) = Z(0) + V(0) X(1) = Z(1) + (-j)V(1) X(2) = Z(0) - V(0) X(3) = Z(1) + jV(1) Key point: We compute 4-point DFT based on two 2-point DFTs Two-point DFT of [x(0) x(2)] Two-point DFT of [x(1) x(3)] Structure like this is called “butterfly”EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-13Decimation-in-Time FFT Algorithm x(0), x(1), … , x(N-1) mN2= Separate into even and odd samples: )12()()2()(+==nxrhrxrg ∑∑∑∑∑−=−=−=+−=−=+=−=+==12/0212/0212/0)12(12/0)2(10)()( )1,...,1,0()()( )()(NrkrNkNNrkrNNrrkNNrrkNNnknNWrhWWrgNkWrhWrgWnxkX Using property 4: )()( )()()()()(12/02/12/02/2)2//(22/22kHWkGWrhWWrgkXWeeWkNNrkrNkNNrkrNkrNkrNjkrNjkrN+=+=⇒===∑∑−=−=−−ππ where G(k) and H(k) are the N/2 point DFT of g(r) and h(r) respectively. ∑∑∑∑−=−=−=−=+====−=+=12/02/12/02/12/02/12/02/)12()()()2()()(1,...,1,0)()()(NrkrNNrkrNNrkrNNrkrNkNWrxWrhkHWrxWrgkGNkkHWkGkX Question: X(k) needs G(k), H(k), k=0… N-1 How do we obtain G(k), H(k), for k > N/2-1 ? G(k) = G(N/2+k) k <= N/2-1 H(k) = H(N/2+k) k <= N/2-1EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-14 Such recursion can be carried on by considering the even and odd samples of the sequence at each stage. For a 8-point FFT, the resulting decomposition looks like: What is the big deal?EE 422G Notes: Chapter 10 Instructor: Cheung Page 10-15(1) Very regular structure ⇒ easy hardware (and software) implementation (2) Big complexity savings!! Why? Let’s say you want to compute 1024-point DFT. Using direct computation, we need 4N2 ~ 4 million operations Using the above strategy: Let C(N) = total operations for 1024-pt DFT C(1024) = 2*1024 + 2*C(512) : One stage butterfly + Two 512-DFT = 2*1024 + 2*[2*512+2*C(256)] = 4*1024 + 4*[2*256+2*C(128)] = 6*1024 + 8*[2*128+2*C(64)] = 8*1024 + 16*[2*64+2*C(32)] =10*1024+ 32*[2*32+2*C(16)] =12*1024+ 64*[2*16+2*C(8)] =14*1024+128*[2*8+2*C(4)] =16*1024+256*C(2) =16*1024+256*4 = 17408 operations ~ A factor of 100 savings! In general, C(N) ~ N(log2N). The great savings come from the reduction of a factor N to (log2N), thanks to the
View Full Document
Unlocking...