??? 摘 要： 采用VHDL語言，在FPGA上實現了單精度" title="單精度">單精度浮點除法器" title="除法器">除法器的設計，通過采用SRT算法、SD表示法、常數比較法以及飛速轉換法，進一步提高電路的運算速度" title="運算速度">運算速度。使用NC－sim和Maxplus2仿真軟件進行前仿真和后仿真，使用Synplify進行邏輯綜合，采用EPF10K40RC208-3芯片，對除法器進行了仿真。
??? 關鍵詞： 除法器? SRT? 單精度浮點? 數字循環法? 仿真

?

??? 在語音通信、圖像處理等領域中，系統往往涉及大量的數據處理，而且數據計算精度和實時性要求很高，需要很高的浮點處理能力來提高系統的執行效率。Soerquist等人^[1]指出，在四種基本浮點運算中，浮點除法的執行速度最慢，處理器執行浮點加法和浮點乘法時，一般需要2～3個機械周期，而浮點除法則需要8到60個機械周期。然而，在浮點運算中浮點除法占的比例較小。Oberman和Flynn認為^[2]在所有浮點指令中，浮點加法指令占55%，浮點乘法大約占37%，浮點除法大約占3%，與浮點加法和浮點乘法相比，浮點除法的比例很小。但是，這并不表示浮點除法對處理器性能的影響很小，在因為浮點指令阻塞等待而引起的處理器性能下降的因素中，浮點除法指令大約占40%，浮點加法大約占42%，浮點乘法大約占18％。由此可見，浮點除法雖然出現的頻率較低，但對處理器整體性能有較大的影響。因此設計一種執行效率較高的浮點除法結構對處理器性能的提高具有很重要的意義。
1 SRT算法的優點
??? 在處理單精度浮點數時，處理除法器的算法主要有兩種：函數迭代法及數字循環法。由于函數迭代法所提供的商的最低位不準確，導致四舍五入操作無效，不能滿足IEEE 754標準對精度的要求，而且它不產生余數，循環部分的執行復雜性程度較高。Oberman和Flynn的研究[2]表明數字循環算法可以取得較好的延時和面積平衡。數字循環算法是以加法和減法運算為基礎的算法，需要多個循環周期，但是，該算法的實現比較簡單，所需的硬件面積較小，功耗也較小，非常利于芯片的設計。
??? 該算法的實現主要有三種方法：恢復余數算法、不恢復余數算法以及SRT^[3](Sweeney，Robertson and Tocher)算法。傳統的除法器采用恢復余數算法或不恢復余數算法，但是這兩種算法的運算速度較低，每次循環僅能產生一位的商數字，需要較多的循環次數" title="循環次數">循環次數才能達到需要的指標。在每次循環時，恢復余數算法都需要將被除數或部分余數與除數進行比較，如果除數較大，還需要將部分余數恢復到上一次循環的數值。不恢復余數算法雖然不需要將部分余數恢復到原來的數值，但是商的數字集會出現負值，最后需要額外的加法器，將商的正數部分與負數部分相減。SRT算法是不恢復余數算法的擴展，具備了不恢復算法的優點，而且每次循環可產生log₂r位結果(r為基數），大大減少了循環的次數。基于SRT算法的優點，并考慮到本除法器應用在自動語音編碼，本文所設計的除法器采用SRT算法進行除法運算。
??? SRT算法由下面的表達式來確定商和余數：
???
??? d表示除數；P_j+1表示第j次循環后的部分余數；r表示SRT算法的基；q_j+1表示第j次循環得到的商，q_j+1的值由除數和部分余數組成的商數字選擇函數決定。最后的商為，最后的余數為：。
2 單精度浮點除法器的設計
??? 本文是針對IEEE 754單精度浮點數據格式進行的浮點除法器設計。IEEE 754單精度浮點格式：A=(-1)^s×M×2^E-127，s表示符號位，E表示偏移碼，E-127表示階碼，M表示尾數。
??? 除法器運算操作分四步進行：
??? (1)確定結果的符號，對被除數和除數的符號位做異或操作。
??? (2)計算階碼，兩數相除，結果的階碼是被除數的階碼與除數的階碼的相減。
??? (3)尾數相除，采用SRT算法進行尾數相除，被除數和除數的實際尾數都是24位數，即尾數實際為1.M，最高位1是隱藏位。
??? (4)結果格式化，將結果整合為單精度浮點格式的標準。
??? 在進行尾數部分處理時，雖然被除數和除數的實際尾數均為24位，但考慮到最后格式化以及商的數值的要求，實際上需要進行處理的位數為26位。因此，根據SRT算法公式，要使得循環次數減少，并且面積適中，必須選擇適合的基數。而且每次循環時都需要與除數進行比較，若26位數進行比較，則延時較大，必須選擇位數較少的數值代替26位的除數。為了適應自適應語音編碼對速度的需求，本文針對上述兩個需要進行時序改善的地方，設計了基4的SRT算法的除法器結構，如圖1所示。

