數(shù)字信號(hào)處理中基2 FFT算法的教學(xué)研究

摘 要 基2 FFT算法是數(shù)字信號(hào)處理課程中的重點(diǎn)知識(shí)點(diǎn)之一。以“引導(dǎo)思考、授以方法、鍛煉能力”為教學(xué)設(shè)計(jì)原則，探索以問題引導(dǎo)算法思想、分層次數(shù)學(xué)推導(dǎo)、應(yīng)用流圖計(jì)算及結(jié)合MATLAB驗(yàn)證多角度開展課堂教學(xué)的教學(xué)方法。作為數(shù)字信號(hào)處理課程建設(shè)的一部分，基2 FFT算法的教學(xué)研究有利于促進(jìn)數(shù)字信號(hào)處理課程的教育教學(xué)發(fā)展。

關(guān)鍵詞 數(shù)字信號(hào)處理 FFT 教學(xué)研究

中圖分類號(hào)：G424 文獻(xiàn)標(biāo)識(shí)碼：A

0 引言

快速傅里葉變換FFT（Fast Fourier Transform）是離散傅里葉變換DFT（Discrete Fourier Transform）的快速算法。數(shù)字信號(hào)處理學(xué)科隨FFT的出現(xiàn)和發(fā)展而迅速得到發(fā)展。因此，F(xiàn)FT是數(shù)字信號(hào)處理課程中的重要內(nèi)容?；?FFT算法是FFT的最基本算法，也是應(yīng)用最多的算法。

FFT的教學(xué)具有數(shù)學(xué)推導(dǎo)多、算法流圖多的特點(diǎn)，學(xué)生在學(xué)習(xí)時(shí)容易出現(xiàn)陷入繁瑣的公式流圖不得要領(lǐng)的現(xiàn)象，課程學(xué)習(xí)結(jié)束后受益不大。作者針對(duì)數(shù)字信號(hào)處理中基2FFT算法教學(xué)內(nèi)容進(jìn)行教學(xué)探索和研究。

1 教學(xué)設(shè)計(jì)原則

中國有句古話叫“授人以魚不如授人以漁”，聯(lián)合國教科文組織曾談到：今后的文盲將不再是不識(shí)字的人，而是不會(huì)自學(xué)和學(xué)了知識(shí)不會(huì)應(yīng)用的人。①這些都說明了教以方法或某種信念的重要性。對(duì)于高等教育，一個(gè)好的稱職的教師，不但要給學(xué)生以知識(shí)，還要教會(huì)學(xué)生自學(xué)和應(yīng)用的方法。作者認(rèn)為，高校的課程學(xué)習(xí)不僅要為學(xué)生今后專業(yè)化的職業(yè)奠定知識(shí)基礎(chǔ)，還要讓學(xué)生學(xué)到解決問題的方法與思路，后者對(duì)學(xué)生長(zhǎng)遠(yuǎn)的職業(yè)發(fā)展和能力提升意義更為重大?；谶@樣的教學(xué)理念，教學(xué)設(shè)計(jì)的總體原則為引導(dǎo)思考、授以方法、鍛煉能力。在基2FFT算法教學(xué)中探索問題引導(dǎo)算法思想、分層次數(shù)學(xué)推導(dǎo)、應(yīng)用流圖計(jì)算及結(jié)合MATLAB驗(yàn)證多角度開展課堂教學(xué)。

2 算法原理的教學(xué)設(shè)計(jì)

2.1 問題引導(dǎo)算法思想

以問題引導(dǎo)算法核心思想的展開，通過互動(dòng)式教學(xué)方式提出問題、討論問題，進(jìn)而得到解決問題的辦法。

（1）提出問題1：直接計(jì)算N點(diǎn)DFT的計(jì)算量有多大？

討論問題：直接計(jì)算N點(diǎn)DFT總共需要計(jì)算N2次復(fù)數(shù)乘法和N（N-1）～ N2次復(fù)數(shù)加法，復(fù)數(shù)乘法和復(fù)數(shù)加法次數(shù)均與N2成正比。直接計(jì)算DFT的算法復(fù)雜度是O（N2），隨著N的增加，計(jì)算量將是驚人的。②

解決問題：通過減小N降低運(yùn)算量，提高運(yùn)算速度。

（2）提出問題2：在長(zhǎng)序列分解為短序列的過程中短序列長(zhǎng)度是多少合適？

討論問題：DFT的最小運(yùn)算點(diǎn)數(shù)是2點(diǎn)。2點(diǎn)和4點(diǎn)DFT計(jì)算沒有復(fù)數(shù)乘法，為后面的基2算法、基4算法及分裂基算法打好基礎(chǔ)。

