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