where G[k]is the (N/2)-point DFT of the even numbered x[n],and Hk]is the (N/2)-point DFT of the odd numbered xn].Note that both G[k]and H[k]are periodic in k with period (N/2),so when computing the value of X[N/2],we can use G[o]and H[0],and so on.OSB Figure 9.3 depicts the computation using Equation 4 for N=8. Now,the number of complex multiplications and complex additions are both reduced to 2(+N which is less than N2 for N>2.Similarly to the decimation-in-frequency algorithm,we can continue the decomposition until we are left with only two inputs as depicted in OSB Figure 9.5and9.7. OSB Figure 9.8 shows the basic butterfly structure in the flow graph.Since wN+w/2)=WWW②=-w5, we can further reduce the number of multiplications by replacing the structure in OSB Figure 9.8 with the one in OSB Figure 9.9. The flow graph of an 8-point DFT using the butterfly computation of OSB Figure 9.9 is shown in OSB Figure 9.10.Notice that the input is in bit-reverse order and the output is in normal order.We can rearrange nodes to sort the input in normal order and the output in bit-reverse order as shown in OSB Figure 9.14. In Lecture 6,we learned that the transposition of a flow graph is obtained by interchanging the input and output and reversing the direction of signal flow.Generally,for each decimation-in- time FFT algorithm flow graph,there exist a decimation-in-frequency algorithm obtained by transposing the original flow graph.One example is shown in OSB Figure 9.10 and 9.20.The flow graph in OSB Figure 9.10 depicts a decimation-in-time algorithm,and OSB Figure 9.20 shows a decimation-in-frequency flow graph.You can check that the flow graph in the right is the transpose of the flow graph in the left. As in the decimation-in-frequency algorithm,if we rearrange nodes to sort both the input and output in normal order,we can not accomplish in-place computation.A flow graph that does not allow in-place computation,but nonetheless useful,is shown in OSB Figure 9.16.The same geometry for each stage permits sequential data accessing and storage. 4where G[k] is the (N/2)-point DFT of the even numbered x[n], and H[k] is the (N/2)-point DFT of the odd numbered x[n]. Note that both G[k] and H[k] are periodic in k with period (N/2), so when computing the value of X[N/2], we can use G[0] and H[0], and so on. OSB Figure 9.3 depicts the computation using Equation 4 for N = 8. Now, the number of complex multiplications and complex additions are both reduced to N 2 · ( 2 ) 2 + N, which is less than N2 for N > 2. Similarly to the decimation-in-frequency algorithm, we can continue the decomposition until we are left with only two inputs as depicted in OSB Figure 9.5 and 9.7. OSB Figure 9.8 shows the basic butterfly structure in the flow graph. Since W(r+N/2) NW(N/2) = −Wr = Wr N N N , we can further reduce the number of multiplications by replacing the structure in OSB Figure 9.8 with the one in OSB Figure 9.9. The flow graph of an 8-point DFT using the butterfly computation of OSB Figure 9.9 is shown in OSB Figure 9.10. Notice that the input is in bit-reverse order and the output is in normal order. We can rearrange nodes to sort the input in normal order and the output in bit-reverse order as shown in OSB Figure 9.14. In Lecture 6, we learned that the transposition of a flow graph is obtained by interchanging the input and output and reversing the direction of signal flow. Generally, for each decimation-in￾time FFT algorithm flow graph, there exist a decimation-in-frequency algorithm obtained by transposing the original flow graph. One example is shown in OSB Figure 9.10 and 9.20. The flow graph in OSB Figure 9.10 depicts a decimation-in-time algorithm, and OSB Figure 9.20 shows a decimation-in-frequency flow graph. You can check that the flow graph in the right is the transpose of the flow graph in the left. As in the decimation-in-frequency algorithm, if we rearrange nodes to sort both the input and output in normal order, we can not accomplish in-place computation. A flow graph that does not allow in-place computation, but nonetheless useful, is shown in OSB Figure 9.16. The same geometry for each stage permits sequential data accessing and storage. 4