快速傅氏變換（FFT）是離散傅氏變換的快速算法

快速傅氏變換(FFT)是離散傅氏變換的快速算法,它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性,對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的。它對(duì)傅氏變換的理論并沒(méi)有新的發(fā)現(xiàn),但是對(duì)于在計(jì)算機(jī)系統(tǒng)或者說(shuō)數(shù)字系統(tǒng)中應(yīng)用離散傅立葉變換,可以說(shuō)是進(jìn)了一大步。
設(shè)x(n)為N項(xiàng)的復(fù)數(shù)序列,由DFT變換,任一X(m)的計(jì)算都需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法,而一次復(fù)數(shù)乘法等于四次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法,一次復(fù)數(shù)加法等于兩次實(shí)數(shù)加法,即使把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運(yùn)算”(四次實(shí)數(shù)乘法和四次實(shí)數(shù)加法),那么求出N項(xiàng)復(fù)數(shù)序列的X(m),即N點(diǎn)DFT變換大約就需要N2次運(yùn)算。當(dāng)N=1024點(diǎn)甚至更多的時(shí)候,需要N2=1048576次運(yùn)算,在FFT中,利用WN的周期性和對(duì)稱性,把一個(gè)N項(xiàng)序列(設(shè)N=2k,k為正整數(shù)),分為兩個(gè)N/2項(xiàng)的子序列,每個(gè)N/2點(diǎn)DFT變換需要(N/2)2次運(yùn)算,再用N次運(yùn)算把兩個(gè)N/2點(diǎn)的DFT變換組合成一個(gè)N點(diǎn)的DFT變換。這樣變換以后,總的運(yùn)算次數(shù)就變成N+2(N/2)2=N+N2/2。繼續(xù)上面的例子,N=1024時(shí),總的運(yùn)算次數(shù)就變成了525312次,節(jié)省了大約50%的運(yùn)算量。而如果我們將這種“一分為二”的思想不斷進(jìn)行下去,直到分成兩兩一組的DFT運(yùn)算單元,那么N點(diǎn)的DFT變換就只需要Nlog2N次的運(yùn)算,N在1024點(diǎn)時(shí),運(yùn)算量?jī)H有10240次,是先前的直接算法的1%,點(diǎn)數(shù)越多,運(yùn)算量的節(jié)約就越大,這就是FFT的優(yōu)越性