DFT的計(jì)算量
離散傅里葉變換在實(shí)際應(yīng)用中是非常重要的,利用它可以計(jì)算信號(hào)的頻譜、功率譜和線性卷積等。但是,如果使用定義式(3.20)來直接計(jì)算DFT,當(dāng)N很大時(shí),即使使用高速計(jì)算機(jī),所花的時(shí)間也太多。因此,如何提高計(jì)算DFT的速度,便成了重要的研究課題。1965年庫利 (Cooley)和圖基(Tukey)在前人的研究成果的基礎(chǔ)上提出了快速計(jì)算DFT的算法,之后,又出現(xiàn)了各種各樣快速計(jì)算DFT的方法,這些方法統(tǒng)稱為快速傅里葉變換(Fast Fourier Transform),簡(jiǎn)稱為FFT。FFT的出現(xiàn),使計(jì)算DFT的計(jì)算量減少了兩個(gè)數(shù)量級(jí),從而成為數(shù)字信號(hào)處理強(qiáng)有力的工具。
快速傅里葉變換(FFT)是離散傅里葉變換(DFT)的快速算法。它是DSP領(lǐng)域中的一項(xiàng)重大突破,它考慮了計(jì)算機(jī)和數(shù)字硬件實(shí)現(xiàn)的約束條件、研究了有利于機(jī)器操作的運(yùn)算結(jié)構(gòu),使DFT的計(jì)算時(shí)間縮短了1~2個(gè)數(shù)量級(jí),還有效地減少了計(jì)算所需的存儲(chǔ)容量,F(xiàn)FT技術(shù)的應(yīng)用極大地推動(dòng)了DSP的理論和技術(shù)的發(fā)展。
在導(dǎo)出FFT算法之前,首先來估計(jì)一下直接計(jì)算DFT所需的計(jì)算量。
DFT的定義
將DFT定義式展開成方程組
將方程組寫成矩陣形式
用復(fù)數(shù)表示:
FFT算法是基于可以將一個(gè)長度為N的序列的離散傅里葉變換逐次分解為較短的離散傅里葉變換來計(jì)算這一基本原理的。這一原理產(chǎn)生了許多不同的算法,但它們?cè)谟?jì)算速度上均取得了大致相當(dāng)?shù)母纳啤?/font>
在本章中我們集中討論兩類基本的FFT算法。
第一類 稱為按時(shí)間抽取(Decimation-in-Time)的基2FFT算法,它的命名來自如下事實(shí):在把原計(jì)算安排成較短變換的過程中,序列x(n)(通??醋魇且粋€(gè)時(shí)間序列)可逐次分解為較短的子序列。
第二類稱為按頻率抽取(Decimation-in-Frequency)的基2FFT算法,在這類算法中是將離散傅里葉變換系數(shù)序列X(k)分解為較短的子序列。
前面兩種算法特別適用于N等于2的冪的情況。
對(duì)于N為合數(shù)的情況,本章也將介紹兩種處理方法。