which contains both combinational logic and memory

components.

The combinational logic cloud is an acyclic graph

of components that obeys the static discipline.

The static discipline guarantees if we supply valid and stable

digital inputs, then we will get valid and stable

digital outputs by some specified

interval after the last input transition.

There's also a functional specification that tells us

the output values for every possible combination of input

values.

In this diagram, there are k+m inputs and k+n outputs,

so the truth table for the combinational logic will have

2^(k+m) rows and k+n output columns.

The job of the state registers is

to remember the current state of the sequential logic.

The state is encoded as some number k of bits,

which will allow us to represent 2^k unique states.

Recall that the state is used to capture,

in some appropriate way, the relevant history of the input

sequence.

To the extent that previous input values influence

the operation of the sequential logic,

that happens through the stored state bits.

Typically the LOAD input of the state registers

is triggered by the rising edge of a periodic signal, which

updates the stored state with the new state calculated

by the combinational logic.

As designers we have several tasks:

first we must decide what output sequences

need to be generated in response to the expected input

sequences.

A particular input may, in fact, generate a long sequence

of output values.

Or the output may remain unchanged

while the input sequence is processed, step-by-step,

where the FSM is remembering the relevant information

by updating its internal state.

Then we have to develop the functional specification

for the logic so it calculates the correct output

and next state values.

Finally, we need to come up with an actual circuit diagram

for sequential logic system.

All the tasks are pretty interesting,

so let's get started!

As an example sequential system, let's make a combination lock.

The lock has a 1-bit input signal,

where the user enters the combination

as a sequence of bits.

There's one output signal, UNLOCK,

which is 1 if and only if the correct combination has been

entered.

In this example, we want to assert UNLOCK, i.e.,

set UNLOCK to 1, when the last four input values are

the sequence 0-1-1-0.

Mr. Blue is asking a good question:

how many state bits do we need?

Do we have to remember the last four input bits?

In which case, we'd need four state bits.

Or can we remember less information

and still do our job?

Aha!

We don't need the complete history of the last four

inputs, we only need to know if the most recent entries

represent some part of a partially-entered correct

combination.

In other words if the input sequence doesn't represent

a correct combination, we don't need to keep track of exactly

how it's incorrect, we only need to know that is incorrect.

With that observation in mind, let's figure out how

to represent the desired behavior of our digital system.

We can characterize the behavior of a sequential system using

a new abstraction called a finite state machine,

or FSM for short.

The goal of the FSM abstraction is

to describe the input/output behavior

of the sequential logic, independent

of its actual implementation.

A finite state machine has a periodic CLOCK input.

A rising clock edge will trigger the transition

from the current state to the next state.

The FSM has a some fixed number of states,

with a particular state designated

as the initial or starting state when

the FSM is first turned on.

One of the interesting challenges in designing an FSM

is to determine the required number of states since there's

often a tradeoff between the number of state bits

and the complexity of the internal combinational logic

required to compute the next state and outputs.

There are some number of inputs, used

to convey all the external information

necessary for the FSM to do its job.

Again, there are interesting design tradeoffs.

Suppose the FSM required 100 bits of input.

Should we have 100 inputs and deliver the information

all at once?

Or should we have a single input and deliver the information

as a 100-cycle sequence?

In many real world situations where the sequential logic is

*much* faster than whatever physical process we're trying

to control,

we'll often see the use of bit-serial inputs where

the information arrives as a sequence, one bit at a time.

That will allow us to use much less signaling hardware,

at the cost of the time required to transmit

the information sequentially.

The FSM has some number outputs to convey the results

of the sequential logic's computations.

The comment before about serial vs. parallel inputs

applies equally to choosing how information should

be encoded on the outputs.

There are a set of transition rules,

specifying how the next state S-prime is

determined from the current state S and the inputs I.

The specification must be complete,

enumerating S-prime for every possible combination

of S and I.

And, finally, there's the specification for how

the output values should be determined.

The FSM design is often a bit simpler

if the outputs are strictly a function of the current state

S, but, in general, the outputs can

be a function of both S and the current inputs.

Now that we have our abstraction in place,

let's see how to use it to design our combinational lock.