利用矩陣法計算離散傅里葉變換的教學研究

王世強　高彩云 　張秦　白娟　曾會勇

[摘 要]離散傅里葉變換（DFT）及快速傅里葉變換（FFT）是數(shù)字信號處理課程中的核心內(nèi)容之一。傳統(tǒng)教學方法中的先拋概念定理，再推導計算的方法存在學生課堂上難以立即接受，課下難以深入理解的問題。以學生掌握的既有知識為基礎，通過對DFT的矩陣分析，引導學生從矩陣理論思考DFT的快速算法，得出與經(jīng)典FFT算法相同的計算效果和復雜度，可以取得較好的教學效果。該文對這一教學方法進行了探索實踐，其成果可以促進數(shù)字信號處理課程的教育教學發(fā)展。

[關鍵詞]數(shù)字信號處理;矩陣分析;教育;教學研究

[中圖分類號] G642.0 [文獻標識碼] A [文章編號] 2095-3437（2021）09-0098-03

一、引言

數(shù)字信號處理中的部分知識利用常規(guī)方法講解，學生不容易理解和掌握。如能通過已學習的課程，從熟悉的學習內(nèi)容引申開來，建立新的理論體系和知識單元，而不是直接拋出新的概念和定理，造成學生學習和理解上的困難，就可以很大程度上提高學生的理解能力。

在數(shù)字信號處理課程中，離散傅里葉變換（DFT）及其快速算法——快速傅里葉變換（FFT）是核心內(nèi)容之一。在講授快速傅里葉變換（FFT）時，直接利用DFT的公式進行推導[1～4]，內(nèi)容讓學生覺得晦澀難懂。而且要在課堂中理解掌握蝶形運算結(jié)構(gòu)的引入、推導和簡化DFT的過程，往往很難做到。教學實踐表明，直接利用教材中的方法進行講解，學生的理解往往似是而非，教學效果差強人意。劉元會對時間抽取的FFT 矩陣形式進行了研究，得出了DFT的矩陣形式，具有一定的可行性。但該方法以時間抽取的基-2FFT 算法原理為引，導出矩陣形式，仍需要學生進一步對DFT公式進行化簡變形。且拋出若干定義和引理，不利于學生理解和掌握[5]。姚力波從矩陣理論的角度出發(fā)，分析了數(shù)字信號處理，并對DFT和數(shù)字濾波器（DF）的矩陣表示進行研究，得出了矩陣理論是“數(shù)字信號處理”課程最基礎的數(shù)學理論的結(jié)論，具有一定的教學參考價值[6]。

文獻[7]指出，根據(jù)數(shù)字信號處理課程的特點和教學中存在的問題，教學方法既要強調(diào)教學內(nèi)容的意義，又要形象化教學，循序漸進，注重實際應用。姜恩華等也對DFT的教學進行了探索[8]。本文根據(jù)數(shù)字信號處理教學過程中的實踐經(jīng)驗，對FFT的教學方法進行探索，并通過矩陣方法的引入，從另一方面講授DFT的快速算法。

二、FFT教學的引入

相比傅立葉家族中的其他變換，DFT是實用性最強的算法。該算法首次實現(xiàn)了頻域的離散化，信號在時域和頻域均是離散的，非常便于計算機的有效處理。但是DFT在具體的工程實踐中一開始并沒有得到很大應用，其原因就在于巨大的運算量。

因為當序列的長度N很大時，直接計算N點的DFT的計算量是非常大的。即使采用計算機也很難對問題進行實時處理，所以在相當長的一段時間內(nèi)，DFT算法并沒有得到真正的運用。直到1965年情況才發(fā)生了根本改變。在1965年，IBM公司的Cooley和MIT的Tukey這二位科學家提出了一種離散傅立葉變換的快速算法：快速傅里葉變換，使得DFT的運算量降低一個數(shù)量級以上。一個以上數(shù)量級是因為它與序列的長度N取值有關系。

FFT算法大大推動了數(shù)字信號處理技術(shù)的快速發(fā)展。業(yè)界一直將1965年定為數(shù)字信號處理這門學科的誕生之年。因此，F(xiàn)FT算法在數(shù)字信號處理的發(fā)展史上占有很重要的地位。目前FFT算法已廣泛應用于通信、雷達、生物醫(yī)學等眾多技術(shù)領域。如3G和4G通信中采用的正交頻分復用（OFDM ）技術(shù)，采用的就是FFT算法。FFT算法算法優(yōu)勢明顯，但是教學實踐表明，直接用定義和公式推導來教學效果不理想，可以從其他方面考慮DFT的快速計算，與FFT計算殊途同歸。

三、DFT計算量的分析

信號處理無論是時域還是頻域的運算都是以乘法、加法和移位作為最基本的運算形式，因此對某一算法可以用所需的乘法次數(shù)和加法次數(shù)來衡量它的運算量和運算效率。同樣對于DFT的運算量，我們只需分析它所需要的乘法次數(shù)和加法次數(shù)。前面的章節(jié)我們已經(jīng)學過，對于N點有限長的序列[x（n）]，它的DFT的數(shù)學表達式乘加運算，如公式（1）所示。

