0 引言

    余數(shù)系統(tǒng)作為一種數(shù)值表征系統(tǒng)，憑借其在并行計算、數(shù)字信號處理以及大規(guī)模集成電路等領(lǐng)域的潛在應(yīng)用前景，受到了廣泛的研究。近些年來，隨著冗余余數(shù)系統(tǒng)(Redundant Residue Number System，RRNS)及其相關(guān)算法在糾錯領(lǐng)域的不斷應(yīng)用，余數(shù)基的選擇和構(gòu)建變得愈發(fā)重要。模乘單元的性能對于一種基的選擇和構(gòu)建起到了關(guān)鍵的作用，如何提供更多形式的高速模乘法器成為了余數(shù)系統(tǒng)發(fā)展的關(guān)鍵問題之一。

    2ⁿ-2^p±1形式的基可以構(gòu)建出高平衡度的余數(shù)基，是RRNS中最常用的一種基。其對應(yīng)的乘法器也已經(jīng)被廣泛的研究。在文獻[4]中，一種通用形式的模乘法器被提出，雖然可以用來構(gòu)造模(2ⁿ-2^p-1)乘法器，但是效果不佳。在文獻[5]中，我們提出了一種剩余范圍的擴展方法，通過這種方法，在沒有開銷的情況下將剩余范圍從[0，2ⁿ-2^p-1]擴展到[0，2ⁿ-1]，為化簡模(2ⁿ-2^p-1)乘法器的結(jié)構(gòu)提供了便利。在文獻[6，7]中，基于Booth編碼的模(2ⁿ-2^p-1)乘法器被提出，但是由于Booth編碼引入了負數(shù)，而負數(shù)在模乘法器中的修正問題會造成較大的性能損失。文獻[8]提出了一種高效且利于EDA實現(xiàn)的TDM壓縮樹(Three Dimensional Minimization，TDM)算法?？紤]到余數(shù)系統(tǒng)中乘法器是無符號的且位數(shù)不高(通常小于32)，采用非Booth編碼的TDM壓縮樹結(jié)構(gòu)反而可以起到很好的效果。本文提出的模(2ⁿ-2^p-1)乘法器沿用了剩余范圍的擴展方法，采用TDM壓縮樹解決[6，7]中出現(xiàn)的負數(shù)修正問題，取得了較大的性能提升。

    本文首先介紹TDM壓縮樹及剩余范圍的擴展方法，然后提出高速模(2ⁿ-2^p-1)乘法器的結(jié)構(gòu)并給出結(jié)構(gòu)圖，最后進行分析對比。

1 TDM壓縮樹算法

    在全加器中，不同輸入端到不同輸出端的延遲是不同的。文獻[8]中提出TDM算法可以將壓縮樹中不同全加器的最長延遲路徑和最短延遲路徑相連接。這種算法可以很方便地用腳本實現(xiàn)，具有通用性。為了解決布局布線的不規(guī)整的問題，TDM算法支持將全加器替換為4：2或者其他形式的壓縮器，以進一步提升速度。最終通過TDM壓縮樹可以將部分積(Partial Product，PP)壓縮至兩行。需要注意的是，雖然相較文獻[6，7]中采用的Booth編碼的混合型壓縮結(jié)構(gòu)，TDM壓縮樹會產(chǎn)生較大的面積，但是考慮到Booth編碼引入負數(shù)所帶來的復雜修正問題，這些面積會被抵消且總的延遲更小。

2 剩余范圍的擴展方法

3 高速模(2ⁿ-2^p-1)乘法器的結(jié)構(gòu)

    假設(shè)A[n-1:0]是乘數(shù)，B[n-1:0]是被乘數(shù)，A[n-1:0]×B[n-1:0]所產(chǎn)生的PP被TDM壓縮樹壓縮至兩列，分別為P₀[2n-2:0]，P₁[2n-2:0]。模(2ⁿ-2^p-1)乘法器可以被表示為：

    其中H₀[n-2:0]，L₀[n-1:0]分別代表P₀[2n-2:0]的高n-1位和低n位。H₁[n-2:0]，L₁[n-1:0]分別代表P₁[2n-2:0]的高n-1位和低n位。根據(jù)文獻[5]中模(2ⁿ-2^p-1)乘法器的性質(zhì)，有：

    其中符號#用來連接各比特位。將式(2)、式(3)帶入式(1)，可以進一步得到：

    將式(4)中前四項和后四項分別兩個(n-1)位的CSA和兩個n位的CSA進行處理，可以得到：

