利用矩陣法計(jì)算離散傅里葉變換的教學(xué)研究

王世強(qiáng)　高彩云 　張秦　白娟　曾會(huì)勇

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

[關(guān)鍵詞]數(shù)字信號(hào)處理;矩陣分析;教育;教學(xué)研究

[中圖分類號(hào)] G642.0 [文獻(xiàn)標(biāo)識(shí)碼] A [文章編號(hào)] 2095-3437（2021）09-0098-03

一、引言

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

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

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

二、FFT教學(xué)的引入

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

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

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

三、DFT計(jì)算量的分析

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

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

引導(dǎo)學(xué)生思考是否存在解決辦法，解決的途徑在哪里呢？

四、DFT矩陣計(jì)算方法

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

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

啟發(fā)學(xué)生以8點(diǎn)DFT為例進(jìn)行說(shuō)明。

N點(diǎn)DFT的矩陣表示為：

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

也就是變成這個(gè)矩陣：

由已有的知識(shí)可知，[D′8]矩陣可由[D8]右乘以置換矩陣而來(lái)，置換哪一列，就相當(dāng)于置換矩陣對(duì)應(yīng)行中此列為1。基于這種運(yùn)算，假設(shè)置換矩陣為[P8]，由于[D8]變換到[D′8]，對(duì)于偶數(shù)列相當(dāng)于將[D8]的第2列，第4列，第6列，置換到第5列，第6列，第7列，因此[P8]矩陣中第2行，第4行，第6行對(duì)應(yīng)的第5列，第6列，第7列為1，也就是[P8]的元素[P8（2，5）=1]，[P8（4，6）=1]，[P8（6，7）=1];同樣，對(duì)于奇數(shù)列，相當(dāng)于將[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，由此就可以寫出置換矩陣：

接下來(lái)，對(duì)[D′8]進(jìn)行化簡(jiǎn)，由[WNN=1]，[Wk+nNN=WkN]，k和n為整數(shù)，N=8，得到：

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

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

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

也就是說(shuō)，通過(guò)矩陣變換，將8點(diǎn)的DFT化簡(jiǎn)為兩個(gè)N=4點(diǎn)的DFT。

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

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

五、結(jié)論

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

[ 參 考 文 獻(xiàn) ]

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

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

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

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

[5] 劉元會(huì)，常安定.按時(shí)間抽取的FFT矩陣形式的研究[J].紡織高校基礎(chǔ)科學(xué)學(xué)報(bào)，2008（4）：389-392.

[6] 姚力波，劉瑜，董凱，等.基于矩陣?yán)碚摰摹皵?shù)字信號(hào)處理”教學(xué)研究[J].電氣電子教學(xué)學(xué)報(bào)，2017（5）：97-99.

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

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

[責(zé)任編輯：林志恒]