王書敏，崔曉平

(南京航空航天大學 電子信息工程學院，江蘇 南京 211100)

基于并行前綴結(jié)構(gòu)的十進制加法器設(shè)計

王書敏，崔曉平

(南京航空航天大學 電子信息工程學院，江蘇 南京 211100)

摘要針對硬件實現(xiàn)BCD碼十進制加法需要處理無效碼的問題，設(shè)計了一種基于并行前綴結(jié)構(gòu)的十進制加法器。該十進制加法器依據(jù)預先加6，配合二進制加法求中間和，然后再減6修正的算法，并將減6修正步驟整合到重新設(shè)計的減6修正進位選擇加法器中，充分利用并行前綴結(jié)構(gòu)大幅提高了電路運算的并行度。采用Verilog HDL對加法器進行實現(xiàn)并利用Design Compiler進行綜合，得到設(shè)計的32位，64位，128位的十進制加法器的延時分別為0.56 ns，0.61 ns，0.71 ns，面積分別為1 310 μm2，2 681 μm2，5 485 μm2。

關(guān)鍵詞十進制加法；并行前綴結(jié)構(gòu)；減6修正進位選擇加法器

自從馮·諾依曼體系結(jié)構(gòu)出現(xiàn)之后，二進制一直在計算機算術(shù)中占據(jù)主導地位，處理器設(shè)計人員也一直傾向于采用二進制設(shè)計計算機運算電路。但是隨著金融以及商業(yè)計算等領(lǐng)域的發(fā)展，提供硬件以支持十進制運算變得越來越迫切。這是以下幾點原因造成的：首先，大多數(shù)十進制小數(shù)，比如0.2，無法在二進制格式下完全精確表示。其次，商業(yè)數(shù)據(jù)庫中所存儲的十進制數(shù)據(jù)多于二進制數(shù)據(jù)，因此采用二進制電路運算時需要在十進制與二進制之間進行轉(zhuǎn)換，這些進制轉(zhuǎn)換工作需要花費時間[1]。另外，當前的金融計算采用軟件模擬十進制運算來處理數(shù)據(jù)以獲得精確的結(jié)果，但是軟件模擬十進制運算要比硬件進行二進制運算至少慢100倍以上[2]，兩者之間性能有較大差距。

加法器是十進制以及二進制算術(shù)運算單元中不可缺少的運算電路，因此很多二進制甚至是十進制加法器的實現(xiàn)方法被提出。但十進制加法的研究熱度一直無法與二進制加法相比，直到2000年以后十進制加法的研究才逐漸成為國內(nèi)外關(guān)注的熱點[1]。國外研究人員對BCD碼十進制加法做了大量的研究工作[2-11]，在設(shè)計十進制加法器時采用8421-BCD碼對十進制操作數(shù)進行編碼。本文根據(jù)BCD碼加法中預先加6修正，配合二進制加法求中間和，然后再次減6修正的算法設(shè)計了基于并行前綴結(jié)構(gòu)的十進制加法器[1]。實驗表明，本文設(shè)計的十進制加法器能像二進制加法器一樣高效地完成加法運算。

1BCD碼十進制加法算法

本文設(shè)計的十進制加法器采用8421-BCD碼對d位(4dbit)十進制操作數(shù)A,B進行編碼，具體形式如式(1)所示

(1)

其中，Ai∈[0,9]是十進制操作數(shù)A的第i個十進制位；aj[j]∈[0,2]是Ai的8421-BCD編碼的第j個bit。操作數(shù)B的編碼方式與A一致。

十進制加法中因為需要處理十進制進位而變得復雜。由于8421-BCD碼在表示十進制數(shù)時有16種組合，其中6種組合(10102～11112)屬于無效碼，為產(chǎn)生正確的和以及進位，這些無效碼需要跳過。解決這一問題的方法是在其中一個操作數(shù)A的每個十進制位加上6得到A*，并采用二進制加法將A*和B相加得到中間和，如果中間和的某個十進制位的進位輸出為0,則再對中間和的相應十進制位進行減6修正得到最終和。上述算法的實例如圖1所示。

圖1　BCD十進制加法舉例

在圖1中，P=66610=0110_0110_01102被加到操作數(shù)A上產(chǎn)生一個預操作之后的臨時操作數(shù)A*。然后對操作A*和B采用二進制加法求和得到未修正的中間和H。C表示每一個十進制位進位輸出的情況，中間和H中沒有產(chǎn)生十進制進位的十進制位都被減去6(0110)以得到最終和S。