???????????????????????????
2.1 基數的選擇
??? 考慮到部分余數以及基數實現的簡單性，本除法器選擇SRT算法的基數為2的冪次方。基數大小和所需的循環次數成反比，基數越大，實現除法所需要的循環次數越少。但是基數增加，會導致商數字選擇函數復雜性的提高，而且商數字選擇函數往往處在關鍵路徑上，其復雜度的增加無疑增加了每次循環的時間延遲。另外，大基數使得產生所有可能商的乘積的硬件電路變得復雜，增大了每個循環周期。因此，在實際應用中，SRT算法的基數一般限制在2或4。相比較而言，基4的性能較優，每次循環產生的位數為基2的兩倍，Oberman的研究^[4]表明，基4除法的速度幾乎是基2除法速度的2倍，而且更有利于進一步優化，降低整體的時間延遲。因此，在平衡面積和速度方面，本除法器的SRT算法選取基4，這樣可以用較小的面積消耗換取較快的速度。
2.2 商數字集
??? 由于SRT算法的基數選擇了4，因此，商的數字集不再是{0，1}，而是{0，…，3}。在傳統的非冗余表示法中，商的每一位僅由一個正確的有效值表示，因此在確定每一位商數字時，需要將部分余數和除數進行完整的比較，即24位數的比較，效率較低。為了進一步提高除法器的運算速度，本除法器采用Avizienis^[5]介紹的冗余商數字集SD，它是一種對稱的冗余表示法，商數字集表示為≤a≤r-1，冗余因子。在確定每位商數字時，僅需要將部分余數和除數進行粗略的比較，不要求當前循環確定的商準確，可由下次循環修正，商的選擇余地較大，而且產生的所有可能商的乘積數目較少，可以簡化商數字選擇函數。對于基4來說，商數字集只有兩種選擇，最小冗余{-2，-1，0，1，2}和最大" title="最大">最大冗余{-3，-2，-1，0，1，2，3}，Oberman的研究^[4]表明采用最大冗余商數字集的商數字選擇函數速度比最小冗余的快20%,而且面積小50%，因此本除法器采用商數字集的最大冗余表示法。
2.3 商數字選擇函數
??? 商數字選擇函數的功能是從商數字集中有效地選擇出正確的商數字，它是除法器的核心。由于商數字集選擇了最大冗余，因此商數字選擇公式如下：
????q_j+1=k∈{-3，-2，-1，0，1，2，3}
??? 如果d(k-1)≤rp[j]??? 由基4最大冗余的Robertson圖^[6]可見(如圖2所示)，部分余數的有效區域共分8個小區域，相鄰區域有部分區域重疊，每個商數字都有兩個區域與之對應，就是說允許商數字有兩個選擇，不正確的可通過下次循環進行糾正。但是，有效地判斷部分余數所在的區域，選擇比較接近的商數字，可以提高商數字選擇函數的執行效率和實現的簡單性，因此必須選取合適的區域分界點。傳統的做法是通過PD曲線法來求得各區域的分界點，但是需要將部分余數和除數進行比較，24位數比較產生的時延較大，而且商數字選擇函數的實現比較復雜。為了簡化商數字選擇函數，提高除法器的運算速度，本除法器采用常數選擇法，用常數來代替除數進行比較，將所需要進行比較的位數縮小，降低這部分引起的時間延時，而且實現起來比較簡單。其主體思想是把分解成若干個小區域，，然后判斷除數的合適區域，再確定比較常數及每一位商數字所對應的區域，最后根據部分余數確定每一位商數字。常數選擇法如圖3^[7]所示。
??? ?

