#! https://zhuanlan.zhihu.com/p/656904738

离散傅里叶级数与离散傅里叶变换

离散傅里叶级数（DFS)

离散傅里叶级数指的是任何周期序列都可以由谐波相关的复指数序列的加权和组成。

$\tilde{X} [k] = \sum_{n = 0}^{N - 1} \tilde{x} [n] \cdot e^{- j \frac{2 π}{N} k n}$

$\tilde{x} [n]$ 是周期为 $N$ 的离散时间信号，即 $\tilde{x} [n] = \tilde{x} [n + N]$ ；
跟连续时间周期信号的傅里叶级数中无限项谐波相关复指数函数的加权和不同，这里是有限项的加权和；
$\tilde{X} [k]$ 是 $\tilde{x} [n]$ 的离散傅里叶级数，其周期同样是 $N$ ；
时域是离散的、周期的，频域也是离散的，周期的。

定义 $W_{N} = e^{- j \frac{2 π}{N}}$ ，则离散傅里叶级数可以写成：

$\tilde{X} [k] = \sum_{n = 0}^{N - 1} \tilde{x} [n] \cdot W_{N}^{k n}$

离散傅里叶级数的反变换为：

$\tilde{x} [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} \tilde{X} [k] \cdot W_{N}^{- k n}$

周期序列的时域和其离散傅里叶级数如下图所示：

周期序列的时域和其离散傅里叶级数

离散傅里叶级数的性质

\begin{array}{r} \begin{array}{cc} 周 期 序 列 & 离 散 傅 里 叶 级 数 \\ \tilde{x} [n] & \tilde{X} [k] \\ {\tilde{x}}_{1} [n] + b {\tilde{x}}_{2} [n] & a {\tilde{X}}_{1} [k] + b {\tilde{X}}_{2} [k] \\ \tilde{x} [n - m] & W_{N}^{k m} \tilde{X} [k] \\ W_{N}^{- l n} \tilde{x} [n] & \tilde{X} [k - l] \\ \tilde{X} [n] & N \tilde{x} [- k] \\ \sum_{m = 0}^{N - 1} \tilde{x} [m] {\tilde{x}}^{*} [n - m] 圆 周 卷 积 & {\tilde{X}}_{1} [k] \cdot {\tilde{X}}_{2} [k] \\ {\tilde{x}}_{1} [n] \cdot {\tilde{x}}_{2} [n] & \frac{1}{N} {\tilde{X}}_{1} [k] * {\tilde{X}}_{2} [k] 圆 周 卷 积 \\ {\tilde{x}}^{*} [n] & {\tilde{X}}^{*} [- k] \\ {\tilde{x}}^{*} [- n] & {\tilde{X}}^{*} [k] \\ Re {\tilde{x} [n]} & {\tilde{X}}_{e} [k] = \frac{1}{2} (\tilde{X} [k] + {\tilde{X}}^{*} [- k]) \\ j Im {\tilde{x} [n]} & {\tilde{X}}_{o} [k] = \frac{1}{2} (\tilde{X} [k] - {\tilde{X}}^{*} [- k]) \\ {\tilde{x}}_{e} [n] = \frac{1}{2} (\tilde{x} [n] + {\tilde{x}}^{*} [- n]) & Re {\tilde{X} [k]} \\ {\tilde{x}}_{o} [n] = \frac{1}{2} (\tilde{x} [n] - {\tilde{x}}^{*} [- n]) & j Im {\tilde{X} [k]} \\ 当 \tilde{x} [n] 为 实 序 列 时 & \begin{aligned} \tilde{X} [k] 为 共 轭 对 称 序 列 ， & 即 \tilde{X} [k] = {\tilde{X}}^{*} [N - k] \\ Re {\tilde{X} [k]} & = Re {{\tilde{X}}^{*} [- k]} \\ Im {\tilde{X} [k]} & = - Im {{\tilde{X}}^{*} [- k]} \\ | \tilde{X} [k] | & = | \tilde{X} [- k] | \\ ∠ \tilde{X} [k] & = - ∠ \tilde{X} [- k] \end{aligned} \\ 当 \tilde{x} [n] 为 实 偶 序 列 时 & Re {\tilde{X} [k]} \\ 当 \tilde{x} [n] 为 实 奇 序 列 时 & j Im {\tilde{X} [k]} \end{array} \end{array}

离散傅里叶变换（DFT）

离散傅里叶变换是将有限长的离散时间序列转换为离散频率序列的变换。通过取周期序列的一个周期，可以将离散傅里叶级数转换为离散傅里叶变换。

$\tilde{X} [k] R_{N} [k] = \sum_{n = 0}^{N - 1} \tilde{x} [n] W_{N}^{k n} R_{N} [k]$

$X [k] = \sum_{n = 0}^{N - 1} x [n] \cdot e^{- j \frac{2 π}{N} k n}, k = 0, 1, \dots, N - 1$

