浮點(diǎn)FFT模塊設(shè)計(jì)方案

1、浮點(diǎn)FFT模塊設(shè)計(jì)方案1 概述1.1 功能、特點(diǎn)概述FFT運(yùn)算在語音識(shí)別、圖像處理和頻譜分析等有著廣泛的應(yīng)用,許多系統(tǒng)對(duì)數(shù)據(jù)傳輸?shù)乃俾室笫謬?yán)格,因此在速度上對(duì)FFT處理器提出了很高的要求。隨著Xilinx高性能FPGA的誕生,自主研發(fā)的高性能FFT模塊成為可能。采用自頂向下的設(shè)計(jì)方法設(shè)計(jì)1024點(diǎn)的浮點(diǎn)數(shù)傅里葉變換FFT模塊,并在RTL級(jí)給出完整的設(shè)計(jì)描述,編寫測(cè)試平臺(tái)對(duì)于每個(gè)模塊進(jìn)行前仿真和時(shí)序分析。1.2 運(yùn)用背景FFT模塊廣泛應(yīng)用于數(shù)字信號(hào)處理等領(lǐng)域,在頻譜分析中有著廣泛的應(yīng)用,過去通常用DSP實(shí)現(xiàn),隨著超大規(guī)?？删幊踢壿嬈骷陌l(fā)展,通過FPGA實(shí)現(xiàn)專門的DSP算法無論從性能上還是成

