基4fft蝶形圖運算單元解析

　　蝶形運算，2點DFT運算稱為蝶形運算，而整個FFT就是由若干級迭代的蝶形運算組成，而且這種算法采用塬位運算，故只需N個存儲單元2. ∑∑（2）式（2）是FFT基4頻域抽取算法的基本運算單元，一般稱為蝶形運算。

　　1. 2點DFT運算稱為蝶形運算，而整個FFT就是由若干級迭代的蝶形運算組成，而且這種算法采用塬位運算，故只需N個存儲單元2. ∑∑（2）式（2）是FFT基4頻域抽取算法的基本運算單元，一般稱為蝶形運算。下一步再將X（4m+i），i=0，1，2，3分解成4個N42序列，迭代r次后完成計算，整個算法的復雜度減少為O（Nlog4N）

　　第一列蝶形運算只有一種類型：系數(shù)，參加運算的兩個數(shù)據(jù)點間距為1。第二列有兩種類型的蝶形運算：系數(shù)分別為 ，參加蝶形運算的兩個數(shù)據(jù)點的間距等于2。第叁列有4種類型的蝶形運算：系數(shù)分別是 ，參加蝶形運算的兩個數(shù)據(jù)點的間距等于4?？梢?，每一列的蝶形類型比前一列增加一倍，參加蝶形運算的兩個數(shù)據(jù)點的間距也增大一倍，最后一列系數(shù)用得最多，為4個，即 ，而前一列只用到它偶序號的那一半，即，

　　第一列只有一個系數(shù)，即。上訴結(jié)論可以推廣到N=的一般情況，規(guī)律是第一列只有一種類型的蝶形運算，系數(shù)是 ，以后每列的蝶形類型，比前一列增加一倍，到第是N/2個蝶形類型，系數(shù)是，共N/2個。由后向前每推進一列，則用上述系數(shù)中偶數(shù)序號的那一半，例如第列的系數(shù)則為參加蝶形運算的兩個數(shù)據(jù)點的間距，則是最末一級最大，其值為N/2，向前每推進一列，間距減少一半。

　　FFT（快速傅里葉變換）作為數(shù)字信號處理領域的核心算法之一。蝶形運算單元是FFT設計的核心單元。本文研究基24FFT蝶形運算單元芯片設計?；赥SMC（***集成電路制造公司）0.18LmCMOS標準單元庫的半定制ASIC（專用集成電路）設計，采用自頂向下、以關鍵模塊為設計對象的設計方法，使用VerilogHDL描述系統(tǒng)，在Modelsim、DesignCompiler和ASTRO等EDA（電子設計自動化）工具中完成

　　基4FFT蝶形運算單元的設計

　　蝶形運算單元是FFT處理器的核心單元，蝶形運算單元結(jié)構(gòu)的穩(wěn)定性和運算的準確性直接影響到FFT處理器的性能。分析基4FFT的特點，綜合考慮面積、性能、功耗各個方面的因素，設計出結(jié)合流水線技術(shù)和并行結(jié)構(gòu)的蝶形運算單元。

　　蝶形運算單元結(jié)構(gòu)設計

　　基24FFT中蝶形運算單元的處理結(jié)構(gòu)見圖

　　傳統(tǒng)的基4算法是用3個復數(shù)乘法器和12個復數(shù)加法器構(gòu)成，每次復數(shù)乘法器由4個實數(shù)乘法器和2個實數(shù)加法實現(xiàn)，每個復數(shù)加法由2個實數(shù)加法器實現(xiàn)。如此將基24算法的計算結(jié)構(gòu)直接映射至硬件需消耗大量的邏輯資源（12個實數(shù)乘法器和22個實數(shù)加法器）。

　　經(jīng)過重新排列如下：

　　觀察xc和uc，Xc和Uc，yc和zc，Yc和Zc這4組表達式，可以發(fā)現(xiàn)其對應的實部和虛部括號內(nèi)的內(nèi)容相同，因此可以將流水線方式與并行結(jié)構(gòu)的思想巧妙結(jié)合起來，用4個循環(huán)序列對各寄存器進行嚴格的時序控制，只用1個實數(shù)乘法器來實現(xiàn)一次復數(shù)乘法器，對應3個不同的復數(shù)乘法用3個實數(shù)乘法并行進行;加法器也并行進行循環(huán)使用。因此，完成一個基4FFT蝶形運算單元僅需要3個實數(shù)乘法以及6個實數(shù)加法，相比傳統(tǒng)基24FFT蝶形運算單元，可節(jié)省75%的乘法器邏輯資源和72.7%的加法器邏輯資源。

