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