2、本上都有著很大的優(yōu)勢(shì)。2 算法實(shí)現(xiàn)2.1 離散傅里葉變換(DFT連續(xù)信號(hào)的傅里葉變換定義如下公式所示: 上面兩個(gè)公式表達(dá)了一個(gè)無限持續(xù)時(shí)間和帶寬的連續(xù)信號(hào),實(shí)際中需要在時(shí)間和頻率上對(duì)其采樣,并對(duì)幅值進(jìn)行量化,更希望在時(shí)間和頻率上使用有限的采樣,即是離散傅里葉變換DFT,如下面的公式所示: 其中逆變換IDFT的公式為: 式中定義為旋轉(zhuǎn)因子;DFT把信號(hào)從時(shí)域變換到頻域,從而可以研究信號(hào)或者濾波器的頻率特性,將離散的數(shù)字信號(hào)變換為不同頻率分量之和,使得我們可以更加清楚信號(hào)的頻率分布;DFT算法的運(yùn)算復(fù)雜度與N的平方成正比,當(dāng)N很大時(shí)運(yùn)算復(fù)雜度將大幅增加,FFT快速傅里葉變換算法的提出使得傅里葉變換

3、的運(yùn)算時(shí)間縮短一到二個(gè)數(shù)量級(jí),運(yùn)算復(fù)雜度為N/2*log2N,運(yùn)算速度得到很好的改善。2.2 快速傅里葉變換(FFTFFT算法的核心思想是將N點(diǎn)的序列逐次分解為(N-1/2,直至2點(diǎn)的DFT,按照分解方式可以分成按時(shí)域抽取(DIT-FFT和按頻域抽取(DIF-FFT兩種算法,分別是對(duì)時(shí)間序列x(n和頻率序列X(k進(jìn)行分解。對(duì)于基為2的DIT時(shí)域抽取FFT算法我們有: 由上式可知后項(xiàng)相同,從而可以使得復(fù)數(shù)乘法的運(yùn)算次數(shù)減半,其中Y(k和Z(k是分別按照K的奇偶項(xiàng)將x(k分解成的兩個(gè)子序列;上式可以用蝶形運(yùn)算圖來表示,圖2中左邊結(jié)點(diǎn)表示Y(k和Z(k,右邊結(jié)點(diǎn)表示合成序列X(k,每個(gè)箭頭表示結(jié)點(diǎn)與

4、W N k相乘,當(dāng)沒有W N k時(shí)表示與1相乘。Y(kX(k Z(kX(k+n/2圖1 蝶形運(yùn)算單元基于上述蝶形運(yùn)算單元得到4點(diǎn)時(shí)域抽取FFT算法流程圖如圖3所示,其中寄存器用于緩存蝶形運(yùn)算中間值,4點(diǎn)FFT需要2級(jí)流水線運(yùn)算來完成,輸入數(shù)據(jù)重新進(jìn)行排序,輸出數(shù)據(jù)順序輸出;而對(duì)于頻域抽取FFT的流程圖則是輸入數(shù)據(jù)順序輸入,輸出數(shù)據(jù)重新排序。 圖2 時(shí)域抽取FFT算法流程圖同時(shí)還有基為4和8的FFT算法,雖然基數(shù)越高流水線級(jí)數(shù)越少運(yùn)算次數(shù)也越少,但控制結(jié)構(gòu)復(fù)雜,同時(shí)也加重了其他模塊的設(shè)計(jì)負(fù)擔(dān)。基于上述考慮我們采用基為2的時(shí)域抽取FFT 算法來設(shè)計(jì)FFT 處理器,在點(diǎn)數(shù)不是很大的情況下比基為4的算

5、法更容易實(shí)現(xiàn)和控制,數(shù)據(jù)位寬是32位的數(shù)據(jù),采用浮點(diǎn)數(shù)格式存儲(chǔ)。2.3 單精度浮點(diǎn)數(shù)格式大多數(shù)的計(jì)算機(jī)浮點(diǎn)數(shù)格式定義都按照IEEE754標(biāo)準(zhǔn)來規(guī)定浮點(diǎn)數(shù)的存儲(chǔ)格式,IEEE754標(biāo)準(zhǔn)規(guī)定了浮點(diǎn)數(shù)的格式、精度、算術(shù)操作和異常處理等等,此設(shè)計(jì)的浮點(diǎn)數(shù)FFT模塊也按照IEEE754標(biāo)準(zhǔn)來定義浮點(diǎn)數(shù)格式,采用32位的單精度浮點(diǎn)數(shù)格式,分為符號(hào)位、指數(shù)位和尾數(shù)位三個(gè)存儲(chǔ)部分,格式如下: 313023220符號(hào)位為1時(shí)表示是負(fù)數(shù),為0表示正數(shù);指數(shù)位的偏移量是127(7FH,所以存儲(chǔ)的指數(shù)位是原來的指數(shù)位加上偏移量的結(jié)果,計(jì)算時(shí)存儲(chǔ)的指數(shù)位要減去偏移量才用于浮點(diǎn)數(shù)計(jì)算;23位的尾數(shù)位代表的意義是0.1xx

6、xxxx,即前面默認(rèn)存儲(chǔ)的是規(guī)格化的0和1。當(dāng)數(shù)據(jù)進(jìn)入蝶形運(yùn)算單元之前都要進(jìn)行一個(gè)預(yù)處理模塊,對(duì)存儲(chǔ)的浮點(diǎn)數(shù)進(jìn)行必要的處理以滿足加法和乘法運(yùn)算的要求。2.4 加法運(yùn)算蝶形運(yùn)算單元的復(fù)數(shù)加減法運(yùn)算分為實(shí)部和虛部分別進(jìn)行加減法法運(yùn)算,實(shí)部和虛部的加法運(yùn)算歸結(jié)于浮點(diǎn)數(shù)加法運(yùn)算的實(shí)現(xiàn),浮點(diǎn)數(shù)加法運(yùn)算一般需要以下的步驟完成:(1指數(shù)相減:將兩個(gè)指數(shù)化為相同值,通過比較兩個(gè)指數(shù)的大小求出指數(shù)差的絕對(duì)值|E|;(2對(duì)階移位:將指數(shù)較小的操作數(shù)的尾數(shù)右移|E|位;(3尾數(shù)操作:對(duì)完成對(duì)階的尾數(shù)進(jìn)行加法或者減法運(yùn)算;(4轉(zhuǎn)換:當(dāng)尾數(shù)相加/減的結(jié)果出現(xiàn)負(fù)數(shù),需要進(jìn)行求補(bǔ)操作,將其轉(zhuǎn)換為符號(hào)-尾數(shù)的表達(dá)方式;(5前

7、導(dǎo)1或前導(dǎo)0的判定:判定由于減法結(jié)果產(chǎn)生的左移數(shù)量或者由于加法產(chǎn)生的右移數(shù)量;(6規(guī)格化移位:對(duì)尾數(shù)加減結(jié)果進(jìn)行移位,消除非有效位,使得前面一位為1的位;(7舍入:有限精度浮點(diǎn)數(shù)需要將最終的計(jì)算結(jié)果進(jìn)行舍入以滿足23位尾數(shù)的固定結(jié)果。上述步驟簡單概括就是指數(shù)對(duì)齊,對(duì)尾數(shù)進(jìn)行加/減法操作,再對(duì)尾數(shù)移位規(guī)格化和舍入以得到最終的浮點(diǎn)數(shù)計(jì)算結(jié)果。尾數(shù)加/減法采用二進(jìn)制加法器的超前進(jìn)位加法器CLA,我們知道1 位全加器定義的進(jìn)位產(chǎn)生Gi和進(jìn)位傳播Pi 滿足下面的關(guān)系: 從而可有1位全加器的輸出結(jié)果: 同理可以構(gòu)建4位的CLA全加器,再在4位CLA全加器的基礎(chǔ)上得到16位的CLA全加器,對(duì)于24位浮點(diǎn)尾數(shù)

8、的加減法運(yùn)算我們采用32位的CLA來設(shè)計(jì),未使用到的高位全部補(bǔ)0。2.5 乘法運(yùn)算研究浮點(diǎn)數(shù)乘法運(yùn)算之前要來了解復(fù)數(shù)的乘法運(yùn)算,蝶形運(yùn)算單元中包含一個(gè)復(fù)數(shù)乘法運(yùn)算單元,對(duì)于復(fù)數(shù)A=a+jb和B=c+jd,有: 化簡得到: 由上面兩式可知減少了一個(gè)乘法器的使用,節(jié)約硬件資源;另外在蝶形運(yùn)算單元中有一個(gè)乘數(shù)因子是旋轉(zhuǎn)因子,旋轉(zhuǎn)因子對(duì)應(yīng)的復(fù)數(shù)是處在半徑為1 的單位圓內(nèi),即模小于等于1,乘法器的輸出將不會(huì)在單精度浮點(diǎn)數(shù)格式中溢出。浮點(diǎn)數(shù)通常用下列的公式來表示: 其中S 是符號(hào)位,M 是尾數(shù)位,E 是指數(shù)位,故兩乘數(shù)對(duì)應(yīng)為F A和F B的乘法表達(dá)式可以表示為: 傳統(tǒng)的浮點(diǎn)數(shù)乘法器結(jié)構(gòu)如圖4所示。 圖3

9、浮點(diǎn)數(shù)乘法器結(jié)構(gòu)圖由上圖可知浮點(diǎn)數(shù)乘法運(yùn)算最主要的運(yùn)算是進(jìn)行擴(kuò)展位后的24位尾數(shù)乘法器,擴(kuò)展后的尾數(shù)都是大于0小于1的數(shù),相乘得到的也是處在0,1之間的數(shù),滿足最后規(guī)格化的要求。浮點(diǎn)數(shù)乘法器主要步驟包括部分積產(chǎn)生,部分積壓縮,進(jìn)位傳播加法和舍入處理,如何進(jìn)行部分積壓縮是區(qū)別各種算法的關(guān)鍵所在,最簡單的部分積壓縮方法是采用迭代的方法,通過移位累加操作完成部分積的壓縮,這種算法速度比較慢,對(duì)N 個(gè)部分積的加法需要N 個(gè)時(shí)鐘周期,對(duì)于高位寬的浮點(diǎn)數(shù)乘法時(shí)間消耗比較大。將Booth 譯碼進(jìn)行改進(jìn),采用并行譯碼。二進(jìn)制補(bǔ)碼表示的Y 為:211022n n in i i Y Y Y -=-+Y 可以被改寫

10、成:/212212210(22n i i i i i Y YY Y -+=+-括號(hào)中表達(dá)式的值可以是-2,-1,0,+1,+2。如乘數(shù)B按照3位一組分成重疊的組。每組對(duì)應(yīng)相應(yīng)的對(duì)被乘數(shù)A進(jìn)行的并行乘法操作-2X,-X,0,X,=0對(duì)部分2X,所有這些乘法操作都可以通過移位和求補(bǔ)運(yùn)算得到。(其中Y-1積求和時(shí),為避免浪費(fèi)資源,對(duì)以二進(jìn)制補(bǔ)碼表示的各部分積符號(hào)擴(kuò)展時(shí)采取符號(hào)補(bǔ)償?shù)姆椒?對(duì)每一個(gè)部分積最高位取反;在最高位左面補(bǔ)1;按照原被乘數(shù)A的最高位給部分積的和對(duì)應(yīng)位置加1。其中加1可以用對(duì)應(yīng)位加法器進(jìn)位輸入為1來實(shí)現(xiàn)。表1Booth譯碼列表 BOOTH譯碼涉及到的操作有:“direction”、

11、“shift”、“addition”, direction 操作數(shù)決定被乘數(shù)究竟是取其本身X,還是要取反X,舉個(gè)例子來說,如果乘數(shù)Y有一個(gè)三個(gè)一組分成的數(shù)“101”,我們則需要取被乘數(shù)X的補(bǔ)碼。但是,這很難實(shí)現(xiàn),因此我們的部分積只要求將X取反,然后再加一即可達(dá)到要求。Shift 操作數(shù)意味著把操作數(shù)向左移動(dòng)一個(gè)位置,如果Y中有個(gè)待譯碼的數(shù)組“011”,“100”, 我們則都需要將X左移一位。Addition操作數(shù)則意味著在部分積的最低位加上一。其中“direction”,“shift”,“addition”跟Ym-1、Ym、Ym+1的關(guān)系為:Direction = Ym+1;Shift = Y

12、m-1 (Ym+1 Ym + Ym-1_bar (Ym+1 Ym;Addition = Ym-1 Ym;其中對(duì)被乘數(shù)X的操作主要如下所說:-2X,-X,0,X,2X-2X:將X左移一位,再取反,并在其最低位加1。-X:將X取反,在其最低位加1。0:將X的各位全都用0代替。X:X的各位保持不變。2X:將X左移一位。這樣即可得到各個(gè)部分積。以1616Bit的乘法加以說明,部分積生成電路根據(jù)Booth編碼結(jié)果生成部分積,當(dāng)被乘數(shù)是16位時(shí),部分積是17位。由于Booth算法所產(chǎn)生的部分積是有符號(hào)數(shù),所以在進(jìn)入Wallace樹開始運(yùn)算前需要進(jìn)行符號(hào)擴(kuò)展,符號(hào)擴(kuò)展本身需要占用電路,耗費(fèi)時(shí)間,而且符號(hào)擴(kuò)展

13、還增加了Wallace樹的規(guī)模。所以應(yīng)對(duì)其進(jìn)行改進(jìn)。經(jīng)Booth編碼后生成的部分積為8個(gè),假設(shè)8個(gè)部分積的符號(hào)位分別為:S7 ,S6 ,S5 S0 。對(duì)由于符號(hào)擴(kuò)展所引起的附加值S進(jìn)行化簡: 由以上表達(dá)式即可看出,我們僅需要做到以下幾步:將每個(gè)部分積的符號(hào)位取反;將1加在每個(gè)部分積的左邊;按照原被乘數(shù)X的最高位給部分積的和對(duì)應(yīng)位置加1?？焖俪朔ㄆ饔蒪ooth譯碼得到部分積后,這些部分積對(duì)齊形式如下圖所示的平行四邊形:圖4 部分積示意圖使用華萊士樹方法對(duì)部分積壓縮,最終得到Carry和Sum,將兩者用CLA高速加法器相加的最終乘積。25位(經(jīng)符號(hào)擴(kuò)展后尾數(shù)相乘,得到12個(gè)25位部分積。示意圖如下

14、: 圖5Wallace結(jié)構(gòu)示意圖3 功能模塊列表3.1 FFT實(shí)現(xiàn)結(jié)構(gòu)綜合起來FFT 實(shí)現(xiàn)整體結(jié)構(gòu)有四種:順序處理、級(jí)連處理、并行處理和陣列處理。順序處理結(jié)構(gòu)的基本思想就是利用一個(gè)蝶形運(yùn)算單元對(duì)存儲(chǔ)器內(nèi)的數(shù)據(jù)一級(jí)一級(jí)地循環(huán)運(yùn)算,利用雙口RAM實(shí)現(xiàn)的順序處理結(jié)構(gòu)如圖5所示,有一個(gè)存儲(chǔ)器,一個(gè)蝶形運(yùn)算單元,當(dāng)數(shù)據(jù)到齊后控制邏輯安順序每次提取進(jìn)行蝶形運(yùn)算的一組數(shù)據(jù),運(yùn)算完后放回原來的地址處,直到運(yùn)算完成。 圖6 順序處理結(jié)構(gòu)對(duì)于一些高速數(shù)據(jù)實(shí)時(shí)處理系統(tǒng),需要在相對(duì)短的時(shí)間內(nèi)完成FFT操作,流水線型的FFT處理比較適合這種高速數(shù)據(jù)處理的結(jié)構(gòu),FFT處理過程可以看做是一級(jí)一級(jí)順序處理的,每一級(jí)的處理都相

15、對(duì)獨(dú)立,每一級(jí)都有自己的存儲(chǔ)單元和蝶形運(yùn)算單元,當(dāng)一級(jí)的數(shù)據(jù)全部計(jì)算完成后,下一級(jí)的運(yùn)算開始。我們還可以對(duì)一列中的N/2個(gè)蝶形單元并行運(yùn)算,而各列是相續(xù)迭代,當(dāng)N 很大時(shí)將消耗很大的硬件資源;當(dāng)然也可以在一個(gè)處理器當(dāng)中全部并行處理所有的蝶形運(yùn)算單元,顯然這兩種方法速度比較快,但也相應(yīng)地消耗更多的硬件資源,這里就不用過多考慮,特別要通過FPGA來實(shí)現(xiàn)FFT處理模塊,很大的IP核將增加驗(yàn)證難度和驗(yàn)證周期,我們主要考慮流水線設(shè)計(jì)和雙口RAM兩種實(shí)現(xiàn)方案, 對(duì)于1024點(diǎn)的FFT處理器來說,采用單一雙口RAM來實(shí)現(xiàn)延遲很大,而且吞吐量不足,采用流水線設(shè)計(jì)可以有效提高系統(tǒng)頻率,提高FFT處理能力與吞吐量

16、,在本文的設(shè)計(jì)當(dāng)中采用流水線的設(shè)計(jì)思想設(shè)計(jì)FFT處理模塊。3.2 模塊列表由復(fù)數(shù)加法模塊,復(fù)數(shù)減法模塊,復(fù)數(shù)乘法模塊三個(gè)運(yùn)算模塊構(gòu)成蝶形運(yùn)算單元,并采用CSA 進(jìn)位保留加法器加速浮點(diǎn)數(shù)加法運(yùn)算和浮點(diǎn)數(shù)乘法運(yùn)算。蝶形運(yùn)算單元采用純組合邏輯設(shè)計(jì),綜合時(shí)認(rèn)為是一條長周期路徑,占用3個(gè)時(shí)鐘周期的計(jì)算時(shí)間。通過C語言編程得到各級(jí)旋轉(zhuǎn)因子表放入ROM中,同時(shí)采用線與邏輯對(duì)ROM進(jìn)行初始賦值,輸出由讀使能和讀地址指定讀取數(shù)值;讀地址和讀使能由系統(tǒng)控制單元統(tǒng)一置位,輸出實(shí)部和虛部的旋轉(zhuǎn)因子進(jìn)入蝶形運(yùn)算單元。各級(jí)旋轉(zhuǎn)因子表大小不同,節(jié)省ROM 的存儲(chǔ)空間。存儲(chǔ)單元主要用于存儲(chǔ)輸入數(shù)據(jù),緩存中間結(jié)果,以及最后的計(jì)

17、算結(jié)果。10 級(jí)流水線FFT處理器每一級(jí)都有一個(gè)單獨(dú)的迭代控制單元進(jìn)行控制,用于產(chǎn)生該級(jí)的讀寫使能和讀寫地址指針,采用512的計(jì)數(shù)器完成迭代控制;流水線首尾分別是輸入級(jí)和輸出級(jí),采用1024的計(jì)數(shù)器完成輸入或者輸出。4 接口及寄存器4.1 接口信號(hào)表2FFT模塊接口信號(hào)列表Signal Num of Bits I/O Descriptionsclk 1 I 系統(tǒng)時(shí)鐘信號(hào)din_re 32 I 輸入數(shù)據(jù)實(shí)部din_im 32 I 輸入數(shù)據(jù)虛部system_en 1 I 系統(tǒng)使能信號(hào)ifft_fft 1 I 選擇信號(hào),低電平為FFT運(yùn)算,高電平為IFFT運(yùn)算system_requset 1 I 系

18、統(tǒng)請(qǐng)求信號(hào)system_reset 1 I 系統(tǒng)復(fù)位信號(hào)finish 1 O FFT運(yùn)算完成信號(hào)dout_re 32 O 輸出數(shù)據(jù)實(shí)部dout_im 32 O 輸出數(shù)據(jù)虛部model_select 2 I 模式選擇信號(hào)overflow 1 O 溢出標(biāo)志位,當(dāng)輸出有溢出則為高電平。其中model_select信號(hào)是模式選擇信號(hào),有如下模式選擇:(100 表示單次512 點(diǎn)運(yùn)算模式;(201 表示單次1024 點(diǎn)運(yùn)算模式;(310 表示高速512 點(diǎn)運(yùn)算模式;(411 表示高速1024 點(diǎn)運(yùn)算模式。在上述的接口描述之外,還可以包含更高的接口層,用于和AMBA總線或者I2C總線等總線規(guī)定下的模塊進(jìn)行

19、互連,也可以做為單獨(dú)的IP核應(yīng)用于FFT運(yùn)算要求頻繁的場(chǎng)合。4.2 狀態(tài)寄存器在FFT 處理器頂層包含一個(gè)16 位狀態(tài)寄存器,格式如下:Reg Name FFT_RegR/W R/WReset 0x0000_0000 Bits Signal Name Descripition15 Reserved保留位14:5 PIPL十級(jí)流水線標(biāo)志位,該級(jí)流水線工作時(shí)對(duì)應(yīng)標(biāo)志位置14 HS高速模式標(biāo)志位3:2 MOD1:0模式選擇標(biāo)志位1 OVE溢出標(biāo)志位0 FIN完成標(biāo)志位5 蝶形運(yùn)算單元5.1 功能概述由復(fù)數(shù)加法模塊,復(fù)數(shù)減法模塊,復(fù)數(shù)乘法模塊三個(gè)運(yùn)算模塊構(gòu)成蝶形運(yùn)算單元,并采用CSA 進(jìn)位保留加法器加

20、速浮點(diǎn)數(shù)加法運(yùn)算和浮點(diǎn)數(shù)乘法運(yùn)算。蝶形運(yùn)算單元采用純組合邏輯設(shè)計(jì),綜合時(shí)認(rèn)為是一條長周期路徑,占用3個(gè)時(shí)鐘周期的計(jì)算時(shí)間。5.2 內(nèi)部模塊 圖7 蝶形運(yùn)算單元由復(fù)數(shù)加法模塊,復(fù)數(shù)減法模塊,復(fù)數(shù)乘法模塊三個(gè)運(yùn)算模塊構(gòu)成蝶形運(yùn)算單元,由全局時(shí)鐘信號(hào)和使能信號(hào)en控制。模塊輸入兩個(gè)復(fù)數(shù)和旋轉(zhuǎn)因子,輸出兩個(gè)復(fù)數(shù),輸入復(fù)數(shù)由雙口RAM_1提供,輸入旋轉(zhuǎn)因子由ROM提供,輸出復(fù)數(shù)送給RAM_2緩存;蝶形單元使能,ROM讀出地址,RAM存取地址和使能全部由控制單元統(tǒng)一控制;三級(jí)流水線運(yùn)算,輸入級(jí),乘法運(yùn)算級(jí)和加減法運(yùn)算級(jí),時(shí)鐘頻率能達(dá)到60.63MHz。蝶形運(yùn)算單元,旋轉(zhuǎn)因子表和雙口RAM在控制單元里被例化

21、,受控制單元的控制迭代,控制單元輸出讀寫使能和讀寫指針給RAM,輸出讀指針和讀地址給ROM,同時(shí)輸出運(yùn)算使能控制信號(hào)給蝶形運(yùn)算單元。5.3 接口信號(hào)表3 蝶形單元接口信號(hào)列表Signal Num of Bits I/O Descriptionsclk 1 I 系統(tǒng)時(shí)鐘信號(hào)en 1 I 運(yùn)算使能信號(hào),由控制單元提供Y_re 32 I 輸入數(shù)據(jù)Y實(shí)部Y_im 32 I 輸入數(shù)據(jù)Y虛部Signal Num of Bits I/O Descriptions Z_re 32 I 輸入數(shù)據(jù)Z實(shí)部Z_im 32 I 輸入數(shù)據(jù)Z虛部W_re 32 I 輸入旋轉(zhuǎn)因子實(shí)部W_im 32 I 輸入旋轉(zhuǎn)因子虛部X1_

22、re 32 O 輸出數(shù)據(jù)X1實(shí)部X1_im 32 O 輸出數(shù)據(jù)X1虛部X2_re 32 O 輸出數(shù)據(jù)X2實(shí)部X2_im 32 O 輸出數(shù)據(jù)X2虛部5.4 具體實(shí)現(xiàn)輸入的浮點(diǎn)數(shù)規(guī)定都為正數(shù),即符號(hào)位都是0;指數(shù)位輸入后分別減去127;23位尾數(shù)位進(jìn)行位擴(kuò)展在首位加上1成24位的尾數(shù)。蝶形單元中加法/減法運(yùn)算電路的設(shè)計(jì)有如下特點(diǎn):(1 純組合邏輯設(shè)計(jì),加法和減法分開到兩個(gè)模塊當(dāng)中,不采用整合的做法,減法器可以由加法器實(shí)現(xiàn);(2 24位的尾數(shù)加法運(yùn)算可能會(huì)溢出,在首位引入保護(hù)位,得到的25位結(jié)果需要移位和舍入到標(biāo)準(zhǔn)單精度格式;(3 尾數(shù)規(guī)格化部分引入前導(dǎo)零計(jì)數(shù)器用于計(jì)算前0的個(gè)數(shù),前導(dǎo)零計(jì)數(shù)器的速度

23、會(huì)對(duì)整個(gè)模塊的運(yùn)算速度產(chǎn)生影響;對(duì)于25位的尾數(shù)計(jì)算其前0的個(gè)數(shù)我們把這尾數(shù)拆分成5個(gè)5位緩存數(shù)存儲(chǔ)于寄存器中,對(duì)這5個(gè)寄存器分別來判斷其前0的數(shù)目,從而加速了前0探測(cè)器的尋找時(shí)間。圖7是RTL級(jí)結(jié)構(gòu)圖。 圖8 浮點(diǎn)數(shù)加法器組合邏輯結(jié)構(gòu)圖左邊起第一個(gè)模塊計(jì)算階碼之間的差值即尾數(shù)移位的位數(shù),第二個(gè)模塊對(duì)尾數(shù)進(jìn)行移位,第三個(gè)模塊根據(jù)符號(hào)位的不同進(jìn)行加法或者減法運(yùn)算,第四個(gè)模塊是首零探測(cè)器,用于得到的結(jié)果尾數(shù)規(guī)格化,第五個(gè)模塊整合得到的結(jié)果。采用兩個(gè)浮點(diǎn)加法器就可以組成復(fù)數(shù)加法器,分別完成實(shí)部和虛部的加法運(yùn)算,復(fù)數(shù)加法采用全局時(shí)鐘同步控制。類似于加法器,復(fù)數(shù)減法器則把被減數(shù)的首位取反采用加法器則可以

24、實(shí)現(xiàn)得到。浮點(diǎn)數(shù)乘法器符號(hào)位進(jìn)行異或運(yùn)算,指數(shù)位相加減去偏移量,關(guān)鍵的計(jì)算是對(duì)于24 位擴(kuò)展尾數(shù)的運(yùn)算,采用Booth 譯碼進(jìn)行部分積的加速壓縮,部分積相加采用CSA 壓縮器相加,最后得到輸出結(jié)果。設(shè)計(jì)的浮點(diǎn)數(shù)乘法運(yùn)算單元具有如下特點(diǎn):(1把Booth 譯碼單元和Wallce 樹都整合到一個(gè)組合邏輯當(dāng)中,采用長路徑使得在一個(gè)時(shí)鐘周期內(nèi)能完成乘法操作;(2對(duì)于24 位的尾數(shù)設(shè)計(jì)12 個(gè)部分積,部分積的位寬是51 位,實(shí)際上有用的是47:0之間的數(shù)值,大于48 位的都是保護(hù)位,每個(gè)部分積的首位作為符號(hào)位,取反加1 后是0,不影響累加過程;(3CSA 的位寬和部分積一樣是50 位,加法運(yùn)算得到最終結(jié)

25、果后先舍入到25位的尾數(shù)形式,再輸入到前0計(jì)數(shù)器進(jìn)行規(guī)格化操作;前0計(jì)數(shù)器采用的快速尋0方法和加法器一樣;指數(shù)位對(duì)應(yīng)于0的個(gè)數(shù)進(jìn)行相應(yīng)地移位。1. 采用Booth譯碼的乘法器實(shí)現(xiàn)Booth 譯碼對(duì)應(yīng)部分積的累加結(jié)構(gòu)圖如圖4-5 所示,51 位的部分積首位都為符號(hào)位,剩下的50 位用于存儲(chǔ)部分積的值,存儲(chǔ)之前對(duì)負(fù)數(shù)的部分積采用取反加1 的操作使得部分積滿足累加要求。 圖9Booth譯碼后部分積累加結(jié)構(gòu)圖對(duì)于被乘數(shù)尾數(shù)是23位,擴(kuò)展1后是24位,在Booth譯碼的部分積因?yàn)樾枰笠埔晃凰允?5位,即上圖中每一種顏色都表示是25位的數(shù),每次累加都需要把部分積向左移兩位再疊加,最終要加上22位,所以

26、數(shù)據(jù)段是47位,加上一位保護(hù)位則有用數(shù)據(jù)段是48位的數(shù)據(jù)段和第一位的符號(hào)位。因?yàn)楦↑c(diǎn)數(shù)默認(rèn)格式是尾數(shù)前面加入一個(gè)1位,所以兩個(gè)數(shù)相乘得到的也是一個(gè)首位為1的數(shù),所以可以撤掉首1計(jì)數(shù)器,節(jié)省硬件資源和規(guī)格化所需時(shí)間,得到改進(jìn)的結(jié)構(gòu)圖如圖9所示,圖中左邊起第一個(gè)邏輯模塊是Booth 譯碼單元,并完成對(duì)負(fù)數(shù)的轉(zhuǎn)換工作;第二步進(jìn)入10個(gè)CSA組成的Wallce樹快速累加單元,中間這個(gè)模塊即Wallce樹控制器,完成對(duì)CSA各級(jí)信號(hào)的調(diào)度和控制;第三步采用一個(gè)異或門得到符號(hào)位的值,并且根據(jù)部分積首位來判斷得到最終的輸出符號(hào)位;第四步是首0計(jì)數(shù)器,對(duì)尾數(shù)規(guī)格化,并對(duì)指數(shù)減去偏移量和首0對(duì)應(yīng)數(shù);最后輸出整體

27、結(jié)果。 圖10 改進(jìn)的浮點(diǎn)數(shù)乘法器電路實(shí)現(xiàn)圖2. 復(fù)數(shù)乘法器實(shí)現(xiàn)由浮點(diǎn)數(shù)乘法器,浮點(diǎn)數(shù)加法器和減法器整合在一起構(gòu)成復(fù)數(shù)乘法器,包含浮點(diǎn)數(shù)加法器和浮點(diǎn)數(shù)乘法器兩個(gè)模塊,引入全局同步時(shí)鐘和復(fù)位信號(hào),在一個(gè)時(shí)鐘周期內(nèi)完成復(fù)數(shù)乘法運(yùn)算,圖10是其實(shí)現(xiàn)電路結(jié)構(gòu)圖。 圖11 復(fù)數(shù)乘法器電路實(shí)現(xiàn)圖復(fù)數(shù)乘法器主要由三級(jí)流水線構(gòu)成,第一級(jí)包含三個(gè)浮點(diǎn)數(shù)加法器,第二級(jí)包含三個(gè)浮點(diǎn)數(shù)乘法器,第三級(jí)包含兩個(gè)浮點(diǎn)數(shù)加法器,所有寄存器由全局時(shí)鐘同步控制,第一級(jí)寄存器之前加入選擇器由全局reset 信號(hào)控制,用于復(fù)位輸出。6 旋轉(zhuǎn)因子表6.1 概述研究8點(diǎn)的時(shí)域抽取FFT運(yùn)算流程圖,得到圖11的8點(diǎn)FFT圖示,由圖中 三次

28、迭代運(yùn)算可以看出旋轉(zhuǎn)因子的變化。W8X(0X(5 X(6 X(7 X(4 X(3 X(2 X(1圖128 點(diǎn)FFT流程圖其中,在第一級(jí)迭代中,只有一種類型的蝶形運(yùn)算系數(shù),即W80,參加蝶形運(yùn)算的兩個(gè)數(shù)據(jù)點(diǎn)間隔位1;在第二級(jí)迭代中有兩個(gè)蝶形運(yùn)算系數(shù),分別是W80和W82,參加蝶形運(yùn)算的兩個(gè)數(shù)據(jù)點(diǎn)的間隔為2;在第三級(jí)的迭代中有四種類型的蝶形運(yùn)算系數(shù),分別是W80、W81、W82、W83,參加蝶形運(yùn)算的兩個(gè)數(shù)據(jù)點(diǎn)的間隔位4。對(duì)于1024點(diǎn)FFT來說,每一級(jí)需要512次的蝶形運(yùn)算,第一級(jí)只有一種運(yùn)算系數(shù)W10240,第二級(jí)有兩種運(yùn)算系數(shù)W10240和W10242,第三級(jí)有四種運(yùn)算系數(shù)W10240、W1

29、0241、W10242和W10243,一直到第十級(jí)是512種運(yùn)算系數(shù)從W10240到W1024511,每個(gè)運(yùn)算系數(shù)由32位的實(shí)部和虛部組成,采用浮點(diǎn)數(shù)格式存儲(chǔ)于ROM中。6.2 C語言實(shí)現(xiàn)采用C語言建模的方法把k從0到511對(duì)應(yīng)的旋轉(zhuǎn)因子計(jì)算出來并轉(zhuǎn)化為浮點(diǎn)數(shù)格式,下面給出計(jì)算旋轉(zhuǎn)因子的C語言程序: 得到旋轉(zhuǎn)因子的實(shí)部和虛部列表,總共512個(gè),程序運(yùn)行后得到的是10進(jìn)制的數(shù)值顯示,在編寫RTL級(jí)代碼時(shí)同樣輸入的是十進(jìn)制數(shù)值,對(duì)應(yīng)系數(shù)n就是數(shù)值在ROM中的存放地址,地址數(shù)從0開始增加到511。十進(jìn)制數(shù)值列表需要轉(zhuǎn)換為二進(jìn)制的數(shù)值列表,規(guī)格化成標(biāo)準(zhǔn)浮點(diǎn)數(shù)類型。旋轉(zhuǎn)因子都是小于1的小數(shù),主要工作是把

30、旋轉(zhuǎn)因子表轉(zhuǎn)換成浮點(diǎn)數(shù)的尾數(shù)部分,同時(shí)移位使得所有數(shù)的左邊起第一位為1,首位不是1的進(jìn)行移位,記錄下移位的位數(shù),加入到指數(shù)位當(dāng)中,實(shí)現(xiàn)的C語言代碼段如下: 6.3 ROM實(shí)現(xiàn)二進(jìn)制浮點(diǎn)數(shù)在C語言中采用數(shù)組來表示,經(jīng)過上述代碼轉(zhuǎn)化可以把旋轉(zhuǎn)因子表采用二進(jìn)制表示,默認(rèn)的形式都是0.xxxxxxx這樣一種格式,分別輸出到兩個(gè)文件當(dāng)中,把首1去掉,加上處理過的符號(hào)位和指數(shù)位,寫入到ROM模塊中。采用兩個(gè)ROM分別存儲(chǔ)512個(gè)單精度浮點(diǎn)數(shù),采用線與邏輯對(duì)ROM進(jìn)行初始賦值,輸出由讀使能和讀地址指定讀取數(shù)值;讀地址和讀使能由系統(tǒng)控制單元統(tǒng)一置位,輸出實(shí)部和虛部的旋轉(zhuǎn)因子進(jìn)入蝶形運(yùn)算單元。當(dāng)FPGA配置時(shí)這

31、個(gè)存儲(chǔ)器被初始化,配置之后無法再改寫,采用組合邏輯實(shí)現(xiàn)的ROM隨著個(gè)數(shù)的增加將會(huì)非常復(fù)雜。對(duì)于流水線設(shè)計(jì)的FFT處理模塊來說,各級(jí)的旋轉(zhuǎn)因子存儲(chǔ)數(shù)據(jù)也不同,對(duì)于第n級(jí)的蝶形運(yùn)算需要的旋轉(zhuǎn)因子的數(shù)目是2n-1個(gè),對(duì)應(yīng)于每一級(jí)的旋轉(zhuǎn)因子表的大小選擇不同大小的ROM 來存儲(chǔ),地址編碼也會(huì)有差別。7 存儲(chǔ)單元7.1 概述RAM是存儲(chǔ)數(shù)據(jù)輸入及中間運(yùn)算結(jié)果的單元,每個(gè)蝶形運(yùn)算單元的輸入,輸出都要經(jīng)過RAM的讀寫操作,RAM的頻繁讀寫操作對(duì)FFT模塊的處理速度影響比較大,為了加快FFT運(yùn)算速度,需要構(gòu)造雙口RAM來加快數(shù)據(jù)傳輸,即輸入和輸出采用不同的數(shù)據(jù)總線,邊讀邊寫。7.2 接口信號(hào)表4 雙口RAM接口

32、信號(hào)列表Signal Num of Bits I/O Descriptionsclk 1 I 系統(tǒng)時(shí)鐘信號(hào)we 1 I 寫使能信號(hào),高電平有效re 1 I 讀使能信號(hào),高電平有效waddress 10 I 寫輸入地址raddress 10 I 讀輸入地址din 32 I 32位數(shù)據(jù)輸入dout 32 O 32位數(shù)據(jù)輸出7.3 具體實(shí)現(xiàn)采用順序結(jié)構(gòu)的FFT處理器需要四個(gè)1024*32bit的RAM分別讀寫數(shù)據(jù)和起到緩存的作用,圖12很好地體現(xiàn)了雙口RAM乒乓結(jié)構(gòu)的設(shè)計(jì)特點(diǎn),對(duì)于多級(jí)流水線結(jié)構(gòu)來說將會(huì)減少很多讀取時(shí)間。 圖13 雙口RAM讀寫操作圖由上圖可知兩個(gè)RAM分別存放運(yùn)算的前后數(shù)據(jù),Con

33、trol控制模塊分別控制兩個(gè)RAM的讀寫操作,對(duì)于每一次運(yùn)算過程讀寫同地址;在乒乓結(jié)構(gòu)開始運(yùn)算前需要把1024個(gè)復(fù)數(shù)輸入到RAM_2中,在完成整個(gè)迭代運(yùn)算之后同樣需要把所有數(shù)據(jù)從RAM_1中輸出。一般RAM需要特定的芯片廠商專門定制速度會(huì)比采用片上寄存器描述速度要快得多,考慮到設(shè)計(jì)的整體性和接口的穩(wěn)定性建議采用FPGA片上的RAM資源。7.4 輸入數(shù)據(jù)重排對(duì)于時(shí)域抽取FFT算法需要對(duì)輸入數(shù)據(jù)進(jìn)行數(shù)據(jù)重排,把RAM中特定位置的數(shù)據(jù)對(duì)換,滿足蝶形運(yùn)算的要求。數(shù)據(jù)重排不受控制單元的控制,在數(shù)據(jù)輸入完成后自動(dòng)進(jìn)行,當(dāng)寫使能為高電平時(shí)輸入1024個(gè)復(fù)數(shù)數(shù)據(jù),經(jīng)過1024個(gè)時(shí)鐘周期完成數(shù)據(jù)輸入后寫使能為低

34、電平時(shí)進(jìn)行數(shù)據(jù)重排。數(shù)據(jù)輸入和重排構(gòu)成整個(gè)FFT處理器運(yùn)算的輸入級(jí)。對(duì)于8點(diǎn)時(shí)域抽取算法需要預(yù)處理兩個(gè)數(shù)據(jù)重排,把X1和X4,X3和x6分別交換位置;對(duì)于1024點(diǎn)的時(shí)域抽取需要預(yù)處理X1和X512,X3和X514,X1+2m和X512+2m,X511和X1022一共256個(gè)數(shù)據(jù)重排, m從0到255逐增。圖13是其數(shù)據(jù)重排算法示意圖。 圖14 數(shù)據(jù)重排結(jié)構(gòu)圖對(duì)于1024點(diǎn)的FFT來說RAM地址位寬是10,對(duì)數(shù)據(jù)的重排可以轉(zhuǎn)變成地址的對(duì)換就可以實(shí)現(xiàn),需要對(duì)換數(shù)據(jù)對(duì)應(yīng)地址編碼列舉如下: 地址變換規(guī)律即首位和末位互換,其他位置都不改變,對(duì)于末位為0的即偶數(shù)地址將維持原來的地址不發(fā)生改變。算法對(duì)應(yīng)的

35、核心Verilog代碼實(shí)現(xiàn)如下: 數(shù)據(jù)重排操作時(shí)需要注意的一個(gè)時(shí)序上的細(xì)節(jié)是:讀使能應(yīng)該在寫使能完成后有效,以確保數(shù)據(jù)有效。輸出的數(shù)據(jù)就是重新排序的數(shù)據(jù),符合1024點(diǎn)迭代運(yùn)算的要求,實(shí)部虛部分別存儲(chǔ)于上述的雙口RAM重排模塊,讀出數(shù)據(jù)時(shí)每次蝶形運(yùn)算需要讀兩個(gè)數(shù)據(jù),需要兩個(gè)時(shí)鐘周期來完成讀出時(shí)序,同樣寫入RAM 也需要兩個(gè)時(shí)鐘來完成。8 控制單元8.1 輸入級(jí)控制單元當(dāng)系統(tǒng)使能到來以后激勵(lì)數(shù)據(jù)寫入使能和寫入地址,內(nèi)部計(jì)數(shù)器從0開始計(jì)數(shù),計(jì)數(shù)器累加的同時(shí)寫地址累加,一直到計(jì)數(shù)器為1024時(shí)停止計(jì)數(shù),寫使能為低電平,并送出完成信號(hào)給下一流水線級(jí)。圖14是輸入級(jí)控制單元的狀態(tài)機(jī)ASM圖。 圖15 輸入級(jí)ASM狀態(tài)圖輸入級(jí)設(shè)計(jì)有如下的特點(diǎn):(1在輸入寫入完成后才能發(fā)出讀信號(hào)給下級(jí)流水線;(2在系統(tǒng)時(shí)鐘的同步下,輸出的地址和數(shù)據(jù)頻率下降一倍,在時(shí)序仿真時(shí)要注意這個(gè)細(xì)節(jié),并通知給下一流水線;(3給出的finish_replace 信號(hào)除了通知給下一流水線級(jí)外也要通知頂層模塊,便于頂層模塊調(diào)度。8.2 中間各級(jí)控制單元中間每一級(jí)流水線由一個(gè)頂層模塊實(shí)現(xiàn),每一個(gè)頂層模塊控制內(nèi)部的512次蝶形運(yùn)算,由上一級(jí)輸入該級(jí)的使能信號(hào),并產(chǎn)生送給下一級(jí)流水線的使能信號(hào),包含control,fu_ram,float_radix和float_rom四個(gè)子模塊,控制信號(hào)由con