The procedure suggested by Equation 2 and 3 is illustrated in OSB Figure 9.17 for the case N=8. Recall that N2 complex multiplications were required to compute the N-point DFT using Equation 1.By comparison,using the procedure in the figure above,we need two (N/2)-point DFTs and additional(N/2)complex multiplications.Therefore,the number of multiplications required to compute the N-point DFT using Equation 2 and 3 is 2+ N which is smaller than N2.The number of additions is also reduced to approximately 2.()2+N. Similarly,we can compute the (N/2)-point DFTs using the (N/4)-point DFTs as illustrated in OSB Figure 9.18.Now the number of multiplications required is 。N.N 4()2+2 4+2 We can continue the decomposition until we are left with only 2-point transforms which can be computed easily with the butterfly structure shown in OSB Figure 9.19. In general,using the complete decimation-in-frequency decomposition,we need (N/2)log2 N complex multiplications and Nlog2 N complex additions to compute the N-point DFT.The flow graph for the case of an 8-point DFT is given in OSB Figure 9.20. The flow graph above suggests a useful way of storing the original data and the results of the computation.If we store the input (xns)in the same order as they appear in the figure from top to bottom,the output(X[ks)will appear in bit-reversed order.That is,the binary digits are sorted starting with the least significant bit instead of starting with the most significant bit as in normal order sorting. Other rearrangements of the flow graph are discussed in OSB Section 9.4.2. Decimation-in-Time The decimation-in-frequency algorithm decomposes the output sequence X[k]into successively smaller subsequences.We can also decompose the input sequence x[n]into smaller subse- quences,starting from decomposing into the even-and odd-numbered samples. N-1 Xk= zinjWat n=0 ∑mw*+∑W n even n odd =Gik]+WHk], (4) 3The procedure suggested by Equation 2 and 3 is illustrated in OSB Figure 9.17 for the case N = 8. Recall that N2 complex multiplications were required to compute the N-point DFT using Equation 1. By comparison, using the procedure in the figure above, we need two (N/2)-point DFTs and additional (N/2) complex multiplications. Therefore, the number of multiplications required to compute the N-point DFT using Equation 2 and 3 is N N 2 · ( 2 ) 2 + 2 , 2 ) which is smaller than N 2+N. 2. The number of additions is also reduced to approximately 2·( N Similarly, we can compute the (N/2)-point DFTs using the (N/4)-point DFTs as illustrated in OSB Figure 9.18. Now the number of multiplications required is N N 4 · ( 4 ) 2 + 2 N · + . 4 2 We can continue the decomposition until we are left with only 2-point transforms which can be computed easily with the butterfly structure shown in OSB Figure 9.19. In general, using the complete decimation-in-frequency decomposition, we need (N/2)log2 N complex multiplications and N log2 N complex additions to compute the N-point DFT. The flow graph for the case of an 8-point DFT is given in OSB Figure 9.20. The flow graph above suggests a useful way of storing the original data and the results of the computation. If we store the input (x[n]s) in the same order as they appear in the figure from top to bottom, the output(X[k]s) will appear in bit-reversed order. That is, the binary digits are sorted starting with the least significant bit instead of starting with the most significant bit as in normal order sorting. Other rearrangements of the flow graph are discussed in OSB Section 9.4.2. Decimation-in-Time The decimation-in-frequency algorithm decomposes the output sequence X[k] into successively smaller subsequences. We can also decompose the input sequence x[n] into smaller subse￾quences, starting from decomposing into the even- and odd- numbered samples. N−1 X[k] = � x[n]Wnk N n=0 = � x[n]Wnk N + � x[n]Wnk N n even n odd = G[k] + Wk N H[k], (4) 3