论文部分内容阅读
[摘 要]离散傅里叶变换（DFT）及快速傅里叶变换（FFT）是数字信号处理课程中的核心内容之一。传统教学方法中的先抛概念定理，再推导计算的方法存在学生课堂上难以立即接受，课下难以深入理解的问题。以学生掌握的既有知识为基础，通过对DFT的矩阵分析，引导学生从矩阵理论思考DFT的快速算法，得出与经典FFT算法相同的计算效果和复杂度，可以取得较好的教学效果。该文对这一教学方法进行了探索实践，其成果可以促进数字信号处理课程的教育教学发展。
[关键词]数字信号处理;矩阵分析;教育;教学研究
[中图分类号] G642.0 [文献标识码] A [文章编号] 2095-3437（2021）09-0098-03
一、引言
数字信号处理中的部分知识利用常规方法讲解，学生不容易理解和掌握。如能通过已学习的课程，从熟悉的学习内容引申开来，建立新的理论体系和知识单元，而不是直接抛出新的概念和定理，造成學生学习和理解上的困难，就可以很大程度上提高学生的理解能力。
在数字信号处理课程中，离散傅里叶变换（DFT）及其快速算法——快速傅里叶变换（FFT）是核心内容之一。在讲授快速傅里叶变换（FFT）时，直接利用DFT的公式进行推导[1～4]，内容让学生觉得晦涩难懂。而且要在课堂中理解掌握蝶形运算结构的引入、推导和简化DFT的过程，往往很难做到。教学实践表明，直接利用教材中的方法进行讲解，学生的理解往往似是而非，教学效果差强人意。刘元会对时间抽取的FFT 矩阵形式进行了研究，得出了DFT的矩阵形式，具有一定的可行性。但该方法以时间抽取的基-2FFT 算法原理为引，导出矩阵形式，仍需要学生进一步对DFT公式进行化简变形。且抛出若干定义和引理，不利于学生理解和掌握[5]。姚力波从矩阵理论的角度出发，分析了数字信号处理，并对DFT和数字滤波器（DF）的矩阵表示进行研究，得出了矩阵理论是“数字信号处理”课程最基础的数学理论的结论，具有一定的教学参考价值[6]。
文献[7]指出，根据数字信号处理课程的特点和教学中存在的问题，教学方法既要强调教学内容的意义，又要形象化教学，循序渐进，注重实际应用。姜恩华等也对DFT的教学进行了探索[8]。本文根据数字信号处理教学过程中的实践经验，对FFT的教学方法进行探索，并通过矩阵方法的引入，从另一方面讲授DFT的快速算法。
二、FFT教学的引入
相比傅立叶家族中的其他变换，DFT是实用性最强的算法。该算法首次实现了频域的离散化，信号在时域和频域均是离散的，非常便于计算机的有效处理。但是DFT在具体的工程实践中一开始并没有得到很大应用，其原因就在于巨大的运算量。
因为当序列的长度N很大时，直接计算N点的DFT的计算量是非常大的。即使采用计算机也很难对问题进行实时处理，所以在相当长的一段时间内，DFT算法并没有得到真正的运用。直到1965年情况才发生了根本改变。在1965年，IBM公司的Cooley和MIT的Tukey这二位科学家提出了一种离散傅立叶变换的快速算法：快速傅里叶变换，使得DFT的运算量降低一个数量级以上。一个以上数量级是因为它与序列的长度N取值有关系。
FFT算法大大推动了数字信号处理技术的快速发展。业界一直将1965年定为数字信号处理这门学科的诞生之年。因此，FFT算法在数字信号处理的发展史上占有很重要的地位。目前FFT算法已广泛应用于通信、雷达、生物医学等众多技术领域。如3G和4G通信中采用的正交频分复用（OFDM ）技术，采用的就是FFT算法。FFT算法算法优势明显，但是教学实践表明，直接用定义和公式推导来教学效果不理想，可以从其他方面考虑DFT的快速计算，与FFT计算殊途同归。
三、DFT计算量的分析
信号处理无论是时域还是频域的运算都是以乘法、加法和移位作为最基本的运算形式，因此对某一算法可以用所需的乘法次数和加法次数来衡量它的运算量和运算效率。同样对于DFT的运算量，我们只需分析它所需要的乘法次数和加法次数。前面的章节我们已经学过，对于N点有限长的序列[x（n）]，它的DFT的数学表达式乘加运算，如公式（1）所示。
引导学生由DFT矩阵形式分析计算量。DFT矩阵是N×N的矩阵，x是N×1的向量，由于[WnkN]为复数，因此[DNx]共需要N2次复数乘法，N（N+1）次复数加法，可以说N点DFT的乘法和加法次数均与N2成正比。当N比较大时，运算量增长非常快。如当N=64时需要4094次复数乘法和复数加法，而当N=2048时，需要4194304次复数乘法和复数加法。运算量很大。这对实时性很强的信号处理来说，如雷达信号处理，必将对系统的处理速度有着十分苛刻的要求。
引导学生思考是否存在解决办法，解决的途径在哪里呢？
四、DFT矩阵计算方法
由DFT矩阵形式的表达式可以看出，造成计算量巨大的原因是DFT矩阵中的复数旋转因子，因此需要着手分析DFT矩阵，看是否能对它进行处理，降低运算量。
不难证明：[W0N=1]，[WN2N=-1]，[WNN=1]，[WknN=Wk（N+n）N=Wn（N+k）N]，[Wk+N2N=-WkN]，[WkN=WmkmN]。
启发学生以8点DFT为例进行说明。
N点DFT的矩阵表示为：
要对这个矩阵进行运算化简，就要先对它进行一定的处理，考虑将[D8]的各列重新进行排列，使得它的奇数列全部都在偶数列的前面。
也就是变成这个矩阵：
由已有的知识可知，[D′8]矩阵可由[D8]右乘以置换矩阵而来，置换哪一列，就相当于置换矩阵对应行中此列为1。基于这种运算，假设置换矩阵为[P8]，由于[D8]变换到[D′8]，对于偶数列相当于将[D8]的第2列，第4列，第6列，置换到第5列，第6列，第7列，因此[P8]矩阵中第2行，第4行，第6行对应的第5列，第6列，第7列为1，也就是[P8]的元素[P8（2，5）=1]，[P8（4，6）=1]，[P8（6，7）=1];同样，对于奇数列，相当于将[D8]的第3列，第5列，第7列，置换到第2列，第3列，第4列，[P8（3，2）=1]，[P8（5，3）=1]，[P8（7，4）=1];第1列和第8列不用置换，因此[P8（1，1）=1]，[P8（8，8）=1]，其他元素为0，由此就可以写出置换矩阵： 接下来，对[D′8]进行化简，由[WNN=1]，[Wk+nNN=WkN]，k和n为整数，N=8，得到：
如果将[D′8]分成2×2的块矩阵，显然矩阵的块（1，1）和（2，1）是相等的，将其记为[D4]，再根据[WknNn=WkN]则有：
而对于块（1，2）和（2，2），它们之间也存在一定关系，观察可以发现，块（1，2）的元素乘以[W48]就能得到块（2，2）。因此，令
左乘[T4]相当于把第k行乘以[Wk-18]，块（1，2）和（2，2）就可以分别表示为[T4D4]和[-T4D4]，这样，就可以利用分块乘法实现DFT的计算，也就是：
也就是说，通过矩阵变换，将8点的DFT化简为两个N=4点的DFT。
由此启发学生，上述过程可以推广到N为任意偶数的情况。在实际应用中，通常取N=2k，k为正整数，因此某些场景下需要将数据序列补零满足上述条件。
通过以上分析，启发学生计算DFT的时间復杂度，并验证其结果。事实上，利用矩阵化简计算DFT与利用FFT算法的时间复杂度相等;对于复数乘法，需要的次数为[N2log2N]，复数加法次数为[Nlog2N]，相对直接计算DFT，运算效率为[N2N2log2N]，大大提高了计算速度。
五、结论
数字信号处理课程教学中，根据学生前期的知识储备，由已经熟知的矩阵分析方法深入思考离散傅里叶变换（DFT）的快速计算方法，可以避免学生陷入生涩的概念理解和繁复的公式推导中。文章对这一教学方法进行了探索研究，从矩阵角度理解、计算离散傅里叶变换（DFT），可以提高数字信号处理课程教学的有效性。事实上，数字信号处理中的数字滤波器设计、卷积、相关、相乘等知识点都有矩阵分析的数学理论基础，从这一方面入手，可以提升学生的理解能力和掌握程度。作为课程建设的一部分，矩阵分析教学方法的引入有利于促进数字信号处理课程的进一步发展。
[ 参 考 文 献 ]
[1] A.V.奥本海姆，R.W.谢弗，J.R.巴克.离散时间信号处理[M].刘树棠，黄建国，译.第2版.西安：西安交通大学出版社，2001.
[2] 胡广书.数字信号处理导论[M].北京：清华大学出版社，2005.
[3] 王世一.数字信号处理（修订版）[M].北京：北京理工大学出版社，1997.
[4] 高西全，丁玉美，阔永红.数字信号处理——原理、实现及应用.第2版[M].北京：电子工业出版社，2010.
[5] 刘元会，常安定.按时间抽取的FFT矩阵形式的研究[J].纺织高校基础科学学报，2008（4）：389-392.
[6] 姚力波，刘瑜，董凯，等.基于矩阵理论的“数字信号处理”教学研究[J].电气电子教学学报，2017（5）：97-99.
[7] 陈强，徐科军.以DFT为例探讨数字信号处理教学方法[J].中国电力教育，2012（6）：49-50.
[8] 姜恩华，杨一军，窦德召.数字信号处理课程中的傅里叶变换教学探索[J].廊坊师范学院学报（自然科学版），2017（1）：52-56.
[责任编辑：林志恒]
[关键词]数字信号处理;矩阵分析;教育;教学研究
[中图分类号] G642.0 [文献标识码] A [文章编号] 2095-3437（2021）09-0098-03
一、引言
数字信号处理中的部分知识利用常规方法讲解，学生不容易理解和掌握。如能通过已学习的课程，从熟悉的学习内容引申开来，建立新的理论体系和知识单元，而不是直接抛出新的概念和定理，造成學生学习和理解上的困难，就可以很大程度上提高学生的理解能力。
在数字信号处理课程中，离散傅里叶变换（DFT）及其快速算法——快速傅里叶变换（FFT）是核心内容之一。在讲授快速傅里叶变换（FFT）时，直接利用DFT的公式进行推导[1～4]，内容让学生觉得晦涩难懂。而且要在课堂中理解掌握蝶形运算结构的引入、推导和简化DFT的过程，往往很难做到。教学实践表明，直接利用教材中的方法进行讲解，学生的理解往往似是而非，教学效果差强人意。刘元会对时间抽取的FFT 矩阵形式进行了研究，得出了DFT的矩阵形式，具有一定的可行性。但该方法以时间抽取的基-2FFT 算法原理为引，导出矩阵形式，仍需要学生进一步对DFT公式进行化简变形。且抛出若干定义和引理，不利于学生理解和掌握[5]。姚力波从矩阵理论的角度出发，分析了数字信号处理，并对DFT和数字滤波器（DF）的矩阵表示进行研究，得出了矩阵理论是“数字信号处理”课程最基础的数学理论的结论，具有一定的教学参考价值[6]。
文献[7]指出，根据数字信号处理课程的特点和教学中存在的问题，教学方法既要强调教学内容的意义，又要形象化教学，循序渐进，注重实际应用。姜恩华等也对DFT的教学进行了探索[8]。本文根据数字信号处理教学过程中的实践经验，对FFT的教学方法进行探索，并通过矩阵方法的引入，从另一方面讲授DFT的快速算法。
二、FFT教学的引入
相比傅立叶家族中的其他变换，DFT是实用性最强的算法。该算法首次实现了频域的离散化，信号在时域和频域均是离散的，非常便于计算机的有效处理。但是DFT在具体的工程实践中一开始并没有得到很大应用，其原因就在于巨大的运算量。
因为当序列的长度N很大时，直接计算N点的DFT的计算量是非常大的。即使采用计算机也很难对问题进行实时处理，所以在相当长的一段时间内，DFT算法并没有得到真正的运用。直到1965年情况才发生了根本改变。在1965年，IBM公司的Cooley和MIT的Tukey这二位科学家提出了一种离散傅立叶变换的快速算法：快速傅里叶变换，使得DFT的运算量降低一个数量级以上。一个以上数量级是因为它与序列的长度N取值有关系。
FFT算法大大推动了数字信号处理技术的快速发展。业界一直将1965年定为数字信号处理这门学科的诞生之年。因此，FFT算法在数字信号处理的发展史上占有很重要的地位。目前FFT算法已广泛应用于通信、雷达、生物医学等众多技术领域。如3G和4G通信中采用的正交频分复用（OFDM ）技术，采用的就是FFT算法。FFT算法算法优势明显，但是教学实践表明，直接用定义和公式推导来教学效果不理想，可以从其他方面考虑DFT的快速计算，与FFT计算殊途同归。
三、DFT计算量的分析
信号处理无论是时域还是频域的运算都是以乘法、加法和移位作为最基本的运算形式，因此对某一算法可以用所需的乘法次数和加法次数来衡量它的运算量和运算效率。同样对于DFT的运算量，我们只需分析它所需要的乘法次数和加法次数。前面的章节我们已经学过，对于N点有限长的序列[x（n）]，它的DFT的数学表达式乘加运算，如公式（1）所示。
引导学生由DFT矩阵形式分析计算量。DFT矩阵是N×N的矩阵，x是N×1的向量，由于[WnkN]为复数，因此[DNx]共需要N2次复数乘法，N（N+1）次复数加法，可以说N点DFT的乘法和加法次数均与N2成正比。当N比较大时，运算量增长非常快。如当N=64时需要4094次复数乘法和复数加法，而当N=2048时，需要4194304次复数乘法和复数加法。运算量很大。这对实时性很强的信号处理来说，如雷达信号处理，必将对系统的处理速度有着十分苛刻的要求。
引导学生思考是否存在解决办法，解决的途径在哪里呢？
四、DFT矩阵计算方法
由DFT矩阵形式的表达式可以看出，造成计算量巨大的原因是DFT矩阵中的复数旋转因子，因此需要着手分析DFT矩阵，看是否能对它进行处理，降低运算量。
不难证明：[W0N=1]，[WN2N=-1]，[WNN=1]，[WknN=Wk（N+n）N=Wn（N+k）N]，[Wk+N2N=-WkN]，[WkN=WmkmN]。
启发学生以8点DFT为例进行说明。
N点DFT的矩阵表示为：
要对这个矩阵进行运算化简，就要先对它进行一定的处理，考虑将[D8]的各列重新进行排列，使得它的奇数列全部都在偶数列的前面。
也就是变成这个矩阵：
由已有的知识可知，[D′8]矩阵可由[D8]右乘以置换矩阵而来，置换哪一列，就相当于置换矩阵对应行中此列为1。基于这种运算，假设置换矩阵为[P8]，由于[D8]变换到[D′8]，对于偶数列相当于将[D8]的第2列，第4列，第6列，置换到第5列，第6列，第7列，因此[P8]矩阵中第2行，第4行，第6行对应的第5列，第6列，第7列为1，也就是[P8]的元素[P8（2，5）=1]，[P8（4，6）=1]，[P8（6，7）=1];同样，对于奇数列，相当于将[D8]的第3列，第5列，第7列，置换到第2列，第3列，第4列，[P8（3，2）=1]，[P8（5，3）=1]，[P8（7，4）=1];第1列和第8列不用置换，因此[P8（1，1）=1]，[P8（8，8）=1]，其他元素为0，由此就可以写出置换矩阵： 接下来，对[D′8]进行化简，由[WNN=1]，[Wk+nNN=WkN]，k和n为整数，N=8，得到：
如果将[D′8]分成2×2的块矩阵，显然矩阵的块（1，1）和（2，1）是相等的，将其记为[D4]，再根据[WknNn=WkN]则有：
而对于块（1，2）和（2，2），它们之间也存在一定关系，观察可以发现，块（1，2）的元素乘以[W48]就能得到块（2，2）。因此，令
左乘[T4]相当于把第k行乘以[Wk-18]，块（1，2）和（2，2）就可以分别表示为[T4D4]和[-T4D4]，这样，就可以利用分块乘法实现DFT的计算，也就是：
也就是说，通过矩阵变换，将8点的DFT化简为两个N=4点的DFT。
由此启发学生，上述过程可以推广到N为任意偶数的情况。在实际应用中，通常取N=2k，k为正整数，因此某些场景下需要将数据序列补零满足上述条件。
通过以上分析，启发学生计算DFT的时间復杂度，并验证其结果。事实上，利用矩阵化简计算DFT与利用FFT算法的时间复杂度相等;对于复数乘法，需要的次数为[N2log2N]，复数加法次数为[Nlog2N]，相对直接计算DFT，运算效率为[N2N2log2N]，大大提高了计算速度。
五、结论
数字信号处理课程教学中，根据学生前期的知识储备，由已经熟知的矩阵分析方法深入思考离散傅里叶变换（DFT）的快速计算方法，可以避免学生陷入生涩的概念理解和繁复的公式推导中。文章对这一教学方法进行了探索研究，从矩阵角度理解、计算离散傅里叶变换（DFT），可以提高数字信号处理课程教学的有效性。事实上，数字信号处理中的数字滤波器设计、卷积、相关、相乘等知识点都有矩阵分析的数学理论基础，从这一方面入手，可以提升学生的理解能力和掌握程度。作为课程建设的一部分，矩阵分析教学方法的引入有利于促进数字信号处理课程的进一步发展。
[ 参 考 文 献 ]
[1] A.V.奥本海姆，R.W.谢弗，J.R.巴克.离散时间信号处理[M].刘树棠，黄建国，译.第2版.西安：西安交通大学出版社，2001.
[2] 胡广书.数字信号处理导论[M].北京：清华大学出版社，2005.
[3] 王世一.数字信号处理（修订版）[M].北京：北京理工大学出版社，1997.
[4] 高西全，丁玉美，阔永红.数字信号处理——原理、实现及应用.第2版[M].北京：电子工业出版社，2010.
[5] 刘元会，常安定.按时间抽取的FFT矩阵形式的研究[J].纺织高校基础科学学报，2008（4）：389-392.
[6] 姚力波，刘瑜，董凯，等.基于矩阵理论的“数字信号处理”教学研究[J].电气电子教学学报，2017（5）：97-99.
[7] 陈强，徐科军.以DFT为例探讨数字信号处理教学方法[J].中国电力教育，2012（6）：49-50.
[8] 姜恩华，杨一军，窦德召.数字信号处理课程中的傅里叶变换教学探索[J].廊坊师范学院学报（自然科学版），2017（1）：52-56.
[责任编辑：林志恒]