2十進制加法器設(shè)計

根據(jù)上述介紹的算法可知，設(shè)計十進制加法器時需要在進行二進制加法前對操作數(shù)A進行預加6操作，二進制加法結(jié)束后根據(jù)十進制進位情況進行減6修正得到最終和。本文按照二進制加法中性能最為優(yōu)越的并行前綴進位選擇結(jié)構(gòu)來設(shè)計十進制加法運算電路，并將減6修正整合到重新設(shè)計的十進制減6修正進位選擇加法器中以提高電路運算的并行度。

本文設(shè)計的十進制加法器需要在二進制加法前對其中一個操作數(shù)A進行加6預操作，其電路如圖2所示[11]。

圖2　加6電路圖

經(jīng)過預加6操作后A*和B按照二進制加法進行運算。二進制并行前綴進位選擇加法器中常用的樹形前綴單元包括Sklansky(SK)結(jié)構(gòu)、Kogge-Stone(KS)結(jié)構(gòu)和Brent-Kung(BK)結(jié)構(gòu)，其中KS結(jié)構(gòu)為最快的樹形結(jié)構(gòu)，本文采用KS樹形結(jié)構(gòu)作為前綴運算單元，16位KS結(jié)構(gòu)如圖3所示[12-13]。

圖3　Kogge-Stone樹

在二進制并行前綴進位選擇加法器中，進位選擇加法器為兩組進位輸入分別為0和1的4位行波進位加法器。進位選擇加法器和樹形前綴單元并行運算，樹形前綴單元輸出的進位信號到達后只需經(jīng)過一個二選一數(shù)據(jù)選擇器就可以得到最終和。在BCD十進制加法中，按照二進制加法得到的是需要減6修正的中間和。本文將減6修正步驟整合到重新設(shè)計的進位選擇加法中。由上述理論可得，判斷中間和的某個十進制位是否要修正的條件是這一十進制位是否有進位輸出。如果沒有則需要進行減6修正，否則不需要修正。由于在進行二進制加法前有預加6操作，所以中間和中需要修正的十進制位Hi≥6,可以得到如表1所示的真值表。

表1　減6真值表

由表1可以得到從中間和Hi到最終和Si的轉(zhuǎn)換邏輯，如式(2)所示

si[3]=hi[3]·hi[2]·hi[1]；

si[2]=hi[2]⊕hi[1];

(2)

si[0]=hi[0]‘

根據(jù)式(2)可知，要將減6修正步驟整合到二進制進位選擇加法器中，則需要修改組成二進制進位選擇加法器的4位行波進位加法器的電路結(jié)構(gòu)，使其根據(jù)最高位全加器的進位輸出決定是否進行減6修正，具體電路如圖4所示。

圖4　減6修正行波進位加法器

兩個如圖4所示的減6修正行波進位加法器可以構(gòu)成一個4位減6修正進位選擇加法器，其結(jié)構(gòu)如圖5所示。

圖5　減6修正進位選擇加法器

將二進制并行前綴進位選擇加法器中的進位選擇加法器，替換為圖5所示的4位減6修正進位選擇加法器，并將經(jīng)過預加6操作的操作數(shù)輸入到圖3所示的并行前綴單元，即可得到所設(shè)計的基于并行前綴進位選擇結(jié)構(gòu)的十進制加法器。32位十進制加法器結(jié)構(gòu)如圖6所示。

圖6　32位基于并行前綴結(jié)構(gòu)的十進制加法器

圖6所示32位基于并行前綴進位選擇結(jié)構(gòu)的十進制加法器可以拓展為64位，128位十進制加法器，只需要將并行前綴單元改為相應的位寬即可。由此可以得到基于并行前綴進位選擇結(jié)構(gòu)的十進制加法器的總體結(jié)構(gòu)如圖7所示。

圖7　十進制加法器結(jié)構(gòu)圖

3實驗數(shù)據(jù)及結(jié)果

為獲得設(shè)計的32位，64位，128位十進制加法器，采用圖2所示的預加6操作電路產(chǎn)生 ，并將操作數(shù) 和 輸入到圖7所示的基于并行前綴進位選擇結(jié)構(gòu)的十進制加法器中就可以得到十進制和S。減6修正在重新設(shè)計的減6修正進位選擇加法器中進行，大幅提高電路運算的并行度。使用Verilog HDL語言分別對32位，64位，128位十進制加法器進行描述并在ModelSim平臺上進行仿真驗證。在Nangate Open Cell 45 nm標準工藝庫下，通過Synopsys公司綜合工具Design Compiler進行綜合，最終得到32位，64位，128位十進制加法器的綜合結(jié)果如表2所示。

