Subtitles section Play video

• In the last chapter we developed sequential logic,

• 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.

In the last chapter we developed sequential logic,

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it

6.2.1 Finite State Machines

• 3 0
林宜悉 posted on 2020/03/29
Video vocabulary