Information Technology Reference
In-Depth Information
01, 10
00
11
Start
q
0
/
0
q
2
/
0
11
01, 10
01, 10
00
11
00
q
3
/
1
q
1
/
1
01, 10
00
11
Figure 3.10
A finite-state machine that adds two binary numbers. Their two least significant
bits are supplied first followed by those of increasing significance. The output bits represent the
sum of the two numbers.
results of this section can be useful. We illustrate this here for binary addition by exhibiting
small and shallow circuits for the adder FSM of Fig.
3.10
. The circuit simulation for this
FSM produces the carry-lookahead adder circuit of Section
2.7
.Inthissectionweusematrix
multiplication, which is covered in Chapter
6
.
The new method is based on the representation of the function
f
(
T
)
M
Ψ
T
computed in
T
steps by an FSM
M
=(Σ
,
Ψ
,
Q
,
δ
,
λ
,
s
,
F
)
in terms of the set of
state-to-
state mappings
S
=
Σ
T
:
Q
×
→
Q
×
{
h
:
Q
→
Q
}
where
S
contains the mappings
{
Δ
x
:
Q
→
Q
|
x
∈
Σ
}
and
Δ
x
is defined below.
Δ
x
(
q
)=
δ
(
q
,
x
)
(3.1)
That is,
Δ
x
(
q
)
is the state to which state
q
is carried by the input letter
x
.
The FSM shown in Fig.
3.10
adds two binary numbers sequentially by simulating a ripple
adder. (See Section
2.7
.) Its input alphabet is
2
, tha t i s , the s e t of pa i r s of 0 's and 1 's .
B
It s
output alphabet is
. (A sequential circuit for this
machine is designed in Section
3.3
.) It has the state-to-state mappings shown in Fig.
3.11
.
Let
B
and its state set is
Q
=
{
q
0
,
q
1
,
q
2
,
q
3
}
:
S
2
→
S
be the operator defined on the set
S
of state-to-state mappings where for
arbitrary
h
1
,
h
2
∈
S
and state
q
∈
Q
the operator
is defined as follows:
(
h
1
h
2
)(
q
)=
h
2
(
h
1
(
q
))
(3.2)
q
Δ
0,0
(
q
)
q
Δ
0,1
(
q
)
q
Δ
1,0
(
q
)
q
Δ
1,1
(
q
)
q
0
q
0
q
0
q
1
q
0
q
1
q
0
q
2
q
1
q
0
q
1
q
1
q
1
q
1
q
1
q
2
q
2
q
1
q
2
q
2
q
2
q
2
q
2
q
3
q
3
q
1
q
3
q
2
q
3
q
2
q
3
q
3
Figure 3.11
The state-to-state mappings associated with the FSM of Fig.
3.10
.
Search WWH ::
Custom Search