Subtitles section Play video

• We'll describe the operation of the FSM for our combination lock using a state transition

• diagram.

• Initially, the FSM has received no bits of the combination, a state we'll call SX.

• In the state transition diagram, states are represented as circles, each labeled for now

• with a symbolic name chosen to remind us of what history it represents.

• For this FSM, the unlock output U will be a function of the current state, so we'll

• indicate the value of U inside the circle.

• Since in state SX we know nothing about past input bits, the lock should stay locked and

• so U = 0.

• We'll indicate the initial state with a wide border on the circle.

• We'll use the successive states to remember what we've seen so far of the input combination.

• So if the FSM is in state SX and it receives a 0 input, it should transition to state S0

• to remind us that we've seen the first bit of the combination of 0-1-1-0.

• We use arrows to indicate transitions between states and each arrow has a label telling

• us when that transition should occur.

• So this particular arrow is telling us that when the FSM is in state SX and the next input

• is a 0, the FSM should transition to state S0.

• Transitions are triggered by the rising edge of the FSM's clock input.

• Let's add the states for the remainder of the specified combination.

• The rightmost state, S0110, represents the point at which the FSM has detected the specified

• sequence of inputs, so the unlock signal is 1 in this state.

• Looking at the state transition diagram, we see that if the FSM starts in state SX, the

• input sequence 0-1-1-0 will leave the FSM in state S0110.

• So far, so good.

• What should the FSM do if an input bit is not the next bit in the combination?

• For example, if the FSM is in state SX and the input bit is a 1, it still has not received

• any correct combination bits, so the next state is SX again.

• Here are the appropriate non-combination transitions for the other states.

• Note that an incorrect combination entry doesn't necessarily take the FSM to state SX.

• For example, if the FSM is in state S0110, the last four input bits have been 0-1-1-0.

• If the next input is a 1, then the last four inputs bits are now 1-1-0-1, which won't lead

• to an open lock.

• But the last two bits might be the first two bits of a valid combination sequence and so

• the FSM transitions to S01, indicating that a sequence of 0-1 has been entered over the

• last two bits.

• We've been working with an FSM where the outputs are function of the current state, called

• a Moore machine.

• Here the outputs are written inside the state circle.

• If the outputs are a function of both the current state and the current inputs, it's

• called a Mealy machine.

• Since the transitions are also a function of the current state and current inputs, we'll

• label each transition with appropriate output values using a slash to separate input values

• from output values.

• So, looking at the state transition diagram on the right, suppose the FSM is in state

• S3.

• If the input is a 0, look for the arrow leaving S3 labeled "0/".

• The value after the slash tells us the output value, in this case 1.

• If the input had been a 1, the output value would be 0.

• There are some simple rules we can use to check that a state transition diagram is well

• formed.

• The transitions from a particular state must be mutually exclusive, i.e., for a each state,

• there can't be more than one transition with the same input label.

• This makes sense: if the FSM is to operate consistently there can't be any ambiguity

• about the next state for a given current state and input.

• By "consistently" we mean that the FSM should make the same transitions if it's restarted

• at the same starting state and given the same input sequences.

• Moreover, the transitions leaving each state should be collectively exhaustive, i.e., there

• should a transition specified for each possible input value.

• If we wish the FSM to stay in it's current state for that particular input value, we

• need to show a transition from the current state back to itself.

• With these rules there will be exactly one transition selected for every combination

• of current state and input value.

• All the information in a state transition diagram can be represented in tabular form

• as a truth table.

• The rows of the truth table list all the possible combinations of current state and inputs.

• And the output columns of the truth table tell us the next state and output value associated

• with each row.

• If we substitute binary values for the symbolic state names, we end up with a truth table

• just like the ones we saw in Chapter 4.

• If we have K states in our state transition diagram we'll need log_2(K) state bits, rounded

• up to the next integer since we don't have fractional bits!

• In our example, we have a 5-state FSM, so we'll need 3 state bits.

• We can assign the state encodings in any convenient way, e.g., 000 for the first state, 001 for

• the second state, and so on.

• But the choice of state encodings can have a big effect on the logic needed to implement

• the truth table.

• It's actually fun to figure out the state encoding that produces the simplest possible

