数字信号处理中基2 FFT算法的教学研究

摘 要 基2 FFT算法是数字信号处理课程中的重点知识点之一。以“引导思考、授以方法、锻炼能力”为教学设计原则，探索以问题引导算法思想、分层次数学推导、应用流图计算及结合MATLAB验证多角度开展课堂教学的教学方法。作为数字信号处理课程建设的一部分，基2 FFT算法的教学研究有利于促进数字信号处理课程的教育教学发展。

关键词 数字信号处理 FFT 教学研究

中图分类号：G424 文献标识码：A

0 引言

快速傅里叶变换FFT（Fast Fourier Transform）是离散傅里叶变换DFT（Discrete Fourier Transform）的快速算法。数字信号处理学科随FFT的出现和发展而迅速得到发展。因此，FFT是数字信号处理课程中的重要内容。基2FFT算法是FFT的最基本算法，也是应用最多的算法。

FFT的教学具有数学推导多、算法流图多的特点，学生在学习时容易出现陷入繁琐的公式流图不得要领的现象，课程学习结束后受益不大。作者针对数字信号处理中基2FFT算法教学内容进行教学探索和研究。

1 教学设计原则

中国有句古话叫“授人以鱼不如授人以渔”，联合国教科文组织曾谈到：今后的文盲将不再是不识字的人，而是不会自学和学了知识不会应用的人。①这些都说明了教以方法或某种信念的重要性。对于高等教育，一个好的称职的教师，不但要给学生以知识，还要教会学生自学和应用的方法。作者认为，高校的课程学习不仅要为学生今后专业化的职业奠定知识基础，还要让学生学到解决问题的方法与思路，后者对学生长远的职业发展和能力提升意义更为重大。基于这样的教学理念，教学设计的总体原则为引导思考、授以方法、锻炼能力。在基2FFT算法教学中探索问题引导算法思想、分层次数学推导、应用流图计算及结合MATLAB验证多角度开展课堂教学。

2 算法原理的教学设计

2.1 问题引导算法思想

以问题引导算法核心思想的展开，通过互动式教学方式提出问题、讨论问题，进而得到解决问题的办法。

（1）提出问题1：直接计算N点DFT的计算量有多大？

讨论问题：直接计算N点DFT总共需要计算N2次复数乘法和N（N-1）～ N2次复数加法，复数乘法和复数加法次数均与N2成正比。直接计算DFT的算法复杂度是O（N2），随着N的增加，计算量将是惊人的。②

解决问题：通过减小N降低运算量，提高运算速度。

（2）提出问题2：在长序列分解为短序列的过程中短序列长度是多少合适？

讨论问题：DFT的最小运算点数是2点。2点和4点DFT计算没有复数乘法，为后面的基2算法、基4算法及分裂基算法打好基础。

解决问题2：要定义最小运算单元的点数M——基，可分为基3算法、基3算法、基4算法等。

（3）提出问题3：长序列分解为短序列的方法是什么？

讨论问题：长序列的分解

解决问题：长序列分解为短序列的方法——抽取方法，分为时间抽取和频率抽取。

最后加以总结：FFT算法的核心思想就是按照一定的规则（抽取方法）将N点长序列分解为短序列，直到分解为最小运算单元点数（基）M，然后计算M点DFT，将计算所有M点DFT结果组合为N点DFT。这种问题引导教学内容展开的教学设计一方面可以更深层次地引导学生理解：任何算法的存在一定有其应用背景和所针对解决的问题。另一方面，教会学生解决问题一般的方法与思路，从而有效提高学生发现问题、解决问题能力。

2.2 分层次的数学推导

在我校教学中分为卓越班、普通班，学生的数学基础和学习能力的存在差异。针对不同层次的学生，在教学上采用不同深度的算法数学推导。

（1）对于普通班学生按照常规的多步分解展开算法的数学推导。

以时间抽取基-2 FFT算法为例。首先将长度为N=2L的序列（）按序号是奇数还是偶数分为两个短序列（）和（）。（）是（）的N点DFT ，可计算为：

其中（）是（）的N/2点DFT，（）是（）的N/2点DFT。N点DFT（）变成两个N/2点DFT（）和（）的组合，其数学描述为（） = （） + （）。

（）和（）的计算采用相同的长序列分解为短序列的计算方法，即将N/2点DFT变成两个N/4点DFT的组合。以此类推，直至分解到最小运算单元2点。

