Information Technology Reference
In-Depth Information
x
[
1, 2
]
x
[
1, 4
]
x
[
1, 6
]
x
[
1, 8
]
x
[
1, 1
]
x
[
1, 3
]
x
[
1, 5
]
x
[
1, 7
]
P
(
n
)
P
(
n/
2
)
P
(
n/
4
)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
Figure 2.13
A simple recursive construction of a prefix circuit when
n
=
2
k
=
8. The gates
used at each stage of the construction are grouped into individual shaded regions.
2.7 Addition
Addition is a central operation in all general-purpose digital computers. In this section we
describe the standard ripple adder and the fast carry-lookahead addition circuits. The ripple
adder mimics the elementary method of addition taught to beginners but for binary instead of
decimal numbers. Carry-lookahead addition is a fast addition method based on the fast prefix
circuit described in the preceding section.
Consider the binary representation of integers in the set
0, 1, 2,
...
,2
n
{
−
}
1
.Theyare
represented by binary
n
-tuples
u
=(
u
n−
1
,
u
n−
2
,
...
,
u
1
,
u
0
)
and have value
n−
1
u
j
2
j
|
u
|
=
j
=
0
where
denotes integer addition.
The
addition function
f
(
n
)
n
+
1
computes the sum of two binary
n
-bit
numbers
u
and
v
, as shown below, where
+
denotes integer addition:
add
:
B
2
n
→B
n−
1
(
u
j
+
v
j
)
2
j
|
u
|
|
v
|
+
=
j
=
0
The tuple
((
u
n−
1
+
v
n−
1
)
,
(
u
n−
2
+
v
n−
2
)
,
...
,
(
u
0
+
v
0
))
is not a binary number because the
coefficients of the powers of 2 are not Boolean. However, if the integer
u
0
+
v
0
is converted to
Search WWH ::
Custom Search