　　蝶形運算單元的結(jié)構(gòu)如圖2所示

　　數(shù)據(jù)切換單元

　　流水線技術(shù)與并行結(jié)構(gòu)相結(jié)合的方法可以提高設計的靈活性，減小核心單元的面積，提高芯片運行的速度。流水線技術(shù)與并行結(jié)構(gòu)相結(jié)合必須在時序的嚴格控制下執(zhí)行。

　　數(shù)據(jù)切換單元由狀態(tài)機組成，以蝶形運算單元的第1級數(shù)據(jù)切換單元為例。每組數(shù)據(jù)輸入乘法器分為4個狀態(tài)（分別為A、B、C、D）。狀態(tài)A輸入乘數(shù)的實部和旋轉(zhuǎn)因子的實部;狀態(tài)B輸入乘數(shù)的實部和旋轉(zhuǎn)因子的虛部;狀態(tài)C輸入乘數(shù)的虛部和旋轉(zhuǎn)因子的實部;狀態(tài)D輸入乘數(shù)的虛部和旋轉(zhuǎn)因子的虛部。其他3級數(shù)據(jù)切換單元根據(jù)前一級運算結(jié)構(gòu)輸出以此類推得到。每一級的具體結(jié)果以及步驟見表1。完成4級運算后，并行輸出結(jié)果的實部和虛部

　　浮點乘法器的設計

　　本設計中浮點數(shù)乘法器需完成2個IEEE754單精度浮點數(shù)之間的乘法，包括3個部分尾數(shù)乘法、指數(shù)加法和符號處理。浮點乘法器結(jié)構(gòu)見圖3

　　乘法的處理可分為3個步驟：

　　a）對輸入數(shù)據(jù)進行預處理，即判斷輸入中是否有0，同時將輸入數(shù)據(jù)的符號位、指數(shù)部分以及尾數(shù)部分拆開分別處理，符號位寄存，指數(shù)部分相加，尾數(shù)部分預處理;

　　b）將23位尾數(shù)和1位隱含位/10構(gòu)成的24位有效數(shù)送入定點乘法器進行運算，并寄存預處理單元的其他輸出數(shù)據(jù);

　　c）接收定點乘法運算結(jié)果以及相關寄存器輸出，將最終結(jié)果規(guī)格化為IEEE754標準單精度浮點格式。

　　24位定點乘法器采用了經(jīng)典的陣列式結(jié)構(gòu)結(jié)合改進Booth算法的樹形結(jié)構(gòu)。陣列式定點乘法器結(jié)構(gòu)規(guī)整，適合于流水線處理，但是流水線深度過深，初始時延過長，硬件資源消耗過大。

　　改進的Booth算法將24位定點乘法運算的部分積由24個壓縮至13個，降低硬件開銷，減少流水線級數(shù)。利用改進的Booth算法設計一種華萊士樹形結(jié)構(gòu)，如圖4所示。

　　用3級4B2壓縮器將13個部分積逐級壓縮到2個，級間插入寄存器實現(xiàn)全流水，壓縮后的2個部分積用快數(shù)加法器相加得到最終結(jié)果。4B2壓縮器的邏輯結(jié)構(gòu)見圖5，由4B2壓縮單元級聯(lián)組成。

　　對并行的全加器進行邏輯化簡可以得到4B2壓縮單元，其邏輯表達式如下：

　　利用改進后的結(jié)構(gòu)設計的定點乘法器流水線深度只有7級，降低了硬件成本，減小了流水線的初始延時，提高了系統(tǒng)的性能。

　　浮點乘法器的改進

　　分析4B2壓縮器的邏輯表達式，可以發(fā)現(xiàn)當輸入的a1，a2，a3，a4相同的時候，輸出的Cout相同;當輸入的a1，a2，a3，a4以及Cin相同時，輸出的S和C都相同。

