Lecture 19 Solutions: Computation of the Discrete Fourier Transform (Part 2)

COMPUTATION OF THE DISCRETE FOURIER TRANSFORM - PART 2 Solution 19.1 NORMAL ORDER x(0000) = x (0001) BIT REVERSED ORDER x(0) x (0000) = x(0) x(1) x (1000) x(0010) = x(2) x (0100) = x(4) x(0011) = x(3) x (1100) = x(12) x(0100) = x(4) x (0010) = x(2) x (0101) = x(5) x (1010) = x(10) x(0110) = x(6) = x(6) x (0111) = x(14) = x(7) x(0110) x (1110) x(1000) = x(8) x (0001) = x(1) x(1001) = x (1001) x(0101) x(9) = x(9) x(10) = x(1010) = x(5) x (1011) = ,x(ll) x(1101) = x(13) x(1100) = x (0011) = x (1101) = x(12) x(13) x (1011) = x(3) x(11) x (1110) = x(14) x (0111) = x(7) x(1111) = x(15) x (1111) = x(15) Solution 19.2 (a) x(0) x (2) ^ X(0) V. IM y X(2) x(l) x(3) A X(1) 192 -1 W -1 - - B X(3) Figure Sl9. 2-1 S19.1 (b) x(l) 0 x (l) X (2) Oh -1 rFZX (1) x (2) o. x(3) -1 0- o X(3) Figure S19.2-2 The desired flow-graph is obtained by interchanging lines A and B in Figure S19.2-1 Solution 19.3 (a) N/2 (b) WMk/2 (c) N-2-m (d) N. 2 -m+l k =Ol,...,N/M - 1 M = 2m 24 m < log 2 N * Solution 19.4 (a) Xm+ lx (p= 1 |m+1 (P) Xm (p) + W I< IX (p) m X (q) + Iwr X (q) + ; Xm Thus with IXm(p)| and IXm(q)l IX +(p)| I I(p) X I + I X (q)I m~p |m both less than 1/2, < 1 and consequently IXm+l(p) 22<1 Finally, since M+l(p) 2 =Re [Xm+l(p) ]+lIm [XM it follows that IRe [Xra 1 (p)]I < 1 JIm [Xm+l 1I <1 S19.2 I(p)] 2 In a similar manner it follows that Re [Xm+ 1(q) |Im (b) < [Xm+ 1(q) < Re [Xm+1(p)] = Re [Xm(p)] + Re Xm(q)I WNr Let Xm(q) be expressed in polar form as Ae Then Re [X m+l (p)] = Re [X (p)] + Acos(8 m 0 - 27)r N Re [Xm(p)] is constrained to be less than 1/2 and since the magnitudes of the real and imaginary parts of Xm(q) are constrained to be less than 1/2, A must be less than 1//2. If 6 _ 2r , then N IRe [Xm+ 1 (p)]| = |Re [Xm(p)] + A| < + ­ Since this is greater than unity, we see that the stated constraints will not guarantee that no over-flow occurs. * Solution 19.5 (a) (1) Bit reversal - lines 7 through 16 (2) Recursive computation of WN's - line 29 (3) Basic Butterfly computation - lines 26 through 28 (b) (1) Insert between lines 7 and 8: (2) Line 22 should read: If (I.GE.J) GO TO 5 W = CMPLX(COS(PI/FLOAT(LEI)), - SIN(PI/FLOAT(LEl))) (3) Line 25: IP = I + LEl S19.3