离散傅里叶级数·离散傅里叶变换

复指数序列的周期性

$x[n] = e^{j\omega_0 n}$，由于$\omega_0 \in [0, 2\pi)$的周期性，因此有：$x[n] = e^{j\omega_0 n} = e^{j(\omega_0 + 2\pi k)n}$，令$\omega_0 N = 2\pi k, k \in Z$，有：

$x[n] = e^{j\omega_0 n} = e^{j(\omega_0 + 2\pi k)n} = x[n + N]$

复指数序列$x[n]$具有周期性，称$N$为其周期。

由于$\omega_k = \frac{2\pi k}{N} \in [0, 2\pi)$，因此当序列周期为$N$时，当且仅当$k = 0, 1, 2, \ldots, N - 1$时存在$N$个不同的$\omega_k$。$N = \frac{2\pi k}{\omega_0}$。
code

离散傅里叶级数（DFS）

根据连续时间周期信号的傅里叶变换：

$x(t) = \sum_{k=-\infty}^{\infty} X(k\Omega_0) e^{jk\Omega_0 t}$

其中连续信号的角频率为：$\Omega_0 = \frac{2\pi}{T}$
类比连续时间周期信号，设周期序列$\tilde{x}[n]: \tilde{x}[n] = \tilde{x}[n+rN], r \in Z$，有：

$\tilde{x}[n] = \sum_{k=-\infty}^{\infty} X(k\Omega_0) e^{j\frac{2\pi}{N}kn}$

由于满足条件的频率分量$\omega_k$只有$N$个：

$\tilde{x}[n] = \sum_{k=-\infty}^{\infty} X(k\Omega_0) e^{j\frac{2\pi}{N}kn}$ $= \sum_{k=0}^{N-1} X(k\Omega_0) e^{j\frac{2\pi}{N}kn}$ $= \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j\frac{2\pi}{N}kn}$

其中$\tilde{X}[k]$为离散傅里叶级数系数，可反推得到：

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

定义$W_N^{kn} = e^{-j(\frac{2\pi}{N})kn}$，有离散傅里叶级数分析：

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

离散傅里叶级数合成：

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

$W_N^{kn}$是复数的角度表示形式，一般计算时转化为z域中的坐标以方便计算。如:$W_4^2=e^{-j\frac{2\pi}{4}\times2}=-1$

离散傅里叶级数的意义

周期为$N$的序列可以表示为$N$个周期为$N$的复指数序列的线性组合。
离散傅里叶级数与离散时间傅里叶变换（DTFT）的关系
事实上，可以将离散傅里叶级数看作是对离散时间傅里叶变换结果$X(e^{j\omega})$以周期为$N$做延拓后，对其进行采样的结果。
code

离散傅里叶级数与Z变换的关系

给定Z变换：$X(z)|_{z=e^{j\omega}}=X(e^{j\omega})$，那么：

$\tilde{X}[k]=X(z)|_{z=e^{j(2\pi/N)k}}=X(e^{j(2\pi/N)k}), k=0,1,\ldots,N-1$

即离散傅里叶级数可以看做是在Z变换的单位圆上做均匀采样的结果。
离散傅里叶级数的性质

周期性：如果$\tilde{x}[n]$的周期为$N$，$\tilde{X}[k]$的周期同样为$N$。
线性：$a\tilde{x}_1[n]+b\tilde{x}_2[n]\leftrightarrow a\tilde{X}_1[k]+b\tilde{X}_2[k]$
时移：$\tilde{x}[n-m]\leftrightarrow W_N^{km}\tilde{X}[k]$
频移：$\tilde{X}[k-l]\leftrightarrow W_N^{-nl}\tilde{x}[n]$
对偶性：如果$\tilde{x}[n]\leftrightarrow\tilde{X}[k]$，那么$\tilde{X}[n]\leftrightarrow N\tilde{x}[-k]$
周期卷积
如果两个序列$\tilde{x}_1[n]$、$\tilde{x}_2[n]$有相同的周期$N$，有： $\tilde{x}_1[n]\tilde{\otimes}\tilde{x}_2[n]=\sum_{m=0}^{N-1}\tilde{x}_1[m]\tilde{x}_2[n-m]\leftrightarrow\tilde{X}_1[k]\tilde{X}_2[k]$ 周期卷积定理可以被矩阵化为： $\tilde{x}[n] \tilde{\otimes} \tilde{y}[n] = \left[ \begin{array}{c} \tilde{z}[0] \\ \tilde{z}[1] \\ \cdots \\ \tilde{z}[N-2] \\ \tilde{z}[N-1] \end{array} \right] \mid_{periodic} = \left[ \begin{array}{ccccc} \tilde{y}[0] & \tilde{y}[N-1] & \cdots & \tilde{y}[2] & \tilde{y}[1] \\ \tilde{y}[1] & \tilde{y}[0] & \cdots & \tilde{y}[3] & \tilde{y}[2] \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ \tilde{y}[N-2] & \tilde{y}[N-1] & \cdots & \tilde{y}[0] & \tilde{y}[N-1] \\ \tilde{y}[N-1] & \tilde{y}[N-2] & \cdots & \tilde{y}[1] & \tilde{y}[0] \end{array} \right] \left[ \begin{array}{c} \tilde{x}[0] \\ \tilde{x}[1] \\ \cdots \\ \tilde{x}[N-2] \\ \tilde{x}[N-1] \end{array} \right]$ 可以发现矩阵 $Y$ 内部每一列的元素在进行周期性的位置轮换。
周期卷积计算可以在 MATLAB® 中使用命令 toeplitz(x,y) 得到，其中 x, y 为两个周期序列单周期内所有元素组成的向量，两个向量长度相同。

