Synthesis of Arithmetic Circuits

2's Complement Expression Algorithm

The 2's complement expression of the result will be given by the following algorithm.

Algorithm 5.14.b 2Booth_decodez z)( stands for the Boolean complement ofi 0,1,..k-2for in loopc _in=0if ithen00 +iz =z ; c _in=zi+1 i.r+r-1ielse00 _+i rz =(z -c _in) mod 2 ; c _in=z (z̄ .z̄ .i i i+1 i.r+r-1 i.r+r-2 i.r+r-3...z̄ ); end if;i.rend loop;_in=0cif k-1then00 +k-1z =z ; z =zk.r k.r-1k-1else00 _+k-1 rz =(z -c _in) mod 2 ; z =z (z̄ .z̄ .k-1 k.r kr-1 k.r-2 k.r-3k-1 );...z̄ end if;(k-1).r102 ARITHMETIC OPERATIONS: MULTIPLICATIONThe above algorithm actually sets all signed digits to a positive value carrying anegative correction bit to the following digit (on the left) whenever necessary.zThe last correction bit is the sign bit.k.rLetExample 5.7n ¼ r ¼ k ¼ Z ¼ 4 4 ¼15; 3; 5; 1 2 3 001, 100, 100, 010, 011The result is built up in 2’s complement representation,00¼ ¼) z ¼ c _in ¼ z ¼Step 1: c _in 0 011; 0.00 1

Step 2: c = ¼, z = c _in = z _in = 0 010; 0.11 2 500

Step 3: c = ¼, z = c = z _in = 0 100; _in = 1.22 3 800

Step 4: c = ¼, z = ¼, c = z __in = 1 (100 – 001) mod 8 011; _in = (z̄ .z̄ )433 11 10 9= 1. 00

Step 5: c _in = ¼, z = ¼, z = z _1 = (001 – 001) mod 8 000; (z̄ .z̄ )44 15 14 13 12= 0;00 00 00 00 00 00

Z = z z z z z = 0 0000111000100114 3 2 1 0

5.2.4 Booth Multiplication for Base-B Numbers

