第一章 离散时间信号与系统
第二章 z变换和离散时间傅里叶变换(DTFT)
第三章 离散傅里叶变换
第四章 快速傅里叶变换（FFT）
第五章 数字滤波器的基本结构
第六章 无限长单位冲激响应(IIR)数字滤波器的设计方法
第七章 有限长单位冲激响应(FIR)数字滤波器的设计方法
第八章 序列的抽取与插值——多抽样率数字信号处理基础
第四章 快速傅里叶变换（FFT）
4.1 直接计算DFT的运算量，减少运算量的途径
直接计算DFT的问题
直接计算N点DFT需要：
- N^2次复数乘法，N(N-1)次复数加法。
- 4N^2次实数乘法，2N(2N-1)次实数加法。
改善DFT运算效率的基本途径
对于旋转因子W^{nk}_N，有以下性质：
- W^{nk}_N的共轭对称性；
- W^{nk}_N的周期性；
- W^{nk}_N的可约性。
利用这些性质可以使DFT运算的某些项合并，可以将长序列分解成短序列的DFT。常用的快速傅里叶变换算法分为两大类：DIT和DIF。
4.2 按时间抽选(DIT)的基-2 FFT算法（库里-图基算法）
算法原理
-
基-2 FFT：N为2的整数次幂的FFT。
-
按照奇偶将x(n)分为两个N/2点的子序列：
x(n) \begin{cases} x_1(r)=x(2r)&,r=0,1,...,\frac N2-1\\ x_2(r)=x(2r+1)&,r=0,1,...,\frac N2-1 \end{cases}
将x(n)做傅里叶变换：
\begin{aligned} X(k)=&\sum^{N-1}_{n=0}x(n)W_N^{nk}\\ =&\sum_{n为偶数}x(n)W_N^{nk} +\sum_{n为奇数}x(n)W_N^{nk}\\ =&\sum_{r=0}^{\frac N2-1}x(2r)W_N^{2rk}+\sum_{r=0}^{\frac N2-1}x(2r+1)W_N^{(2r+1)k}\\ =&\sum_{r=0}^{\frac N2-1}x_1(r)W_{N/2}^{rk}+W_N^{k}\sum_{r=0}^{\frac N2-1}x_2(r)W_{N/2}^{rk}\\ =&X_1(k)+W^k_NX_2(k),0\le k\le \frac N2-1 \end{aligned}
-
问题：
X(k)=X_1(k)+W^k_NX_2(k)中，0\le k \le \frac N2-1只能得到前\frac N2个点的DFT，此时我们需要用到W^{rk}_{N/2}的周期性：
\begin{aligned} X_1(k+\frac N2)&=\sum^{\frac N2-1}_{r=0}x_1(r)W^{r(k+\frac N2)}_{N/2}\\ &=\sum^{\frac N2-1}_{r=0}x_1(r)W^{rk}_{N/2} \\&=X_1(k) \end{aligned}
\begin{aligned} W^{(k+\frac N2)}_{N}X_2(k+\frac N2) = -W^k_NX_2(k) \end{aligned}
-
结果：
N点X(k)可以表示成前\frac N2点和后\frac N2点两部分：
前半部分：
X(k)=X_1(k)+W_N^kX_2(k)
后半部分：
X(k)=X_1(k)-W^k_NX_2(k)
用信号流图来表示：
表示一个蝶形结。
DIT FFT算法与直接计算运算量的比较
下图是2^3 =8个序列的FFT信号流图：
以此类推：当N=2^L时，采用基-2 FFT和直接计算DFT的运算量分别为：
| 复乘 | 复加 | |
|---|---|---|
| 基-2 FFT | \frac N2\log_2N | N\log_2N |
| 直接计算DFT | N^2 | N(N-1) |
DIT-FFT算法的特点
-
原位运算（同址运算）
每列计算都是由N/2个蝶形运算构成的，蝶形结的两个输出值仍存放回蝶形两个输入所在的存储器中。
-
倒位序规律
输出序列按照倒位序进行排列。例如：在N^3 = 8中，3对应的二进制数为011，其倒位序为110，对应的十进制数为6，故3号位存储的序列应为x(6)。
-
蝶形运算两节点的“距离”
当输入为倒位序，输出为正常顺序时，第m级蝶形，每个蝶形的两节点“距离”为2^{m-1}。
-
系数变化规律：
对于N=2^L，一共有L列系数，最后一列系数有\frac N2个类型，为：W^0_N,W^1_N,W^2_N,...,W^{N/2-1}_N。由后向前每推进一列，系数类型减半，且为上一列偶数序号那一半。
4.3 按频率抽选(DIF)的基-2 FFT算法（桑德-图基算法）
算法原理
取N=2^L：
\begin{aligned} X(k)&=\sum^{N-1}_{n=0}x(n)W_N^{nk}=\sum^{\frac N2-1}_{n=0}x(n)W_N^{nk}+\sum^{N-1}_{n=\frac N2}x(n)W_N^{nk}\\ &=\sum^{\frac N2-1}_{n=0}x(n)W_N^{nk}+\sum^{\frac N2-1}_{n=0}x(n+\frac N2)W_N^{(n+\frac N2)k}\\ &=\sum^{\frac N2-1}_{n=0}\bigg[x(n)+W^{\frac N2k}_Nx(n+\frac N2)\bigg]W^{nk}_N\\ &=\sum^{\frac N2-1}_{n=0}\bigg[x(n)+(-1)^kx(n+\frac N2)\bigg]W^{nk}_N \end{aligned}
X(k)=\begin{cases} X(2r)&=\sum\limits^{\frac N2-1}_{n=0}\bigg[ x(n)+x(n+\frac N2)\bigg]W^{n2r}_N\\ X(2r+1)&=\sum\limits^{\frac N2-1}_{n=0}\bigg[ x(n)-x(n+\frac N2)\bigg]W^{n2(r+1)}_N\\ \end{cases}
蝶形图为：
DIF-FFT算法的特点：
-
原位运算
-
两节点间的距离：2^{L-m}=\frac N{2^m}。
-
系数变化规律：
对于N=2^L，一共有L列系数，第一列系数有\frac N2个类型，为：W^0_N,W^1_N,W^2_N,...,W^{N/2-1}_N。由前向后每推进一列，系数类型减半，且为上一列偶数序号那一半。
-
X(k)为倒位序排列。
4.4 DIT-FFT与DIF-FFT的异同
不同
-
DIT输入倒位序，输出顺序；DIF输入顺序，输出倒位序。
-
蝶形运算不同：
DIT的系数相乘出现在加减法运算之前；
DIF的系数相乘出现在加减法运算之后。
相同
- 两种算法运算量相同，都有L列蝶形运算，有N/2个蝶形结。
- 两种算法均可以原位运算。
DIF和DIT的基本鲽形是互为转置的
转置就是将所有的之路方向都反向，交换输入和输出，但节点变量值不交换。
4.5 离散傅里叶反变换(IDFT)的快速算法IFFT
方法一（不常用）
在FFT中：
- 用W^{-r}_N来代替W^{r}_N；
- 在L列中每列分别乘一个\frac12因子；
- 输入输出对调。
经过如上的方法：
- DIT-FFT变为DIF-IFFT；
- DIF-FFT变为DIT-IFFT。
方法二（常用）
\begin{aligned} x(n)&=\frac 1N\sum^{N-1}_{k=0}X(k)W_N^{-nk}\\ &=\frac 1N\bigg[\sum^{N-1}_{k=0}X^*(k)W_N^{nk}\bigg]\\ &=\frac 1N\bigg\{\mathrm{DFT}[X^*(k)]\bigg\}^* \end{aligned}
步骤为：X(k)→求共轭→FFT→求共轭→乘\frac 1N→x(n)。
方法三
令p(n)=\sum\limits^{N-1}_{k=0}X(k)W_N^{nk}，则：
\begin{aligned} x(n)&=\frac 1Np(N-n)\\ &=\frac 1N\sum\limits^{N-1}_{k=0}X(k)W_N^{(N-n)k}\\ &=\frac 1N\sum\limits^{N-1}_{k=0}X(k)W_N^{-nk} \end{aligned}
步骤为：X(k)→由FFT得p(n)→计算\frac 1Np(N-n)→x(n)
4.6 基-2 FFT流程图
- 该内容非考点，了解即可
4.9 利用FFT计算线性卷积
所谓FFT计算线性卷积，就是将DFT计算线性卷积的算法改为FFT算法。
问题
如果x(n)的点数很多的时候，比如说1025，那么我们需要补零点到2048，很不经济，因此我们需要用分段过滤的方法来计算线性卷积。
将x_i(n)表示x(n)的第i段：
\begin{aligned} x_i(n)=\begin{cases} x(n),&iL\le n\le(i+1)L-1\\ 0,&其他n \end{cases} \end{aligned}
则输入序列可以表示成：
x(n)=\sum\limits^{\infty}_{i=0}x_i(n)\\ \begin{aligned} y(n)&=x(n)*h(n)=\sum^{\infty}_{i=0}x_i(n)*h(n)\\&=x_0(n)*h(n)+x_1(n)*h(n)+x_3(n)*h(n)+... \end{aligned}
重叠相加法
设h(n)的点数为M，信号x(n)为很长的序列。将x(n)分为很多段，每段为L点，L选择和M的数量级相同。每一个y_i(n)=x_i(n)*h(n)都可用上面讨论的快速卷积方法计算。
因此，将x(n)分段后，其每段的卷积结果y_i(n)都不能完全和相应的y(n)相等，需要把上一段的后过渡过程和本段的前过渡过程对应相加，才能得到完整的y(n)。
- 用FFT法实现重叠相加法的步骤如下：
- 计算N点FFT，H(k)=\mathrm{DFT}[h(n)]；
- 计算N点FFT，X_i(k)=\mathrm{DFT}[x_i(n)]；
- 相乘，Y_i(k)=X_i(k)H(k)；
- 计算N点IFFT，y_i(n)=\mathrm{IDFT}[Y_i(k)]；
- 将各段y_i(n)（包括重叠部分）相加。
重叠保留法
与重叠相加法比较：
相同之处：先将x(n)分段，每段L个点。
不同之处：序列中补零处不补零，而是在每一段的前边补上前一段最后的(M-1)个值，组成L+M-1点序列x_i(n)。
由于x_i(n)为N=L+M-1点序列，这时用FFT实现h(n)和x_i(n)的N点圆周卷积，圆周卷积结果的前(M-1)个值发生混叠，不等于线性卷积值，必须舍去。
此时的到的y(n)的长度与L相同。
在重叠保留法中y_i(n)，不能恢复出y(n)的后过渡部分。
实序列的FFT算法
-
一次N点FFT同时计算两个N点实序列的FFT
设X_1(k)=\mathrm{DFT}[x_1(n)]、X_2(k)=\mathrm{DFT}[x_2(n)]。
令x(n)=x_1(n)+\mathrm jx_2(n)，则X_1(k)=X_{ep}(k)，X_2(k)=-\mathrm jX_{op}(k)。
-
一次N点FFT计算一个2N点实序列的FFT
令：
x_1(n)=x(2n)\\x_2(n)=x(2n+1)\\n=0,1,...,\frac N2-1
再令：
y(n)=x_1(n)+\mathrm jx_2(n)
则：
X_1(k)=Y_{ep}(k)\\X_2(k)=-\mathrm jY_{op}(k)
再由DIT-FFT可得：
\begin{cases} X(k)=X_1(k)+W^k_{2N}X_2(k)\\X(k+N)=X_1(k)-W^k_{2N}X_2(k) \end{cases}
习题
-
（1）画出基-2按频率抽取（DIF）的4点FFT的信号流图。 （2）已知四点序列x(n)=\{\underline4,2,1,3\}，用上题的流图计算其4点DFT。 （3）试计算序列y(n)=x((n))_4R_8(n)的8点离散傅里叶变换Y(k)。 （4）假设已有计算N点DFT的FFT程序，请给出用此程序计算N点X(k)的IFFT方法。
-
答案
-
答案
-
答案
-
答案
评论区