Method and apparatus for generating sign-digit format of sum of two numbers

The present invention generally relates to the computation of binary numbers, and more particularly to the efficient conversion of binary numbers into sign-digit redundant form.

In order to build compact binary multipliers, the sign-digit representation of a binary number is used in the hardware design. If a digit of the binary number is made wider, then the total number of digits is reduced. Accordingly, certain radix digits are chosen for the desired numbering system. The most popular system uses sign-digit numbers with radix 4. Accordingly, each two bits of a number are substituted by a digit which has a value from the set of {−2, −1, 0, 1, 2}. An advantage of this radix system is that a partial product generated by multiplying the digit by a second argument involves only simple logic operations to produce. For instance, the partial product may be generated by masking, shifting by one and inversion. Accordingly, instead of generating n partial products for a n-bit binary number, only n/2+2 partial products are generated.

After all the partial products have been generated during multiplication, then the partial products are added together using the well-known Wallace Tree. The Wallace Tree reduces the number of partial products at each stage without full carry propagation. The Wallace Tree functions as a “carry-save” adder (CSA) and does not make use of full carry propagation. The output of the CSA is a carry save-number which contains the partial sum of the number and all of the carries. In order to compute the final value, a carry propagation adder (CPA) is used to add the carries. Typically, the CPA has a larger delay by comparison to the CSA.

Referring to FIG. 1 , the delays with the addition and multiplication of three values A, B, and C is shown. The desired result is (A+B)·C wherein A, B, and C are binary numbers. Both the values A and B are inputted into adder CPA 10 that is a carry propagation adder which has a large delay associated therewith. Once the values A and B have been added by the CPA 10 , the sum of A+B is fed into a multiplier Wallace Tree 14 . The value C is fed into a booth encoder 12 which can encode the value C for multiplication using the well-known Booth's algorithm. The encoded value of C from the booth encoder 12 is then fed into the multiplier 14 which computes the value (A+B)·C with a final CPA 11 . As previously mentioned, the delay of the CPA 10 and the final CPA 11 is significantly large compared to the multiplier Wallace Tree 14 such that the arrangement of FIG. 1 has a large latency caused by using two CPAs with appropriate delays.

FIG. 2 shows the same operation as FIG. 1 , but carried out in a different manner. Specifically, the values of A and B are fed into respective multiplier Wallace Trees 14 a and 14 b . The value C is also fed into each of the multipliers 14 a and 14 b after being booth encoded in encoder 12 . In this respect, multiplier 14 a computes the value of A-C and multiplier 14 b computes the value of B·C. The outputs of the multipliers 14 a and 14 b are fed into adder 16 which adds the values together to achieve the final result A·C+B·C (i.e., (A+B)·C). As is evident from FIG. 2 , this method of computation reduces the delay from the CPA 10 , but increases the complexity and gate count of the circuit by including two multipliers 14 a and 14 b.

The present invention addresses the above-mentioned deficiencies in computation of binary numbers by providing a system and method that reduces circuit complexity and latency in the computation. Specifically, the present invention provides a method whereby the gate count for the computational circuit is reduced compared to the circuit of FIG. 2 , yet the speed of the computation is not decreased by providing an efficient conversion of the binary numbers into sign-redundant form. Accordingly, the present invention provides a good balance between complexity and latency in order to achieve a small, and simple device.

In accordance with the present invention, there is provided a method for partial adding and converting two numbers having binary digits into a redundant sign-digit format. The method uses partial propagation of the carry of the sum regarding the desired radix of the Booth encoder. The radix is used as a bias for interim results. The binary digits of each number are added together with a first adder in order to generate a first result with a first carry. A second adder adds the first result to a first input carry of a previous digit. A value equal to the radix of the binary digits is subtracted from the first result with the second addition block if the first result is greater than an initial threshold such that an intermediate result and a second carry is generated. A third adder adds the intermediate result to a second input carry of the previous digit. With the third adder, the value of the radix is subtracted from the intermediate result if the intermediate result is greater than a prescribed value in order to generate a final output in redundant sign-digit format. The method is continued for all sets of binary digits.

In accordance with the present invention, there is also provided a system for multiplying the sum of a first number A and a second number B by a third number C. The system has a first adder configured to add the binary digits of A and B together and generate a first result with a first carry. The system also includes a second adder block configured to add the first result to the first input carry of a previous digit. Furthermore, the second adder is configured to subtract the value of the radix from the first result if the first result is greater than an initial threshold in order to generate an intermediate result with a second carry. The system includes a third adder configured to add the intermediate result to a second input carry of a previous digit and subtract the value of the radix from the intermediate result if the intermediate result is greater than a prescribed value. In this regard, the first, second, and third adders are configured to add and convert the numbers A and B into sign-digit redundant format. The system further includes a multiplier configured to multiply the redundant sign-digit format of the addition of A and B from the third adder by the value of C in order to generate the final result.

