# High-Speed FPGA 10's Complement Adders-Subtractors

Authors: G. Bioul; M. Vazquez; J. P. Deschamps; G. Sutter
Journal: International Journal of Reconfigurable Computing
 (2010)

---

## Abstract

This paper first presents a study on the classical BCD adders from which a carry-chain type adder is redesigned to fit within the Xilinx FPGA's platforms. Some new concepts are presented to compute theP and G functions for carry-chain optimization purposes. Several alternative designs are presented. Then, attention is given to FPGA implementations of add/subtract algorithms for 10's complement BCD numbers. Carry-chain type circuits have been designed on 4-input LUTs (Virtex-4, Spartan-3) and 6-input LUTs (Virtex-5) Xilinx FPGA platforms. All designs are presented with the corresponding time performance and area consumption figures. Results have been compared to straight implementations of a decimal ripple-carry adder and an FPGA 2's complement binary adder-subtractor using the dedicated carry logic, both carried out on the same platform. Better time delays have been registered for decimal numbers within the same range of operands.


---

## Body

## 1. Introduction

In a number of computer arithmetic applications, decimal systems are preferred to the binary ones. The reasons come not only from the complexity of coding/decoding interfaces but mostly from the lack of precision and clarity in the results of the binary systems.Decimal arithmetic plays a key role in data processing environments such as commercial, financial, and Internet-based applications [1–3]. Performances required by applications with intensive decimal arithmetic are not met by most of the conventional software-based decimal arithmetic libraries [1]. Hardware implementation embedded in recently commercialized general purpose processors [3, 4] is gaining importance.Furthermore,IEEE has recently published a new standard 754-2008 [5] that supports the floating point representation for decimal numbers.At the moment, Binary Coded Decimal (BCD) is used for decimal arithmetic algorithm implementations. Although other coding systems may be of interest, BCD seems to be the best choice until now. Issues of hardware realization of decimal arithmetic units appear to be widely open: potential improvements are expected in what refers to algorithm concepts as well as to hardware design. This paper resumes some new concepts about carry-chain type algorithms for adding BCD numbers. Two key ideas have been introduced: (i) the PropagateP and generate G functions are computed from the input data instead of intermediate BCD sums, and (ii) the functions have been implemented in Xilinx Virtex-4 [6] and Virtex-5 FPGA platforms [7], taking advantage of the 6-input LUTs structure of Virtex-5 version.Signed numbers addition is used as a primitive operation for computing most arithmetic functions, so that it deserves particular attention. It is well known that in classical algorithms the execution time of any program or circuit is proportional to the numberN of digits of the operands. In order to minimize the computation time, several ideas have been proposed in the literature [8, 9]. Most of them consist in modifying the classical algorithm in such a way as to minimize the computation time of each carry; the time complexity may still be proportional to N, but the proportionality constant may be reduced. Moreover, it has to be pointed out that, within the same range, decimal addition involves shorter carry propagation process than for the straight binary code. It will be shown in the practical implementations that adding BCD digits can not only save coding interfaces but moreover provides time delay reductions. Hardware consumption for BCD will be greater, if coding and decoding processes are not considered; as of today, the dramatic decreasing of hardware cost stimulates work on time saving.In this paper, decimal carry-chain and ripple-carry adders have been implemented on Virtex-4 XilinxFPGA platforms, for a number of operand sizes; comparative performances are presented for binary and BCD digit operands.Additionally, three implementations of adders-subtractors have been implemented on FPGA Xilinx Virtex-5 platforms for a number of operand sizes; comparative performances are presented for binary and BCD digit operands, respectively. Adder-subtractor inputs are 10’s complement signed BCD numbers; sign-change algorithm is used whenever subtraction is at hand.


## 2. Base-B Ripple-Carry Adders

Consider the base-B representations of two n-digit numbers:(1)x=xn-1·Bn-1+xn-2·Bn-2+⋯+x0·B0,y=yn-1·Bn-1+yn-2·Bn-2+⋯+y0·B0·Algorithm1 (pencil and paper) computes the (n+1)-digit representation of the sum z=x+y+cin where cin is an initial carry equal to 0 or 1.Algorithm 1.
Classic addition (ripple carry):
c(0):=c_in;
foriin0⋯n-1loop
ifx(i)+y(i)+c(i)>B-1thenc(i+1):=1;
elsec(i+1):=0;end if;
z(i):=(x(i)+y(i)+c(i)) mod B;
end loop;
z(n):=c(n);Asc(i+1) is a function of c(i), the execution time of Algorithm 1 is proportional to n (Figure 1). In order to reduce the execution time of each iteration step, Algorithm 1 can be modified as shown in Section 3.Figure 1
Ripple-Carry adder.


## 3. Base-B Carry-Chain Adders

