Information Technology Reference
In-Depth Information
ARITHMETIC OPERATIONS
2.25 Design a circuit that finds the most significant non-zero position in an
n
-bit binary
number and logically shifts the binary number left so that the non-zero bit is in the most
significant position. The circuit should produce not only the shifted binary number but
also a binary representation of the amount of the shift.
2.26 Consider the function
π
[
j
,
k
]=
π
[
j
,
k
is defined in Section
2.7.1
. Show by induction that the first component of
π
[
j
,
k
]
is 1
if and only if a carry propagates through the full adder stages numbered
j
,
j
+
1,
...
,
k
and its second component is 1 if and only if a carry is generated at one of these stages,
propagates through subsequent stages, and appears as a carry out of the
k
th stage.
−
1
]
π
[
k
,
k
]
for 1
≤
j<k
≤
n
−
1, where
2.27 Give a construction of a circuit for subtracting one
n
-bit positive binary integer from
another using the two's-complement operation. Show that the circuit has size
O
(
n
)
and depth
O
(log
n
)
.
2.28 Complete the proof of Theorem
2.9.3
outlined in the text.
In particular, solve the
recurrence given in equation (
2.10
).
2.29 Show that the depth bound stated in Theorem
2.9.3
can be improved from
O
(log
2
n
)
to
O
(log
n
)
without affecting the size bound by using carry-save addition to form the
six additions (or subtractions) that are involved at each stage.
Hint:
Observe that each multiplication of
(
n/
2
)
-bit numbers at the top level is ex-
panded at the next level as sums of the product of
(
n/
4
)
-bit numbers and that this type
of replacement continues until the product is formed of 1-bit numbers. Observe also
that 2
n
-bit carry-save adders can be used at the top level but that the smaller carry-save
adders can be used at successively lower levels.
2.30 Residue arithmetic can be used to add and subtract integers. Given positive relatively
prime integers
p
1
,
p
2
,
...
,
p
k
(no common factors), an integer
n
in the set
{
0, 1, 2,
...
,
N
p
k
, can be represented by the
k
-tuple
n
=(
n
1
,
n
2
,
...
,
n
k
)
,
where
n
j
=
n
mod
p
j
.Let
n
and
m
be in this set.
a)
−
1
}
,
N
=
p
1
p
2
···
=
m
.
b) Form
n
+
m
by adding corresponding
j
th components modulo
p
j
. Show that
n
+
m
uniquely represents
(
n
+
m
)mod
N
.
c) Form
n
Show that if
n
=
m
,
n
m
by multiplying corresponding
j
th components of
n
and
m
modulo
p
j
. Show that
n
×
m
istheuniquerepresentationfor
(
nm
)mod
N
.
2.31 Use the circuit designed in Problem
2.19
to build a circuit that adds two
n
-bit binary
numbers modulo an arbitrary third
n
-bit binary number. You may use known circuits.
2.32 In
prime factorization
an integer
n
is represented as the product of primes. Let
p
(
N
)
be the largest prime less than
N
.Then,
n
×
is represented by the
exponents (
e
2
,
e
3
,
...
,
e
p
(
N
)
), where
n
=
2
e
2
3
e
3
...p
(
N
)
e
p
(
N
)
. The representation
for the product of two integers in this system is the sum of the exponents of their
respective prime factors. Show that this leads to a multiplication circuit whose depth
is proportional to
log log log
N
. Determine the size of the circuit using the fact that
there are
O
(
N/
log
N
)
primes in the set
∈{
2,
...
,
N
−
1
}
{
2,
...
,
N
−
1
}
.
Search WWH ::
Custom Search