快速傅立叶变换研究过程

离散信号傅立叶变换分析

【

X(k)=\sum_{n=0}^Nx(n)W_N^{nk}

此公式中所涉及的变量定义如下：

W_N=e^{-j\frac{2\pi}{N}}

同时，参数 k 的取值范围为：

k=0,1,...,N-1

基2时域抽取FFT算法设计

离散傅立叶变换的表达式可表示为

X(k)=\sum_{n=0}^Nx(n)W_N^{nk}

此表达式能够进一步进行拆分，具体形式如下：

X(k)=\sum_{n=0}^{\frac{N}{2}-1}(x(2n)W_N^{2nk}+x(2n+1)W_N^{(2n+1)k})

进一步展开后可得：

\quad = \sum_{n=0}^{\frac{N}{2}-1}x(2n)W_N^{2nk}+\sum_{n=0}^{\frac{N}{2}-1}x(2n+1)W_N^{(2n+1)k}

继续简化为：

\quad = \sum_{n=0}^{\frac{N}{2}-1}x(2n)W_N^{2nk}+W_N^{k}\sum_{n=0}^{\frac{N}{2}-1}x(2n+1)W_N^{(2n)k}\quad(EQ.1)