DFT与FFT

2020-01-16 本文已影响0人 echo_ye4

回顾离散时间傅里叶级数DFS

${\boxed{x[n] = \sum_{k=<N>} a_ke^{jk\frac{2\pi}{N}n}\\ a_k = a_{k\pm mN} = \frac 1N \sum_{n=<N>}x[n]e^{-jk\frac{2\pi}{N}n}}}$

回顾离散时间傅里叶变换DTFT

${\boxed{x[n] = \frac 1{2\pi} \int_{2\pi}X(e^{jw})e^{jwn}dw\\ X(e^{jw}) = \sum_{n=\infty}x[n]e^{-jwn}}}$

DFT

要在计算机上实现DTFT，有一个问题就是所需的采样点是无限的，而离散傅里叶变换DFT解决了这个问题，所需的采样点有限，利用有限的采样值确定信号的频谱分量。
DFT定义为：
$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j2\pi \frac kN n}, k=0, 1, ..., N-1$
时域的采样个数与频域的采样个数相等，因此解决了另外一个问题： $X(e^{jw})$ 定义在无限个频率上，而 $X[k]$ 定义在有限个k上，易于处理。
把DFT中N个时域采样点看成是处于DFT窗内，位于窗外的采样点不影响分析。
${\boxed{ x[n] = \frac 1N \sum_{k=0}^{N-1}X[k]e^{j2\pi \frac kN n} \\ X[k] = \sum_{n=0}^{N-1}x[n]e^{-j2\pi \frac kN n} }}$
当对同一组时域采样信号进行DFT和DTFT时，两者是相符的，DFT是DTFT的采样形式。
DFS在N点上运算，只要DFT也取相同点数，DFS和DFT就相同，区别只是解释不同，DFT是非周期信号加窗后再进行周期延拓所得。

FFT

DFT使得DTFT可以在计算机上实现，而FFT可以得出与DFT一样的结果且运算量要小得多，因此DSP软件包中一般都是应用FFT。
最常用的FFT是基2时域抽取法，基本原理是将一个N点的计算分解为两个N/2的计算，每个N/2的计算再分解为N/4的计算，以此类推。

先将时域的N个采样点分为偶采样序列 $y[n]=x[2n]$ 和奇采样序列 $z[n]=x[2n+1]$
$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j2\pi \frac kN n}=\sum_{n=0}^{N/2-1}y[n]e^{-j2\pi \frac kN (2n)} + \sum_{n=0}^{N/2-1}z[n]e^{-j2\pi \frac kN (2n+1)}$
$X[k] = Y[k] + e^{-j\frac {2\pi k}{N}}Z[k]$
由于 $Y[k], Z[k]$ 是 $N/2$ 点的信号，因此周期为 $N/2$
$X[k] = X[k+N/2] = Y[k] + e^{-j\frac {2\pi k}{N}}Z[k], k = 0, 1, ..., N/2-1$

上述形成了FFT的一个步骤，将N点的DFT分解为N/2点的DFT，以此类推可以不断得进行分解；随着N的增大，FFT的优势将越来越明显。

DFT与FFT

回顾离散时间傅里叶级数DFS

回顾离散时间傅里叶变换DTFT

DFT

FFT

猜你喜欢

热点阅读