Information Technology Reference
In-Depth Information
3.2.1 A Shallow Circuit Simulating Addition
Applying the above result to the adder FSM of Fig.
3.10
, we produce a circuit that accepts
T
pairs of binary inputs and computes the sum as
T
-bit binary numbers. Since this FSM
has four states, the theorem states that the circuit has size
O
(
T
)
and depth
O
(log
T
)
.The
carry-lookahead adder of Section
2.7
has these characteristics.
We can actually produce the carry-lookahead circuit by a more careful design of the state-
to-state mappings. We use the following encodings for states, where states are represented by
pairs
{
(
c
,
s
)
}
.
State Encoding
q cs
q
0
00
q
1
01
q
2
10
q
3
11
Since the next-state mappings are the same for inputs 0, 1, and 1, 0, we encode an input
pair
(
u
,
v
)
by
(
g
,
p
)
,where
g
=
u
v
are the carry-generate and carry-
propagate variables introduced in Section
2.7
and used above. With these encodings, the three
different next-state mappings
∧
v
and
p
=
u
⊕
{
Δ
0,0
,
Δ
0,1
,
Δ
1,1
}
defined in Fig.
3.11
can be encoded as shown
in the table below. The entry at the intersection of row
(
c
,
s
)
and column
(
p
,
g
)
in this table
is the value
(
c
∗
,
s
∗
)
of the generic next-state function
(
c
∗
,
s
∗
)=Δ
p
,
g
(
c
,
s
)
. (Here we abuse
notation slightly to let
Δ
p
,
g
denote the state-to-state mapping associated with the pair
(
u
,
v
)
and represent the state
q
of
M
by the pair
(
c
,
s
)
.)
g
0 0 1
p
0 1 0
cs c
∗
s
∗
c
∗
s
∗
c
∗
s
∗
00 000110
01 000110
10 011011
11 011011
Inspection of this table shows that we can write the following formulas for
c
∗
and
s
∗
:
c
∗
=(
p
s
∗
=
p
∧
c
)
∨
g
,
⊕
c
Consider two successive input pairs
(
u
1
,
v
1
)
and
(
u
2
,
v
2
)
and associated pairs
(
p
1
,
g
1
)
and
(
p
2
,
g
2
)
.IftheFSMofFig.
3.10
is in state
(
c
0
,
s
0
)
and receives input
(
u
1
,
v
1
)
,itentersthe
state
(
c
1
,
s
1
)=(
p
1
c
0
)
. This new state can be obtained by combining
p
1
and
g
1
with
c
0
.Let
(
c
2
,
s
2
)
be the successor state when the mapping
Δ
p
2
,
g
2
is applied to
(
c
1
,
s
1
)
.
Theeffectoftheoperator
∧
c
0
∨
g
1
,
p
1
⊕
on successive state-to-state mappings
Δ
p
1
,
g
1
and
Δ
p
2
,
g
2
is shown
below, in which (
3.2
)isused:
(Δ
p
1
,
g
1
Δ
p
2
,
g
2
)(
q
)=Δ
p
2
,
g
2
(Δ
p
1
,
g
1
((
c
0
,
s
0
)))
=Δ
p
2
,
g
2
(
p
1
∧
c
0
∨
g
1
,
p
1
⊕
c
0
)
Search WWH ::
Custom Search