正交變換及其快速算法

1、3/17/2024,1,正交變換及其快速算法,3.1 快速傅里葉變換(FFT),FFT算法分類： 1) 按時(shí)間抽取(DIT) 2) 按頻率抽取(DIF),快速傅里葉變換(FFT),3/17/2024,2,3.1.1 按時(shí)間抽取(DIT)的FFT,按時(shí)間抽取(DIT)的FFT,3/17/2024,3,這樣，一個(gè)N點(diǎn)的DFT被分解成兩個(gè)N/2點(diǎn)的DFT,3/17/2024,4,3/17/2024,5,總結(jié)

2、：FFT算法的兩個(gè)特點(diǎn) 1) 原位運(yùn)算 即每一級(jí)運(yùn)算的結(jié)果仍然存儲(chǔ)在原來的存儲(chǔ)器中 2) 變址 輸入倒序，輸出順序，存在“碼位倒置”,3/17/2024,6,3.1.2 按頻率抽取(DIF)的FFT,按頻率抽取(DIF)的FFT,3/17/2024,7,3/17/2024,8,3.1.3 IFFT的運(yùn)算方法,算法一：FFT流圖中所有系數(shù)變符號(hào)，再除以常數(shù)N,

3、 然后輸入輸出位置對(duì)換，即為IFFT,算法二：改變蝶形公式 時(shí)間抽取的FFT－－－頻率抽取的IFFT 頻率抽取的FFT－－－時(shí)間抽取的IFFT,IFFT的運(yùn)算方法,3/17/2024,9,3.1.4 混合基FFT算法,定義：當(dāng)N是一個(gè)復(fù)合數(shù),即可把N分解成一些因子的乘積 則可以用FFT的一般算法,混合基FFT算法,3/17/202