0 引言

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

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

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

1 TDM壓縮樹算法

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

2 剩余范圍的擴展方法

3 高速模(2ⁿ-2^p-1)乘法器的結構

    假設A[n-1:0]是乘數，B[n-1:0]是被乘數，A[n-1:0]×B[n-1:0]所產生的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位。根據文獻[5]中模(2ⁿ-2^p-1)乘法器的性質，有：

    其中符號#用來連接各比特位。將式(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]繼續用兩個n位CSA進行處理，得到：

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

    令C[2:0]=NH[n]+NL[n]+RH[n]+RL[n]，式(9)產生的四個部分項可以進一步用一個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時，結果不會溢出。整體結構如圖2所示，在關鍵路徑上包含1個TDM壓縮樹，5個CSA，以及2個n位的二進制加法器。

4 分析與比較

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

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

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

5 結論

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

參考文獻

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

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

[3] 胡劍浩，唐青.面向低電壓供電數字電路的容錯計算系統結構設計[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.