一種高速模(2n-2p-1)乘法器的設計

張清宇，李 磊

(電子科技大學 電子科學技術(shù)研究院，四川 成都 611731)

一種高速模(2n-2p-1)乘法器的設計

張清宇，李 磊

(電子科技大學 電子科學技術(shù)研究院，四川 成都 611731)

結(jié)合余數(shù)系統(tǒng)以及模乘法器本身的特點，一種高速的模(2n-2p-1)乘法器被提出。得益于剩余范圍的擴展和新型的部分積壓縮樹的采用，該設計相較于傳統(tǒng)的模乘法器在關(guān)鍵路徑上減少了一個長度為2n的加法器且避免了此類 Booth編碼模乘法器中復雜的負數(shù)修正問題。在90 nm工藝下的綜合結(jié)果表明，該模乘(2n-2p-1)乘法器相較當前的模(2n-2p-1)乘法器有10.4%到49%的延遲性能提升。

余數(shù)系統(tǒng)；剩余范圍擴展；部分積壓縮樹

0 引言

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

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

本文首先介紹TDM壓縮樹及剩余范圍的擴展方法，然后提出高速模(2n-2p-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 剩余范圍的擴展方法

對于任意整數(shù) X，有〈X〉2n-2p-1=x，x∈[0，2n-2p-1]。也就是說，模(2n-2p-1)的剩余范圍是[0，2n-2p-1]。為了化簡運算，可以將剩余范圍擴展到[0，2n-1]。因為有〈2n-2p-1+i〉2n-2p-1=i，i∈[1，2p+1]，這樣就可以使用2n-2p-1+i在乘法器中來表示 i。圖1所示的 RNS系統(tǒng)中，這種擴展并不會產(chǎn)生計算錯誤，并且很容易在后向轉(zhuǎn)換中進行修正。通過使用這種擴展方法，可以化簡模(2n-2p-1)乘法器的結(jié)構(gòu)，避免了重復將[2n-2p-1，2n-1]修正到[1，2p]所帶來的浪費。

圖1 RNS系統(tǒng)框圖

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

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

其中H0[n-2:0]，L0[n-1:0]分別代表 P0[2n-2:0]的高n-1位和低n位。H1[n-2:0]，L1[n-1:0]分別代表P1[2n-2:0]的高n-1位和低n位。根據(jù)文獻[5]中模(2n-2p-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]：

繼續(xù)對R[n:0]折疊：

最終，得到最后結(jié)果Y[n-1:0]：

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

圖2 模(2n-2p-1)乘法器的結(jié)構(gòu)

4 分析與比較

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

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

文獻[5，7]中的兩種設計是兩種典型的高效模(2n-2p-1)乘法器，下面將著重對本設計以及文獻[5，7]進行靜態(tài)分析。設計[5，7]都包含一個 Booth編碼的壓縮樹，而本設計包含一個非 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]相比，本設計在關(guān)鍵路徑上使用四個CSA替代了一個2n位的大加法器和一個n位的小加法器。與文獻[7]相比，本設計在關(guān)鍵路徑上減少了一個CSA和一個2n位加法器。采用文獻[4]中的單位門評估方法，具體結(jié)果如表1所示。

圖3 p=3時模(2n-2p-1)乘法器的延遲性能

圖4 p=4時模(2n-2p-1)乘法器的延遲性能

表1 靜態(tài)時序分析

5 結(jié)論

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

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

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

[3]胡劍浩，唐青.面向低電壓供電數(shù)字電路的容錯計算系統(tǒng)結(jié)構(gòu)設計[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.

A high speed modulo(2n-2p-1)multiplier design

Zhang Qingyu，Li Lei
(Research Institute of Electronic Science and Technology，University of Electronic Science and Technology of China，Chengdu 611731，China)

Based on the features of residue number systems(RNS)and modular multipliers,a high speed architecture which is more suitable for design high speed modulo(2n-2p-1)multipliers is proposed.Leveraging the novel partial production reduction tree,we eliminate the complicated correction components which is introduced to correct negative number without performance loss.On the other hand,At the cost of two Carry Save Adders(CSAs)on the critical path,we reduce the delay of a 2n-bit binary adder. Compared with the current modulo(2n-2p-1)multipliers,synthesized results in which based on 90 nm process technology demonstrate that the proposed(2n-2p-1)multipliers can achieve a 10.4%～49%delay saving.

residue number systems(RNS)；residue set extending；partial production reduction tree

TN402

A

10.16157/j.issn.0258-7998.2016.11.037

張清宇，李磊 .一種高速模(2n-2p-1)乘法器的設計[J].電子技術(shù)應用，2016，42(11)：137-140.

英文引用格式：Zhang Qingyu，Li Lei.A high speed modulo(2n-2p-1)multiplier design[J].Application of Electronic Technique，2016，42(11)：137-140.

2016-08-02)

張清宇(1990-)，男，碩士研究生，主要研究方向：專用集成電路(ASIC)和SOC設計。

李磊(1983-)，男，博士，副研究員，主要研究方向：專用集成電路(ASIC)和SOC設計。