B)(Booth-r Algorithm in Base B .The above algorithms may be extended to base 2, within the followingconditions. [ . . . B + xB x {0,1, , 1}is valuedis assumed even, and the sign-digit n1 n1x , B=2 x B,whenever and otherwise. The sign function sign(x) isn1 n1defined as = b2: x=Bc:sign(x) (5:16)This means that = x B=2sign(x) 1 if (X negative)and = x , B=2sign(x) 0 if (X positive):x . . . x xX =

x , , , , is thus given by the expression

A base-B signed number n₂1 n₂2 1 0n₁ n₂X ¼ B:sign(x þ x :B þ þ x :B þ x :B þ x²(x )):B (5:17)n₁ n₁ n₂ 2 1 0n-digit n/r r-digit

Then, given an base-B integer shredded into slices, the general-ized Booth coding can be performed according to

0 r₁ r₂¼ B:sign(x þ x :B þ þ x :Bx 2(x )):Bi:rþr₁ i:rþr₁ i:rþr₂ i:rþ2i (5:18)þ x :B þ x þ sign(x )i:rþ1 i:r i:r₁ 1035.2 INTEGERS B’s r-digit

This means that each slice is viewed as a complement number. So when- B/2, þx a correction sign(x ) has to be made at the next leftever i.rþr₂1 i.rþr₂1xdigit .i.rþr Let

Example 5.8 n ¼ r ¼ B ¼24; 4; 10X ¼ 0000 9124 6458 2123 5252 5632 2145

Booth-4 coding 0 0 0 0 0 0 0X ¼ ¼ x x x x x x x0001 9125 6458 2124 5253 5632 2145 , , , , , ,6 5 4 3 2 1 01 has to be added at the end of every slice

whose next digit (on the right) is greater than 4.

The decimal values of Booth digits are given by:

0x ¼ 160x ¼ 1000 þ ¼ 87512550 ¼ 4000 þ ¼ 3542x 45840x ¼ 212430 ¼ 5000 þ ¼ 4747x 25320x ¼ 5000 þ ¼ 436863210 ¼x 21450C ¼ 4

Assuming 10 þ þX ¼ 6 5 4 3 2875:C 3542:C 2124:C 4747:C 4368:C 21451:C¼ 9124 6458 2123 5252 5632 2145B

Algorithm 5.15 Booth-r in Base

The Booth-r multiplication, Algorithm 5.11, can be modified as follows.

P(0):=0;i 0..k-1for in loopX((i*r)-1) B/2 sum(-1):=Y; sum(-1):=0;if then else end if;j 0..r-2for in loopsum(j):=sum(j-1)+X((i*r)+j)*Y*(B**j);end loop; X((i*r)+r-1) B/2 sum(r-1):=sum(r-2)+(X((i*r)+r-1)if then-B)*Y*(B**(r-1));sum(r-1):=sum(r-2)+X((i*r)+r-1)*Y*(B**(r-1));else P(i+1):=(P(i)+sum(r-1))/(B**r);end if;end loop;Z:=P(n)*(B**n);

104 ARITHMETIC OPERATIONS: MULTIPLICATION

The complexity of the partial products computation is an

Important drawback for the above algorithm. Moreover, increasing the base or increasing the side of the slices in Booth coding are approaches conceptually similar. Both techniques reduce the number of computational steps, but the rise of the step complexity is the price to be paid. The Booth algorithm in base-B could be more suitable for some Per Gelosia inspired applications with suitable hardware resources such as look-up table (LUT) B to implement the partial products within acceptable times. Obviously, increasing r and/or would quickly make the LUT size unmanageable.

5.3 SQUARING

5.3.1 Base-B Squaring

Although any multiplication system could readily be used for squaring, specialized systems can provide both time and cost savings. Actually, normal multiplication n^2 requires partial products while the maximum depth of the adding tree reaches n(n-1)/2 (maximum column depth in Figure 5.1a). Squaring only needs 1/2 partial products, plus digit-squares. Moreover, the adding process is simplified by

The fact that each nonsquare partial product digit appears twice. As far as partial products are multiplied by two beforehand, the maximum depth of the adding tree is reduced to dn=2e. B. The complexity of squaring in base 2 comes from the fact that digit double products could need up to three digits while squaring only needs two. So the saving in column depth is consumed by second-order carries. For the particular B ¼ case 2, the digit squaring is trivial as double products are performed through straight shifts. Moreover, Boolean simplification provides further reductions in the depth of the adding tree.

5.3.1.1 Cellular Carry – Save Squaring Algorithm Algorithm 5.16 is a modification of the cellular carry-save Algorithm 5.5. It computes (i, j)-cell i ¼ j, difference rests upon the loops, adding squares whenever and adding double products otherwise, to the successive carries and partial sums. What is saved in computing the double products is

somewhat consumed by the carries, tobe handled by additional adding procedures. Actually, to cope with the basicscheme suggested by Algorithm 5.5, the only modification (besides that of the partialj)-cellproducts) rests on the substitution of some (i, procedures by half-adder ones.

Algorithm 5.16 Carry-Save Squaring/(Symbol stands for integer division)

j 0..n-1 
p(0, j):=D(j); 
carry1(0, j):=C(j);
for in loop
carry2(0, j):=0;
end loop;
p(1, n):=0;
sum(0, 0):=(carry1(0, 0)+p(0, 0)+X(0)**2) mod B;
carry1(1, 0):=((carry1(0, 0)+p(0, 0)+X(0)**2)/B) mod B;
carry2(1, 1):=(carry1(0, 0)+p(0, 0)+X(0)**2)/B**2;
j 1..n-1
for in loop 1055.3 SQUARING
sum(0, j):=(carry1(0, j)+carry2(0, j)+p(0, j)+2*X(0)*X(j))mod B;
carry1(1,j):=((carry1(0,j)+carry2(0,j)+p(0,j)+2*X(0)*X(j))/B) mod B;
carry2(1,j+1):=(carry1(0,j)+carry2(0,j)+p(0,j)+2*X(0)*X(j))/B**2;
end loop;
j 0..n-1 p(1,j):=sum(0,j);
endfor in loop loop;
p(2, n+1):=carry2(1, n);
i 1..n-2
for in loop
j 0..i-1
for in loop
sum(i, j):=(carry1(i,j)+p(i, i+j)) mod B;
carry1(i+1,j):=(carry1(i,j)+p(i, i+j)) mod B;
end loop;

i+j))/B;end loop;
sum(i,i):=(carry1(i,i)+carry2(i,i)+p(i,i+i)+X(i)**2) mod B;
carry1(i+1,i):=((carry1(i,i)+carry2(i,i)+p(i,i+i)+X(i)**2)/B) mod B;
carry2(i+1,i+1):=(carry1(i,i)+carry2(i,i)+p(i, i+i)+X(i)**2)/B**2;
j i+1..n-1for in loop
sum(i,j):=(carry1(i,j)+carry2(i,j)+p(i,i+j)+2*X(i)*X(j))mod B;
carry1(i+1, j):=((carry1(i, j)+carry2(i, j)+p(i,i+j)+2*X(i)*X(j))/B) mod B;
carry2(i+1, j+1):=(carry1(i, j)+carry2(i, j)+p(i, i+j)+2*X(i)*X(j))/B**2;
end loop;
j 0..i-1 p(i+1, j):=p(i, j);for in loop end loop;
j 0..n-1 p(i+1, j+i):=sum(i, j);for in loop end loop;
p(i+2, n+i+1):=carry2(i+1, n);end loop;
j 0..n-2for in loop
sum(n-1, j):=(carry1(n-1, j)+p(n-1, n-1+j))mod B;
carry1(n, j):=(carry1(n-1, j)+p(n-1, n-1+j))/B;
end loop;
sum(n-1, n-1):=(carry1(n-1, n-1)+carry2(n-1, n-1)+p(n-1,2*n-2)+X(n-1)**2) mod B;
carry1(n, n-1):=((carry1(n-1, n-1)+carry2(n-1, n-1)+p(n-1,2*n-2)+X(n-1)**2)/B) mod B;
carry2(n, n):=(carry1(n-1, n-1)+carry2(n-1, n-1)+p(n-1,2*n-2)+X(n-1)**2)/B**2;
j 0..n-2 p(n, j):=p(n-1, j);for in loop