（2）对于卓越班学生采用多基多进制的一般数学表达式展开算法的数学推导。

以N=8基-2频率抽取FFT为例。

i. 首先设置变量及其维数。

N=2L，N=8，维数为3，N = 讇譺0 ，其中===2。此时设置6个变量表示输入序列序号和输出序列序号：0≤≤，0≤≤，0≤≤，0≤≤，0≤≤，0≤≤。为了满足原位运算，输入与输出必须有一个为倒位序。设定输入（）自然位序，输出（）倒位序，因此的三维表达式为 = + 2 + 和。两个式子所定义的位序可以互为倒位序。

ii. 列写表达式，对分解，并化简。

求和从最高位开始，并且由于是DIF-FFT算法，频率抽取是频域自变量按照奇偶分解。因而化简是对的二进制表示进行的。

由数学运算表达式可以准确地画出对应流图，其中和是级间旋转因子。可以按照输入（）和输出（）位序的不同得到2个原位运算图。

这种分层次教学设计既可以确保普通班学生能够理解掌握基2算法的数学机理，又可以让卓越班学生在此基础上掌握通用的多基多进制数学表达式推导方法，启发卓越班学生应用自行推导其他单基单进制、多基多进制算法，培养学生的学习迁移能力。

表1 时间抽取与频率抽取的对比表

2.3 两种抽取列表对比

在两种抽取方法的算法学习后，时间抽取与频率抽取对比这部分教学内容的设计是：首先让学生分组讨论两种抽取方法的区别和共性，列表对比；然后每个小组讨论结论做简短的陈述；教师作点评、补充及总结。最终对比列表见表1，这种教学方式引导学生掌握知识归纳总结的方法，提高分析归纳能力。

2.4 流图的画法与应用

总结出流图5步画法，③步骤如下：（1）画出N条平行数据线。（2）确定输入和输出的位序。输入和输出其中一个为自然位序，另一个为倒位序，以满足原位运算。（3）画蝶形结。邻近倒位序的蝶形结的距离最近，邻近自然位序的蝶形结的距离最远，各级蝶形结的距离按照运算级而逐渐变大（输入是倒位序情况）或者变小（输入是自然位序情况）。（4）为每个蝶形结添加“-1”。（5）添加旋转因子。如果是时间抽取，则旋转因子位于每级蝶形结的前面，而且第一级旋转因子为，其余各级旋转因子按规律添加。如果是频率抽取，则旋转因子位于每级蝶形结的后面，而且最后一级旋转因子为，其余各级旋转因子按规律添加。

上述5步画法体现了原位运算、输入输出互为倒位序及旋转因子规律特点，可用于两种抽取方法的基2-FFT原位算法的蝶形流图绘制，便于记忆和掌握。

流图的应用：

以4点基-2 DIF-FFT算法流图为例，利用4点基-2 DIF-FFT算法流图计算（） = {1，2，3，4}的（）。

最后将输出排成自然位序，得到（） = {10， + ，，}。教学上，要求学生会应用流图计算DFT。

2.5 运算量的MATLAB验证

在课堂上应用MATLAB验证FFT算法的效率，运行调用fft函数直接计算DFT的计算程序和利用矩阵运算DFT的程序，利用cputime函数比较两种程序运算时间，让学生直观体会随着DFT点数的增加，FFT算法的有效性越显著。

3 结束语

作者以多年教学积累为基础，以“引导思考、授以方法、锻炼能力”为教学设计原则，探索问题引导算法思想、分层次数学推导、应用流图计算及结合MATLAB验证多角度的课堂教学设计，总结出益于学生知识构建和学习迁移的教法。它作为数字信号处理课程建设的一部分，有利于促进数字信号处理课程的教育发展。

基金项目：北京信息科技大学2011年课程建设项目（数字信号处理

注释

① 百度百科.授人以鱼不如授人以渔[DB/OL].http：//baike.baidu.com/linkurl= 8B5I7Xus44LQ9bFzvVbVHqc4kbThKye-BgQFeNWm5kfz_szUqQS86o fetp1bSjmZ.

② 郑方，徐明星.信号处理原理[M].北京：清华大学出版社，2003.8.

③ 焦瑞莉，罗倩，汪毓铎，顾奕.数字信号处理[M].北京：机械工业出版社，2012.6.