唐斌-数字信号处理课件-chap9 第2讲.pptVIP

Comparison of DIT-FFT and DIF-FFT The Fast computation of IDFT—— IFFT Homework 9.6, 9.22，9.26 9.4. Decimation-In-Frequency FFT algorithms The decimation-in-frequency FFT algorithms are based on dividing the output sequence X[k] into smaller and smaller subsequences in the same manner as the decimation-in-time FFT algorithms. Let Principle of the DIF-FFT Algorithm (i) Another representation of X[k] (ii) Decompose X[k] into two sequences according k is even or odd k is even k is odd Then —— Butterfly Computation in DIF-FFT So, two complex addition + one complex multiplication Let e. g. Computation = N/2 butterflies + two N/2-point DFTs (iii) The 2nd decomposition: e. g. Computation = 2 stages butterflies + Four N/4-point DFTs (iv) Further decomposition until 2-point DFTs are left butterfly e. g. So, the 8-point DIF-FFT: Computation of DIF-FFT complex mul: complex add: Characteristics of DIF-FFT (i) In-Place Computation 存储数据只需要N个存储单元 (ii) input: normal order output: bit-reversed order (iii) Distance between two source nodes of one butterfly 依次类推，对于 点DIF-FFT，当输入为正常序，输出为倒位序时，其第m级运算每个蝶形的两节点间距离为 第一级(第一列)每个蝶形的两个节点间距离为4 第二级(第二列)每个蝶形的两个节点间距离为2 第三级(第三列)每个蝶形的两个节点间距离为1 (iv) Determine 第一级有N/2种： 第二级有N/4种: 依次类推，最后一级有1种： (v) 存储单元 存储输入序列 的N个存储单元单元，以及存储系数 的N/2个存储单元。 Alternative Forms Figure 9.22, Figure 9.23, Figure 9.24 (i) idea DIT-FFT: divide the input sequence x[n] into smaller and smaller subsequences DIF-FFT: divide the output sequence X[k] into smaller and smaller subsequences (ii) Butterfly computation is different DIT-FFT: DIF-FFT: —— be transposed each other (fig. 9.11 ) (fig. 9.21 ) (iii) Structures are transposed each other DIT-FFT: (fig. 9.10 ) DIF-FFT: (fig. 9.20 ) (iv) Both are in-place computation (v) The computation is same DFT: IDFT: (i) (ii) 1. The first method e.g., 8-point DIF-IFFT