数字信号处理翻转课堂笔记9

The Flipped Classroom9 of DSP

对应教材：《数字信号处理（第五版）》西安电子科技大学出版社，丁玉美、高西全著

一、要点

1、DFT的计算复杂度问题和减少计算量的思路；
2、时域抽取法基2FFT（DIT-FFT）的原理及其蝶形运算分解图（重点）；
3、直接计算DFT和用DIT-FFT的计算量比较；
4、DIT-FFT的运算规律及编程思想（难点，一般了解）。

二、问题与解答

1、画出16点序列的DIT-FFT蝶形运算分解图，介绍DIT-FFT算法的思路和基本原理，分析各级蝶形运算旋转因子的构成特点。
2、详细对比分析直接计算DFT和利用DIT-FFT的计算量，举例说明FFT在减少计算量方面的优势。
3、任取1个序列（实或复序列均可），分别用MATLAB直接计算（直接计算DFT的函数参见实验二指导书）和用DIT-FFT计算（采用fft函数）其DFT（512点以上），利用MATLAB的计时函数tic、toc，分别统计直接计算和FFT计算所需的时间，比较其计算时间差异，与理论上的计算量差异进行比较分析。若多次重复运行以上程序，会发现每次运行之后统计的计算时间并不完全相同，查阅相关资料，分析为什么会产生这样的结果（非本课程内容，请从计算机操作系统工作机制的角度去分析）。
4、如果采用DFT计算两个序列的线性卷积（参见第8次课问题1），其中的DFT和IDFT都采用FFT快速算法来实现，分析计算两个长度为N的复序列的线性卷积，分别需要多少次复数乘法和复数加法。与直接计算线性卷积相比，其计算量降低了多少？分别列出N=8,64,512,2048时的计算量（复数乘法和加法次数）对比表并进行分析总结。基于MATLAB平台，编写程序分别实现直接计算（可以用conv函数）和采用FFT计算两个2048点复序列的线性卷积，用tic和toc分别统计其计算时间，并进行对比验证。
5、FFT算法中的“原位计算”指的是什么？满足“原位计算”的特点对于FFT在计算机平台上的实现有什么好处？
6、FFT算法中，序列的“顺序”和“倒序”分别指什么？DIT-FFT算法的输入输出分别是如何排序的？查阅相关资料，了解有没有其他的排序方式的DIT-FFT算法，如果有，是如何实现的？能不能让输入和输出序列都是“顺序”的形式？如果有，这种形式的算法有什么缺点？

1、16点序列的DIT-FFT蝶形运算分解图

画出16点序列的DIT-FFT蝶形运算分解图，介绍DIT-FFT算法的思路和基本原理，分析各级蝶形运算旋转因子的构成特点。

旋转因子的变化规律：

2、理论分析DFT和DIT-FFT的计算量

详细对比分析直接计算DFT和利用DIT-FFT的计算量，举例说明FFT在减少计算量方面的优势。

3、用matlab实验比较DFT和FFT的运算速度

任取1个序列（实或复序列均可），分别用MATLAB直接计算（直接计算DFT的函数参见实验二指导书）和用DIT-FFT计算（采用fft函数）其DFT（512点以上），利用MATLAB的计时函数tic、toc，分别统计直接计算和FFT计算所需的时间，比较其计算时间差异，与理论上的计算量差异进行比较分析。若多次重复运行以上程序，会发现每次运行之后统计的计算时间并不完全相同，查阅相关资料，分析为什么会产生这样的结果（非本课程内容，请从计算机操作系统工作机制的角度去分析）。

代码：
DFT函数：

function [Xk]=dft(xn,N)
n=[0:1:N-1];
k=[0: N-1];
WN=exp(-j*2*pi/N);
nk=n'*k;
WNnk=WN.^(nk);
Xk=xn*WNnk;    %  采用矩阵相乘的方法

运行：

for a=[1 2 3 4];
N=512*2.^a;
xn=1:N;
tic
dft (xn,N);
toc
tic
fft (xn,N);
toc
end

运行结果：

由图可见，每次直接计算的时间都大于采用FFT算法的时间。
每次运行时间不一样的原因：
与操作系统的时间调度有关，操作系统给每个线程分时间片调度，每次调度的程序不同，所以运行时间不同。

4、利用FFT计算与直接计算复序列的线性卷积

如果采用DFT计算两个序列的线性卷积（参见第8次课问题1），其中的DFT和IDFT都采用FFT快速算法来实现，分析计算两个长度为N的复序列的线性卷积，分别需要多少次复数乘法和复数加法。与直接计算线性卷积相比，其计算量降低了多少？分别列出N=8,64,512,2048时的计算量（复数乘法和加法次数）对比表并进行分析总结。基于MATLAB平台，编写程序分别实现直接计算（可以用conv函数）和采用FFT计算两个2048点复序列的线性卷积，用tic和toc分别统计其计算时间，并进行对比验证。
暂未完成，后续更新

5、“原位计算”及其优势

FFT算法中的“原位计算”指的是什么？满足“原位计算”的特点对于FFT在计算机平台上的实现有什么好处？

---

每个蝶形的两个输入数据只用于本蝶形运算;前一级的N个数据只用于求下一级的个点的数据,求出下一级,数据后前一级的数据不需要继续保留。这种利用同一存储单元存储蝶形计算输入、输出数据的方法称为“原位计算”。
对每个蝶形进行计算后,其结果可直接存入源数据所在的存储单元,从而节省数据存储器。

6、FFT算法中的顺序与倒序

FFT算法中，序列的“顺序”和“倒序”分别指什么？DIT-FFT算法的输入输出分别是如何排序的？查阅相关资料，了解有没有其他的排序方式的DIT-FFT算法，如果有，是如何实现的？能不能让输入和输出序列都是“顺序”的形式？如果有，这种形式的算法有什么缺点？

1）
顺序：自然顺序增加1，是在顺序数最低位加1，逢2向高位进位；
倒序：倒序数是在M位二进制最高位加1,逢2向低位进位；
2）
DIT-FFT算法输入倒序，输出顺序
DIF-FFT算法输入顺序，输出倒序

3）有，如图

输入顺序，输出倒序
4）

缺点为不能进行原位计算。

三、反思总结