$R_{N} [k]$ 是矩形序列，其定义为： $R_{N} [k] = {\begin{cases} 1, & if 0 \leq k < N \\ 0, & otherwise \end{cases}$

$x [n]$ 是周期序列 $\tilde{x} [n]$ （也可以表示为 $x ((n))_{N}$ ）的一个周期，即 $x [n] = \tilde{x} [n]$ ， $0 \leq n \leq N - 1$ ；
$X [k]$ 是频域上周期序列 $\tilde{X} [k]$ （也可以表示为 $X ((k))_{N}$ ）的一个周期，即 $X [k] = \tilde{X} [k]$ ， $0 \leq k \leq N - 1$ ；
有限长序列在做离散傅里叶变换时，隐含了“周期性”，也就是说我们需要将有限长序列看成是周期序列的一个周期。离散傅里叶变换的各种性质也是由离散傅里叶级数的性质推导出来的。

有限长序列的时域和其离散傅里叶变换如下图所示：

有限长序列的时域和其离散傅里叶变换

从离散傅里叶级数和离散傅里叶变换的图中可以看出，有限长离散时间信号的傅里叶变换的时域是周期序列取了其中的第一个周期，我们也称之为主值区间，其频域也是周期序列的频域取了其主值区间。

离散傅里叶变换的性质

\begin{array}{r} \begin{array}{cc} 有 限 长 序 列 ， 长 度 为 N & N 点 的 离 散 傅 里 叶 变 换 \\ x [n] & X [k] \\ x_{1} [n] + b x_{2} [n] & a X_{1} [k] + b X_{2} [k] \\ x ((n - m))_{N} R_{N} (n) & W_{N}^{k m} X [k] \\ W_{N}^{- l n} x [n] & X ((k - l))_{N} R_{N} (k) \\ X [n] & N x [N - k] \\ \sum_{m = 0}^{N - 1} x [m] x ((n - m))_{N} R_{N} [n] & X_{1} [k] \cdot X_{2} [k] \\ x_{1} [n] \cdot x_{2} [n] & \frac{1}{N} \sum_{l = 0}^{N} X_{1} [l] X_{2} ((k - l))_{N} R_{N} [k] \\ x^{*} [n] & X^{*} [N - k] \\ x^{*} ((- n))_{N} R_{N} [n] & X^{*} [k] \\ Re {x [n]} & X_{e} [k] = \frac{1}{2} (X [k] + X^{*} ((- k))_{N}) R_{N} [k] \\ j Im {x [n]} & X_{o} [k] = \frac{1}{2} (X [k] - X^{*} ((- k))_{N}) R_{N} [k] \\ x_{e} [n] = \frac{1}{2} (x [n] + x^{*} ((- n))_{N}) R_{N} [n] & Re {X [k]} \\ x_{o} [n] = \frac{1}{2} (x [n] - x^{*} ((- n))_{N}) R_{N} [n] & j Im {X [k]} \\ 当 x [n] 为 实 序 列 时 & \begin{aligned} X [k] 为 共 轭 对 称 序 列 ， & 即 X [k] = X^{*} [N - k] \\ Re {X [k]} & = Re {X^{*} [N - k]} \\ Im {X [k]} & = - Im {X^{*} [N - k]} \\ | X [k] | & = | X [N - k] | \\ ∠ X [k] & = - ∠ X [N - k] \end{aligned} \\ 当 x [n] 为 实 偶 序 列 时 & Re {X [k]} \\ 当 x [n] 为 实 奇 序 列 时 & j Im {X [k]} \end{array} \end{array}

特殊的应用

在做DFT的时候，通常时域上的输入是实数序列，也就是说 $x [n]$ 是实数序列，其频域输出 $| X [k] | = | X [N - k] |, ∠ X [k] = - ∠ X [N - k]$ 。因此，我们只需要计算 $0 \leq k \leq N / 2$ 的数据，这些数据包括了 $0 \leq k \leq N / 2$ 的数据和 $N / 2 + 1 \leq k \leq N - 1$ 的数据。这样做的好处是减少了一半的计算量，同时也减少了一半的存储空间。
利用共轭对称性，可以用一次DFT运算来计算两个实数序列的DFT，因而可以减少计算量。

设 $x_{1} [n]$ 和 $x_{2} [n]$ 为N点的实数序列，其DFT分别为 $X_{1} [k]$ 和 $X_{2} [k]$ ，则：

先用这两个实数序列组成一个复数序列 $x [n] = x_{1} [n] + j x_{2} [n]$ ，求其DFT为 $X [k]$ ，然后利用共轭对称性，可以得到：

\begin{array}{r} \begin{aligned} X_{1} [k] & = D F T {R e {x [n]}} \\ = \frac{1}{2} (X [k] + X^{*} [N - k]) \end{aligned} \end{array}

\begin{array}{r} \begin{aligned} X_{2} [k] & = D F T {I m {x [n]}} \\ = \frac{1}{2 j} (X [k] - X^{*} [N - k]) \end{aligned} \end{array}