表2　十進制加法器綜合結(jié)果

4結(jié)束語

BCD十進制加法在運算過程中需要解決無效碼的問題使得其復雜度遠遠超過二進制加法。為減少十進制加法的復雜度，本文根據(jù)預先加6修正，配合二進制加法，得到中間和后再次減6修正的算法，設(shè)計了基于并行前綴結(jié)構(gòu)的十進制加法器。對進位選擇加法器重新設(shè)計，將減6修正步驟整合到重新設(shè)計的減6修正進位選擇加法器中，大幅提高了電路運算的并行度。本文設(shè)計的十進制加法器借鑒了二進制加法器中性能優(yōu)越的電路結(jié)構(gòu)，使得十進制加法也能夠像二進制加法那樣高效的完成。

參考文獻

[1]Wang L K, Erle M A, Tsen C, et al. A survey of hardware designs for decimal arithmetic[J]. IBM Journal of Research and Development, 2010, 54(2): 8-22.

[2]Cowlishaw M F. Decimal floating-point: algorism for computers[C]. Santiagode， Compostela：16th IEEE Symposium on Computer Arithmetic, 2003.

[3]Microprocessor Standards Committee of the IEEE Computer Society. IEEE standard for floating-point arithmetic, IEEE Std. 754-2008[S]. America: IEEE,2008.

[4]Schmookler M, Weinberger A. High speed decimal addition[J]. IEEE Transactions on Computers, 1971, 20(8): 862-866.

[5]Hwang I S. High speed binary and decimal arithmetic: U.S. Patent, 4866656[P]. 1989.

[6]Flora L P. Fast BCD/binary adder: U.S. Patent, 5008010[P].1991.

[7]Haller W, Krauch U. Combined binary/decimal adder unit: U.S. Patent, 5928319[P].1999.

[8]Haller W, Li W H. Highly parallel structure for fast multi cycle binary and decimal adder unit: U.S. Patent Application, 20060031279[P]. 2006.

[9]Sacks-Davis R. Applications of redundant number representations to decimal arithmetic[J]. Computer Journal, 1982, 25(4): 471-477.

[10]Shirazi B, Yun D, Zhang C. VLSI designs for redundant binary-coded decimal addition[C]. MA,USA: 7th Annual International Phoenix Conference on Computers and Communications, 1988.

[11]Vázquez A,Antelo E. Conditional speculative decimal addition[C]. HW,USA: 7th Conference on Real Numbers and Computers, 2006.

[12]Mathew S K, Ander M,Krishnamurthy R K, et al. A 4GHz 130nm address generation unit with 32-bit sparse-tree adder core[J]. IEEE Journal of Solid-State Circuits, 2003, 38(5): 689-695.

[13]Dimitrakopoulos G, Nikolos D. High-speed parallel-prefix VLSI ling adders[J]. IEEE Transactions on Computers, 2005, 54(2): 225-231.

Design of Decimal Adder Based on Parallel Prefix Structure

WANG Shumin，CUI Xiaoping

(College of Electronic and Information Engineering, Nanjing University of Aeronautics &Astronautics,Nanjing 210016, China)

AbstractAiming at the problem that the hardware implementation of the BCD code decimal addition requires the processing of invalid code, a new decimal adder based on the parallel prefix structure is designed. The proposed decimal adder based on the algorithm of adding six to each BCD digit of one operand prior to performing binary addition and then subtract six again if a carryout of the digit is not occur. The parallelism of circuit operation is increased by taking the advantage of parallel prefix structure. The designed decimal adder have been realized by Verilog HDL and synthesized by Design Compiler, the delay of decimal adder in 32 bit, 64 bit and 128 bit is 0.56 ns, 0.61 ns and 0.71 ns; the area is 1310 μm2, 2681 μm2 and 5485 μm2 .

Keywordsdecimal addition; parallel prefix structure; carry select adder of subtraction 6

收稿日期:2015-10-19

作者簡介:王書敏(1990-)，男，碩士研究生。研究方向:數(shù)字系統(tǒng)設(shè)計與計算機應用。崔曉平(1962-)，女，副教授，碩士研究生。研究方向：數(shù)字系統(tǒng)設(shè)計與計算機應用。

doi:10.16180/j.cnki.issn1007-7820.2016.06.006

中圖分類號TP332.2+1

文獻標識碼A

文章編號1007-7820(2016)06-019-04