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

ADD COMMENTlink
modified 3.4 years ago  • written 3.4 years ago by gravatar for Juilee Juilee2.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 ,

enter image description here

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.

ADD COMMENTlink
written 3.4 years ago by gravatar for Juilee Juilee2.4k
Please log in to add an answer.