UNIT-1 Theory topics PDF

3.4. DECIMATION IN TIME (DIT) RADIX 2 FFT: Decimation in Time (DIT) Radix 2 FFT algorithm converts the time domain N point sequence x(n) to a frequency domain N-point sequence X(k).In Decimation in Time algorithm the time domain sequence x(n) is decimated and smaller point DFT are performed....

3.4. DECIMATION IN TIME (DIT) RADIX 2 FFT: Decimation in Time (DIT) Radix 2 FFT algorithm converts the time domain N point sequence x(n) to a frequency domain N-point sequence X(k).In Decimation in Time algorithm the time domain sequence x(n) is decimated and smaller point DFT are performed. The results of smaller point DFTs are combined to get the result of N-point DFT. In DIT radix -2 FFT the time domain sequence is decimated into 2-point sequences. For each 2-point sequence,2 -point DFT can be computed. From the result of 2-point DFT the 4-point DFT can be calculated. From the result of 4-point DFT the 8- point DFT can be calculated. This process is continued until we get N point DFT.This FFT algorithm is called radix-2 FFT. In decimation in time algorithm the N point DFT can be realized from two numbers of N/2 point DFTs, The N/2 point DFT can be calculated from two numbers of N/4-point DFTs and so on. Let x (n) be N sample sequence, we can decimate x (n) into two sequences of N/2 samples. Let the two sequences be f1 (n) and f2 (n).Let f1 (n) consists of even numbered samples of x (n) and f2(n) consists of odd numbered samples of x(n). f 1(n) = x(2n) for n=0,1,2,3………… - 1 2 f 2(n) = x(2n +1) for n=0,1,2,3………… - 1 2 Let X (k) = N-point DFT of x (n) F1 (k) = N/2 point DFT of f 1(n) F2 (k) = N/2 point DFT of f 2(n) By definition of DFT the N/2 point DFT of f1(n) and f2(n) are given by −1 F1 (k) = ∑2 =0 1( ) ; /2 −1 F2 (k) = ∑ 2 =0 2( ) /2 Now-point DFT X (k), in terms of N/2 point DFTs F1 (k) and F2 (k) is given by X (k) = F1 (k) + Wk N F2(k), where, k= 0,1,2,...................... (N-1)  Having performed the decimation in time once, we can repeat the process for each of the sequences f1 (n) and f2 (n).Thus f1(n) would result in the two N/4 point sequences and f2(n) would result in another two N/4 point sequences. Let the decimated N/4 point sequences of f1 (n) be V11 (n) and V12 (n). V11 (n) = f1 (2n); for n= 0, 1, 2,….. -1 4 V12 (n) = f1 (2n+1) ; for n= 0,1,2,….. – 1 4 Let the decimated N/4 point sequences of f2(n) be V21(n) and V22(n). V 21(n) = f1 (2n) ; for n= 0,1,2,….. - 1 4 V 22(n) = f1 (2n+1) ; for n= 0,1,2,….. – 1 4 Let V11 (k) = N/4 point DFT of V11 (n); V12 (k) = N/4 point DFT of V12 (n) V 21(k) = N/4 point DFT of V 21(n) V 22(k) = N/4 point DFT of V 22(n) Then like earlier analysis we can show that, F1 (k) = V11 (k) + Wk N/2 V12 (k) ; for k = 0,1,2,3,........................ -1 2 F2 (k) = V21 (k) + Wk N/2 V 22(k) ; for k = 0,1,2,3,……………… -1 2 Hence the N/2 point DFTs are obtained from the results of N/4 point DFTs. The decimation of the data sequence can be repeated again and again until the resulting sequences are reduced to 2-point sequences. Flow graph for 8 point DFT using radix 2 DIT FFT Fig.3.4.1.Basic Butterfly computation [Source: ‘Digital Signal Processing Principles, Algorithms and Applications’ by J.G. Proakis and D.G. Manolakis page-460] In each computation two complex numbers “a” and “b” are considered. The complex number “b” is multiplied by a phase factor “WNk “The product “b WNk” is added to complex number “a” to form new complex number “A”. The product “b W Nk ” is subtracted from complex number “a” to form new complex number”B”. The input sequence is 8 point sequence.Therefore, N =8=23=rm.Here r=2 and m=3.The sequence x (n) is arranged in bit reversed order and then decimated into two sample sequences. Fig.3.4.2.Bit reversed order [Source: ‘Digital Signal Processing Principles, Algorithms and Applications’ by J.G. Proakis and D.G. Manolakis page-462] Fig 3.4.3. Three stages in the computation of an N = 8 point [Source: ‘Digital Signal Processing Principles, Algorithms and Applications’ by J.G. Proakis and D.G. Manolakis page-459]  Fig 3.4.4. Eight point Decimation In Time-FFT [Source: ‘Digital Signal Processing Principles, Algorithms and Applications’ by J.G. Proakis and D.G. Manolakis page-460] 3.5. DECIMATION IN FREQUENCY (DIF) RADIX 2 FFT: In Radix-2 decimation-in-frequency (DIF) FFT algorithm, original sequence s(n) is decomposed into two subsequences as first half and second half of a sequence. There is no need of reordering (shuffling) the original sequence as in Radix-2 decimation-in- time (DIT) FFT algorithm. In this algorithm the N-point time domain sequence is converted into two numbers of N/2 sequences. Then each N/2 point sequence is converted into two numbers of N/4 point sequences. Thus we get four numbers of N/4 point sequences. This process is continued until we get N/2 numbers of 2-point sequences. It can be shown that the N-point DFT of x(n) can be realized from two numbers of N/2 point DFTs.The N/2 point DFTs can be realized from two numbers of N/4 point DFTs and so on. The decimation is continued up to 2-point DFTs. Flow graph for 8 point DFT using Radix-2 DIF FFT Fig 3.5.1.Basic Butterfly Computation [Source: ‘Digital Signal Processing Principles, Algorithms and Applications’ by J.G. Proakis and D.G. Manolakis page-464] In each computation two complex numbers “a” and “b” are considered. The sum of the two complex numbers is computed which forms a new complex number “A”. Then subtract complex number “b” from “a” to get the term “a-b”.The difference term “a-b”is multiplied with the phase factor “W k “ to form a new complex number N “B”. Let x (n) and X(k) be N-point DFT pair. Let G1 (k) and G2 (k) be two numbers of N/2 point sequences obtained by the decimation of X (k). Let G1 (k) be N/2 point DFT of g1(n) and G2(k) be N/2 point DFT of g2(n). Now, the N point DFT X(k) can be obtained from the two numbers of N/2 point DFTs of G1(k) and G2(k) as shown below. X (k) | k=even = G1 (k) X (k) | k=odd = G2 (k) Fig.3.5.2.N=8 point decimation in frequency FFT algorithm. [Source: ‘Digital Signal Processing Principles, Algorithms and Applications’ by J.G. Proakis and D.G. Manolakis page-464] In the next stage of decimation the N/2 point frequency domain sequence G1 (k) is decimated into two numbers of N/4 point sequences D11 (k) and D12 (k), and G2 (k) is decimated into two numbers of N/4 point sequences D21 (k) and D22 (k). Let D11 (k) and D12 (k) be two numbers of N/4 point sequences obtained by the decimation of G1 (k). Let D11 (k) be N/4 point DFT of d11(n),and D12(k) be N/4 point DFT of d12(n). Let D21 (k) and D22 (k) be two numbers of N/4 point sequences obtained by the decimation of G2 (k). Let D21 (k) be N/4 point DFT of d21 (n) and D22 (k) be N/4 point DFT of d22 (n). Now, N/2 point DFTs can be obtained from two numbers of N/4 point DFTs as shown below. G1 (k) | k=even = D11 (k) G1 (k) | k=odd = D12 (k) G2 (k) | k=even = D21 (k) G2 (k) | k=odd = D22 (k) The decimation of the frequency domain sequence can be continued until the resulting sequences are reduced to 2-point sequences. The entire process of decimation involves,m stages of decimation where m = log 2 N.The computation of the N-point DFT via the decimation in frequency FFT algorithm requires (N/2)log2N Complex multiplications and Nlog2N complex additions.