傅立叶变换属于是那种难学难记，而且每隔上一段时间还要用一下的神奇玩意。为了下次被它背刺的时候没那么痛苦，谨作文一篇以供以后复习。
基础信息
- 离散傅立叶变换（Discrete Fourier Transform）用于有限长序列，有快速算法FFT（Fast Fourier Transform）。
- 基础表达式：N（区间长度），n（时间），k（频率）
- $X(k) = DFT[x(n)] = \Sigma^{N-1}_{n = 0}x(n)W^{nk}_{N},0\le k \le N-1$
- $x(n) = IDFT[X(k)] =\frac{1}{N} \Sigma^{N-1}_{k = 0}X(k)W^{-nk}_{N},0\le n \le N-1$
- 而$W_N = e^{-j\frac{2\pi}{N}}$
- 为频率时要/N且有负号
傅立叶变换一家
| 时域 | 变换名称 | 频域 |
|---|---|---|
| 连续非周期 | FT | 连续非周期 |
| 连续周期 | FS | 离散非周期 |
| 离散非周期 | DTFT | 连续周期 |
| 离散周期 | DFS | 离散周期 |
「S」指级数，「T」为变换
离散傅立叶级数DFS
有限长序列$x(n)$的Z变换为：$X(z) = \Sigma^{N-1}_{n = 0}x(n)z^{-n}$
若令$z = W^{nk}_{N}$，则该式就变成了DFS，所以可以说，DFS可以看做$x(n)$的Z变换在单位圆上按等间隔角$\frac{2\pi}{N}$抽样得到。
DFS数学性质
线性性质：$DFS[ax_1(n) + bx_2(n)] = aX_1(k) + bX_2(k)$
位移性质：
- $DFS[x(n + m)] = W^{-mk}_NX(k)$
- DFT位移要改符号
- $DFS[W^{ln}_Nx(n)] = X(l + k)$
对偶性质：$DFS[X(n)] = Nx(-k)$
共轭对称性质：
- $X(k)$只有实部 = $x(n)$实部偶对称，虚部奇对称
- $X(k)$只有虚部 = $x(n)$虚部偶对称，实部奇对称
DFS周期卷积和
DFS相乘 <=> 原函数作周期卷积和然后再DFS
周期卷积和方法：对一个周期内（两者周期相同）先做卷积，再作周期延拓。
DFS与DFT
DFT为有限长序列，DFS来自周期离散序列，而DFS在$0 \le n \le N$之间的部分就是DFT。
用DFT分析一段时域连续非周期信号
即用DFT来模拟FT变换
分为三步：a）时域离散化。b）时域截断。c）频域离散化
a的离散化让频域变成周期的（原信号需要是限带的防止混叠），b的时域截断用于防止当频域抽样时时域发生混叠，最后做c中的频域离散化，对频域进行抽样。
设$T,F_0$分别为时域和频域的抽样间隔，$T_0,f_s$分别为时域和频域的长度，$N$为抽样点数
则有：$T_0 = N \cdot T = \frac{N}{f_s}$，$f_s = N \cdot F_0$，$T \cdot f_s = T_0 \cdot F_0 = 1$
代入有：$X(jk\Omega) = T \cdot DFT[x(n)]$，$x(n) = \frac{1}{T}IDFT[X(k)]$
用DFS/DFT分析其他信号
用DFS逼近FS
步骤：a）时域离散化。b）频域截断
最后得到：$X(k) = \frac{1}{N}DFT[x(n)]$，$x(n) = N \cdot IDFT[X(k)]$
用DFT逼近DTFT
步骤：a）频域离散化。b）时域截断
最后得到：$X(n) = IDFT[X(k)]$，$X(e^{j\frac{2\pi k}{N}}) = DFT[x(n)]$
分析信号的问题
- 混叠现象：因为抽样导致在另一个域中出现重叠（若抽样的频率太小就会混叠，标准：$f_s > 2f_h$）
- N一定时，信号最高频率与频率分辨率是相互矛盾的
- 快速估计最高频率：$f_h = \frac{1}{2(b-a)}$，其中ab为时域变化最快的相邻波峰波谷
- 栅栏效应：频域离散化后会漏掉一些分量，故可以在时域后面补零。
- 提高了计算分辨率，但物理频率分辨力没有。
- 截断处理：相当于在另一个域卷积一个sinc函数，会有频谱泄漏（频谱更宽了）和谱间干扰（产生波纹）
DFT的性质
线性
注意抽样点数为大的那个
序列移位
若$X(k) = DFT[x(n)]$，则$IDFT[X((k+l))_nR_n(k)] = W^{nl}_nx(n)$
共轭对称性
有限长的$x(n)$的周期延拓称为$\widetilde x(n)$，在复数域上，称$x(n)$正的和负的部分分别为$\widetilde x_ep，\widetilde x_op$，而$\widetilde x(n)$正的和负的部分分别为$\widetilde x_e，\widetilde x_o$
则有：$DFT{Re[x(n)]} = X_ep(k) = \frac{1}{2}[X((k))_N + X\bar {(N - k)}]R_N(k)$，$DFT{iIm[x(n)]} = X_op(k) = \frac{1}{2}[X((k))_N - X\bar {(N - k)}]R_N(k)$
可以用这个公式来减少DFT的次数。
圆周卷积和
当$Y(k) = X_1(k) \cdot X_2(k)$时，则有$y(n) = IDFT[Y(k)] = [\Sigma ^{N-1}_{m = 0}x_1(m)x_2(n-m)_N]R_N(n)$。
相似的，有：当$y(k) = x_1(k) \cdot x_2(k)$时，则有$Y(n) = DFT[Y(k)] = \frac{1}{N}[\Sigma ^{N-1}_{m = 0}X_1(m)X_2(n-m)_N]R_N(n)$。
卷积圆周和和周期圆周和几乎一样，但和普通线性卷积不一样。
用圆周卷积和计算线性卷积
设$N_1,N_2$分别为$x_1(n),x_2(n)$的序列长度，则有：$N \ge N_1 + N_2 -1$时二者相等（将两个序列都补齐为$N$），否则会产生交叠现象，此时不能用圆周卷积和代替。
长序列卷积短序列时，可采用分段卷积方法：
- 重叠相加法：将长的序列分段，分别和短的卷积，最后再相加。
- 重叠保留法：舍弃掉超出的一部分卷积，把这部分替换为上一次的输入值，有点迷。
卷积计算的变换域解法
通过在频域相乘避免直接在时域相卷积的方法。
圆周相关
$R_xy = X(k)\bar Y(k)$，所以实数下$r_xy$为$xy$的圆周卷积和。
帕塞瓦定理
$\Sigma^{N-1}_{n=0}x(n) \dot{y}(n) = \frac{1}{N}\Sigma ^{N-1}_{k=0}X(k)\dot{Y}(k)$
频域抽样定理
定理：频域抽样点数$N \ge $原序列长度$M$时，可由频谱抽样恢复原序列。
插值函数：$X(z) = \Sigma ^{N-1}_{k=0}X(k) \cdot \Phi_k(z)$，而$\Phi_k(z) = \frac{1}{N} \cdot \frac{1-z^{-N}}{1-W^{-k}_N\cdot z^{-1}}$为插值函数。
插值函数零点：$z = W_N^{r},r = 0,1,…,N-1$，极点：$z = W_N^k$一个极点，说明在$r = k$处不为零，其余零点都为零。
内插恢复公式：$X(e^{jw}) = \Sigma^{N-1}_{k = 0}X(k) \cdot \Phi(\omega - \frac{2\pi k}{N})$