Information Technology Reference
In-Depth Information
π [ 0, j ] is 1 if and only if a carry generated at the zeroth stage, c 0 , is propagated through the
j th stage. Since c 0 = 0, this component is not used. The second component of π [ 0, j ] , c j + 1 ,
is 1 if and only if a carry is generated at or before the j th stage. From ( 2.6 ) we see that the
sum bit generated at the j th stage, s j , satisfies s j = p j
c j . Thus the j th output bit, s j ,is
obtained from the EXCLUSIVE OR of p j and the second component of π [ 0, j
1 ] .
THEOREM 2.7.2 For n = 2 k , k an integer, the addition function f ( n )
add
n + 1 can
be realized with a carry-lookahead adder with the following size and depth bounds over the basis
Ω=
2 n
:
B
→B
{∧
⊕}
,
,
:
C Ω f ( n )
add
8 n
D Ω f ( n )
add
4 log 2 n + 2
Proof The prefix circuit uses 2 n
log 2 n
and has depth 2 log 2 n .Since
3 instances of
each instance of
can be realized by a circuit of size 3 and depth 2, each of these bounds is
multiplied by these factors. Since the first component of π [ 0, j ] is not used, the propagate
value computed at each output combiner vertex can be eliminated. This saves one gate per
result bit, or n gates. However, for each 0
1 we need two gates to compute p j
and q j and one gate to compute s j ,3 n additional gates. The computation of these three
sets of functions adds depth 2 to that of the prefix circuit. This gives the desired bounds.
j
n
The addition function f ( n )
add is computed by the carry-lookahead adder circuit with 1.6
times as many gates as the ripple adder but in logarithmic instead of linear depth.
When exact addition is expected and every number is represented by n bits, a carry-out of
the last stage of an adder constitutes an overflow ,anerror.
2.8 Subtraction
Subtraction is possible when negative numbers are available. There are several ways to repre-
sent negative numbers. To demonstrate that subtraction is not much harder than addition, we
consider the signed two's complement representation for positive and negative integers in the
set ￿ ( n )=
2 n , ... ,
1, 0, 1, 2, ... ,2 n
{−
}
. Each signed number u is represented by
an ( n + 1 ) -tuple ( σ , u ) ,where σ is its sign and u =( u n− 1 , ... , u 0 ) is a binary number that
is either the magnitude
2,
1
of the number u , if positive, or the two's complement 2 n
|
u
|
−|
u
|
of
it, if negative. The sign σ is defined below:
σ = 0thenum r u is positive or zero
1thenum r u is negative
The two's complement of an n -bit binary number v is easily formed by adding 1 to t =
2 n
.Since2 n
1 is represented as the n -tuple of 1's, t is obtained by complementing
( NOT ing) every bit of v . Thus, the two's complement of u is obtained by complementing every
bit of u and then adding 1. It follows that the two's complement of the two's complement of
a number is the number itself. Thus, the magnitude of a negative number ( 1, u ) is the two's
complement of u .
1
−|
v
|
Search WWH ::




Custom Search