解決問題2：要定義最小運(yùn)算單元的點(diǎn)數(shù)M——基，可分為基3算法、基3算法、基4算法等。

（3）提出問題3：長(zhǎng)序列分解為短序列的方法是什么？

討論問題：長(zhǎng)序列的分解

解決問題：長(zhǎng)序列分解為短序列的方法——抽取方法，分為時(shí)間抽取和頻率抽取。

最后加以總結(jié)：FFT算法的核心思想就是按照一定的規(guī)則（抽取方法）將N點(diǎn)長(zhǎng)序列分解為短序列，直到分解為最小運(yùn)算單元點(diǎn)數(shù)（基）M，然后計(jì)算M點(diǎn)DFT，將計(jì)算所有M點(diǎn)DFT結(jié)果組合為N點(diǎn)DFT。這種問題引導(dǎo)教學(xué)內(nèi)容展開的教學(xué)設(shè)計(jì)一方面可以更深層次地引導(dǎo)學(xué)生理解：任何算法的存在一定有其應(yīng)用背景和所針對(duì)解決的問題。另一方面，教會(huì)學(xué)生解決問題一般的方法與思路，從而有效提高學(xué)生發(fā)現(xiàn)問題、解決問題能力。

2.2 分層次的數(shù)學(xué)推導(dǎo)

在我校教學(xué)中分為卓越班、普通班，學(xué)生的數(shù)學(xué)基礎(chǔ)和學(xué)習(xí)能力的存在差異。針對(duì)不同層次的學(xué)生，在教學(xué)上采用不同深度的算法數(shù)學(xué)推導(dǎo)。

（1）對(duì)于普通班學(xué)生按照常規(guī)的多步分解展開算法的數(shù)學(xué)推導(dǎo)。

以時(shí)間抽取基-2 FFT算法為例。首先將長(zhǎng)度為N=2L的序列（）按序號(hào)是奇數(shù)還是偶數(shù)分為兩個(gè)短序列（）和（）。（）是（）的N點(diǎn)DFT ，可計(jì)算為：

其中（）是（）的N/2點(diǎn)DFT，（）是（）的N/2點(diǎn)DFT。N點(diǎn)DFT（）變成兩個(gè)N/2點(diǎn)DFT（）和（）的組合，其數(shù)學(xué)描述為（） = （） + （）。

（）和（）的計(jì)算采用相同的長(zhǎng)序列分解為短序列的計(jì)算方法，即將N/2點(diǎn)DFT變成兩個(gè)N/4點(diǎn)DFT的組合。以此類推，直至分解到最小運(yùn)算單元2點(diǎn)。

（2）對(duì)于卓越班學(xué)生采用多基多進(jìn)制的一般數(shù)學(xué)表達(dá)式展開算法的數(shù)學(xué)推導(dǎo)。

以N=8基-2頻率抽取FFT為例。

i. 首先設(shè)置變量及其維數(shù)。

N=2L，N=8，維數(shù)為3，N = 讇譺0 ，其中===2。此時(shí)設(shè)置6個(gè)變量表示輸入序列序號(hào)和輸出序列序號(hào)：0≤≤，0≤≤，0≤≤，0≤≤，0≤≤，0≤≤。為了滿足原位運(yùn)算，輸入與輸出必須有一個(gè)為倒位序。設(shè)定輸入（）自然位序，輸出（）倒位序，因此的三維表達(dá)式為 = + 2 + 和。兩個(gè)式子所定義的位序可以互為倒位序。

ii. 列寫表達(dá)式，對(duì)分解，并化簡(jiǎn)。

求和從最高位開始，并且由于是DIF-FFT算法，頻率抽取是頻域自變量按照奇偶分解。因而化簡(jiǎn)是對(duì)的二進(jìn)制表示進(jìn)行的。

由數(shù)學(xué)運(yùn)算表達(dá)式可以準(zhǔn)確地畫出對(duì)應(yīng)流圖，其中和是級(jí)間旋轉(zhuǎn)因子。可以按照輸入（）和輸出（）位序的不同得到2個(gè)原位運(yùn)算圖。

這種分層次教學(xué)設(shè)計(jì)既可以確保普通班學(xué)生能夠理解掌握基2算法的數(shù)學(xué)機(jī)理，又可以讓卓越班學(xué)生在此基礎(chǔ)上掌握通用的多基多進(jìn)制數(shù)學(xué)表達(dá)式推導(dǎo)方法，啟發(fā)卓越班學(xué)生應(yīng)用自行推導(dǎo)其他單基單進(jìn)制、多基多進(jìn)制算法，培養(yǎng)學(xué)生的學(xué)習(xí)遷移能力。