当两向量长度不等时，使用0进行补齐。
离散傅里叶变换（DFT）
当离散傅里叶序列变换的对象变成非周期有限长度序列时，此时的变换称为离散傅里叶变换（DFT）：
$X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}, 0 \leq n \leq N-1$
其反变换为：
$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-kn}, 0 \leq n \leq N-1$

离散傅里叶变换的性质

线性：$a x_1[n] + b x_2[n] \leftrightarrow a X_1[k] + b X_2[k], 0 \leq k \leq N-1$
2.对偶性：如果$x[n]\leftrightarrow X[k]$,那么$\tilde{X}[n]\leftrightarrow Nx[(-k)mod(N)],0\leq k\leq N-1$
3.$N$点循环时移：$x[(n-m)mod(N)]\leftrightarrow W_N^kmX[k],0\leq k\leq N-1$

可以发现：离散傅里叶级数是对离散时间傅里叶变换的结果进行采样，而一周期内的采样结果则为离散傅里叶变换的结果。
对于Z变换，$z=re^{j\omega}$，如果选择$r=1$，那么Z变换将退化为离散时间傅里叶变换：

$X(e^{j\omega}) = X(z)\big|_{z=e^{j\omega}}$

因此，Z域单位圆上的任意一点表示$e^{j\omega}$。而离散傅里叶变换是对离散时间傅里叶变换一周期内的采样，因此离散傅里叶变换是在Z域单位圆上的均匀采样。
\section*{循环卷积/圆周卷积}
定义两个序列非周期序列的$N$点$x[n]$、$y[n]$循环卷积/圆周卷积（Circular shift）为：

$x[n]\otimes_Ny[n]=\sum_{m=0}^{N-1}x[m]y[(n-m)mod(N)]$

$x[n]$和$y[n]$具有相同的序列长度，两个序列长度如果不相同，使用0进行补齐。
其物理意义是将其中一个序列反转（称为反褶）后，进行$N$点循环时移$m$次，与原序列线性卷积的结果。
同样地，循环卷积也可以被矩阵化为：

$x[n]\otimes y[n]=\begin{bmatrix} z[0] \\ z[1] \\ \cdots \\ z[N-2] \\ z[N-1] \end{bmatrix} = \begin{bmatrix} y[0] & y[N-1] & \cdots & y[2] & y[1] \\ y[1] & y[0] & \cdots & y[3] & y[2] \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ y[N-2] & y[N-1] & \cdots & y[0] & y[N-1] \\ y[N-1] & y[N-2] & \cdots & y[1] & y[0] \end{bmatrix} \begin{bmatrix} x[0] \\ x[1] \\ \cdots \\ x[N-2] \\ x[N-1] \end{bmatrix}$

利用矩阵化后的式子可以高效地在时域计算循环卷积。
在频域上，循环卷积对应两个序列DFT的乘积：

$x[n] \otimes y[n] \leftrightarrow X[k]Y[k]$

当 $N$ 大于两个序列的长度时，直接将两个序列的长度用0填充到长度 $N$，再进行循环卷积。
当 $N$ 小于两个序列的长度时，循环卷积时则会发生混叠（Aliasing）。长度为 $L$ 的序列 $x[n]$ 发生混叠的过程表示为：

$\begin{aligned} & x[0], x[1], \ldots, x[N], \ldots, x[L-2], x[L-1] \\ & \downarrow \\ & x[0] + x[N], x[1] + x[N+1], \ldots, x[N-1] + x[2N-1] \end{aligned}$

\section{循环卷积与线性卷积的关系}
当循环卷积的点数大于 $2L-1$（即线性卷积的长度）时，其结果与线性卷积 $\left( x[n] \backslash ^ y[n] \right)$ 完全相同。
\section*{循环卷积与周期卷积的关系}
如果 $\tilde{x_1}[n]$ 、 $\tilde{x_2}[n]$ 分别对应是 $x_1[n]$ 、 $x_2[n]$ 以周期为 $N$ 的延拓，有：

$(x_1[n] \otimes_N x_2[n]) R_N = \tilde{x_1}[n] \tilde{\otimes}_N \tilde{x_2}[n]$

$R_N$ 表示以周期为 $N$ 的延拓。
即在周期卷积对象的主值序列是循环卷积对象时， $N$ 点循环卷积是 $N$ 点周期卷积的主值序列。