基于Radix-4 Booth編碼的模2n+1乘法器設計*

鄢 斌，李 軍

(1.海軍計算技術研究所，北京 100841；2.成都三零嘉微電子有限公司，四川 成都 610041)

基于Radix-4 Booth編碼的模2n+1乘法器設計*

鄢 斌1，李 軍2

(1.海軍計算技術研究所，北京 100841；2.成都三零嘉微電子有限公司，四川 成都 610041)

模2n+1乘法(n=8、16)在分組密碼算法中比較常見，如IDEA算法，但由于其實現(xiàn)邏輯復雜，往往被視為密碼算法性能的瓶頸。提出了一種適用于分組密碼算法運算特點的基于Radix-4 Booth編碼的模2n+1乘法器實現(xiàn)方法，其輸入/輸出均無需額外的轉(zhuǎn)換電路，并通過簡化部分積生成、采用重新定義的3-2和4-2壓縮器等措施以減少路徑時延和硬件復雜度。比較其他同類設計，該方法具有較小的面積、時延，可有效提高分組密碼算法的加解密性能。

分組密碼算法；Radix-4 Booth編碼；3-2和4-2壓縮器；模2n+1乘法

0 引 言

模2n+1乘法(n=8、16)是分組密碼算法中常用的非線性部件，如IDEA[1]密碼算法中的模216+1乘法。模2n+1乘法(n=8、16)的快速實現(xiàn)對于分組密碼算法的高加解密性能非常關鍵，因此，不少學者都提出了關于模2n+1乘法的實現(xiàn)結構[2-9]大體上可以分為縮1碼形式和原碼形式的實現(xiàn)方式。分組密碼算法中，模2n+1乘法(n=8、16)一般是將乘數(shù)形式上的全零定義為數(shù)值上的2n，因此縮1碼形式和原碼形式的實現(xiàn)上還需要額外的數(shù)據(jù)轉(zhuǎn)換電路，不太適合分組密碼算法。本文在文獻[7]的基礎上，提出了一種適合分組密碼算法的基于Radix-4布斯編碼的模2n+1乘法(n=8、16)結構。比較結果表明，本文提出的結構在時延上具有明顯優(yōu)勢。

1 Radix-4編碼原理

Booth編碼本質(zhì)上是將二進制數(shù)據(jù)中連續(xù)的“1”串轉(zhuǎn)換為一正一負兩個數(shù)，以達到減少乘數(shù)中“1”的目的。圖1中，以二進制數(shù)據(jù)“0111100110”為例對Booth編碼進行了說明。

圖1 二進制數(shù)據(jù)Booth編碼示意

Radix-4 Booth編碼的含義則是將Booth編碼后的數(shù)據(jù)每2比特組合成一個基為4的數(shù)。圖2中，以二進制數(shù)據(jù)“0111100110”為例對Radix-4 Booth編碼進行了說明。

圖2 二進制數(shù)據(jù)Radix-4 Booth編碼示意

根據(jù)前述Radix-4 Booth編碼的含義，每一個Radix-4 Booth編碼值都與被編碼數(shù)據(jù)中連續(xù)3比特數(shù)據(jù)相關，其真值表如表1所示，對應的硬件電路如圖3所示。

表1 Radix-4 Booth編碼真值

圖3 Radix4 Booth編碼電路BEC

2 模2n+1乘法原理

2.1 模2n+1的基本性質(zhì)

證明：

證明：

證明：

證明：

證明：

由于A、B是n比特無符號數(shù)，則0≤A,B≤2n-1，進而有0≤A+B≤2n+1-2。

當2n≤A+B≤2n+1-2時，即Cout=1且2n+1≤A+B+1≤2n+1-1，有0≤A+B+1-(2n+1)<2n-1，進而可得

2.2 模2n+1乘法中的Radix-4Booth編碼

根據(jù)Radix-4Booth編碼原理以及性質(zhì)1，模2n+1乘法的操作數(shù)X可表示為：

(1)

根據(jù)式(1)以及如圖3所示的Radix-4Booth編碼電路，可以得到模2n+1乘法的Radix-4Booth編碼方案，如圖4所示。

圖4 模2n+1乘法的Radix-4 Booth編碼方案

2.3 模2n+1乘法的部分積與補償項

基于Radix-4 Booth編碼的模2n+1乘法將產(chǎn)生n/2+2個部分積，其中n/2個部分積根據(jù)式(1)中的Booth編碼項來產(chǎn)生，如表2所示；式(1)中-1將產(chǎn)生其中一個部分積；最后一個部分積則由補償項來產(chǎn)生。下面著重說明補償項的情況。

