基2FFT原理

首發(fā)于個(gè)人博客

FFT前置知識(shí)

FT和DFT

傅里葉變換FT（fourier transform）用于將時(shí)域信號(hào) $x(t)$ 和頻域信號(hào) $X(f)$ 之間變換，公式如下所示：
$X(f) = \int^{\infty}_{-\infty}x(t)e^{-j2\pi ft}dt \\ x(t) = \int^{\infty}_{-\infty}X(f)e^{j2\pi ft}df$
對(duì)于計(jì)算機(jī)系統(tǒng)中剥汤，無(wú)法處理連續(xù)的過程，因此離散化為離散傅里葉變換DFT（Discrete Fourier Transform）：
$X[k] = \frac{1}{N}\sum\limits^{N-1}_{n=0} x[n] \times e^{-\frac{2\pi k}{N}j\times n} \\ x[n] = \frac{1}{N}\sum\limits^{N-1}_{k=0} X[k]\times e^{-\frac{2\pi n}{N}j\times k}$
取 $W_N = e^{-\frac{2\pi}{N}j}$ ，可將DFT改寫為以下公式：
$X[k] = \frac{1}{N}\sum\limits^{N-1}_{n=0} x[n] \times W_N^{kn} \\ x[n] = \frac{1}{N}\sum\limits^{N-1}_{k=0} X[k]\times W_N^{-kn}$

DFT改進(jìn)（削減計(jì)算量）

首先分析原始公式的計(jì)算量，取一個(gè)8點(diǎn)DFT算法炕横，對(duì)于一個(gè)點(diǎn)：

需要復(fù)數(shù)乘法N次，每次復(fù)數(shù)乘法由四次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法實(shí)現(xiàn)
需要復(fù)數(shù)加法N-1次葡粒，每次復(fù)數(shù)加法由兩次實(shí)數(shù)加法構(gòu)成

因此份殿，對(duì)于一個(gè)點(diǎn)，需要實(shí)數(shù)乘法共4N次塔鳍，實(shí)數(shù)加法共（2N-2+2N）=4N-2次伯铣。削減計(jì)算量的主要重點(diǎn)在 $W_N$ 上，使用歐拉公式有：
$W_N^{k} = e^{-\frac{2\pi}{N}jk} = \cos\frac{2\pi k}{N} - j\sin\frac{2\pi k}{N}$
考慮 $W_N^{k+\frac{N}{2}}$ 的情況轮纫，有以下公式：
$W_N^{k+\frac{N}{2}} = e^{-\frac{2\pi}{N}j(k+\frac{N}{2})} = \cos\frac{2\pi (k+\frac{N}{2})}{N} - j\sin\frac{2\pi (k+\frac{N}{2})}{N} \\ = \cos(\frac{2\pi k}{N}+\pi) - j\sin(\frac{2\pi k}{N}+\pi) = -\cos\frac{2\pi k}{N} + j\sin\frac{2\pi k}{N} = -W_N^{k}$
同理有 $W_N^{k+N} = W_N$ 腔寡，因此以一個(gè)4點(diǎn)DFT為例，有以下公式：
$X[1] = x(0)W_4^0 + x(1)W_4^1 +x(2)W_4^2+x(3)W_4^3 =[x(0) - x(2)]W^0_4 + [x(1)-x(3)]W_4^2$
可減少所需要的復(fù)數(shù)乘法的次數(shù)掌唾，進(jìn)而減少對(duì)應(yīng)的實(shí)數(shù)乘法和加法的數(shù)量

FFT

基2FFT

基2FFT指點(diǎn)數(shù)為 $2^n$ 的FFT變換放前，取 $N = 2^n$ 的FFT變換如下所示：
$X[k] = \sum\limits^{N-1}_{n=0}x(n)W_N^{kn} = \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n)W_N^{2kn} + \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n+1)W_N^{(2n+1)k}$
將一個(gè)N點(diǎn)的FFT分解為兩個(gè)FFT，一個(gè)為奇數(shù)項(xiàng)的FFT糯彬，另一個(gè)為偶數(shù)項(xiàng)的FFT凭语。對(duì)于 $W_N^{nk}$ 而言，考慮以下變化：
$W_N^{2nk} = e^{-\frac{2\pi \times 2nk}{N}j} = e^{-\frac{2\pi \times nk}{\frac{N}{2}}j} = W_{\frac{N}{2}}^{nk}$
帶入上式撩扒，有以下：
$X[k] =\sum\limits^{\frac{N}{2}-1}_{n=0}x(2n)W_N^{2kn} + W_N^k\sum\limits^{\frac{N}{2}-1}_{n=0}x(2n+1)W_N^{2nk} = \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n)W_{\frac{N}{2}}^{kn} +W_N^k \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n+1)W_{\frac{N}{2}}^{nk}$
取 $FFT_1(k) = \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n)W_{\frac{N}{2}}^{kn}$ 和 $FFT_2(k) = \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n+1)W_{\frac{N}{2}}^{nk}$ 分別是兩個(gè)長(zhǎng)度為 $\frac{N}{2}$ 的FFT運(yùn)算似扔，有：
$X[k] = FFT_1(k) +W_N^k\times FFT_2(k)$
上述有 $n < \frac{N}{2}$ ，考慮后半段結(jié)果搓谆，有：
$FFT_1(k+\frac{N}{2}) =\sum\limits^{\frac{N}{2}-1}_{n=0}x(2n)W_{\frac{N}{2}}^{n(k+\frac{N}{2})} = \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n)W_{\frac{N}{2}}^{nk+\frac{Nk}{2}} = \sum\limits^{\frac{N}{2}-1}_{n=0}x(2n)W_{\frac{N}{2}}^{kn} = FFT_1(k)$
同理有 $FFT_2(k+\frac{N}{2}) = FFT_2(k)$ 炒辉，因此當(dāng) $n \geq \frac{N}{2}$ 時(shí)，考慮 $W_N$ 的周期性泉手，有：
$X[k] = FFT_1(k) + W_N^{k+\frac{N}{2}}\times FFT_2(k) =FFT_1(k) - W_N^k\times FFT_2(k)$
綜上所述對(duì)于一個(gè)N點(diǎn)的FFT運(yùn)算黔寇，有
$X[k] = \begin{cases} FFT_1(k) +W_N^k\times FFT_2(k) & k < \frac{N}{2} \\ FFT_1(k-\frac{N}{2}) -W_N^k\times FFT_2(k-\frac{N}{2}) & k \geq \frac{N}{2} \end{cases}$
其中， $FFT_1$ 為對(duì)偶數(shù)序列的 $\frac{N}{2}$ 點(diǎn)FFT斩萌； $FFT_2$ 為對(duì)應(yīng)奇數(shù)序列的 $\frac{N}{2}$ 點(diǎn)FFT缝裤。該操作將一個(gè)N點(diǎn)FFT分解為兩個(gè) $\frac{N}{2}$ 點(diǎn)的FFT屏轰。

