UNIVERSAL BUILDING BLOCKS
• IN’UT�.�——�
FIGURE 14
�
-/;WR)�
Finite-state machine, with logic block feeding register
controller at an intersection where the light turns red in both
directions after the Walk button is pressed. Each drawing of
light represents a state and each arrow represents a transition
between states. The transition depends on whether or not the
“walk” button is pressed.
To store the state of the finite-state machine, we need to
introduce one last building block-a device called a register,
which can be used to store bits. An n-bit register has n inputs
and n outputs, plus an additional timing input that tells th e
register when to change state. Storing new information is
called “writing” the state of the register. When the timing
signal tells the register to write a new state, the register
changes its state to match the inputs . The outputs of the reg
ister always indicate its current state. Registers can be imple
mented in many ways, one of which is to use a Boolean logic
block to steer the state information around in a circle. This
type of register is often used in electronic computers, which
is why they lose track of what they’re doing if their power is
interrupted.
A finite-state machine consists of a Boolean logic block
connected to a register, as shown in Figure 14. The finite-
D d. __ fior a traffic-
light controller state machine advances its state by writing the output of the State 1agr …..
JJ
34 THE PA TTERN ON
THE STONE
Boolean logic blo ck into the regis
ter; the logic blo ck then
computes the next state, based on the
input and the cur rent
state. This next sta te is then written
into the register on the
next cycle. The pro cess repeats in eve
ry cycle.
The function of a finite-state machi
ne can be specified by
a table that sho ws, for every state
and every input, the state
that follows. For e xample, we can s
ummarize the ope ration
of the traffic-light controller by the
following table:
Outputs:
Inputs:
Walk Cu rrent Main
Cross Next
Button St ate Road
Road State
Not Pressed A Red Green
B
Not Pressed B Red Yello
w D
Not Pressed c Yellow Red
A
Not Pressed D Green Red
c
Not Pressed W alk Walk
Walk D
Pressed A Red Green
B
Pressed B Red Yellow
Walk
Pressed c Yellow Red
Walk
Pressed D Green Red
c
Pressed W alk Walk
Walk Walk
The first step in im plementing a finit
e-state machine is to
generate such a t able. The second s
tep is to assign a di fferent
pattern of bits to e ach state. The five
states of the traffi c-light
controller will req uire three bits. (Si
nce each bit doubl es the
number of possibl e patterns, it is p
ossible to store up to 2″
states using n bits.) By consistently re
placing each word i n the
preceding table wit h a binary pattern, w
e can convert the table
to a function that can be implemented
with Boolean logic.
In the traffic-light system, a timer co
ntrols the writing of
the register, which ca uses the state to ch
ange at regular inte r·
vals. Another exampl e of a finite-state
machine that advanc es
its state at regular intervals is a digital
clock. A digital clo ck
with a seconds indica tor can be in one of 2
4 x 60 x 60 = 86,400
UNIVERSAL BUILDING BLOCKS 35
possible display states-one for each second of the day. The
timing mechanism within the clock causes it to advance
its state exactly once per second. Many other types of digital
computing devices, including most general-purpose comput
ers, also advance their state at regular intervals, and the rate at
which they advance is called the clock rate of the machine.
Within a computer, time is not a continuous flow but a fixed
sequence of transitions between states. The clock rate of the
computer determines the rate of these transitions, hence the
correspondence between physical and computational time.
For instance, the laptop computer on which I am writing this
book has a clock rate of 33 megahertz, which means that it
advances its state at a rate of 33 million times per second. The
computer would be faster if the clock rate were higher, but its
speed is limited by the time required for information to propa
gate through the logic blocks to compute the next state. As
technology improves, the logic tends to become faster and the
clock rate increases. As I write these words, my computer is
state-of-the-art, but by the time you read this book computers
with 33 megahertz clock rates will probably be considered
slow. This is one of the wonders of silicon technology: as we
learn to make computers smaller and smaller, the logic
becomes faster and faster.
One reason finite-state machines are so useful is that they
can recognize sequences. Consider a combination lock that
opens only when it is given the sequence 0 -5-2. Such a
lock, whether it is mechanical or electronic, is a finite-state
machine with the state diagram shown in Figure 15.
A similar machine can be constructed to recognize any
finite sequence. Finite-state machines can also be made to rec
ognize sequences that match certain patterns. Figure 16 shows
one that recognizes any sequence starting with a 1, followed by
a sequence of any number of Os, followed by a 3. Such a com
bination will unlock the door with the combination 1-0-3, or
a combination such as 1-o–0-0-3, but not with the combina
tion 1-0-2-3, which doesn’t fit the pattern. A more complex
36 THE PATT ERN ON THE
STONE
8 FIGURE 15