表2 基于Radix-4 Booth編碼的模2n+1乘法的部分積

表3 基于Radix-4 Booth編碼的模2n+1乘法的補償項

(2)

在式(2)中，令：

(3)

(4)

將式(4)代入式(3)，可得：

(5)

(6)

(7)

(8)

(9)

在式(9)中，令：

(10)

式(10)中(2u2k+1+u2k)+v2k可看作兩個2比特位寬的無符號數(shù)做加法運算，令4w2k+2+2wk+1+wk=(2u2k+1+u2k)+v2k，根據(jù)無符號二進制數(shù)加法運算規(guī)則，有：

關于超細鼻胃鏡的早期研究多圍繞于其對患者惡性嘔吐、心血管不良事件、舒適性等的影響，在篩查食管胃底靜脈曲張時，研究證實超細鼻胃鏡有效，且患者耐受性較好，對于門脈高壓或肝硬化患者更為安全[3]。對21例需長期監(jiān)測Barrett食管的志愿者進行隨機鼻胃鏡及標準內(nèi)鏡檢查，雖然標準胃鏡的光學圖像質(zhì)量較好，但患者對鼻胃鏡的耐受性更強，60%患者更愿意選擇鼻胃鏡來完成長期監(jiān)測檢查。

(11)

將式(11)代入式(10)，可得：

(12)

(13)

部分積壓縮過程中，無論是采用3-2或者4-2的進位保留加法器CSA(Carry Save Adder)，每減少一個部分積，就會產(chǎn)生一個額外的補償量-1(見2.4小節(jié))。n/2+2個部分積最終壓縮為2個部分積，將產(chǎn)生補償量-n/2，因此整個模乘法器的補償量進一步更新為

(14)

(15)

將式(15)代入式(14)，可得：

(16)

常規(guī)的3-2壓縮器和4-2壓縮器[12-13]都會產(chǎn)生進位，根據(jù)性質(zhì)(1)和性質(zhì)(2)，在模2n+1的條件下需要將進位取反并折返回最低位，由此會分別產(chǎn)生補償量-1和-2。模2n+1乘法所使用的3-2壓縮器和4-2壓縮器分別見圖5(a)和圖5(b)。

圖5 更改后的3-2壓縮器和4-2壓縮器

當n=8時，一共有6個部分積，當n=16時，一共有10個部分積，其壓縮結構分別如圖6(a)和圖6(b)所示。

圖6 模2n+1(n=8,16)乘法器壓縮樹結構

3 模2n+1乘法總體結構

在分組密碼算法中，模2n+1(n=8,16)乘法乘數(shù)全零表示2n，因此需要對乘數(shù)為全零的情況進行特殊處理。假設參與模2n+1乘法的乘數(shù)為X和Y，則有：

a)當X=0,Y≠0時，有

(17)

b)當X≠0,Y=0時，有：

(18)

c)當X=0,Y=0時，有：

(19)

因為X和Y都不為全零的時候，最后需要表達為A+B+1[10，11]的形式，因此各種情況下的統(tǒng)一表達形式如下表所示：

表4 模2n+1乘法器最后加法操作數(shù)一覽

綜上，模2n+1(n=8,16)乘法器的總體結構如圖7所示。

圖7 模2n+1(n=8,16)乘法器的總體結構

4 性能比較

采用Verilog語言對如圖7所示的模2n+1(n=8,16)乘法器進行了描述，并基于SMIC 0.18μm CMOS標準單元庫，在25℃、1.8V環(huán)境下對設計進行了綜合，輸出結果及同類設計綜合結果如所示。

表5 模2n+1(n=8,16)乘法器綜合結果比較

5 結 語

本文提出了一種適應于分組密碼算法的基于Radix-4布斯編碼的模2n+1(n=8,16)乘法器結構，相比較于縮1碼或者源碼結構，具有輸入簡單直觀、部分積生成/壓縮數(shù)據(jù)路徑清晰等特點，并采用Verilog語言進行了描述。作者基于SMIC 0.18μm CMOS標準單元庫，在25℃、1.8V環(huán)境下利用synopsys公司的design compiler工具對設計進行了綜合，與同類設計相比，明顯減小了時延，同時由于其結構規(guī)則、簡單的特點，非常適合VLSI實現(xiàn)，可廣泛應用于各類密碼算法協(xié)處理器中，能顯著提高分組密碼算法的加解密性能。