In addition to the foregoing, there is provided a method for multiplying the sum of a first number A having binary digits and a second number B having binary digits by a third number C. The binary digits of A and B are added together in order to generate the first result with the first carry. The first result is added to the first input carry of the previous digit. Then, the value of the radix is subtracted from the first result if the first result is greater than an initial threshold in order to generate the intermediate result with the second carry. The intermediate result is added to the second input carry of the previous digit and the radix is subtracted from the intermediate result if the intermediate result is greater than a prescribed value. This result is the sum of A and B expressed in sign-digit redundant format. Then, the sign-digit redundant format of the sum of A and B is multiplied with C in order to generate the final result.

These, as well as other features of the present invention, will become more apparent upon reference to the drawings wherein:

FIGS. 1 and 2 are prior art computational circuits;

FIG. 3 is a conversion circuit constructed in accordance with the present invention; and

FIG. 4 is a basic conversion circuit for radix 4 sign-digits.

Referring now to the drawings wherein the showings are for purposes of illustrating a preferred embodiment of the present invention only, and not for purposes of limiting the same, FIG. 3 illustrates a computational circuit 20 constructed in accordance with the preferred embodiment of the present invention and used to compute the value (A+B)·C. The circuit 20 has a CSA to Booth encoder 22 which encodes the value of A+B, as will be further explained below. The value of A+B is fed into a multiplier 24 which also receives the value of C. The multiplier 24 multiplies A+B by C to output the final result of: (A+B)·C.

The CSA to booth encoder 22 provides a novel manner to convert the sum of A and B into sign-digit redundant form for multiplication by C in multiplier 24 . FIG. 4 illustrates the structure of each coder unit 28 replicated for each digit position shown in FIG. 3 . Specifically, A and B are 2 digit binary CSA numbers such that a first result D i is generated with an adder 40 by:

D i =a 1i ·2+ a 0i +b 1i ·2+ b 0i D i ε{0 . . . 6}  (1)

wherein a 1i , a 0i , and b 1i , b 0i are the respective two bit binary digit representations for A and B on the digit position i.

Next, a threshold value n t is declared to be:

n t : n t ε{2 . . . 5}  (2)

Accordingly, then the output carry signal C 1out is determined with comparator 42 to be:

After adding the input carry from the previous digit C 1in with adder 44 , the value of an intermediate result D 1 i is:

D 1i =D i +C 1in −C 1out ·r   (4)

D 1i ε{min( n t −4,0) . . . ( n t , 2)}  (5)

Wherein the bias r=4 is the radix of the binary system used.

At this stage the output carry C 2out can be declared to be with comparator 46 :

The value of the final digits converted into redundant sign-digit format D 2i after adding the input carry from the previous digit C 2in with adder 48 becomes:

D 2i =D 1i +C 2in −C 2out ·r D 2i ε{−2,−1,0,1,2}  (7)

wherein the bias r=4 is the radix of the binary system used.

As will be recognized, D 2i is in sign digit format because it is an element of the set {−2, −1, 0, 1, 2}. This is the digit representation that reduces multiplication steps in the multiplier 24 .

Referring back to FIG. 3 , each coder 28 computes the equations (1)–(7) described above and shown in FIG. 4 for calculating the final result. Each coder 28 generates a respective D 2i . As previously mentioned, the final results are in sign-redundant form that facilitate multiplication with the value C.

Referring to Table 1, an example showing the conversion of two binary numbers into sign-digit redundant format is shown. In this example, the threshold value n, is selected to be n t =4. Table 1 shows the resultant values of D and C using the method of the present invention. As can be seen, the method converts the two binary numbers into sign-digit redundant form while adding their values together to achieve the result: D 2 =111−11=333. As previously discussed, the resultant values can then be multiplied by multiplier 24 with the value of C to achieve the final result.

More specifically, Table 1 describes the situation wherein:

a=162=(10100010) 2   (8)

b=171=(10101011) 2   (9)

a+b= 162+171=(10100010) 2 +(10101011) 2 =333  (10)

⁢ For ⁢ ⁢ a = 162 ( 11 ) = ( 1010010 ⁢ ) 2 ( 12 ) = ( 10 ⁢ ⁢ 10 ⁢ ⁢ 00 ⁢ ⁢ 10 ) 2 ( 13 ) = ( 10 ) 2 · 4 3 + ( 10 ) 2 · 4 2 + ( 00 ) 2 · 4 1 + ( 10 ) 2 · 4 0 ( 14 ) ≡ ∑ j = 0 3 ⁢ Aj · 4 j ( 15 ) wherein, A 3 =(10) 2 , A 2 =(00) 2 , A 1 =(10) 2 and A 0 =(10) 2   (16)

Further define A j :

A j =( a 1j ·2 1 +a 0j ·2 0 )=( a 1j ·2 +a 0j )  (17)

Because A 3 =(10) 2 , then a 13 =1 and a 03 =0.

