數字信號處理中基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.