First define two binary functions of twoB-valued variables, namely, the propagate(P) and generate(G) functions:(2)P(i)≡{P(x(i),y(i))=1ifx(i)+y(i)=B-1,P(x(i),y(i))=0otherwise;G(i)≡{G(x(i),y(i))=1ifx(i)+y(i)>B-1,G(x(i),y(i))=0otherwise.
The next carry ci+1 can be calculated as follows:ifP(i)=1thenc(i+1):=c(i);elsec(i+1):=G(i);end if;The corresponding modified Algorithm2 is the following one.Algorithm 2.
Carry-chain addition
– computation of the generation and propagation conditions:
foriin0⋯n-1loop
G(i):=G(x(i),y(i));
P(i):=P(x(i),y(i));
end loop;
– carry computation:
c(0):=c_in;
foriin0⋯n-1loop(3)ifP(i)=1thenc(i+1):=c(i);elsec(i+1):=G(i);endif;
end loop;
– sum computation
foriin0⋯n-1loop
z(i):=(x(i)+y(i)+c(i)) mod B;
end loop;
z(n):=c(n);Comments
(1)
Instruction sentence (3) is equivalent to the following Boolean equation:
(4)c(i+1)=P(i)·c(i)∨not(P(i))·G(i).
Furthermore, if the preceding relation is used, then the definition of the generate function can be modified:
(5)G(i)=1ifx(i)+y(i)>B-1,G(i)=0ifx(i)+y(i)<B-1,G(i)=0or1(donotcare)otherwise.(2)
Another Boolean equation equivalent to (4) is
(6)c(i+1)=G(i)∨P(i)·c(i).If the preceding relation is used, then the definition of the propagate function can be modified:(7)P(i)={1ifx(i)+y(i)=B-1,0ifx(i)+y(i)<B-1,P(i)=0or1(donotcare)otherwise.The structure of ann-digit adder with separate carry calculation is shown in Figure 2. It is based on Algorithm 2. The G-P (Generate-Propagate) cell calculates the Generate and Propagate functions (2).Figure 2
Carry-chain adder.TheCy.Ch (carry-chain) cell computes the next carry, that is to say(8)c(i+1)={c(i)ifP(i)=1,G(i)otherwise,
so that G(i) generates a carry, whatever happens upstream in the carry-chain, and P(i) propagates the carry from level i-1. The mod Bsum cell calculates(9)z(i)=(x(i)+y(i)+c(i))modB.As regards the computation timeT, the critical path is shaded in Figure 2. It has been assumed that Tsum>TCy.Ch.Another interesting time is the delayTcarry(n) from c(0) to c(n) assuming that all propagate and generate functions have already been calculated:(10)Tcarry(n)=n·Tmux2-1.Comments
The carry-chain cells are binary circuits, whereas thegenerate-propagate and the mod B sum cells are B-ary ones.
Equation (4) can be implemented by a 2-to-1 binary multiplexer (Figure 3(a)) while (6) by a 2-gate circuit (Figure 3(b)). In the first case, the per-digit-delayof a carry-chain adder is equal to the delay Tmux2-1 of a 2-to-1 binary multiplexer, whatever the base B is.Carry-chain cells.
(a)
Carry multiplexer(b)
AND-OR circuitIfB=2 and the carry-chain cell of Figure 3(a) is used, then P(i)=x(i)⊕y(i) and G(i) can be chosen equal to, for example, y(i). The corresponding cell for a n-bit binary adder is shown in Figure 4.Figure 4
Binary adder cell.


## 4. Base-10 Complement and Addition

### 4.1. Ten’s Complement Numeration System

B’s complement representation general principles are available in the literature as, for example, computer arithmetic books such as [8, 9]. One restricts to 10’s complement system to cope with the needs of this paper. A one-to-one function R(x), associating a natural number to x,is defined as follows.Every integerxbelonging to the range(11)-10n2≤x<10n2
is represented by R(x)=xmod10n, so that the integer represented in the form xn-1xn-2⋯x1x0 is(12)xn-1·10n-1+xn-2·10n-2+⋯+x0ifxn-1·10n-1+xn-2·10n-2+⋯+x0<10n2,xn-1·10n-1+xn-2·10n-2+⋯+x0-10nifxn-1·10n-1+xn-2·10n-2+⋯+x0≥10n2.The conditions (12) may be more simply expressed as(13)xn-1·10n-1+xn-2·10n-2+⋯+x0ifxn-1<5,xn-1·10n-1+xn-2·10n-2+⋯+x0-10nifxn-1≥5.
Another way to express a 10’s complement number is(14)xn-1′·10n-1+xn-2·10n-2+⋯+x0,
where xn-1′=xn-1-10 if xn-1≥5 and(15)xn-1′=xn-1ifxn-1<5,
while the sign definition rule is the following one: if  x  is  negative,  then  xn-1≥5;  otherwise  xn-1<5.


### 4.2. Ten’s Complement Sign Change

Given ann-digit 10’s complement integer x, the inverse z=-x of x is an (n+1)-digit 10’s complement integer. Actually the only case that -x cannot be represented with ndigits is when x=-10n/2, so -x=10n/2, that is to say -x=0.10n+(5)·10n-1+0.10n-2+⋯+0.100). The computation of the representation of -x is based on the following property.Assumingxto be represented as an n-digit 10’s complement number R(x),-x may be readily computed as(16)-x=10n+1-R(x).
A straightforward inversion algorithm then consists in representing xwith n+1 digits, complementing every digit to 9, then adding 1. Observe that sign extension is obtained by adding a digit 0 to the left of a positive number or 9 for a negative number, respectively.


## 4.1. Ten’s Complement Numeration System

B’s complement representation general principles are available in the literature as, for example, computer arithmetic books such as [8, 9]. One restricts to 10’s complement system to cope with the needs of this paper. A one-to-one function R(x), associating a natural number to x,is defined as follows.Every integerxbelonging to the range(11)-10n2≤x<10n2
is represented by R(x)=xmod10n, so that the integer represented in the form xn-1xn-2⋯x1x0 is(12)xn-1·10n-1+xn-2·10n-2+⋯+x0ifxn-1·10n-1+xn-2·10n-2+⋯+x0<10n2,xn-1·10n-1+xn-2·10n-2+⋯+x0-10nifxn-1·10n-1+xn-2·10n-2+⋯+x0≥10n2.The conditions (12) may be more simply expressed as(13)xn-1·10n-1+xn-2·10n-2+⋯+x0ifxn-1<5,xn-1·10n-1+xn-2·10n-2+⋯+x0-10nifxn-1≥5.
Another way to express a 10’s complement number is(14)xn-1′·10n-1+xn-2·10n-2+⋯+x0,
where xn-1′=xn-1-10 if xn-1≥5 and(15)xn-1′=xn-1ifxn-1<5,
while the sign definition rule is the following one: if  x  is  negative,  then  xn-1≥5;  otherwise  xn-1<5.


## 4.2. Ten’s Complement Sign Change

Given ann-digit 10’s complement integer x, the inverse z=-x of x is an (n+1)-digit 10’s complement integer. Actually the only case that -x cannot be represented with ndigits is when x=-10n/2, so -x=10n/2, that is to say -x=0.10n+(5)·10n-1+0.10n-2+⋯+0.100). The computation of the representation of -x is based on the following property.Assumingxto be represented as an n-digit 10’s complement number R(x),-x may be readily computed as(16)-x=10n+1-R(x).
A straightforward inversion algorithm then consists in representing xwith n+1 digits, complementing every digit to 9, then adding 1. Observe that sign extension is obtained by adding a digit 0 to the left of a positive number or 9 for a negative number, respectively.


## 5. Base-10 Adders

### 5.1. Base-10 Ripple-Carry Adders

ForB = 10, the classic and naïve approach [8] of ripple-carry for a BCD decimal adder cell can be implemented as in Figure 5. Observe that the critical path involves the carry propagation through 7 binary adders plus a 4-bit Boolean circuit (checking if the sum s is greater than 9 or not).Figure 5
Ripple-Carry BCD adder cell.


### 5.2. Base-10 Carry-Chain Adders

IfB = 10, the carry-chain circuit remains unchanged but the Pand G functions as well as the modulo-10 sums are somewhat more complex. In base 2, the mod B sumcell appears to be a single XOR function, while the mod 10sum cell is more complex as suggested by Figure 5.In base 2, thePand G cells are, respectively, synthesized by XOR and AND functions, while in base 10, P and Gare now defined as follows:(17)P(i)≡{P(x(i),y(i))=1ifx(i)+y(i)=9,P(x(i),y(i))=0otherwise;G(i)≡{G(x(i),y(i))=1ifx(i)+y(i)>9,G(x(i),y(i))=0otherwise.A straightforward way to synthesizePand Gis shown at Figure 6. Nevertheless, functions Pand G may be directly computed from x(i)andy(i) inputs. The following formulas (18) are Boolean expressions of conditions (17),Figure 6
G-P cell for BCD adder.(18)P(i)=p0·[k1·(p3·k2∨k3·g2)∨g1·k3·p2]G(i)=g0·[p3∨g2∨p2·g1]∨g3∨p3·p2∨p3·p1∨g2·p1∨g2·g1
where pj=xj⊕yj,  gj=xj·yj, and kj=xj′·yj′ are the binary propagator, generator, and carry-kill for the jth components of the BCD digits x(i) and y(i).The BCD carry-chain adderith cell is shown at Figure 7. It is made of a first mod 16 adder stage, a carry-chain cell driven by the G-P functions, and an output adder stage performing a correction (adding 6) whenever the carry-out is one. Actually, a zero carry-out c(i+1) identifies that the mod 16 sum does not exceed 9 if c(i) = 0, respectively,  8 if c(i) = 1; so no corrections are needed. Otherwise, the add-6 correction applies.Figure 7
Carry-chain BCD adderith cell.TheG-P functions may be computed according to Figure 6, using the outputs of the mod 16 stage, including the carry-out s4. With more hardware consumption, but saving time delays, formulas (18) may be used.


## 5.1. Base-10 Ripple-Carry Adders

ForB = 10, the classic and naïve approach [8] of ripple-carry for a BCD decimal adder cell can be implemented as in Figure 5. Observe that the critical path involves the carry propagation through 7 binary adders plus a 4-bit Boolean circuit (checking if the sum s is greater than 9 or not).Figure 5
Ripple-Carry BCD adder cell.


## 5.2. Base-10 Carry-Chain Adders

IfB = 10, the carry-chain circuit remains unchanged but the Pand G functions as well as the modulo-10 sums are somewhat more complex. In base 2, the mod B sumcell appears to be a single XOR function, while the mod 10sum cell is more complex as suggested by Figure 5.In base 2, thePand G cells are, respectively, synthesized by XOR and AND functions, while in base 10, P and Gare now defined as follows:(17)P(i)≡{P(x(i),y(i))=1ifx(i)+y(i)=9,P(x(i),y(i))=0otherwise;G(i)≡{G(x(i),y(i))=1ifx(i)+y(i)>9,G(x(i),y(i))=0otherwise.A straightforward way to synthesizePand Gis shown at Figure 6. Nevertheless, functions Pand G may be directly computed from x(i)andy(i) inputs. The following formulas (18) are Boolean expressions of conditions (17),Figure 6
G-P cell for BCD adder.(18)P(i)=p0·[k1·(p3·k2∨k3·g2)∨g1·k3·p2]G(i)=g0·[p3∨g2∨p2·g1]∨g3∨p3·p2∨p3·p1∨g2·p1∨g2·g1
where pj=xj⊕yj,  gj=xj·yj, and kj=xj′·yj′ are the binary propagator, generator, and carry-kill for the jth components of the BCD digits x(i) and y(i).The BCD carry-chain adderith cell is shown at Figure 7. It is made of a first mod 16 adder stage, a carry-chain cell driven by the G-P functions, and an output adder stage performing a correction (adding 6) whenever the carry-out is one. Actually, a zero carry-out c(i+1) identifies that the mod 16 sum does not exceed 9 if c(i) = 0, respectively,  8 if c(i) = 1; so no corrections are needed. Otherwise, the add-6 correction applies.Figure 7
Carry-chain BCD adderith cell.TheG-P functions may be computed according to Figure 6, using the outputs of the mod 16 stage, including the carry-out s4. With more hardware consumption, but saving time delays, formulas (18) may be used.


## 6. FPGA Implementations of the Base-10 Adders on 4-Input LUTs Xilinx Platforms

The base-10 adders of Figures5 and 7 have been implemented on 4-LUTs (Look-Up Tables up to 4 inputs) Xilinx devices. Virtex-4, Spartan 3, and the obsolete Virtex-2, Virtex and Spartan 2 are 4-input LUTs-based FPGA [6, 10]. In what follows the area is expressed in LUTs. In the Xilinx Virtex-4 technology a configurable logic block (CLB) involves 4 slicesanda slice is made by two 4-LUTs and some additional logic. VHDL models are available at [11].


### 6.1. Base-10 Ripple-Carry Adder

The classic implementation of the ripple carry adder cell inFPGA implies a 4-bit adder, a 4-LUT to detect the carry condition, and a final 3-bit adder. The delay and area consumption of an N-digit ripple carry adder are(19)TN-digit-B10-rc-adder=N·[TLUT+4·Tmux-cy+TXOR+Tcon+TLUT+Tcon+TLUT+3·Tmux-cy+TXOR+Tcon],CN-digit-B10-rc-adder=8·NLUTs.


### 6.2. FPGA Implementation of the Base-10 Carry-Chain Adder

In order to make the best use of the resources, the design has been achieved using relative location techniques (RLOC) [12] with low-level component instantiations. This first architecture is called GP_a.The adding stages are implemented as shown at Figures8(a) and 8(b) while the carry-chain structure with the G-P functions has been implemented as shown at Figure 9 where G is computed according to Figure 6, while Pis computed asFPGA implementation of adders: (a) 4-bit adder stage and (b) output adder stage.
(a)(b)Figure 9
FPGA implementation of the carry-chain circuit (GP_a architecture).(20)P=s3·s0·G′
equivalent to the expression of Figure 6. Figure 9 emphasizes that G depends on s1,s2,s3,ands4 while P is computed from s0,s3, and G.The time delay corresponding to the 4-bit adder stage (Figure8(a)) and the output adder stage (Figure 8(b)) is given as(21)T4-bitadder=TLUT+4·Tmux-cy,(22)Toutputadder=TLUT+3·Tmux-cy+TXOR.Both adder stages of Figures8(a) and 8(b) need the same hardware requirement; computed in slices, the area consumption is given as(23)C4-bitadder=Coutputadder=4LUTs.The complexity figures of the carry-chain circuit for a 4-digit unit, as shown at Figure9, are given as(24)TCy-Ch-a=2·TLUT+Tcon1+4·Tmux-cy,(25)CCy-Ch-a=8LUTs,
where Tcon1 stands for the average connection delay between two neighboring slices of the same CLB.The overall circuit is represented in Figure10. The overall time delay is computed from formulas (21), (22) and (24):Figure 10
FPGA implementation of an N-digit BCD Adder.(26)TN-digitadder-a=4·TLUT+(N+7)·Tmux-cy+TXOR+Tcon1+2·Tcon2,
where Tcon2 stands for the average connection delays between two slices located in neighbor columns. Tcon2 has to be accounted twice to involve both the connection delay between the 4-bit adder and the carry-chain and the one between the carry chain and the output adder.From (23) and (25), the area requirement may be computed as(27)CN-digitadder-a=10·NLUTs.


### 6.3. Other Implementations of Base-10 Carry-Chain Adders

FunctionsP and G may be directly computed from x(i) and y(i) inputs using the Boolean expression (18). Using 4-input LUTs (4-LUTs), a first implementation (Figure 11) computesFigure 11
Carry generation (GP_b architecture).(28)c=(x2⊕y2)·(x3′·y3′),b=(x2′·y2′)·(x3⊕y3)∨(x2·y2)·(x3′·y3′),a=(x1′·y1′)·b∨(x1·y1)·c,prop=(x0⊕y0)·a,h=(x0·y0)·(x1·y1),g=(x0·y0)∨x1∨y1,e=(x2·y2)·g∨h·(x2⊕y2),f=(x1⊕y1)∨(x2⊕y2),d=(x0·y0)∨f,gen=(x3·y3)∨(x3⊕y3)·d∨e.This architecture calledGP_bis shown in Figure 11. The corresponding time and area of a carry-chain cell using this architecture is(29)TCy-Ch-b=4·TLUT+3·Tcon1+Tmux-cy,CCy-Ch-b=10LUTs.The complete cell includes a 4-bit adder and a conditional 3-bit output adder adding 6 whenever necessary (similar to Figure5). The overall time delay and area consumption using this carry-computation cell is:(30)TN-digitadder-b=4·TLUT+(N+3)·Tmux-cy+TXOR+3·Tcon1+Tcon2,(31)CN-digitadder-b=18·NLUTs.The results in area and speed are poor compared to theGP_a implementation (obtaining G-P from the results of the 4-bit adder).Another alternative is based on the use of dedicated multiplexers. Xilinx Spartan 3, Virtex-2, and Virtex-4 devices have Look-Up Table multiplexers (muxf5, muxf6, muxf7, muxf8) in order to construct functions of 5, 6, 7, and 8 variables without using the general purpose routing fabric.Using this feature the circuit of Figure12 (GP_c) can be implemented using the following relations:Figure 12
Carry generation (GP_c architecture).(32)b=y3′·y2′·y1′;d=x2′·x1′;c=y3·d∨y3′·e;a=x3·b∨x3′·c;p1=(x0′∨y0′)·a,e=(x2·x1·y2′·y1)∨(x2′·x1·y2·y1)∨(x2·x1′·y2·y1′),k=(x2·y2)∨(x1·y1)·(x2∨y2);h=j=1;i=y3·j∨y3′·k;g1=x3·h∨x3′·i;p2=(x0∨y0).The corresponding time and area of a carry-chain cellGP_c is
(33)TCy-Ch-c=T6-LUT+TLUT+Tcon1+Tmux-cy,CCy-Ch-c=8LUTs,
where T6-LUT stands for the delay from an LUT input to a muxf6 output. The complete cell also includes 4-bit adder and a conditional 3-bit adder. The overall delay-area for GP_c cell is(34)TN-digitadder-c=T6-LUT+TLUT+(2·N+3)·Tmux-cy+TXOR+Tcon1+Tcon2,(35)CN-digitadder-c=16·NLUTs.


## 6.1. Base-10 Ripple-Carry Adder

The classic implementation of the ripple carry adder cell inFPGA implies a 4-bit adder, a 4-LUT to detect the carry condition, and a final 3-bit adder. The delay and area consumption of an N-digit ripple carry adder are(19)TN-digit-B10-rc-adder=N·[TLUT+4·Tmux-cy+TXOR+Tcon+TLUT+Tcon+TLUT+3·Tmux-cy+TXOR+Tcon],CN-digit-B10-rc-adder=8·NLUTs.


## 6.2. FPGA Implementation of the Base-10 Carry-Chain Adder

In order to make the best use of the resources, the design has been achieved using relative location techniques (RLOC) [12] with low-level component instantiations. This first architecture is called GP_a.The adding stages are implemented as shown at Figures8(a) and 8(b) while the carry-chain structure with the G-P functions has been implemented as shown at Figure 9 where G is computed according to Figure 6, while Pis computed asFPGA implementation of adders: (a) 4-bit adder stage and (b) output adder stage.
(a)(b)Figure 9
FPGA implementation of the carry-chain circuit (GP_a architecture).(20)P=s3·s0·G′
equivalent to the expression of Figure 6. Figure 9 emphasizes that G depends on s1,s2,s3,ands4 while P is computed from s0,s3, and G.The time delay corresponding to the 4-bit adder stage (Figure8(a)) and the output adder stage (Figure 8(b)) is given as(21)T4-bitadder=TLUT+4·Tmux-cy,(22)Toutputadder=TLUT+3·Tmux-cy+TXOR.Both adder stages of Figures8(a) and 8(b) need the same hardware requirement; computed in slices, the area consumption is given as(23)C4-bitadder=Coutputadder=4LUTs.The complexity figures of the carry-chain circuit for a 4-digit unit, as shown at Figure9, are given as(24)TCy-Ch-a=2·TLUT+Tcon1+4·Tmux-cy,(25)CCy-Ch-a=8LUTs,
where Tcon1 stands for the average connection delay between two neighboring slices of the same CLB.The overall circuit is represented in Figure10. The overall time delay is computed from formulas (21), (22) and (24):Figure 10
FPGA implementation of an N-digit BCD Adder.(26)TN-digitadder-a=4·TLUT+(N+7)·Tmux-cy+TXOR+Tcon1+2·Tcon2,
where Tcon2 stands for the average connection delays between two slices located in neighbor columns. Tcon2 has to be accounted twice to involve both the connection delay between the 4-bit adder and the carry-chain and the one between the carry chain and the output adder.From (23) and (25), the area requirement may be computed as(27)CN-digitadder-a=10·NLUTs.


## 6.3. Other Implementations of Base-10 Carry-Chain Adders

FunctionsP and G may be directly computed from x(i) and y(i) inputs using the Boolean expression (18). Using 4-input LUTs (4-LUTs), a first implementation (Figure 11) computesFigure 11
Carry generation (GP_b architecture).(28)c=(x2⊕y2)·(x3′·y3′),b=(x2′·y2′)·(x3⊕y3)∨(x2·y2)·(x3′·y3′),a=(x1′·y1′)·b∨(x1·y1)·c,prop=(x0⊕y0)·a,h=(x0·y0)·(x1·y1),g=(x0·y0)∨x1∨y1,e=(x2·y2)·g∨h·(x2⊕y2),f=(x1⊕y1)∨(x2⊕y2),d=(x0·y0)∨f,gen=(x3·y3)∨(x3⊕y3)·d∨e.This architecture calledGP_bis shown in Figure 11. The corresponding time and area of a carry-chain cell using this architecture is(29)TCy-Ch-b=4·TLUT+3·Tcon1+Tmux-cy,CCy-Ch-b=10LUTs.The complete cell includes a 4-bit adder and a conditional 3-bit output adder adding 6 whenever necessary (similar to Figure5). The overall time delay and area consumption using this carry-computation cell is:(30)TN-digitadder-b=4·TLUT+(N+3)·Tmux-cy+TXOR+3·Tcon1+Tcon2,(31)CN-digitadder-b=18·NLUTs.The results in area and speed are poor compared to theGP_a implementation (obtaining G-P from the results of the 4-bit adder).Another alternative is based on the use of dedicated multiplexers. Xilinx Spartan 3, Virtex-2, and Virtex-4 devices have Look-Up Table multiplexers (muxf5, muxf6, muxf7, muxf8) in order to construct functions of 5, 6, 7, and 8 variables without using the general purpose routing fabric.Using this feature the circuit of Figure12 (GP_c) can be implemented using the following relations:Figure 12
Carry generation (GP_c architecture).(32)b=y3′·y2′·y1′;d=x2′·x1′;c=y3·d∨y3′·e;a=x3·b∨x3′·c;p1=(x0′∨y0′)·a,e=(x2·x1·y2′·y1)∨(x2′·x1·y2·y1)∨(x2·x1′·y2·y1′),k=(x2·y2)∨(x1·y1)·(x2∨y2);h=j=1;i=y3·j∨y3′·k;g1=x3·h∨x3′·i;p2=(x0∨y0).The corresponding time and area of a carry-chain cellGP_c is
(33)TCy-Ch-c=T6-LUT+TLUT+Tcon1+Tmux-cy,CCy-Ch-c=8LUTs,
where T6-LUT stands for the delay from an LUT input to a muxf6 output. The complete cell also includes 4-bit adder and a conditional 3-bit adder. The overall delay-area for GP_c cell is(34)TN-digitadder-c=T6-LUT+TLUT+(2·N+3)·Tmux-cy+TXOR+Tcon1+Tcon2,(35)CN-digitadder-c=16·NLUTs.


## 7. FPGA Implementations of Base-10 Adders and Adders-Subtractors on 6-Input LUTs Xilinx Platforms

### 7.1. Base-10 BCD Carry-Chain Adder

In a first version,Ad-I, the adding stage and correction stage are implemented as shown at Figures 8(a) and 8(b), respectively, while the carry-chain structure with the G-Pfunctions is computed according to Figure 6.Xilinx Virtex-5 6-input/2-output LUT is built as two 5-input functions while the sixth input controls a 2-1 multiplexor allowing to implement either two 5-input functions or a single 6-input one; soGand Pfunctions fit in a single LUT as shown at Figure 13.Figure 13
FPGA carry-chain circuit for Ad-I.In a second version,Ad-II, the carry-chain is speeded up thanks to a direct computation of the G-P, namely, using inputs x(i)andy(i), instead of the intermediate sum bits sk. For this purpose one could use formulas (18); nevertheless, in order to minimize time and hardware consumption the implementation of P(i) and G(i) is revisited as follows. Remembering that P(i)=1 whenever the arithmetic sum x(i)+y(i)=9, one defines a 6-input function pp(i) set to be 1 whenever the arithmetic sum of the first 3 bits of x(i) and y(i) is 4. Then P(i) may be computed as(36)P(i)=(x0(i)⊕y0(i))·pp(i).On the other hand,gg(i) is defined as a 6-input function set to be 1 whenever the arithmetic sum of the first 3 bits of x(i) and y(i) is 5 or more. So, remembering that G(i)=1 whenever the arithmetic sum x(i)+y(i)>9,G(i) may be computed as(37)G(i)=gg(i)∨(pp(i)·x0(i)·y0(i)).As Xilinx Virtex-5 LUTs may compute 6-variable functions, thengg(i) and pp(i) may be synthesized using 2 LUTs in parallel while G(i) and P(i) are computed through an additional single LUT as shown at Figure 14.Figure 14
FPGA carry-chain circuit for Ad-II.


### 7.2.10’s Complement BCD Carry-Chain Adder-Subtractor

To computeX+Y similar algorithm as in Section 7.1 is used. In order to compute X–Y, 10’s complement subtraction algorithm actually adds (-Y) to X.


#### 7.2.1.10’s Complement (AS-I)

10’s complement sign change algorithm may be implemented through a digitwise 9’s complement stage followed by an add-1 operation. It can be shown that the 9’s complement binary componentsz3,z2,z1,andz0 of a given BCD digit y3,y2,y1,andy0 are expressed as(38)z3=y3′·y2′·y1′;z2=y2⊕y1;z1=y1;z0=y0′.To computeX–Y, 10’s complement subtraction algorithm actually adds (-Y) to X. So for a first implementation, AS-I, Figure 15 presents a 9’s complement implementation using 6-input/2-output LUTs, available in the Virtex-5 Xilinx technology. A′/S is the add/subtract control signal; if A′/S=1 (subtract), formulas in (38) apply; otherwise A′/S=0 and zj(i)=yj(i)for all i,j.Figure 15
FPGA 9’s complement circuit for AS-I.TheAS-I circuit is similar to the Ad-I (Figures 8 and 13) using, instead of input Y, the input Z as produced by the circuit of Figure 15.


#### 7.2.2. Improving the Adder Stage

To avoid the delay produced by the 9’s complement step, this operation may be carried out within the first binary adder stage, as depicted in Figure16, where p(i) and g(i) are computed asFigure 16
FPGA implementation of the adder stage for a 10’s complement BCD adder-subtractor.(39)p0(i)=x0(i)⊕y0(i)⊕(A′/S),p1(i)=x1(i)⊕y1(i),p2(i)=x2(i)⊕y2(i)⊕y1(i)·(A′/S),p3(i)=x3(i)⊕(y3(i)′·y2(i)′·y1(i)′)·(A′/S)⊕y3(i)·(A′/S)′,gk(i)=xk(i),∀k.


#### 7.2.3. Carry-Chain Stage Computing G and P Directly from the Input Data (AS-II)

As far as addition is concerned, theP and G functions may be implemented according to formulas (36) and (37). The idea of the AS-II is computing the corresponding functions in the subtract mode and then multiplexing according to the add/subtract control signal A′/S. For this reason, assuming that the operation at hand is X+(±Y), one defines on one hand ppa(i) and gga(i) according to Section 7.1, that is, using the straight values of Y’s BCD components.On the other hand,pps(i) and ggs(i) are defined according to the same Section 7.1 but using zk(i) as computed by the 9’s complement circuit shown at Figure 15. As zk(i) are expressed from the yk(i) (38), both pps(i) and ggs(i) may be computed directly from xk(i) andyk(i) as shown in Figure 17. Nevertheless, for subtraction, the computation of z0(k)=y0′(k) is carried out at the output LUT level. So formulas (36) and (37) are then expressed asFigure 17
FPGA implementation of the carry-chain stage AS-II for BCD adder-subtractor.(40)P(i)=(x0(i)⊕y0(i)⊕(A′/S))·pp(i),G(i)=gg(i)∨(pp(i)·x0(i)·(y0(i)⊕(A′/S))).


## 7.1. Base-10 BCD Carry-Chain Adder

In a first version,Ad-I, the adding stage and correction stage are implemented as shown at Figures 8(a) and 8(b), respectively, while the carry-chain structure with the G-Pfunctions is computed according to Figure 6.Xilinx Virtex-5 6-input/2-output LUT is built as two 5-input functions while the sixth input controls a 2-1 multiplexor allowing to implement either two 5-input functions or a single 6-input one; soGand Pfunctions fit in a single LUT as shown at Figure 13.Figure 13
FPGA carry-chain circuit for Ad-I.In a second version,Ad-II, the carry-chain is speeded up thanks to a direct computation of the G-P, namely, using inputs x(i)andy(i), instead of the intermediate sum bits sk. For this purpose one could use formulas (18); nevertheless, in order to minimize time and hardware consumption the implementation of P(i) and G(i) is revisited as follows. Remembering that P(i)=1 whenever the arithmetic sum x(i)+y(i)=9, one defines a 6-input function pp(i) set to be 1 whenever the arithmetic sum of the first 3 bits of x(i) and y(i) is 4. Then P(i) may be computed as(36)P(i)=(x0(i)⊕y0(i))·pp(i).On the other hand,gg(i) is defined as a 6-input function set to be 1 whenever the arithmetic sum of the first 3 bits of x(i) and y(i) is 5 or more. So, remembering that G(i)=1 whenever the arithmetic sum x(i)+y(i)>9,G(i) may be computed as(37)G(i)=gg(i)∨(pp(i)·x0(i)·y0(i)).As Xilinx Virtex-5 LUTs may compute 6-variable functions, thengg(i) and pp(i) may be synthesized using 2 LUTs in parallel while G(i) and P(i) are computed through an additional single LUT as shown at Figure 14.Figure 14
FPGA carry-chain circuit for Ad-II.


## 7.2.10’s Complement BCD Carry-Chain Adder-Subtractor

To computeX+Y similar algorithm as in Section 7.1 is used. In order to compute X–Y, 10’s complement subtraction algorithm actually adds (-Y) to X.


### 7.2.1.10’s Complement (AS-I)

10’s complement sign change algorithm may be implemented through a digitwise 9’s complement stage followed by an add-1 operation. It can be shown that the 9’s complement binary componentsz3,z2,z1,andz0 of a given BCD digit y3,y2,y1,andy0 are expressed as(38)z3=y3′·y2′·y1′;z2=y2⊕y1;z1=y1;z0=y0′.To computeX–Y, 10’s complement subtraction algorithm actually adds (-Y) to X. So for a first implementation, AS-I, Figure 15 presents a 9’s complement implementation using 6-input/2-output LUTs, available in the Virtex-5 Xilinx technology. A′/S is the add/subtract control signal; if A′/S=1 (subtract), formulas in (38) apply; otherwise A′/S=0 and zj(i)=yj(i)for all i,j.Figure 15
FPGA 9’s complement circuit for AS-I.TheAS-I circuit is similar to the Ad-I (Figures 8 and 13) using, instead of input Y, the input Z as produced by the circuit of Figure 15.


### 7.2.2. Improving the Adder Stage

To avoid the delay produced by the 9’s complement step, this operation may be carried out within the first binary adder stage, as depicted in Figure16, where p(i) and g(i) are computed asFigure 16
FPGA implementation of the adder stage for a 10’s complement BCD adder-subtractor.(39)p0(i)=x0(i)⊕y0(i)⊕(A′/S),p1(i)=x1(i)⊕y1(i),p2(i)=x2(i)⊕y2(i)⊕y1(i)·(A′/S),p3(i)=x3(i)⊕(y3(i)′·y2(i)′·y1(i)′)·(A′/S)⊕y3(i)·(A′/S)′,gk(i)=xk(i),∀k.


### 7.2.3. Carry-Chain Stage Computing G and P Directly from the Input Data (AS-II)

As far as addition is concerned, theP and G functions may be implemented according to formulas (36) and (37). The idea of the AS-II is computing the corresponding functions in the subtract mode and then multiplexing according to the add/subtract control signal A′/S. For this reason, assuming that the operation at hand is X+(±Y), one defines on one hand ppa(i) and gga(i) according to Section 7.1, that is, using the straight values of Y’s BCD components.On the other hand,pps(i) and ggs(i) are defined according to the same Section 7.1 but using zk(i) as computed by the 9’s complement circuit shown at Figure 15. As zk(i) are expressed from the yk(i) (38), both pps(i) and ggs(i) may be computed directly from xk(i) andyk(i) as shown in Figure 17. Nevertheless, for subtraction, the computation of z0(k)=y0′(k) is carried out at the output LUT level. So formulas (36) and (37) are then expressed asFigure 17
FPGA implementation of the carry-chain stage AS-II for BCD adder-subtractor.(40)P(i)=(x0(i)⊕y0(i)⊕(A′/S))·pp(i),G(i)=gg(i)∨(pp(i)·x0(i)·(y0(i)⊕(A′/S))).


## 7.2.1.10’s Complement (AS-I)

10’s complement sign change algorithm may be implemented through a digitwise 9’s complement stage followed by an add-1 operation. It can be shown that the 9’s complement binary componentsz3,z2,z1,andz0 of a given BCD digit y3,y2,y1,andy0 are expressed as(38)z3=y3′·y2′·y1′;z2=y2⊕y1;z1=y1;z0=y0′.To computeX–Y, 10’s complement subtraction algorithm actually adds (-Y) to X. So for a first implementation, AS-I, Figure 15 presents a 9’s complement implementation using 6-input/2-output LUTs, available in the Virtex-5 Xilinx technology. A′/S is the add/subtract control signal; if A′/S=1 (subtract), formulas in (38) apply; otherwise A′/S=0 and zj(i)=yj(i)for all i,j.Figure 15
FPGA 9’s complement circuit for AS-I.TheAS-I circuit is similar to the Ad-I (Figures 8 and 13) using, instead of input Y, the input Z as produced by the circuit of Figure 15.


## 7.2.2. Improving the Adder Stage

To avoid the delay produced by the 9’s complement step, this operation may be carried out within the first binary adder stage, as depicted in Figure16, where p(i) and g(i) are computed asFigure 16
FPGA implementation of the adder stage for a 10’s complement BCD adder-subtractor.(39)p0(i)=x0(i)⊕y0(i)⊕(A′/S),p1(i)=x1(i)⊕y1(i),p2(i)=x2(i)⊕y2(i)⊕y1(i)·(A′/S),p3(i)=x3(i)⊕(y3(i)′·y2(i)′·y1(i)′)·(A′/S)⊕y3(i)·(A′/S)′,gk(i)=xk(i),∀k.


## 7.2.3. Carry-Chain Stage Computing G and P Directly from the Input Data (AS-II)

As far as addition is concerned, theP and G functions may be implemented according to formulas (36) and (37). The idea of the AS-II is computing the corresponding functions in the subtract mode and then multiplexing according to the add/subtract control signal A′/S. For this reason, assuming that the operation at hand is X+(±Y), one defines on one hand ppa(i) and gga(i) according to Section 7.1, that is, using the straight values of Y’s BCD components.On the other hand,pps(i) and ggs(i) are defined according to the same Section 7.1 but using zk(i) as computed by the 9’s complement circuit shown at Figure 15. As zk(i) are expressed from the yk(i) (38), both pps(i) and ggs(i) may be computed directly from xk(i) andyk(i) as shown in Figure 17. Nevertheless, for subtraction, the computation of z0(k)=y0′(k) is carried out at the output LUT level. So formulas (36) and (37) are then expressed asFigure 17
FPGA implementation of the carry-chain stage AS-II for BCD adder-subtractor.(40)P(i)=(x0(i)⊕y0(i)⊕(A′/S))·pp(i),G(i)=gg(i)∨(pp(i)·x0(i)·(y0(i)⊕(A′/S))).


## 8. Experimental Results

### 8.1. Xilinx Virtex-4 Adder Implementations

The base-10 adders have been implemented on Xilinx Virtex-4FPGA family speed grade-11 [6]. The Synthesis and implementation have been carried out on XST (Xilinx Synthesis Technology) [13] and Xilinx ISE (Integrated System environment) version 10.1 [14].Performances of differentN-digit BCD adders have been compared to those of an M-bit binary carry chain adder (implemented by XST [13] using Xilinx fast carry logic) covering the same range, that is, as(41)M=⌈N·log2(10)⌉≅3.322×N.The time and hardware complexities of anM-bit ripple-carry adder implemented on the same 4-LUT based XilinxFPGA are given by(42)TM-bitadder=TLUT+M·Tmux-cy,=TLUT+3.322×N×Tmux-cy.(43)CM-bitadder=MLUTs=3.322×NLUTsFormulas (26), (30), (34), and (42) show that, asymptotically, TN-digitadder should be somewhat inferior to TM-bitadder.Nevertheless, as shown by the experimental results, the additive values appearing in (26), (30), and (34) are not negligible for reasonable values of N; so the saving in time will mainly appear for applications where BCD-to-binary coding and decoding operations play a significant role in the overall delay.Post place-and-route time delays and area consumptions are quoted in Tables1 and 2, respectively, where N stands for the number of BCD digits while Mstands for the number of bits required to cover the decimal N-digit range. The results presented in the table are as follows:Table 1
Time delays (nsec) for different adders in Virtex-4 -11.
NN-digit BCD adderMM-bit BinaryRipplePG_aPG_bPG_c8145.86.74.5272.712206.06.84.8403.216276.17.05.1543.724406.47.35.7804.732536.77.66.31075.740667.07.96.91336.648797.38.27.51607.6641057.98.78.72139.696—9.19.911.031913.5128—10.311.113.442617.5Table 2
Area (in LUTs) for different adder’s size in Virtex-4.
Adder Circuit# LUT’sRipple8 ×NPG_a10 ×NPG_b18 ×NPG_c16 ×NBinary⌈3.32×N⌉(i)
Ripple: Naïve implementation of base-10 ripple-carry (Section 5.1, Figures 1 and 5),(ii)
PG_a: base-10 carry chain using an adder to produce P-Gvalues (Section 5.2, Figures 2, 6, 8, 9, and 10),(iii)
PG_b: base-10 carry chain computing directly P-G values (Section 6.3, Figures 2 and 11),(iv)
PG_c: base-10 carry chain computing directly P-G values using muxf5 and muxf6 (Section 6.3, Figures 2 and 12),(v)
M-bit Binary: base-2 carry chain adder covering the same range as an N-digit adder.Figure18 shows the delays for the compared adders. Observe that, for the technology at hand, Table 1 and Figure 18 suggest that for N > 48 the carry-chain decimal implementation of adders is faster than the binary one for the equivalent range. Furthermore for small numbers of digits to add (N < 40) the PG_c architecture is faster than other decimal implementations.Figure 18
Delay inns for different adders in Virtex-4.


### 8.2. Virtex-5 Adder-Subtractor Implementations

The adder-subtractor circuits have been implemented on Xilinx Virtex-5 family with speed grade-2 [7]. The synthesis and implementation have been carried out on XST (Xilinx Synthesis Technology) [13] and Xilinx ISE (Integrated System environment) version 10.1 [14]. The critical parts were designed using low-level components instantiation (lut6_2, muxcy, xorcy, etc.) in order to obtain the desired behavior. Performances of different N-digit BCD adders have been compared to those of an M-bit binary carry chain adder (implemented by XST) covering the same range, that is, such that M=⌈N·log2(10)⌉≅3.322N.Table3 exhibits the postplacement and routing delays in ns for the decimal adder implementations Ad-I and Ad-II of Section 7.1; Table 4 exhibits the delays in ns for the decimal adder-subtractor implementations AS-I and AS-II of Section 7.2. Table 5 lists the consumed areas expressed in terms of 6-input look-up tables (6-input LUTs). The estimated area presented in Table 5 was empirically confirmed.Table 3
Delays in ns for decimal and binary adders in Virtex-5 -2.
N (BCD digits)Ad-IAd-IIM(bits)Binary Adder83.83.6272.1164.44.0542.6325.04.51073.8485.25.11605.1645.65.22136.6966.15.93198.7Table 4
Delays in ns for decimal and binary adder-subtractor in Virtex-5 -2.
N (BCD digits)AS-IAS-IIM(bits)Binary Add-Sub83.83.8272.1164.14.0542.6324.75.01073.8485.35.21605.2645.75.52136.6966.36.23198.8Table 5
Area in 6-input LUTs for different adders and adders-subtractors.
Circuit# LUTsAdderAd-I8 ×NAdderAd-II10 ×NBinary Adder⌈3.32×N⌉Adder-SubtractorAS-I10 ×NAdder-SubtractorAS-II13 ×NBinary Adder-Subtractor⌈3.32×N⌉Comments
Observe that, for large operands, the decimal operations are faster than the binary ones.
The overall area with respect to binary computation is not negligible. In Virtex-4 the area increases, with respect to an equal range binary adder, in a factor between 2.4 and 5.4. In the 6-input LUT family Virtex-5 an adder-subtractor is between 3.0 and 3.9 times bigger.


## 8.1. Xilinx Virtex-4 Adder Implementations

The base-10 adders have been implemented on Xilinx Virtex-4FPGA family speed grade-11 [6]. The Synthesis and implementation have been carried out on XST (Xilinx Synthesis Technology) [13] and Xilinx ISE (Integrated System environment) version 10.1 [14].Performances of differentN-digit BCD adders have been compared to those of an M-bit binary carry chain adder (implemented by XST [13] using Xilinx fast carry logic) covering the same range, that is, as(41)M=⌈N·log2(10)⌉≅3.322×N.The time and hardware complexities of anM-bit ripple-carry adder implemented on the same 4-LUT based XilinxFPGA are given by(42)TM-bitadder=TLUT+M·Tmux-cy,=TLUT+3.322×N×Tmux-cy.(43)CM-bitadder=MLUTs=3.322×NLUTsFormulas (26), (30), (34), and (42) show that, asymptotically, TN-digitadder should be somewhat inferior to TM-bitadder.Nevertheless, as shown by the experimental results, the additive values appearing in (26), (30), and (34) are not negligible for reasonable values of N; so the saving in time will mainly appear for applications where BCD-to-binary coding and decoding operations play a significant role in the overall delay.Post place-and-route time delays and area consumptions are quoted in Tables1 and 2, respectively, where N stands for the number of BCD digits while Mstands for the number of bits required to cover the decimal N-digit range. The results presented in the table are as follows:Table 1
Time delays (nsec) for different adders in Virtex-4 -11.
NN-digit BCD adderMM-bit BinaryRipplePG_aPG_bPG_c8145.86.74.5272.712206.06.84.8403.216276.17.05.1543.724406.47.35.7804.732536.77.66.31075.740667.07.96.91336.648797.38.27.51607.6641057.98.78.72139.696—9.19.911.031913.5128—10.311.113.442617.5Table 2
Area (in LUTs) for different adder’s size in Virtex-4.
Adder Circuit# LUT’sRipple8 ×NPG_a10 ×NPG_b18 ×NPG_c16 ×NBinary⌈3.32×N⌉(i)
Ripple: Naïve implementation of base-10 ripple-carry (Section 5.1, Figures 1 and 5),(ii)
PG_a: base-10 carry chain using an adder to produce P-Gvalues (Section 5.2, Figures 2, 6, 8, 9, and 10),(iii)
PG_b: base-10 carry chain computing directly P-G values (Section 6.3, Figures 2 and 11),(iv)
PG_c: base-10 carry chain computing directly P-G values using muxf5 and muxf6 (Section 6.3, Figures 2 and 12),(v)
M-bit Binary: base-2 carry chain adder covering the same range as an N-digit adder.Figure18 shows the delays for the compared adders. Observe that, for the technology at hand, Table 1 and Figure 18 suggest that for N > 48 the carry-chain decimal implementation of adders is faster than the binary one for the equivalent range. Furthermore for small numbers of digits to add (N < 40) the PG_c architecture is faster than other decimal implementations.Figure 18
Delay inns for different adders in Virtex-4.


## 8.2. Virtex-5 Adder-Subtractor Implementations

The adder-subtractor circuits have been implemented on Xilinx Virtex-5 family with speed grade-2 [7]. The synthesis and implementation have been carried out on XST (Xilinx Synthesis Technology) [13] and Xilinx ISE (Integrated System environment) version 10.1 [14]. The critical parts were designed using low-level components instantiation (lut6_2, muxcy, xorcy, etc.) in order to obtain the desired behavior. Performances of different N-digit BCD adders have been compared to those of an M-bit binary carry chain adder (implemented by XST) covering the same range, that is, such that M=⌈N·log2(10)⌉≅3.322N.Table3 exhibits the postplacement and routing delays in ns for the decimal adder implementations Ad-I and Ad-II of Section 7.1; Table 4 exhibits the delays in ns for the decimal adder-subtractor implementations AS-I and AS-II of Section 7.2. Table 5 lists the consumed areas expressed in terms of 6-input look-up tables (6-input LUTs). The estimated area presented in Table 5 was empirically confirmed.Table 3
Delays in ns for decimal and binary adders in Virtex-5 -2.
N (BCD digits)Ad-IAd-IIM(bits)Binary Adder83.83.6272.1164.44.0542.6325.04.51073.8485.25.11605.1645.65.22136.6966.15.93198.7Table 4
Delays in ns for decimal and binary adder-subtractor in Virtex-5 -2.
N (BCD digits)AS-IAS-IIM(bits)Binary Add-Sub83.83.8272.1164.14.0542.6324.75.01073.8485.35.21605.2645.75.52136.6966.36.23198.8Table 5
Area in 6-input LUTs for different adders and adders-subtractors.
Circuit# LUTsAdderAd-I8 ×NAdderAd-II10 ×NBinary Adder⌈3.32×N⌉Adder-SubtractorAS-I10 ×NAdder-SubtractorAS-II13 ×NBinary Adder-Subtractor⌈3.32×N⌉Comments
Observe that, for large operands, the decimal operations are faster than the binary ones.
The overall area with respect to binary computation is not negligible. In Virtex-4 the area increases, with respect to an equal range binary adder, in a factor between 2.4 and 5.4. In the 6-input LUT family Virtex-5 an adder-subtractor is between 3.0 and 3.9 times bigger.


## 9. Conclusions

The present interest in BCD arithmetic systems stimulates further researches at both the algorithmic and design levels. Considering that the hardware costs are everyday more affordable, full hardware BCD units are now very attractive, with moreover a growing potential in the near future.This paper has developed some implementations of BCD adders and subtractors inFPGA platforms. Experimental results emphasize time performances with reasonable costs in terms of area. Matched with the binary system, the decimal implementations are faster as operand sizes are growing (break even around 50 digits).One of the key points about delays comes from the fact that the carry-propagation computation remains binary; then a faster carry-chain circuit can be designed because, for the same operand range, the number of digits (therefore of carries to propagate) is lower in decimal than in binary. In the carry-chain structures studied in this paper, the propagateP and generate G functions are more complex and therefore more time and area consuming than in the binary ones; therefore, the speed improvements only appear for large enough operands. The breakeven point is obviously technology dependent; so it could be expected to occur for a smaller number of digits in the near future.The area overhead with respect to binary computation is not negligible; it is around five times in Virtex-4 and nearly four times in Virtex-5. That is mainly due to the more complex definition of thecarry propagate and carry generate functions and to the final mod 10 reduction. The decreasing costs of technology make hardware consumption less central.For BCD addition, the performance considerations on Xilinx Virtex-5 platform are similar to those of 4-input LUTs-based Virtex-4 technology. That is, the addition time of BCD digits remains faster than the binary counterpart in the same conditions.Finally, the BCD adder/subtractor, with a relatively small penalty in area, presents time performances quite similar to those of a straight BCD adder.



---

*Source: 219764-2010-02-01.xml*