0 引言

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

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

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

1 TDM壓縮樹(shù)算法

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

2 剩余范圍的擴(kuò)展方法

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壓縮樹(shù)壓縮至兩列，分別為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ù)文獻(xiàn)[5]中模(2ⁿ-2^p-1)乘法器的性質(zhì)，有：

    其中符號(hào)#用來(lái)連接各比特位。將式(2)、式(3)帶入式(1)，可以進(jìn)一步得到：

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

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

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

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

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

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

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

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

4 分析與比較

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

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

[3] 胡劍浩，唐青.面向低電壓供電數(shù)字電路的容錯(cuò)計(jì)算系統(tǒng)結(jié)構(gòu)設(shè)計(jì)[J].電子科技大學(xué)學(xué)報(bào)，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.