封面來(lái)自百度百科

上一期(一個(gè)月前), 我講了離散傅里葉變換并且用算法實(shí)現(xiàn)了, 但是在實(shí)際應(yīng)用中就不會(huì)使用這個(gè)算法的, 為什么呢?

效率慢, 在長(zhǎng)度為n的數(shù)據(jù)中, 做一次DFT需要至少計(jì)算n^2次復(fù)數(shù)乘法和n^2次復(fù)數(shù)加法, (在我的算法里還有附帶n^2次復(fù)數(shù)指數(shù)運(yùn)算,? 沒(méi)有化簡(jiǎn)真的非常對(duì)不起)

那么有沒(méi)有效率比較快的算法呢? (沒(méi)有的話我發(fā)這個(gè)專欄干什么)

快速傅里葉變換 (Fast FT)

以下使用??x_n?表示輸入數(shù)據(jù),??f_n??表示FFT后的結(jié)果,? n? 表示數(shù)據(jù)長(zhǎng)度

上次我們說(shuō)過(guò)的DFT表達(dá)式是這個(gè)

假設(shè)我們的數(shù)據(jù)集是偶數(shù)個(gè),? 那么把偶數(shù)和奇數(shù)分開(kāi),? 得:

化簡(jiǎn)后得:

然后我們?cè)偌僭O(shè)偶部奇部的長(zhǎng)度都為偶數(shù) ,即總數(shù)據(jù)長(zhǎng)度可以被4整除, 重復(fù)上述步驟, 得:

為了讓算式更簡(jiǎn)潔一些,? 我自己創(chuàng)造了一種表示方法:

所以在這種表示方法中,? 上面很長(zhǎng)的式子就變成了:

然后我們?cè)偌僭O(shè)我們的數(shù)據(jù)長(zhǎng)度可以被8整除, 得:

這時(shí)候應(yīng)該可以發(fā)現(xiàn)規(guī)律了

在一個(gè)內(nèi)層括號(hào)里,? 結(jié)構(gòu)都是統(tǒng)一的? ?{8, i} + [4] {8, i+4},? ?而在上一步,可以觀察到? ?{4, i} + [4] {4, i+2}? ? 這樣的結(jié)構(gòu)

所以這是一個(gè)非常有規(guī)律的一種算法

這里有一個(gè)普遍的計(jì)算方法:

假設(shè)數(shù)據(jù)長(zhǎng)度恰好為? 2^n? ,? ? ?然后創(chuàng)造一種記法:? 記? x_i? 為? {2^n,? i}? ,對(duì)下列算式進(jìn)行迭代:

最后得到 {0,0} 就是FFT的結(jié)果了

在上一篇DFT中,? 觀察ω取不同數(shù)值時(shí)的復(fù)平面,? ?我們可以看到ω以4為中心, 左右的圖像是完全對(duì)稱的

在經(jīng)過(guò)一定量的計(jì)算后, 會(huì)得到一種非常神奇的計(jì)算過(guò)程? ? ?(在不存在的附章內(nèi))

以下定義? ?蝶形節(jié)點(diǎn)? ??:

并且定義單位虛根:

那么在長(zhǎng)度為4的數(shù)據(jù)中, FFT就可以用下面的蝴蝶節(jié)點(diǎn)圖來(lái)進(jìn)行計(jì)算

而8個(gè)數(shù)據(jù)可以這樣計(jì)算

那么問(wèn)題來(lái)了, 左邊的輸入排列有什么規(guī)律呢

以8個(gè)數(shù)據(jù)為例,? 原數(shù)據(jù)排列為 [0, 1, 2, 3, 4, 5, 6, 7],? 而輸入排列為?[0, 4, 2, 6, 1, 5, 3, 7] , 看上去好像完全沒(méi)有規(guī)律

但是寫(xiě)成二進(jìn)制的話,? 原數(shù)據(jù)排列為??[000, 001, 010, 011, 100, 101, 110, 111],? ?而輸入排列為??[000, 100, 010, 110, 001, 101, 011, 111]? ?

可以看到把每個(gè)原排列的二進(jìn)制左右對(duì)稱地?fù)Q一下, 就得到了輸入排列

上面說(shuō)的是一種叫做? "基-2? 快速傅里葉變換 (bias-2 FFT)",? ?因?yàn)槲覀冞@里是按偶部奇部對(duì)輸入數(shù)據(jù)進(jìn)行分割,? 所以是"基-2"的

同理如果按照? "對(duì)3取余,? 結(jié)果有0, 1, 2"? 這樣進(jìn)行分割也是可以的, 這種就叫做 "基-3快速傅里葉變換",? ?同理可以創(chuàng)造各種 "基- [質(zhì)數(shù)]? FFT",? 為什么是質(zhì)數(shù)呢

事實(shí)上,? 單獨(dú)一個(gè)蝴蝶節(jié)點(diǎn)才是真正的 "b-2 FFT", 而后面說(shuō)到的4個(gè), 8個(gè)數(shù)據(jù)的其實(shí)是"b-4 FFT"和"b-8 FFT".? ?而且運(yùn)算順序?qū)Y(jié)果不會(huì)產(chǎn)生影響?(如封面和后面的"b-8FFT", 順序不同結(jié)果一樣)

事實(shí)上, 對(duì)一個(gè)數(shù)據(jù)長(zhǎng)度為? (p0*p1*p2* ... *pn)?(p為質(zhì)數(shù))?的序列, 我們可以按照順序作 "b-p0 FFT",?"b-p1?FFT",?"b-p2?FFT", ...,?"b-pn?FFT", 最后得到的結(jié)果是和DFT的結(jié)果一模一樣的

***? FFT不需要專門推導(dǎo)逆算法,? 直接按照蝶形節(jié)的結(jié)構(gòu)反向計(jì)算就可以了 ***

那么說(shuō)了一大堆, FFT真的有比DFT快嗎,? ? ?我們可以直接寫(xiě)程序看看用時(shí)??FFT的程序太復(fù)雜了, 這篇專欄是半夜趕出來(lái)的, 沒(méi)有找到精力去寫(xiě),? 才不是我想咕哦

或者最直接的分析復(fù)雜度

在DFT中,? 長(zhǎng)度為n的數(shù)據(jù)需要進(jìn)行n^2次 (復(fù)數(shù)加法和復(fù)數(shù)乘法)? ?的計(jì)算, 所以DFT的復(fù)雜度為? n^2

在FFT中, 長(zhǎng)度為n的數(shù)據(jù)需要進(jìn)行? n*log2(n)+3次?(復(fù)數(shù)加法和復(fù)數(shù)乘法)? ?的計(jì)算, 所以FFT的復(fù)雜度為??n*log2(n)

那就是快多少呢,? 我們可以畫(huà)一個(gè)圖像來(lái)看看他們的區(qū)別

可以看到隨著n的增大,? DFT和FFT之間的差距是按幾何倍數(shù)增長(zhǎng)的,? 所以

FFT萬(wàn)歲