[1] LAI X, Massey J. A Proposal for a New Block Encryption Standard[J]. Eurocrypt’ 90, 1991,LNCS 473:389-404.

[2] Curigerav, Bonnenbergh, Kaeslinh. Regular VLSI Architectures for Multiplication Modulo (2n+ 1)[J]. IEEE Journal on Solid State Circuits,July 1991,26(7):990-994.

[3] Hiassat A. New Memoryless Mod(2n+1) Residue Multiplier[J]. Electron. Lett, Jan 1992,28(3):314-315.

[4] WANG Z, Jullien G A, Miller W C. An Efficient Tree Architecture for Modulo (2n+1) Multiplication[J]. VLSI Signal Process, Dec 1996, 14(3):241-248.

[5] Sousa L. Algorithm for Modulo (2n+1) Multiplication[J].Electron Lett, May 2003, 39(9):752-754.

[6] Efstathiou C, Vergos H T, Dimitrakopoulos G, et al. Efficient Diminished-1 Modulo 2n+1 Multipliers[J]. IEEE Trans on Computers,Apr 2005, 54(4): 491-496.

[7] Sousa L, Chaves R. A Universal Architecture for Designingefficient Modulo 2n+1 Multipliers[J]. IEEE Trans on Circuits and Systems, Jun 2005,52(6):1166-1178.

[8] 王文瑞.一種規(guī)整高效的縮1碼模2n+1乘法器的VLSI設計[J].通信技術，2010，43(12)：167-173. WANG Wen-rui.A Regular Architecture for Designing Efficient Dimentioned-1 Modulo 2n+1 multiplier[J].Communications Technology, 2010，43(12)：167-173.

[9] Ramya Muralidharan, CHANG Chip-Hong. A Simple Radix-4 Booth EncodedModulo 2n+1 Multiplier[J]. Circuits and System(ISCAS),2011:1163-1166.

[10] Efstathiou C, Vergos H T, Nikolos D. Modulo 2n±1 Adder Design UsingSelect Prefix Blocks[J]. IEEE Trans on Computers, Nov 2003, 52(11): 1399-1406.

[11] Vergos H T, Efstathiou C. Efficient Modulo 2n+1 Adder Architectures[J]. Integration the VLSI Journal, Feb 2009, 42(2): 149-157.

[12] Hsiao S F, Jiang M R, YEH J S. Design of High Speed Low-Power 3-2 Counter and 4-2 Compressorfor Fast Multipliers[J]. Electron Lett, 1998, 34, (4):341-343.

[13] Sreehari Veeramachaneni, Kirthi Krishna M, Lingamneni Avinash, et al. Novel Architectures for High-Speed and Low-Power 3-2, 4-2 and 5-2 Compressors[J]. IEEE 20th International Conference on VLSI Design (VLSID’07), 2007:324-329.

Modulo 2n+1 Multiplier based on Radix-4 Booth Encoding

YAN Bin1，LI Jun2

(1.Naval Institute of Computing Technology, Beijing 100841, China; 2.Chengdu 30 JAVEE Microelectronics Co., Ltd., Chengdu Sichuan 610041, China)

Modulo 2n+1 multiplication (n=8, 16) is fairly common in block-cipher algorithms, such as IDEA algorithm. However, for its high logic complexity, this multiplication structure is usually regarded as the performance bottleneck of crypto algorithm. A modulo 2n+1 multiplication method suitable for the operation characteristics of block-cipher algorithm based on Radix-4 Booth encoding is thus proposed,and no extra conversion circuits is required in its input and output port, and path delay and hardware complexity are reduced by simplifying partial product, and redefining 3-2 and 4-2 compressor. Compared with other similar implementations, the proposed method enjoys less hardware area and timing delay, and thus could effectively enhances the crypto performances of block-cipher algorithm.

block cipher; Radix-4 Booth encoding;3-2 and 4-2 compressor; modulo 2n+1 multiplication

10.3969/j.issn.1002-0802.2015.10.014

2015-05-21；

2015-09-10 Received date:2015-05-21；Revised date：2015-09-10

TN918

A

1002-0802(2015)10-1168-06

鄢 斌(1967—)，女，碩士，高級工程師，主要研究方向為計算工程；

李 軍(1983—)，男，碩士，工程師，主要研究方向為信息安全集成電路設計。