表1 時(shí)間抽取與頻率抽取的對(duì)比表

2.3 兩種抽取列表對(duì)比

在兩種抽取方法的算法學(xué)習(xí)后，時(shí)間抽取與頻率抽取對(duì)比這部分教學(xué)內(nèi)容的設(shè)計(jì)是：首先讓學(xué)生分組討論兩種抽取方法的區(qū)別和共性，列表對(duì)比；然后每個(gè)小組討論結(jié)論做簡(jiǎn)短的陳述；教師作點(diǎn)評(píng)、補(bǔ)充及總結(jié)。最終對(duì)比列表見表1，這種教學(xué)方式引導(dǎo)學(xué)生掌握知識(shí)歸納總結(jié)的方法，提高分析歸納能力。

2.4 流圖的畫法與應(yīng)用

總結(jié)出流圖5步畫法，③步驟如下：（1）畫出N條平行數(shù)據(jù)線。（2）確定輸入和輸出的位序。輸入和輸出其中一個(gè)為自然位序，另一個(gè)為倒位序，以滿足原位運(yùn)算。（3）畫蝶形結(jié)。鄰近倒位序的蝶形結(jié)的距離最近，鄰近自然位序的蝶形結(jié)的距離最遠(yuǎn)，各級(jí)蝶形結(jié)的距離按照運(yùn)算級(jí)而逐漸變大（輸入是倒位序情況）或者變?。ㄝ斎胧亲匀晃恍蚯闆r）。（4）為每個(gè)蝶形結(jié)添加“-1”。（5）添加旋轉(zhuǎn)因子。如果是時(shí)間抽取，則旋轉(zhuǎn)因子位于每級(jí)蝶形結(jié)的前面，而且第一級(jí)旋轉(zhuǎn)因子為，其余各級(jí)旋轉(zhuǎn)因子按規(guī)律添加。如果是頻率抽取，則旋轉(zhuǎn)因子位于每級(jí)蝶形結(jié)的后面，而且最后一級(jí)旋轉(zhuǎn)因子為，其余各級(jí)旋轉(zhuǎn)因子按規(guī)律添加。

上述5步畫法體現(xiàn)了原位運(yùn)算、輸入輸出互為倒位序及旋轉(zhuǎn)因子規(guī)律特點(diǎn)，可用于兩種抽取方法的基2-FFT原位算法的蝶形流圖繪制，便于記憶和掌握。

流圖的應(yīng)用：

以4點(diǎn)基-2 DIF-FFT算法流圖為例，利用4點(diǎn)基-2 DIF-FFT算法流圖計(jì)算（） = {1，2，3，4}的（）。

最后將輸出排成自然位序，得到（） = {10， + ，，}。教學(xué)上，要求學(xué)生會(huì)應(yīng)用流圖計(jì)算DFT。

2.5 運(yùn)算量的MATLAB驗(yàn)證

在課堂上應(yīng)用MATLAB驗(yàn)證FFT算法的效率，運(yùn)行調(diào)用fft函數(shù)直接計(jì)算DFT的計(jì)算程序和利用矩陣運(yùn)算DFT的程序，利用cputime函數(shù)比較兩種程序運(yùn)算時(shí)間，讓學(xué)生直觀體會(huì)隨著DFT點(diǎn)數(shù)的增加，F(xiàn)FT算法的有效性越顯著。

3 結(jié)束語

作者以多年教學(xué)積累為基礎(chǔ)，以“引導(dǎo)思考、授以方法、鍛煉能力”為教學(xué)設(shè)計(jì)原則，探索問題引導(dǎo)算法思想、分層次數(shù)學(xué)推導(dǎo)、應(yīng)用流圖計(jì)算及結(jié)合MATLAB驗(yàn)證多角度的課堂教學(xué)設(shè)計(jì)，總結(jié)出益于學(xué)生知識(shí)構(gòu)建和學(xué)習(xí)遷移的教法。它作為數(shù)字信號(hào)處理課程建設(shè)的一部分，有利于促進(jìn)數(shù)字信號(hào)處理課程的教育發(fā)展。

基金項(xiàng)目：北京信息科技大學(xué)2011年課程建設(shè)項(xiàng)目（數(shù)字信號(hào)處理

注釋

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

② 鄭方，徐明星.信號(hào)處理原理[M].北京：清華大學(xué)出版社，2003.8.

③ 焦瑞莉，羅倩，汪毓鐸，顧奕.數(shù)字信號(hào)處理[M].北京：機(jī)械工業(yè)出版社，2012.6.