小小的研究快速傅里葉的原因是老師講完了快速傅里葉，還在云里霧里時(shí)，老師讓人用C語言寫出來，覺得難得好笑，然后就點(diǎn)名到我了。

  公式推導(dǎo)：從傅里葉到推導(dǎo)到快速傅里葉，這樣的公式推導(dǎo)書上，網(wǎng)上太多了，我就不在這里詳細(xì)推導(dǎo)了。會(huì)列出及重要的結(jié)果：幫助我使用快速傅里葉。

這個(gè)圖只有一維， 也是蝶形算法最基本最簡單的一個(gè)，最好理解?？吹诙€(gè)框圖，前端輸入是x（），右邊是X（），也就是傅里葉變換的結(jié)果，1框圖是詳細(xì)計(jì)算步驟，就這兩步，特別簡單，本身傅里葉特別復(fù)雜，計(jì)算量特別大，這個(gè)我們介紹的算法相比之下，計(jì)算量大大減小，減少多少看書就知道了。

上圖最基本的單位大概理解了，下面是基本的公式估計(jì)也就理解了：

不理解的話，小小的解釋下，左邊是傅里葉結(jié)果，右邊的輸入x1(k),x2(k),Wnk,,估計(jì)就Wnk不理解，另兩個(gè)就是從前端的輸入來的，Wnk，我就動(dòng)手解釋下怎么算的：

上圖把Wnk轉(zhuǎn)化為復(fù)數(shù)，這樣那個(gè)Wnk才能真正的用于實(shí)踐，看了這個(gè)東西，估計(jì)也不會(huì)算，反正我只看了我也不會(huì)，先不管那個(gè)N，k，先看看八位蝶形算法：

原理最關(guān)鍵的就是這個(gè)，左端輸入，通過很多小的蝶形運(yùn)算基本單位，就可以得到左端的結(jié)果。正常的人都可以發(fā)現(xiàn)出來的順序好像出問題了，規(guī)律直接告訴：

就是把所屬的序號(hào)轉(zhuǎn)化為二進(jìn)制，進(jìn)行l(wèi)og2N次圓周移位。這是我總結(jié)的，比書上的簡單，輸入自然序出來倒序，輸入倒序出來自然序。

講到這里，應(yīng)該是懂了怎么算，但是為啥要這么算，得看書去，公式推導(dǎo)，我自己推估計(jì)也不行，但是知道怎么回事就行。

開始講程序了，程序里的注釋應(yīng)該很簡單明了，根據(jù)上面的理解估計(jì)應(yīng)該沒問題，加上我的文字解釋真的太簡單了。

這兩個(gè)頭文件，估計(jì)都知道，能運(yùn)行C語言的環(huán)境基本上都有，這個(gè)沒問題。

定義兩個(gè)參數(shù)：N，就是輸入多少個(gè)點(diǎn)，也就是數(shù)據(jù)，必須滿足2的多少次方，8,16,64,128，等等；那個(gè)log2N，就是2的多少次方的那個(gè)多少，比如說，64，就是2的6次方。

先定義一個(gè)結(jié)構(gòu)體，就是復(fù)數(shù)的實(shí)部real，虛部img，很多頭文件complex都有相關(guān)的定義，但是那個(gè)頭文件麻煩，兼容性不好，所以這里主動(dòng)自己定義了。

x[N]這個(gè)結(jié)構(gòu)體數(shù)組就是輸入的數(shù)組，虛部都是0，因?yàn)椴蓸踊貋淼臎]有虛部，順便說明下，下面的運(yùn)算基本上都是復(fù)數(shù)的方式進(jìn)行的。

這里定義了一個(gè)數(shù)組，按照道理來說，應(yīng)該程序自己算啊，其實(shí)是這樣的，在實(shí)際的工程應(yīng)用當(dāng)中，這樣的運(yùn)算是認(rèn)為有點(diǎn)浪費(fèi)資源的，而且應(yīng)用當(dāng)中輸入的點(diǎn)數(shù)也就是數(shù)據(jù)。都是固定的，所以直接計(jì)算好了定義成數(shù)組，方便高效。

這樣的數(shù)據(jù)哪里來的呢，方法有很多比如EXCEL，或者matlab，或者其他的，我推薦使用matlab，寫一個(gè)小程序就行了：如圖所示

多少位的改上面的參數(shù)就行了，順便說一下，這是我第一次使用matlab做那么一點(diǎn)有用的事。

這里定義幾個(gè)子函數(shù)，懂復(fù)數(shù)的人基本上都知道，如果忘了也沒關(guān)系，反正懂了這個(gè)久了不用也會(huì)忘記，會(huì)調(diào)用就行。

前面將原理的時(shí)候說了，輸入自然序出來倒序，輸入倒序，出來自然序，所以必須將倒倒序轉(zhuǎn)化為自然序，因?yàn)槲覀兿胍目隙ㄊ禽斎胱匀恍颍敵鲎匀恍颉?/p>

其實(shí)得到自然序，主要的就是這個(gè)位運(yùn)算，要是熟悉代碼的人，一看就明白，不熟悉的自己下來仔細(xì)推導(dǎo)一下。

最后那個(gè)if可能很多人就不明白了，很簡單，比如八位的輸入01234567輸出04261537，這里發(fā)現(xiàn)，需要交換數(shù)據(jù)的1和4,3和6，只需要交換一次就可以。

最關(guān)鍵的就是這個(gè)算法了，就是所謂的蝶形運(yùn)算，給了圖我覺得真的不容易懂，我反正看圖叫我寫出來也不可能，因?yàn)槲腋静磺宄降资窃鯓拥玫捷敵龅摹?/p>

下面說說我的理解，這段文字配合上面的蝶形運(yùn)算的圖哈，其實(shí)就是算每一個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)都是利用，里面的每一個(gè)參數(shù)我都講了，我們計(jì)算的時(shí)候，如果想知道某一個(gè)輸出的結(jié)果，那個(gè)必須知道前一級(jí)對(duì)應(yīng)的節(jié)點(diǎn)，然后前一級(jí)對(duì)應(yīng)的節(jié)點(diǎn)又必須知道更前一級(jí)的某些節(jié)點(diǎn)，有些人可能還是不清楚怎樣才知道自己需要前一級(jí)的那些節(jié)點(diǎn)呢，有這樣疑問的同志估計(jì)還是不明白那個(gè)蝶形圖到底怎么回事，那個(gè)圖就是告訴咩一個(gè)數(shù)據(jù)對(duì)應(yīng)的關(guān)系，前者箭頭指向后者就是后者需要前者，這很明了了。

這里說說算法的基本思想流程，先算第一級(jí)蝶形運(yùn)算，，每一個(gè)第一級(jí)都要算完，然后再算，每一級(jí)每一個(gè)數(shù)據(jù)都要算完，這樣才能算下一級(jí)，以此類推，算出最終結(jié)果。

算法里有三重運(yùn)算，每一個(gè)變量也就是ijk，這三個(gè)循環(huán)變量的封頂?shù)哪莻€(gè)數(shù)據(jù)，其實(shí)很容易理解，先假設(shè)輸入八位數(shù)據(jù)，然后把相應(yīng)的封頂數(shù)據(jù)算出來，再弄個(gè)16個(gè)數(shù)據(jù)的，規(guī)律自己就出來了，自己動(dòng)手算一下，就明白了。

需要的函數(shù)都講完了，理解與否看造化。下面是主函數(shù)和輸出的結(jié)果。

這里的數(shù)據(jù)結(jié)果和matlab完全符合，matlab那個(gè)數(shù)據(jù)我沒有截圖，但是是完全正確的。