end loop;
j 0..n-1
    p(n, n-1+j):=sum(n-1, j);
    for in loop
    end loop;
    p(n, 2*n):= carry2(n, n);
    j 0..n-1
        Z(j):=p(n, j);
        for in loop
        end loop;
    k(0):=0;
    j 0..n-1
        for in loop
            Z(j+n):=(p(n, n+j)+carry1(n, j)+k(j)) mod B;
            k(j+1):=(p(n, n+j)+carry1(n, j)+k(j))/B;
        end loop;
106 ARITHMETIC OPERATIONS: MULTIPLICATION
It is straightforward to figure out the relative computational complexity of a special-ized squaring procedure, with respect to classic multiplication. Let us point out that
n(n þthe 1)/2 base-B partial products (either double products or squares) will gen-þ
erate less than 3n(n 1)/2 base-B digits to be added according to some selected
2 . Asymp-algorithm. Using the common multiplication algorithm, this quantity is 2n
totically, a 25% saving can be expected, through the best use of the adding tree
reduction (multioperand addition; Chapter 11). Although some extra benefit could
be taken from the fact that the upper carry digit belongs to {0; 1}, the potential
time/cost saving doesn’t

look attractive for general-purpose computers. Some com-binational implementations are presented in Chapter 12. As a matter of fact, squar-ing is not statistically frequent in most applications where suitable multiplication resources are generally available. So the interest of designing special devices for base-B squaring remains limited. On the contrary, significant advantages can be taken from specific features of base-2 representation, as shown in the following section.

5.3.2 Base-2 Squaring

The following three Boolean relations are key properties allowing important simpli-fications to the squaring computation scheme.

x ^ x ¼ x x [1: , {0, 1} (5:19)

0 0 0 0 the square of a binary digit is itself (c