ch循環(huán)卷積ppt課件-資料下載頁
2025-01-06 13:34本頁面
【正文】 入運算器并進行蝶形運算。 注意：流圖中各蝶形的輸入量或輸出量是互不相重的 ， 任何一個蝶形的二個輸入量經(jīng)蝶形運算后 ，便失去了利用價值 ， 不再需要保存 。 華中科技大學(xué)電信系 58 第 1級運算 :x(1)和 x(5)運算后，結(jié)果送到 M(5)和 M(6)保存， x(3)和 x(7)運算后 ， 結(jié)果送到 M(7)和 M(8)保存 。 第 2級運算 : M(5)和 M(7)運算后，結(jié)果送到 M(5)和 M(7)保存， M(6)和 M(8)運算后 ， 結(jié)果送到 M(6)和 M(8)保存 。 所以 ， 蝶形運算后的結(jié)果便可以送到 M(5)和 M(6)存儲起來 。 直至完成最后一級運算，中間不需要其它存貯器。 ?同址運算的好處：節(jié)省存貯單元。當 N越大，好處越明顯。 華中科技大學(xué)電信系 59 M(1) M(2) M(3) M(4) M(5) M(6) M(7) M(8) 與圖 華中科技大學(xué)電信系 60 可以看出， 每一級的蝶形的輸入與輸出在運算前后可以存儲在同一地址 (原來位置上 )的存儲單元中，這種同址運算的優(yōu)點是 可以節(jié)省存儲單元 ，從而降低對計算機存儲量的要求或降低硬件實現(xiàn)的成本。 蝶形運算的特點是，首先每一個蝶形運算都需要兩個輸入數(shù)據(jù)，計算結(jié)果也是兩個數(shù)據(jù)，與其它結(jié)點的數(shù)據(jù)無關(guān)，其它蝶形運算也與這兩結(jié)點的數(shù)據(jù)無關(guān)。 因此，一個蝶形運算一旦計算完畢，原輸入數(shù)據(jù)便失效了。這就意味著輸出數(shù)據(jù)可以立即使用原輸入數(shù)據(jù)結(jié)點所占用的內(nèi)存。原來的數(shù)據(jù)也就消失了。 ?輸出、輸入數(shù)據(jù)利用同一內(nèi)存單元的這種蝶形計算稱為原位 (同址 )計算 。 華中科技大學(xué)電信系 61 3．變址計算 從圖 3. 19所示的流程圖看出，輸入 x(n)是“混序”排列的。所謂輸入為“混 序”，并不是說輸入是雜亂無章的，實際上它是有規(guī)律的。如果輸入 x(n)的序號用二進制碼來表示，就可以發(fā)現(xiàn)輸入的順序恰好是正序輸入的“ 碼位倒置 ”，表 3. 3列出了這種規(guī)律。 華中科技大學(xué)電信系 62 在實際運算中，按碼位倒置順序輸入數(shù)據(jù) x(n)， 特別當 N較大時，是很不方便的。因此，數(shù)據(jù)總是按自然順序輸入存儲，然后通過“變址”運算將自然順序轉(zhuǎn)換成碼位倒置順序存儲。實現(xiàn)這種轉(zhuǎn)換的程序可用圖 3. 21來說明。 華中科技大學(xué)電信系 63 圖中用 n表示自然順序的標號，用 l表示碼位倒置的標號。 ?當 l=n時 ， x(n)和 x(l)不必互相調(diào)換 。 ?當 l≠n時， 必須將 x(l)和 x(n)互相調(diào)換，但只能調(diào)換一次，為此必須規(guī)定 每當 ln時 ，要將 x(l)和 x(n)相互調(diào)換 ，即把原來存放 x(n)的存儲單元中的數(shù)據(jù)調(diào)入存儲 x(l)的存儲單元中，而把原來存儲 x(l)的存儲單元中的數(shù)據(jù)調(diào)入到存儲x(n)的存儲單元中。 這樣，按自然序輸入的數(shù)據(jù) x(n)經(jīng)過變址計算后變成了碼位倒置的排列順序，便可進入第 1級的蝶形運算。 華中科技大學(xué)電信系 64 時間抽選 FFT算法的 其他形式的流程圖： 對于任何流程圖，只要 保持各節(jié)點所連支路及其傳輸系數(shù)不變 ，則不論節(jié)點位置怎樣排列，所得到的流程圖總是 等效 的，因而都能得到 DFT的正確結(jié)果，只是數(shù)據(jù)的提取和存儲次序不同而已。 ?圖 3. 22所示的流程圖相當于最初由庫利和圖基給出的時間抽選算法。－－輸入正序，輸出混序 華中科技大學(xué)電信系 65 與圖 3. 19比較 華中科技大學(xué)電信系 66 ?輸入和輸出都是正序排列 ?這類流程圖不能進行同址計算，因而需要兩列長度為 N的復(fù)數(shù)存儲器。 M(1) M(2) M(3) M(4) M(5) M(6) M(7) M(8) 華中科技大學(xué)電信系 67 ?DecimationInFrequency FFT ?頻率抽選基 2FFT算法簡稱為頻率抽選 ?它的推導(dǎo)過程遵循兩個規(guī)則： ①對時間序列前后分； ②對頻率序列偶奇分。 對比： 時間抽選的分解過程遵循兩條規(guī)則： ①對時間序列偶奇分； ②對頻率序列前后分。 頻率抽選基 2FFT算法 華中科技大學(xué)電信系 68 FFT算法同樣可以應(yīng)用于 IDFT的計算，稱為快速傅里葉反變換，簡寫為 IFFT。 前述 DFT和 IDFT公式為 比較上面兩式，可以看出，只要把 DFT公式中的系數(shù) 改為 ，并乘以系數(shù) 1/N， 就可用FFT算法來計算 IDFT， 這就得到了 IFFT的算法。 3. 5. 5 IFFT的計算方法 華中科技大學(xué)電信系 69 當把時間抽選 FFT算法用于 IFFT計算時 ， 由于原來輸入的時間序列 x(n)現(xiàn)在變?yōu)轭l率序列 X(k)， 原來是將 x(n)偶奇分的 ， 而現(xiàn)在變成對 X(k)進行偶奇分了 ，因此這種算法改稱為頻率抽選 IFFT算法 。 類似地 ， 當把頻率抽選 FFT算法用于計算 IFFT時 ，應(yīng)該稱為時間抽選 IFFT算法 。 在 IFFT計算中經(jīng)常把常量 1/N分配到每一級上去，即1/N=(1/2)M， 每級的蝶形運算都分別乘 上一個 1/2因子。圖 IFFT流程圖。 華中科技大學(xué)電信系 70 華中科技大學(xué)電信系 71 另一種實現(xiàn) IFFT的方法 1*0101( ) [ ( ) ]1()NnkNkNnkNkx n X k WNX k WN?*???*?????? ?1011( ) ( ) ( )N nkNkx n X k W D F T X kNN*?***??? ?????? ?????因此 ，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1