蝶形運(yùn)算

蝶形運(yùn)算為一個(gè)二輸入二輸出的運(yùn)算，公式如下所示：
$Y_1 = X_1 + W \times X_2 \\ Y_2 = X_1 - W \times X_2$
其中 $X_1,X_2$ 為兩個(gè)輸入憋飞； $Y_1,Y_2$ 為兩個(gè)輸出霎苗；W為權(quán)值，均為復(fù)數(shù)搀崭。蝶形運(yùn)算可以用于映射基2FFT叨粘，首先考慮2點(diǎn)FFT猾编，兩點(diǎn)FFT公式如下所示：
$X[0] = x(0)\times W_2^0 + x(1) \times W_2^0 = x(0) + W_2^0 \times x(1) \\ X[1] = x(0)\times W_2^0 + x(1) \times W_2^1 = x(0) - W_2^0 \times x(1)$
因此可以使用一個(gè)蝶形運(yùn)算實(shí)現(xiàn)瘤睹，權(quán)值為 $W_2^k$ ，現(xiàn)考慮一個(gè)4點(diǎn)FFT答倡，首先將其分解為2個(gè)兩點(diǎn)FFT轰传，分解的公式為
$X[k] = \begin{cases} FFT_1(k) +W_N^k\times FFT_2(k) & k < \frac{N}{2} \\ FFT_1(k-\frac{N}{2}) -W_N^k\times FFT_2(k-\frac{N}{2}) & k \geq \frac{N}{2} \end{cases}$
分解步驟也可以用蝶形運(yùn)算實(shí)現(xiàn)，因此整體運(yùn)算如下圖所示：

fft4.png

更多點(diǎn)數(shù)的FFT可以類似的進(jìn)行瘪撇，即不斷分解為長(zhǎng)度為一半的奇偶序列的FFT變換分層實(shí)現(xiàn)获茬。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市倔既，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌，老刑警劉巖离例，帶你破解...
沈念sama閱讀 206,482評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件绽昏，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡实蓬，警方通過查閱死者的電腦和手機(jī)茸俭，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,377評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)安皱，“玉大人调鬓，你說我怎么就攤上這事∽靡粒” “怎么了腾窝？”我有些...
開封第一講書人閱讀 152,762評(píng)論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)居砖。經(jīng)常有香客問我虹脯，道長(zhǎng)，這世上最難降的妖魔是什么悯蝉？我笑而不...
開封第一講書人閱讀 55,273評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任归形，我火速辦了婚禮，結(jié)果婚禮上鼻由，老公的妹妹穿的比我還像新娘暇榴。我一直安慰自己厚棵，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 64,289評(píng)論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布蔼紧。她就那樣靜靜地躺著婆硬，像睡著了一般。火紅的嫁衣襯著肌膚如雪奸例。梳的紋絲不亂的頭發(fā)上彬犯，一...
開封第一講書人閱讀 49,046評(píng)論 1贊 285
城市分裂傳說
那天，我揣著相機(jī)與錄音查吊，去河邊找鬼谐区。笑死，一個(gè)胖子當(dāng)著我的面吹牛逻卖，可吹牛的內(nèi)容都是我干的宋列。我是一名探鬼主播，決...
沈念sama閱讀 38,351評(píng)論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼评也，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼炼杖！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起盗迟，我...
開封第一講書人閱讀 36,988評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤坤邪，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后罚缕，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體艇纺，經(jīng)...
沈念sama閱讀 43,476評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,948評(píng)論 2贊 324
?白月光啟示錄
正文我和宋清朗相戀三年怕磨，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了喂饥。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,064評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡肠鲫，死狀恐怖员帮，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情导饲，我是刑警寧澤捞高，帶...
沈念sama閱讀 33,712評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站渣锦，受9級(jí)特大地震影響硝岗，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜袋毙，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,261評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一型檀、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧听盖，春花似錦胀溺、人聲如沸裂七。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,264評(píng)論 0贊 19
一樁弒父案仓坞，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)背零。三九已至，卻和暖如春无埃，著一層夾襖步出監(jiān)牢的瞬間徙瓶，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,486評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工嫉称，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留侦镇，地道東北人。一個(gè)月前我還...
沈念sama閱讀 45,511評(píng)論 2贊 354
代替公主和親
正文我出身青樓澎埠，卻偏偏與公主長(zhǎng)得像虽缕，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子蒲稳，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,802評(píng)論 2贊 345