快速傅里叶变换(FFT)中的奇偶分解推导

快速傅里叶变换(FFT)中的奇偶分解推导快速傅里叶变换(FFT)是一种高效计算离散傅里叶变换(DFT)的算法。其核心思想是利用奇偶分解将DFT分解成更小的DFT，并递归计算。以下是详细的推导过程：1. 离散傅里叶变换(DFT)公式：$X[k] = /sum_{n=0}^{N-1} (x[n] /cdot e^{-i /cdot 2/pi /cdot k /cdot /frac{n}{N}})$**2. 奇偶分解:**将DFT公式中的求和项按照索引n的奇偶性分成两组:$X[k] = /sum_{n=0}^{N/2-1} (x[2n] /cdot e^{-i /cdot 2/pi /cdot k /cdot /frac{2n}{N}}) + /sum_{n=0}^{N/2-1} (x[2n+1] /cdot e^{-i /cdot 2/pi /cdot k /cdot /frac{2n+1}{N}})$令$x_e[n] = x[2n]$表示偶数索引项，$x_o[n] = x[2n+1]$表示奇数索引项，则上式可写成:$X[k] = /sum_{n=0}^{N/2-1} (x_e[n] /cdot e^{-i /cdot 2/pi /cdot k /cdot /frac{2n}{N}}) + /sum_{n=0}^{N/2-1} (x_o[n] /cdot e^{-i /cdot 2/pi /cdot k /cdot /frac{2n+1}{N}})$**3. 提取公因子:**提取第二个求和项中的公因子$e^{-i /cdot 2/pi /cdot k / N}$:$X[k] = /sum_{n=0}^{N/2-1} (x_e[n] /cdot e^{-i /cdot 2/pi /cdot k /cdot /frac{2n}{N}}) + e^{-i /cdot 2/pi /cdot k / N} /cdot /sum_{n=0}^{N/2-1} (x_o[n] /cdot e^{-i /cdot 2/pi /cdot k /cdot /frac{2n}{N}})$**4. 递归形式:**注意到上式中的两个求和项都是长度为N/2的DFT，分别对应于偶数索引序列$x_e[n]$和奇数索引序列$x_o[n]$。因此，我们可以将一个长度为N的DFT分解成两个长度为N/2的DFT的线性组合。这个过程可以递归地进行，直到DFT的长度为1，此时可以直接计算。**总结:**通过奇偶分解，我们将DFT公式转化为一种递归形式，这正是FFT算法高效性的关键。递归地将DFT分解成更小的DFT，可以大大减少计算量，从而实现快速计算。