其中MH[n-1:0]，ML[n-1:0]為兩個(n-1)位的CSA的輸出，NH[n:0]，NL[n:0]為兩個(n-1)位的CSA的輸出。NH[n:0]和NL[n:0]可以進一步折疊：

    將四個n位的部分項MH[n-1:0]，ML[n-1:0]，NH[n-1:0]以及ML[n-1:0]繼續(xù)用兩個n位CSA進行處理，得到：

    其中RH[n:0]和RL[n:0]為這兩個n位CSA產(chǎn)生的輸出且可以繼續(xù)折疊：

    令C[2:0]=NH[n]+NL[n]+RH[n]+RL[n]，式(9)產(chǎn)生的四個部分項可以進一步用一個n位CSA壓縮：

    將得到的SH[n-1:0]修正為：

    將SH[n-2:0]#SH[n-1]和SL[n-1:0]用一個n位二進制加法器相加得到R[n:0]：

其中M=R[n]+SH[n-1]。實驗證明當n≥2p時，結(jié)果不會溢出。整體結(jié)構(gòu)如圖2所示，在關(guān)鍵路徑上包含1個TDM壓縮樹，5個CSA，以及2個n位的二進制加法器。

4 分析與比較

    我們將本文提出的模(2ⁿ-2^p-1)乘法器和文獻[4，5，6，7]中的模乘法器進行對比分析。所有的模乘法器都采用Verilog 硬件描述語言進行建模，并采用Design Complier 在90 nm COMS工藝下進行綜合。

    綜合結(jié)果表明，相較于文獻[4]中的設(shè)計，本設(shè)計的平均延遲降低49%，平均面積降低了5.1%。與文獻[5]中的設(shè)計相比，本設(shè)計的平均延遲降低了10.4%，但是平均面積提升了4.5%。和文獻[6]相比，本設(shè)計平均延遲降低了23.2%而平均面積降低了26.1%。與文獻[7]進行比較，本設(shè)計平均延遲降低了10.3%，平均面積提升了1.3%。

    文獻[5，7]中的兩種設(shè)計是兩種典型的高效模(2ⁿ-2^p-1)乘法器，下面將著重對本設(shè)計以及文獻[5，7]進行靜態(tài)分析。設(shè)計[5，7]都包含一個Booth 編碼的壓縮樹，而本設(shè)計包含一個非Booth的TDM壓縮樹，這兩種結(jié)構(gòu)的延遲相差不大。比較重點放在產(chǎn)生兩個2n-1位PP后的路徑，我們稱之為關(guān)鍵路徑。文獻[5]的關(guān)鍵路徑包含1個2n位二進制加法器，1個CSA，3個n位二進制加法器。文獻[7]的關(guān)鍵路徑包含6個CSA和三個二進制加法器。與文獻[5]相比，本設(shè)計在關(guān)鍵路徑上使用四個CSA替代了一個2n位的大加法器和一個n位的小加法器。與文獻[7]相比，本設(shè)計在關(guān)鍵路徑上減少了一個CSA和一個2n位加法器。采用文獻[4]中的單位門評估方法，具體結(jié)果如表1所示。

5 結(jié)論

    得益于剩余范圍的擴展和TDM壓縮樹的使用，本設(shè)計沒有使用復雜的模加法器且避免了負數(shù)修正問題。相較于當前的模(2ⁿ-2^p-1)乘法器有較大的延遲性能提升，是目前已知的延遲性能最佳的模(2ⁿ-2^p-1)乘法器。

參考文獻

[1] 馬上，胡劍浩.余數(shù)系統(tǒng)在VLSI設(shè)計中的基本問題研究與進展[C].中國通信集成電路技術(shù)與應(yīng)用研討會，2006.

[2] 李磊，胡劍浩，敖思遠.高速Booth編碼模(2^n—1)乘法器的設(shè)計[J].微電子學與計算機，2011，28(11)：191-193.

[3] 胡劍浩，唐青.面向低電壓供電數(shù)字電路的容錯計算系統(tǒng)結(jié)構(gòu)設(shè)計[J].電子科技大學學報，2013(6)：831-835.

[4] HIASAT A A.New efficient structure for a modular multiplier for RNS[J].IEEE Transactions on Computers，2000，49(2)：170-174.

[5] LI L，HU J，CHEN Y.An universal architecture for designing modulo(2n-2p-1) multipliers[J].Ieice Electronics Express，2012，9(3)：193-199.

[6] LI L，LI S，YANG P，et al.Booth encoding modulo(2n-2p-1) multipliers[J].Ieice Electronics Express，2014，11(15).

[7] YAN H，LI L，ZHANG Q.A high speed modulo(2n-2p+1) multiplier design[J].Ieice Electronics Express，2015，12(23).

[8] OKLOBDZIJA V G，VILLEGER D，LIU S S.A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach[J].IEEE Transactions on Computers，1996，45(3)：294-306.