• logic.

• With a truth table in hand, we can use the techniques from Chapter 4 to design logic

• circuits that implement the combinational logic for the FSM.

• Of course, we can take the easy way out and simply use a read-only memory to do the job!

• In this circuit, a read-only memory is used to compute the next state and outputs from

• the current state and inputs.

• We're encoding the 5 states of the FSM using a 3-bit binary value, so we have a 3-bit state

• register.

• The rectangle with the edge-triggered input is schematic shorthand for a multi-bit register.

• If a wire in the diagram represents a multi-bit signal, we use a little slash across the wire

• with a number to indicate how many bits are in the signal.

• In this example, both current_state and next_state are 3-bit signals.

• The read-only memory has a total of 4 input signals - 3 for the current state and 1 for

• the input value - so the read-only memory has 2^4 or 16 locations,

• which correspond to the 16 rows in the truth table.

• Each location in the ROM supplies the output values for a particular row of the truth table.

• Since we have 4 output signals - 3 for the next state and 1 for the output value - each

• location supplies 4 bits of information.

• Memories are often annotated with their number of locations and the number of bits in each

• location.

• So our memory is a 16-by-4 ROM: 16 locations of 4-bits each.

• Of course, in order for the state registers to work correctly, we need to ensure that

• the dynamic discipline is obeyed.

• We can use the timing analysis techniques described at the end of Chapter 5 to check

• that this is so.

• For now, we'll assume that the timing of transitions on the inputs are properly synchronized with

• the rising edges of the clock.

• So now we have the FSM abstraction to use when designing the functionality of a sequential

• logic system, and a general-purpose circuit implementation of the FSM using a ROM and

• a multi-bit state register.

• Recapping our design choices: the output bits can be strictly a function of the current

• state (the FSM would then be called a Moore machine),

• or they can be a function of both the current state and current inputs, in which case the

• FSM is called a Mealy machine.

• We can choose the number of state bits - S state bits will give us the ability to encode

• 2^S possible states.

• Note that each extra state bit DOUBLES the number of locations in the ROM!

• So when using ROMs to implement the necessary logic, we're very interested in minimizing

• the number of state bits.

• The waveforms for our circuitry are pretty straightforward.

• The rising edge of the clock triggers a transition in the state register outputs.

• The ROM then does its thing, calculating the next state, which becomes valid at some point

• in the clock cycle.

• This is the value that gets loaded into the state registers at the next rising clock edge.

• This process repeats over-and-over as the FSM follows the state transitions dictated

• by the state transition diagram.

• There are a few housekeeping details that need our attention.

• On start-up we need some way to set the initial contents of the state register to the correct

• encoding for the initial state.

• Many designs use a RESET signal that's set to 1 to force some initial state and then

• set to 0 to start execution.

• We could adopt that approach here, using the RESET signal to select an initial value to

• be loaded into the state register.

• In our example, we used a 3-bit state encoding which would allow us to implement an FSM with

• up to 2^3 = 8 states.

• We're only using 5 of these encodings, which means there are locations in the ROM we'll

• never access.

• If that's a concern, we can always use logic gates to implement the necessary combinational

• logic instead of ROMs.

• Suppose the state register somehow got loaded with one of the unused encodings?

• Well, that would be like being in a state that's not listed in our state transition

• diagram.

• One way to defend against this problem is design the ROM contents so that unused states

• always point to the initial state.

• In theory the problem should never arise, but with this fix at least it won't lead to

• unknown behavior.

• We mentioned earlier the interesting problem of finding a state encoding that minimized

• the combinational logic.

• There are computer-aided design tools to help do this as part of the larger problem of finding

• minimal logic implementations for Boolean functions.

• Mr. Blue is showing us another approach to building the state register for the combination

• lock: use a shift register to capture the last four

• input bits, then simply look at the recorded history to determine if it matches the combination.

• No fancy next0state logic here!

• Finally, we still have to address the problem of ensuring that input transitions don't violate

• the dynamic discipline for the state register.

• We'll get to this in the last section of this chapter.

We'll describe the operation of the FSM for our combination lock using a state transition

Subtitles and vocabulary

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

6.2.2 State Transition Diagrams

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