基于實(shí)乘子的快速傅立葉變換

基于實(shí)乘子的快速傅立葉變換

離散furing變換自1965年裂紋突變（fft突變）提出以來(lái)，分散fowier變換在許多頻率下得到了廣泛應(yīng)用。但是對(duì)于實(shí)時(shí)性要求很高的引信而言,其應(yīng)用還是受到變頻處理速度的限制,而很難應(yīng)用到實(shí)際中。特別是目前的調(diào)頻引信的信號(hào)處理中。所以近年來(lái),人們對(duì)如何提高FFT的變換速度算法的研究一直在繼續(xù),見(jiàn)文獻(xiàn)1算法的組成1.1dft的一般性質(zhì)首先定義四種離散變換形式DFT-J(J=1,2,3,4)。DFT-J是將輸入長(zhǎng)度為N(N=2其正變換公式如下:顯然(1)式就是我們通常意義下的DFT,若將輸入序列x(n)和輸出序列X(k)均看作N維列向量,且分別記作同時(shí)由(1)、(2)、(3)、(4)式還可以得到變換矩陣具有如下性質(zhì):1.2實(shí)時(shí)dft變換的實(shí)乘子算法記DFT-1的變換矩陣FN1的第k行、第n列元素為fN1(k,n),即當(dāng)當(dāng)再對(duì)將上式按虛線所示進(jìn)行分塊,注意變換矩陣的形式,可上式左角恰好為利用矩陣的Kronecker直和和Kronecker直積計(jì)算公式見(jiàn)文獻(xiàn)上式中Q為初等行變換陣,由上述的推導(dǎo)過(guò)程可以得到Q為N維方陣。由初等行變換的性質(zhì)可知,Q可逆,Q同理可得式(15)、(16)、(17)給出四種DFT變換的內(nèi)在關(guān)系和實(shí)乘子算法的基本思路,可以看出一個(gè)N點(diǎn)的DFT-1可以由一個(gè)N/2點(diǎn)的DFT-1和一個(gè)N/2點(diǎn)的DFT-3構(gòu)成,若由(17)式將在(4)式中利用恒等式:所以從而其中其中因此若x(n)為復(fù)序列,則經(jīng)過(guò)2N次實(shí)乘((18)式和2N次實(shí)加((19)式)運(yùn)算后,一個(gè)N點(diǎn)的DFT-4可換算成一個(gè)N點(diǎn)的DFT-3的形式,用矩陣表示為其中由(16)、(20)式可得即就是,將此式和(15)式聯(lián)和起來(lái)就構(gòu)成我們的實(shí)乘子快速算法公式:即計(jì)算一個(gè)N點(diǎn)的DFT-1可以分成一個(gè)N/2點(diǎn)的DFT-1和一個(gè)N/2點(diǎn)的DFT-3,而一個(gè)N/2點(diǎn)的DFT-3可以由二個(gè)N/4點(diǎn)的DFT-3計(jì)算來(lái)構(gòu)成,分成N/2點(diǎn)后,再按(21)式繼續(xù)分解,直至N=2的最簡(jiǎn)單的情況。從而得到計(jì)算DFT的實(shí)乘子的快速算法。2算法的應(yīng)用實(shí)驗(yàn)我們以長(zhǎng)度為N=2從上述流圖中可以看出運(yùn)算簡(jiǎn)單規(guī)則,易于實(shí)現(xiàn)。用Matlab語(yǔ)言和TMS320系列芯片的匯編語(yǔ)言,我們都進(jìn)行了算法的應(yīng)用實(shí)踐,都得到了理想的結(jié)果。我們?nèi)匀灰蚤L(zhǎng)度為N=23同址計(jì)算的個(gè)頻率很從上面的分析和比較中可以看出,利用實(shí)乘子算法在處理短數(shù)據(jù)點(diǎn)時(shí)不僅可以大大減少變域運(yùn)算中的乘法次數(shù),而且也減少了加法次數(shù),使得整個(gè)變頻的處理速度大大提高,使困擾調(diào)頻引信變頻速度的問(wèn)題,不在僅僅通過(guò)提高器件的處理速度,得以解決。從而大大降低了產(chǎn)品研制的成本。但是該算法在用同址計(jì)算時(shí)加大了數(shù)據(jù)的交換量(特別是在處理長(zhǎng)數(shù)據(jù)點(diǎn)時(shí)尤為突出),使該算法在計(jì)算過(guò)程中處理速度雖然有明顯的提高,但并不