什麽(me) 是快速傅裏葉變換？
快速傅裏葉變換
模擬信號使用傅裏葉變化公式，數字信號可以采用離散傅裏葉變化公式，但是離散傅裏葉變化公式計算量大，所以對於(yu) 離散的信號，現
在都是采用快速傅裏葉變化（Fast Fourier Transformation)
這裏以一個(ge) 隨機信號表示離散的信號
依據上述公式，如果計算X(k)，乘法計算8（num）次，加法計算7（num-1）次，計算所有的頻譜，需要乘法64（num^2）次，加
法計算56（num×(num-1)）次。假設乘法使用四個(ge) 時間周期T，加法使用一個(ge) 時間周期T，那麽(me) 8個(ge) 數據占據的周期大約是312T
將這個(ge) 公式和一些軟件計算的結果進行對比，結果是一樣的
FFT
下述公式，首先將係數奇數項和偶數項分開，然後偶數想提出公因式e^(-I 2π/N k)，保持兩(liang) 個(ge) 多項式的e指數有相同的形式，最後合並
2和N，奇數和偶數項構成新的多項式。
假設序列的長度為(wei) 8，按照上述規則，將序列按照奇偶不斷的分裂，直到最後
觀察最後一個(ge) 等號後的公式，從(cong) 小括號，到中括號，到大括號，每個(ge) 括號作為(wei) 一層，可以得到網上的蜘蛛圖
首先從(cong) 小括號看起，小括號內(nei) x0,x2,x4,x6沒有係數，而x1,x3,x5,x7的係數是exp(-8iπk/N)，k從(cong) 0到7內(nei) 取任何整數，exp(-8iπk/N)無
非是+1或者是-1，所以看到在x1,x3,x5,x7後麵可能跟隨著兩(liang) 個(ge) 係數W_N^0或者-1，就是表示相乘的意思，然後在紅色方框內(nei) 相遇
，相遇代表相加。他們(men) 是第一層，同時作為(wei) 下一層的輸入。下一層輸入的係數是exp(-8iπk/N)，k從(cong) 0到7改變，係數可出現四種，
按照圖上的表示應該是
，同時它也作為(wei) 第二層結果，同理可以得到第三層結構。每一層結構有8個(ge) 數據，每個(ge) 數據
都結構都是做了一次乘法和一次加減法。相對於(yu) DFT而言，DFT做乘法64次，而這裏做的乘法隻有不到8*lg8，也就是大約24次左右
，因此能夠節省很多時間。
上麵的叉形圖中，最後的數字排列也是存在規律的。
二維傅裏葉變化FFT2是對一個(ge) 二維矩陣，先做一次FFT，然後轉置後再做一次FFT。這裏以一個(ge) 實際的例子作為(wei) 參考，輸入的信號是一個(ge) 3*3的矩陣
如果用matlab表示信號x，兩(liang) 次FFT變化可以寫(xie) 為(wei) fft(fft(x),3,2)，一次FFT變化可以記作fft2(x)
您可以通過我們(men) 的官方網站了解更多的国产欧美在线信息，或直接來電谘詢4006-888-532。
展示全部 
展示全部