　　再分析Booth算法。Booth編碼是針對有符號數(shù)的乘法，需要將符號位擴展并且移位;2個24bit定點數(shù)相乘，得到1個48bit的乘積，因此產(chǎn)生的部分積有2bit~24bit不等的相同符號位。

　　在華萊士樹形結(jié)構(gòu)中，Booth算法得到的13個48bit的部分積相加，只需要將其中的25bit相加，其他23bit可以通過分析直接得到和位和進位。每個乘法器節(jié)省了70個4B2壓縮器，減少了關鍵路徑時間，提高了乘法器的執(zhí)行速度。

　　浮點加法器設計

　　浮點加法器包括數(shù)據(jù)預處理電路、26bit加法器以及浮點數(shù)格式化處理，采用流水線技術(shù)，見圖6。

　　浮點加法的處理步驟如下：

　　a）數(shù)據(jù)預處理部分，包括判零電路，如果其中一個加數(shù)為0，那么加法輸出結(jié)果應該等于另一個加數(shù);指數(shù)對齊;尾數(shù)移位實現(xiàn)尾數(shù)補齊和隱藏位/10擴展以及符號位擴展。

　　b）運用進位保留和進位傳遞相結(jié)合的26bit加法器。

　　c）將最終結(jié)果再格式化為IEEE754標準單精度浮點格式。

　　26bit定點加法器是浮點加法器的核心加法單元，本設計采用了超前進位和進位保留相結(jié)合的方法，見圖7。超前進位加法器的特點是各級進位信號同時產(chǎn)生，大大減少了進位產(chǎn)生的時間，一般不超過4bi，t故將26bit分成6個3bit塊和2個4bit塊。其中，AF_3、AF_4采用超前進位加法器，26bit進位選擇加法器僅用2級流水線就能達到所需性能要求。

　　浮點加法器的改進

　　在滿足時序的情況下，分析26bit快速加法器。超前進位加法器適用于不超過4bit的數(shù)據(jù)，進位保留加法器是以面積換速度。如果采用兩級流水線完成26bit加法器，時序上一定滿足，但是卻以24個AF_3和8個AF_4為代價?；诿娣e和時序的折衷優(yōu)化，我們采用以下框圖完成26bit加法器。只需要12個AF_3和4個AF_4即可完成26bit進位選擇加法器。

　　邏輯綜合

　　在蝶形運算單元結(jié)構(gòu)完成之后，采用VerilogHDL對整個系統(tǒng)進行了RTL級描述和邏輯綜合及功能驗證。本文基于TSMC0.18LmCMOS標準單元庫，使用Synopsys的DesignCompiler進行邏輯綜合，使用Modsim進行仿真，并且與MATLAB計算結(jié)果進行對比。

　　邏輯綜合

　　設計目標為200MHz時鐘，設定20%裕量，因此約束時鐘為4ns，具體約束條件如下：時鐘周期4ns，時間抖動和歪斜0.1ns，線負載模型tsmc18_wl120，輸入輸出延時0.8ns，滿足時序的情況下面積最小化。

　　綜合完成后結(jié)果如圖8所示。

　　蝶形運算單元邏輯綜合報告顯示關鍵路徑延時3.4ns《4ns，所以slack為正。總單元面積1.12mm2，總的動態(tài)功耗為376.9mW。

　　基24FFT蝶形運算單元使用TSMC0.18LmCMOS標準單元庫，能穩(wěn)定工作在200MHz的時鐘頻率。采用改進的基24FFT蝶形結(jié)構(gòu)圖，將乘法器節(jié)省75%，加法器節(jié)省72.7%;采用改進的浮點乘法器和浮點加法器，使蝶形運算單元的面積節(jié)省了1.64萬門。

　　此蝶形運算單元在滿足200MHz的前提下，面積和功耗得到很大改善。對于N點FFT需要log4N級、每級N/4次蝶形運算，假設每級數(shù)據(jù)需要10點預存，數(shù)據(jù)輸入輸出需要1024@2個時鐘，完成1024點運算的時間［（1024/4+10）@log41024+1024@2］@5ns=16.89ns。

　　可見，使用該蝶形運算單元構(gòu)成FFT處理器在性能上處于領先地位。