Similarly:

a 12 =1, a 02 =0  (18)

a 11 =0, a 01 =0  (19)

a 10 =1, a 00 =0  (20)

For ⁢ ⁢ b = 171 ⁢

= ( 10101011 ) 2 ⁢

= ( 10 ⁢ ⁢ 10 ⁢ ⁢ 10 ⁢ ⁢ 11 ) 2 ⁢

= ( 10 ) 2 · 4 3 + ( 10 ) 2 · 4 2 + ( 10 ) 2 · 4 1 + ( 11 ) 2 · 4 0 ⁢

≡ ∑ j = 0 3 ⁢ B j · 4 j

wherein, B 3 =(10) 2 , B 2 =(10) 2 , B 1 =(10) 2 , B 0 =(11) 2 ,

Further define B j :

B j =( b 1j ·2 1 +b 0j ·2 0 )=( b 1j ·2 +b 0j )  (27)

Accordingly:

b 13 =1, b 03 =0  (28)

b 12 =1, b 02 =0  (29)

b 11 =1, b 01 =0  (30)

b 10 =1, b 00 =1  (31)

And thus:

According to Eq. (1):

D 0i =( a 1i ·2 +a 0i )+( b 1i ·2 +b 0i )  (35)

D 0i =( A j +B j ); and  (36)

D 03 =(1·2+0)+(1·2+0)=4  (37)

D 02 =(1·2+0)+(1·2+0)=4  (38)

D 01 =(0·2+0)+(1·2+0)=2  (39)

D 00 =(1·2+0)+(1·2+1)=5  (40)

As stated previously, in equation (3), C 1i =1 if D 0i ≧n t , otherwise C 1i =0 if D 0i <n t where n t ε{2 . . . 5}. In this example, n t =4. Accordingly:

=C 13 =1  (41)

C 12 =1  (42)

C 11 =0  (43)

C 10 =1  (44)

Therefore:

Accordingly:

D 14 =D 04 +( C 13 −C 14 ·4)=0+1−0·4=1  (47)

D 13 =D 03 +( C 12 −C 13 ·4)=4+1−1·4=1  (48)

D 12 =D 02 +( C 11 −C 12 ·4)=4+0−1·4=0  (49)

D 11 =D 01 +( C 10 −C 11 ·4)=2+1−0·4=3  (50)

D 10 =D 00 +(0 −C 10 ·4)=5+0−1·4=1  (51)

As previously described, C 21 =1 if D 1i ≧2, otherwise C 2i =0 such that:

C 24 =0  (52)

C 23 =0  (53)

C 22 =0  (54)

C 21 =1  (55)

C 20 =0  (56)

Therefore:

D 2i =D li +C 2i-1 −C 2i·r   (57)

Accordingly:

D 24 =D 14 +( C 23 −C 24 ·4)=1+0−0·4=1  (58)

D 23 =D 13 +( C 22 −C 23 ·4)=1+0−0·4=1  (59)

D 22 =D 12 +( C 2i −C 22 ·4)=0+1−0·4=1  (60)

D 21 =D 11 +( C 20 −C 21 ·4)=3+0−1·4=−1  (61)

D 20 =D 10 +(0 −C 20 ·4)=1+0−0·4=1  (62)

Therefore, arranging this information into Table 2:

The previous example show the multiplication of binary numbers in radix 4, however it is possible to compute numbers in other radixes such as radix 8 and 16, etc. . . . . Additionally, the bias r for D 1i and D 2i depends on the radix chosen. Specifically, in the examples for equations (4) and (7) the bias r is chosen as 4 as the radix of the number system used. However, r would be 8 or 16 for number systems with radixes 8 or 16 respectively. Furthermore, in order to further optimize the system, the value of n t may be varied. By changing the value threshold value of propagation n t at the first stage of propagation, it is possible to optimize the hardware of the system.

The following equations illustrate the general case for computing the output result D 2i . If there is an N-bit digit of a binary CSA number such as N>1, then:

For this N-bit digit the radix r is 2 N . A threshold value n t is declared to be:

Then the output carry signal is:

After reading the input carry from the previous digit C 1i-1 , the value of D 1i is:

D 1i =D i s+C i −C 1i ·r

D 1i ε{n low . . . n high }

Where:

Accordingly, the lower boundary n low cannot exceed the desired range even considering any possible carry. The upper boundary n high is chosen to fit the digit into the desired range after the second carry. The threshold value range n t is actually determined by both boundaries such that:

The output carry at this second stage is declared to be:

After adding the input carry from the previous digit C 2i-1 , the value of the output D 2i becomes:

which is in the sign-digit representation for radix 2 N .

Additional modifications and improvements of the present invention may also be apparent to those of ordinary skill in the art. Thus, the particular combination of parts described and illustrated herein is intended to represent only a certain embodiment of the present invention, and is not intended to serve as a limitation of alternative devices within the spirit and scope of the invention.