Question: Explain Decimation is time FFT algorithm with signal flow graph.
0

Mumbai University > Computer Engineering > Sem 7 > Image Processing

Marks: 10 M

Year: Dec 2014

 modified 3.4 years ago  • written 3.4 years ago by Juilee • 2.4k
0

The DFT equation is

$X(K) = \sum_{n=0}^{N-1} x(n) W_N^{nK} \hspace{1cm} K=0,1,2,…..N-1$

In decimation-in-time technique ,we split the input x(n) into odd and even parts.

$X(K) = \sum_{n→even} x(n) W_N^{nK} + \sum_{n→odd} x(n) W_N^{nK} \\ X(K) = \sum_{n=0}^{N/2-1} x(2n) W_N^{2nK} + \sum_{n=0}^{N/2-1} x(2n) W_N^{2n+1}K \\ X(K) = \sum_{n=0}^{N/2-1} x(2n) W_N^{2nK} + \sum_{n=0}^{N/2-1} x(2n) W_N^{2nK} W_N^K \\ Now,W_N^2= W_{N/2} \\ X(K) =\sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} +W_N^K \sum_{n=0}^{N/2-1} x(2n+1) W_{N/2}^{nK} \\ Let F1(K) =\sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} \\ F2(K) = \sum_{n=0}^{N/2-1} x(2n+1) W_{N/2}^{nK} \\ Therefore , X(K) = F1(K)+W_N^K F2(K)$

Since F1(K) and F2 (K) are periodic with period N/2 we can write

$F1(K+N/2) = F1(K) and F2(K+N/2) = F2(K) \\ Also W_{N/2}^{nK}= -W_N^K$

Therefore, We get,

$X(K) = F_1(K)+W_N^K F_2(K) \hspace{1cm} K=0,1,2,……N/2 - 1 \\ X(K+N/( 2)) = F_1(K) -W_N^K F_2(K)$

Hence, the computation of X(K) requires complex multiplications which is almost half the computations required by the conventional method,

$2X(N/2)2 + N/2 = N^2/2 +N/2$

As stated earlier,F1(K) and F2(K) are N/2 point DFT’s (4 point DFT’s if N = 8).These can be further split up into odd and even parts.

$i.e.X(K) = \sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} + W_N^K \sum_{n=0}^{N/2-1} x(2n+1) W_{N/2}^{nK} \\ (A) 2 \ parts \ of \ N/4 \ each \hspace{1cm} (B) \ 2 \ parts \ of \ N/4 \ each \\ (A): = \sum_{n=0}^{N/2-1} x(2n) W_{N/2}^{nK} = \sum_{n=0}^{N/4-1} x(4n) W_{N/2}^{2nK} + \sum_{n=0}^{N/2-1} x(4n+2) W_{N/2}^{(2n+1)K} \\ \hspace{4.8cm} = \sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} + \sum_{n=0}^{N/4-1} x(4n+2) W_{N/2}^{(2nk+k)} \hspace{4.8cm} = \sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} + W_{N/2}^K \sum_{n=0}^{N/4-1} x(4n+2) W_{N/4}^{nK} \\ Therefore, \ F1(K) = \sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} + W_{N/2}^K \sum_{n=0}^{N/4-1} x(4n+2) W_{N/4}^{nK} \\ Let, ∑\sum_{n=0}^{N/4-1} x(4n) W_{N/4}^{nK} = G_1(K) and \sum_{n=0}^{N/4-1} x(4n+2) W_{N/4}^{nK} = G_2(K) \\ Then, F_1(K) = G_1(K) + W_{N/2}^K G_2(K) \\ Similarly, F_2(K) = H_1(K) + W_{N/2}^K H_2(K)$

Hence, the final signal flow graph is , This is called 8-point butterfly diagram.

The DIT-FFT refers to the method in which the input samples are broken into odd and even parts. his time decimation leads to the scrambled order of the input.

 written 3.4 years ago by Juilee • 2.4k