???????????????????????????

???????????????????????????????

??? 根據最大冗余基4的商數字集，區域可以分成兩個小區域，相應的比較常數集分別為{-3/2，-1，-1/2，1/2，1，3/2}和{-2，-1，-1/2，1/2，1，2}，這些比較常數就是每位商數字所對應區域的分界點。由所得到的兩個比較常數集可知，在確定商數字時，僅需要比較部分余數的高三位，而不需要比較24位，產生的延時較小，而且硬件實現比較簡單。
2.4 飛速轉換
??? SD表示的商數字集可以簡化商數字選擇函數的實現，但是商數字集會出現負值，最后需要一個加法器，將商的正數部分與負數部分相減。24位數的相減，位傳遞產生的時延比較大，而且由于商數字的選取空間比較大，會出現最后余數為負的現象，需要對其進行修正。同時，商也需要進行操作，效率較低。較好的轉換方法是飛速轉換法^[8]，它采用移位的方法來完成SD表示的商數字集的轉換，而不采用相減的方法，這樣就不存在借位的問題，效率較高，可以降低時間延時。其轉換公式如下：
???
??? 當完成最后一次轉換后，需要根據最后余數的符號來選擇正確的商，如果最后余數為負，則商選擇qm_i+1，否則商選擇qi+1，則最后余數的選取不需要進行修正。
3 除法器的仿真實現
??? 根據所設計的結構，編寫本單精度除法器的Verilog模型，在NC-sim進行前仿真，然后利用Synplify以Altera FLEX10K工藝庫的EPF10K40RC208-3芯片的參數進行綜合，最后完成的單精度除法器的規模為778個LUT，頻率為20.8MHz。在Max+plus2進行后仿真，輸入除數為424A8000(1.01×2¹²⁷)，被除數為3FA00000(1.10010101×2¹³²)，運算結果為42220000（1.010001×2¹³²），余數為2F000000(0)，時序圖如圖4所示，最后下載到芯片上運行。

????????????????????????????
??? 本文給出了單精度浮點除法器的設計，結合當前比較流行的SRT算法與飛速轉換法對除法器的關鍵部分進行時間延時的改善，具有高精度性及較寬的運算范圍，可以滿足自適應語音編碼的要求。
參考文獻
[1] SOERQUIST P，LEESER M.Area and performance tradeoffs?in floating-point divide and square-root implementations.ACM Computing Surveys(CSUR)，1996，28(3)：518-564.
[2] OBERMAN S，FLYNN M J.Division algorithm and implementations.IEEE transactions on computers，1997，46(8)：833-854.
[3] HARRIS D L，OBERMAN S F，HOROWITZ M A.SRT?division architectures and Implementations.Computer systems
laboratory stanford university，1997.
[4] OBERMAN S F.Design issues in high performance floating?point arithmetic units.PHD thesis，stanford university，Electrical and electronic department，1997，1.
[5] AVIZIENIS A.Signed-Digit number representations for fast?parallel arithmetic.IRE transactions on electronic computers，EC-10：389-400，1961，9.
[6] WILLIAMS T E，HOROWITZ M.SRT division diagrams and?their usage in designing custom integrated circuits for division.Computer systems laboratory department of electrical?engineering stanford university.1986，10.
[7] NIKMEHR H.Architectures for floating-point division.The?university of adelaide australia.2005，8.
[8] JAMES E.S.Digital computer arithmetic datapath design using verilog HDL.Kluwer academic publishers.2004：108-112.