离散傅里叶变换的可约性证明

### 关于离散傅里叶变换可约性证明

#### 定义与背景
离散傅里叶变换（Discrete Fourier Transform, DFT）是一种用于分析有限长度序列频域特性的工具。对于一个长度为 \( N \) 的输入序列 \( x[n] \)，其对应的 DFT 输出序列为：

\[ X[k]=\sum_{n=0}^{N-1}x[n]\cdot e^{-j2\pi nk/N}, k=0,\ldots,N-1 \]

其中，\( W_N=e^{-j2\pi /N} \) 是旋转因子。

#### 可约性原理
DFT 计算复杂度较高，特别是当 \( N \) 较大时，直接实现所需的复数乘法次数达到 \( O(N^2) \)[^2]。然而通过观察可以发现某些特定条件下能够减少计算量。具体来说就是利用周期性和对称性来简化运算过程。

#### 基本分解方法
考虑将原始数据分成两组：一组由偶索引位置上的样本组成；另一组则取奇索引处的数据点。设原序列为 \( x(n), n = 0,...,N−1 \)，那么可以根据下标的奇偶分为两个子序列:

\[
x_e(m)=x(2m)\quad m=0,..,(N/2)-1 \\
x_o(m)=x(2m+1)\quad m=0,..,(N/2)-1
\]

此时有：

\[
X(k)=\sum _{r=0}^{N/2-1}\left[x(r)+(-1)^kw_r^{kr}\right]w_n^{rk}
\]

进一步整理得到：

\[
X(k)=E(k)+W_N^kO(k)
\]

这里定义了新的函数 E 和 O 来表示分别对应偶数组合后的结果以及带有相位偏移项的奇数组合的结果。注意到上述表达式中出现了相同形式的小规模版本的DFT操作——即针对一半大小的新序列执行同样的转换逻辑[^3]。

这种分治策略正是FFT算法的核心思想之一，并且展示了如何有效地降低原本庞大的矩阵向量积问题至更易于管理的形式。因此实现了所谓的“可约”。

// C++ code snippet demonstrating the divide-and-conquer approach of FFT.
void fft(vector<complex<double>>& a){
    int n=a.size();
    if(n<=1)return;
    
    vector<complex<double>> even(a.begin(),a.end()-1);
    vector<complex<double>> odd(a.begin()+1,a.end());
    
    // Recursive calls to compute smaller transforms on evens and odds.
    fft(even);fft(odd);

    for(int k=0;k<n/2;++k){
        complex<double> t=polar(1.0,-2*PI*k/n)*odd[k];
        a[k]=even[k]+t;
        a[k+n/2]=even[k]-t;
    }
}