因?yàn)橐浦睠SK得寫(xiě)快速傅里葉變換的算法，還是二維的肢专，以前在pc平臺(tái)上只需調(diào)用庫(kù)就可以了舞肆，只是有點(diǎn)印象原信號(hào)和變換之后代表的是什么，但是對(duì)于離散傅里葉變換的來(lái)龍去脈忘得已經(jīng)差不多了博杖，最近要用到椿胯，于是重新來(lái)學(xué)習(xí)一遍，翻出了自己大三當(dāng)時(shí)錄的吳鎮(zhèn)揚(yáng)老師講的數(shù)字信號(hào)處理的視頻剃根，DFT-FFT這里老師講了有10講之多哩盲，但每講都不是很長(zhǎng)，20分鐘左右狈醉，這里記錄一下學(xué)習(xí)的過(guò)程廉油，前面的推導(dǎo)有點(diǎn)多，簡(jiǎn)書(shū)又打不了公式苗傅，mathtype的直接復(fù)制也不過(guò)來(lái)抒线，截圖又太麻煩，也為了自己再推導(dǎo)一遍渣慕，手寫(xiě)了前面一部分的內(nèi)容十兢。圖片形式傳上來(lái)。
簡(jiǎn)單說(shuō)幾句：DTFT有了之后為什么還要搞出來(lái)一個(gè)DFT呢摇庙，其根本原因就是因?yàn)镈TFT的頻域是連續(xù)的旱物，無(wú)法用計(jì)算機(jī)進(jìn)行處理。根據(jù)我們之前得到的的傅里葉變換的規(guī)律：
連續(xù)----非周期
離散----周期
周期----離散
非周期----連續(xù)
根據(jù)這四個(gè)規(guī)律卫袒，只有一種情況可以保證兩個(gè)域都是離散的宵呛，那么就是周期離散的信號(hào)，對(duì)應(yīng)的另外一個(gè)域是離散周期的夕凝，但是我們又知道周期的信號(hào)是沒(méi)有傅里葉變換的宝穗，因?yàn)樵谡麄€(gè)Z平面是不收斂的，這就是一個(gè)問(wèn)題了码秉，討論就從這里開(kāi)始逮矛。
從DTFT到DFS
從DFS到DFT
簡(jiǎn)單的來(lái)說(shuō)，DFT是針對(duì)有限長(zhǎng)序列的转砖，那么怎么來(lái)做DFT呢须鼎，這里的做法是找到其對(duì)應(yīng)的周期延拓序列鲸伴，做DFS，然后再截取主值序列晋控。相當(dāng)于是把DFS引申到有限長(zhǎng)序列里來(lái)汞窗，之所以能夠引申是因?yàn)镈FS的時(shí)域和頻域都是周期的，而且周期還是相同的赡译。
上面討論了DFT的三個(gè)性質(zhì)仲吏，分別是線性，循環(huán)移位和循環(huán)卷積,關(guān)于循環(huán)移位和循環(huán)卷積有必要說(shuō)幾句：
DFT的循環(huán)移位和循環(huán)卷積分別對(duì)應(yīng)著DFS的線性移位和周期卷積蝌焚，這兩者實(shí)際上是有著很強(qiáng)烈的關(guān)系的裹唆，甚至在某種情況下是完全一樣的：那就是當(dāng)我們只關(guān)注DFS的一個(gè)周期時(shí)，循環(huán)卷積和線性卷積是一樣的只洒。(所謂循環(huán)移位就是從一端移出去的要從另一端移進(jìn)來(lái))
看個(gè)例子：
這里的根本原因在于：當(dāng)我們只關(guān)注一個(gè)周期時(shí)许帐，周期序列的線性移位和和非周期序列的循環(huán)移位的結(jié)果是完全相同的。
移位
上面都是向右移動(dòng)兩個(gè)單位红碑，如果只關(guān)注主值的話舞吭，循環(huán)移位和線性移位的結(jié)果是完全一樣的泡垃。正是由于這個(gè)原因析珊，所以才有了循環(huán)卷積，卷積里也有移位的操作蔑穴，循環(huán)卷積和周期卷積來(lái)說(shuō)忠寻，如果只關(guān)注一個(gè)主值序列的話，那么結(jié)果是一樣的存和。
關(guān)于循環(huán)卷積還有一些更重要的性質(zhì)奕剃。
循環(huán)卷積（針對(duì)兩個(gè)有限長(zhǎng)序列）
-
若：頻域點(diǎn)積
則有：
時(shí)域循環(huán)卷積
主要意思：時(shí)域循環(huán)卷積相當(dāng)于頻域點(diǎn)積。 - 計(jì)算過(guò)程：
① 有限長(zhǎng)序列構(gòu)造周期序列
② 計(jì)算周期卷積
③ 周期卷積取主值
循環(huán)卷積是可以用DFT來(lái)做的捐腿，因?yàn)?的性質(zhì)纵朋，如果直接用DFT來(lái)做的話，計(jì)算量實(shí)際上是要比卷積大的茄袖， 但是因?yàn)槲覀冇蠪FT操软，所以許多情況下循環(huán)卷積還是可以通過(guò)FFT來(lái)做的，而且計(jì)算量會(huì)大大減小宪祥，特別是其中的一個(gè)序列不變的情況下（比如濾波器聂薪，那么這個(gè)濾波器只需要做一次FFT）。
這樣可能又有疑問(wèn)了：對(duì)于線性系統(tǒng)來(lái)說(shuō)（比如脈沖響應(yīng)）蝗羊，是通過(guò)線性卷積來(lái)算的藏澳，移出去就不會(huì)再移回來(lái)了，那么貌似循環(huán)卷積又沒(méi)什么用了耀找？答案肯定是否定的翔悠！，如果是這樣我們討論著半天不是白說(shuō)了？實(shí)際上凉驻，在某些情況下是可以用循環(huán)卷積來(lái)計(jì)算線性卷積的腻要，下面討論這種情況，看下要滿足什么條件涝登。 - 有限長(zhǎng)序列的循環(huán)卷積和線性卷積雄家。
上面說(shuō)了：循環(huán)卷積在一定條件下可以計(jì)算線性卷積。
假設(shè)有兩個(gè)有限長(zhǎng)序列：x(n)和y(n)胀滚，長(zhǎng)度分別為N,M趟济，那么線性卷積的長(zhǎng)度是N+M-1（算一下就知道了）。
那么我們?nèi)绻麑?duì)這兩個(gè)序列做循環(huán)卷積呢咽笼？要做循環(huán)卷積顷编，序列長(zhǎng)度首先得一樣，那么怎么變得一樣呢剑刑？在后面添0媳纬。添多少呢？現(xiàn)在還不知道施掏。
我們假設(shè)添到L(L>max(M,N))钮惠，添0對(duì)線性卷積是沒(méi)有影響的，為了分析兩者的循環(huán)卷積七芭，先看其周期延拓：
周期延拓
那我們先把周期卷積算一下：
周期卷積
結(jié)論就是：周期卷積相當(dāng)于線性卷積(上面紅色的字打錯(cuò)了素挽，我不小心把mathtype關(guān)了，懶得改了)的周期搬移狸驳。而循環(huán)卷積是周期卷積的主值序列预明。
這樣就說(shuō)明說(shuō)明呢？說(shuō)明周期卷積是線性卷積的周期延拓的關(guān)系耙箍，延拓的周期是L撰糠。
這時(shí)候就要關(guān)注混疊了，因?yàn)長(zhǎng)必須足夠長(zhǎng)才能保證搬移的時(shí)候不會(huì)發(fā)生混疊辩昆，結(jié)合上面線性卷積的長(zhǎng)度阅酪，那么L的長(zhǎng)度最少就是L>=N+M-1，這樣才不會(huì)產(chǎn)生混疊卤材。這樣取主值區(qū)間才能取到線性卷積的結(jié)果遮斥。
這樣就可以用循環(huán)卷積做線性卷積。
共軛對(duì)稱性
設(shè)x(n)的共軛復(fù)序列是x*(n).則：
DFT[x*(n)]=X*(N-K)
證明：
由于W是周期的扇丛，且周期是N术吗，所以可以寫(xiě)作：
看這個(gè)結(jié)果和DFS其實(shí)是一樣的，這里只不過(guò)把它移動(dòng)到主值區(qū)間上罷了帆精。
分別x(n)看實(shí)部和虛部：
根據(jù)線性變換的性質(zhì)较屿，實(shí)部和虛部分別做DFT隧魄，那么可以得到：
那么顯然是有：
為什么把上面的叫做奇對(duì)稱和偶對(duì)稱分量呢？看下面的推導(dǎo)隘蝎，對(duì)于偶對(duì)稱來(lái)說(shuō)：
即：
同理的：共軛奇對(duì)稱分量為：
實(shí)際上：共軛偶對(duì)稱就是實(shí)部DFT的結(jié)果购啄，共軛奇對(duì)稱是虛部DFT的結(jié)果，滿足這樣的關(guān)系嘱么。
那么對(duì)于純實(shí)數(shù)序列來(lái)說(shuō)狮含，其只存在共軛偶對(duì)稱部分，表明實(shí)數(shù)序列的DFT滿足共軛偶對(duì)稱性曼振，利用這一特性几迄，只要知道一半數(shù)目的X(k)，就可以得到另一半冰评，這一特點(diǎn)可以在DFT運(yùn)算中加以利用映胁，提高運(yùn)算效率。甲雅。
還有一個(gè)例子：對(duì)于一個(gè)實(shí)數(shù)序列（長(zhǎng)度為n）來(lái)說(shuō)解孙，其DFT是2n個(gè)點(diǎn)（那個(gè)虛數(shù)），數(shù)據(jù)量是增加了一倍了的抛人，而他們之間只是線性變換而已弛姜，為什么多了這么多數(shù)據(jù)？實(shí)際上用共軛偶對(duì)稱可以很好解釋函匕，實(shí)際上沒(méi)有多娱据，有一半的數(shù)據(jù)就可以通過(guò)共軛對(duì)稱性得到另外一半蚪黑。
另外值得一提的是：DFT的兩端是對(duì)稱的盅惜，即x(n)與X(K)是對(duì)稱的，那么如果把頻域作為原始數(shù)據(jù)忌穿，依然可以找到時(shí)域的共軛偶對(duì)稱和奇對(duì)稱部分抒寂。不細(xì)說(shuō)了。
選頻性
DFT具有選頻性掠剑。
進(jìn)行采樣：
其中
其中q是整數(shù)屈芜，w0=2pi/N時(shí)：
這個(gè)式子前面討論過(guò)，這是n個(gè)模為1的向量朴译，只有k=q+sN時(shí)是1井佑，其他時(shí)候都是0，在這個(gè)主值序列里就是k=q眠寿。
這個(gè)是顯而易見(jiàn)的躬翁，如果輸入序列只有一個(gè)頻率，那么對(duì)這個(gè)序列采樣再進(jìn)行DFT就應(yīng)該只有一個(gè)頻率是有值的盯拱。
當(dāng)如數(shù)頻率是qw0時(shí)盒发，變換X(k)的N個(gè)值中只有X(q)=N,其余均是0例嘱，如果輸入信號(hào)為若干不同頻率的信號(hào)的組合，經(jīng)離散傅里葉變換后宁舰，這些頻率對(duì)應(yīng)的X(k)應(yīng)有對(duì)應(yīng)輸出拼卵，因此，離散傅里葉變換算法實(shí)質(zhì)上對(duì)頻率有選擇性蛮艰。
看個(gè)題：
一個(gè)余弦序列腋腮，頻率是qw0,這樣得到的頻譜就是兩條線，一個(gè)q壤蚜，一個(gè)其對(duì)稱位置低葫。這也驗(yàn)證了剛才共軛偶對(duì)稱的性質(zhì)。
DFT和z變換仍律。
DFT是DTFT頻域采樣的結(jié)果嘿悬。
這樣采樣也會(huì)有問(wèn)題的，就相當(dāng)于通過(guò)一個(gè)柵欄來(lái)觀察DTFT的結(jié)果水泉，肯定有信息丟失善涨，可能就會(huì)有有問(wèn)題，到底采樣密度怎樣才是好的草则。
實(shí)際上從上面討論中可以看到了钢拧，N個(gè)點(diǎn)的DFT是N個(gè)點(diǎn)，所以在頻域的采樣數(shù)M的條件應(yīng)該是：M>=N炕横。
證明：
這個(gè)證明的關(guān)鍵也是在于交換了一個(gè)積分順序源内，結(jié)論是很直觀的，就是在頻域采樣就相當(dāng)于是在時(shí)域周期延拓份殿，那么對(duì)于一個(gè)長(zhǎng)度為N的序列膜钓，只有當(dāng)以大于N的周期去延拓時(shí)才不會(huì)發(fā)生混疊，所以頻域的采樣應(yīng)該至少是N個(gè)點(diǎn)卿嘲。把這個(gè)直觀的結(jié)果記住颂斜，具體的證明如果要用到查書(shū)即可。
中間吳老師還講了帕斯瓦爾定力拾枣，一些信號(hào)處理的流程沃疮，把整個(gè)知識(shí)串起來(lái)的，我快快得看了一遍梅肤。已經(jīng)等不及去看FFT了司蔬。
頻譜泄露這一次才真正理解了，頻譜泄露就是加窗時(shí)發(fā)生的姨蝴，離散周期信號(hào)要進(jìn)行DFT時(shí)要進(jìn)行截?cái)嗫√洌绻皇钦芷诮財(cái)啵鯠FT得到的頻譜就會(huì)發(fā)生泄露似扔，本質(zhì)的原因就是周期延拓的時(shí)候就不是原先的信號(hào)了（因?yàn)闆](méi)有整周期截?cái)啵┒中@個(gè)是個(gè)充要條件搓谆。
其他的就不說(shuō)了。
從DFT到FFT
DFT并不是新的算法豪墅，但是直到FFT的發(fā)現(xiàn)泉手，才讓DFT真正運(yùn)用到工業(yè)和生活中，1965年cooley(IBM)和Tukey(MIT)提出了2FFT（2的冪次）算法偶器。這樣使得DFT的計(jì)算量提高了1,2數(shù)量級(jí)（與N有關(guān)）斩萌。這個(gè)是基2的DFT算法。
實(shí)際上還有其他的算法屏轰，一個(gè)典型的算法是：76年IBM的S.Winograd博士推導(dǎo)了WFTA算法颊郎，使FFT得運(yùn)算再次下降很多，但是由于其用到了取模運(yùn)算來(lái)映射地址霎苗，而這種尋址是非常耗時(shí)的姆吭，所有大數(shù)據(jù)的FFT都不用了，只在一些小范圍內(nèi)還有運(yùn)用（查表方式取模）,這段是吳老師科普的唁盏。
下面主要介紹基2的FFT的算法：
DFT的計(jì)算内狸。
首先我們看下要進(jìn)行n點(diǎn)DFT運(yùn)算時(shí)要進(jìn)行的計(jì)算量：
實(shí)際上這兩者變換只是差了一個(gè)指數(shù)的負(fù)號(hào)和一個(gè)常數(shù)，其計(jì)算量是完全相同的厘擂。這里只討論正變換的計(jì)算量：
一般來(lái)說(shuō)昆淡，我們認(rèn)為x(n),W,X(k)都是復(fù)數(shù)，那么每計(jì)算一個(gè)k刽严，需要N的復(fù)數(shù)乘法昂灵，以及N-1個(gè)復(fù)數(shù)加法（N個(gè)相加），一共需要計(jì)算N各k舞萄，所以一次N點(diǎn)的DFT要用到：
N*N的復(fù)數(shù)乘法和N(N-1)的復(fù)數(shù)加法眨补。
而實(shí)際上復(fù)數(shù)的乘法和加法都是通過(guò)實(shí)數(shù)完成的，每一次復(fù)數(shù)乘法需要4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法鹏氧，所以最后換算到實(shí)數(shù)計(jì)算量：
每一次N點(diǎn)的DFT所需的計(jì)算量：4N^2次乘法和2N(2N-1)次加法渤涌。
DFT有幾個(gè)特點(diǎn)：
-
系數(shù)W是周期的和對(duì)稱的佩谣。
- 計(jì)算量是正比于N^2的把还，所以當(dāng)N比較小的時(shí)候，計(jì)算量是可以接受的茸俭，所以一個(gè)思路就是把大的序列拆成小的序列吊履。
基2的FFT主要有兩種，按時(shí)間抽取的和按頻率抽取的调鬓。重點(diǎn)說(shuō)按時(shí)間抽取的艇炎，即按照n抽取的。
按時(shí)間抽取的基2FFT
首先我們假定序列x(n)長(zhǎng)度是2^M,不夠的話補(bǔ)零腾窝。
帶入求DFT得公式之中：
由于：
則有：
這兩個(gè)求和實(shí)際上還是DFT缀踪，分別是偶數(shù)序列和奇數(shù)序列的居砖，點(diǎn)數(shù)均是N/2。然后加權(quán)求和驴娃。
根據(jù)上面分析的疆柔，則有：其實(shí)我一開(kāi)始很糾結(jié)這塊關(guān)于括號(hào)里的2r奏候，這個(gè)其實(shí)不要被表面蒙騙了，雖然是2r,但是在這個(gè)序列里還是代表的是第r個(gè)數(shù)唇敞，所有求和符號(hào)與W里都化簡(jiǎn)成了r蔗草，都是從0開(kāi)始到N/2的自然數(shù)。
其中兩個(gè)x分別是偶數(shù)序列和技術(shù)序列咒精，這樣就很明顯了，就是兩個(gè)分離的DFT旷档。
但是我們知道模叙，N點(diǎn)對(duì)應(yīng)的DFT的點(diǎn)數(shù)是N點(diǎn)，這兩個(gè)都是N/2的鞋屈，那么對(duì)應(yīng)變換再求和還是只有N/2個(gè)點(diǎn)啊向楼，但是X(k)應(yīng)該是有N個(gè)點(diǎn)的，怎么會(huì)少了一半呢谐区？帶著這個(gè)疑問(wèn)再往下看吧湖蜕。
其中G(k)和H(k)分別代表偶數(shù)序列和奇數(shù)序列的DFT。都是以N/2為周期的宋列。
所以：
前面證明過(guò)：
所以有：
所以N點(diǎn)的DFT可以拆成奇偶兩部分昭抒，然后分別以不同形式加權(quán)（加和減）獲得，前一半的k做加法炼杖，后一半做減法灭返，這樣就能得到N點(diǎn)的DFT結(jié)果。
如果我們簡(jiǎn)化用a坤邪，b熙含，w分別表示上面的式子，那么我們需要計(jì)算兩個(gè)式子：
畫(huà)的這個(gè)圖就是簡(jiǎn)化的地方：右邊的計(jì)算只需要一次復(fù)數(shù)乘法（wb只需要計(jì)算一次）和兩次復(fù)數(shù)加法艇纺。這就是一個(gè)蝶形運(yùn)算怎静。
到這里歸納一下：一個(gè)偶數(shù)點(diǎn)的DFT可以分成奇偶兩部分，然后通過(guò)蝶形運(yùn)算加權(quán)起來(lái)黔衡，我們這里取得N是2的m次冪蚓聘，所以這樣我們可以按照這個(gè)思想一致分下去，一直分到2為止盟劫。
先看一個(gè)簡(jiǎn)單的：
以N=8為例夜牡，做一次奇偶分解，然后通過(guò)蝶形運(yùn)算組合起來(lái)：
這個(gè)很好理解吧侣签，還可以再拆一次塘装，拆的過(guò)程省略了急迂，直接看計(jì)算的結(jié)果：
x的下標(biāo)是分解的結(jié)果，x1是第一次分解的偶數(shù)蹦肴，x2是第一次分解的奇數(shù)袋毙，x3是x1分解的偶數(shù)，x4是x1分解的奇數(shù)冗尤，以此類推听盖。
稍微有疑問(wèn)的一點(diǎn)可能是做完N/4的DFT之后的因子為什么是W(N-0)和W(N-2）,這是因?yàn)椋?div id="5vz9thr" class="image-package">