引導學生由DFT矩陣形式分析計算量。DFT矩陣是N×N的矩陣，x是N×1的向量，由于[WnkN]為復數(shù)，因此[DNx]共需要N2次復數(shù)乘法，N（N+1）次復數(shù)加法，可以說N點DFT的乘法和加法次數(shù)均與N2成正比。當N比較大時，運算量增長非常快。如當N=64時需要4094次復數(shù)乘法和復數(shù)加法，而當N=2048時，需要4194304次復數(shù)乘法和復數(shù)加法。運算量很大。這對實時性很強的信號處理來說，如雷達信號處理，必將對系統(tǒng)的處理速度有著十分苛刻的要求。

引導學生思考是否存在解決辦法，解決的途徑在哪里呢？

四、DFT矩陣計算方法

由DFT矩陣形式的表達式可以看出，造成計算量巨大的原因是DFT矩陣中的復數(shù)旋轉(zhuǎn)因子，因此需要著手分析DFT矩陣，看是否能對它進行處理，降低運算量。

不難證明：[W0N=1]，[WN2N=-1]，[WNN=1]，[WknN=Wk（N+n）N=Wn（N+k）N]，[Wk+N2N=-WkN]，[WkN=WmkmN]。

啟發(fā)學生以8點DFT為例進行說明。

N點DFT的矩陣表示為：

要對這個矩陣進行運算化簡，就要先對它進行一定的處理，考慮將[D8]的各列重新進行排列，使得它的奇數(shù)列全部都在偶數(shù)列的前面。

也就是變成這個矩陣：

由已有的知識可知，[D′8]矩陣可由[D8]右乘以置換矩陣而來，置換哪一列，就相當于置換矩陣對應行中此列為1。基于這種運算，假設置換矩陣為[P8]，由于[D8]變換到[D′8]，對于偶數(shù)列相當于將[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];同樣，對于奇數(shù)列，相當于將[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為整數(shù)，N=8，得到：

如果將[D′8]分成2×2的塊矩陣，顯然矩陣的塊（1，1）和（2，1）是相等的，將其記為[D4]，再根據(jù)[WknNn=WkN]則有：

而對于塊（1，2）和（2，2），它們之間也存在一定關系，觀察可以發(fā)現(xiàn)，塊（1，2）的元素乘以[W48]就能得到塊（2，2）。因此，令

左乘[T4]相當于把第k行乘以[Wk-18]，塊（1，2）和（2，2）就可以分別表示為[T4D4]和[-T4D4]，這樣，就可以利用分塊乘法實現(xiàn)DFT的計算，也就是：

也就是說，通過矩陣變換，將8點的DFT化簡為兩個N=4點的DFT。

由此啟發(fā)學生，上述過程可以推廣到N為任意偶數(shù)的情況。在實際應用中，通常取N=2k，k為正整數(shù)，因此某些場景下需要將數(shù)據(jù)序列補零滿足上述條件。

通過以上分析，啟發(fā)學生計算DFT的時間復雜度，并驗證其結(jié)果。事實上，利用矩陣化簡計算DFT與利用FFT算法的時間復雜度相等;對于復數(shù)乘法，需要的次數(shù)為[N2log2N]，復數(shù)加法次數(shù)為[Nlog2N]，相對直接計算DFT，運算效率為[N2N2log2N]，大大提高了計算速度。

五、結(jié)論

數(shù)字信號處理課程教學中，根據(jù)學生前期的知識儲備，由已經(jīng)熟知的矩陣分析方法深入思考離散傅里葉變換（DFT）的快速計算方法，可以避免學生陷入生澀的概念理解和繁復的公式推導中。文章對這一教學方法進行了探索研究，從矩陣角度理解、計算離散傅里葉變換（DFT），可以提高數(shù)字信號處理課程教學的有效性。事實上，數(shù)字信號處理中的數(shù)字濾波器設計、卷積、相關、相乘等知識點都有矩陣分析的數(shù)學理論基礎，從這一方面入手，可以提升學生的理解能力和掌握程度。作為課程建設的一部分，矩陣分析教學方法的引入有利于促進數(shù)字信號處理課程的進一步發(fā)展。

[ 參 考 文 獻 ]

[1] A.V.奧本海姆，R.W.謝弗，J.R.巴克.離散時間信號處理[M].劉樹棠，黃建國，譯.第2版.西安：西安交通大學出版社，2001.

[2] 胡廣書.數(shù)字信號處理導論[M].北京：清華大學出版社，2005.

[3] 王世一.數(shù)字信號處理（修訂版）[M].北京：北京理工大學出版社，1997.

[4] 高西全，丁玉美，闊永紅.數(shù)字信號處理——原理、實現(xiàn)及應用.第2版[M].北京：電子工業(yè)出版社，2010.

[5] 劉元會，常安定.按時間抽取的FFT矩陣形式的研究[J].紡織高校基礎科學學報，2008（4）：389-392.

[6] 姚力波，劉瑜，董凱，等.基于矩陣理論的“數(shù)字信號處理”教學研究[J].電氣電子教學學報，2017（5）：97-99.

[7] 陳強，徐科軍.以DFT為例探討數(shù)字信號處理教學方法[J].中國電力教育，2012（6）：49-50.

[8] 姜恩華，楊一軍，竇德召.數(shù)字信號處理課程中的傅里葉變換教學探索[J].廊坊師范學院學報（自然科學版），2017（1）：52-56.

[責任編輯：林志恒]