[MUSIC] This lesson deals with the description of sequential circuits. In the case of combinational circuits the straight forward method was to define tables. What about sequential circuits specification? In this case, state transition graphs are used. They consist of a set of vertices, vertices that correspond to the internal states, and of a set of directed edges that define the state transitions. Consider a sequential machine, and assume that it has three internal states that we call Q0, Q1, and Q2. So, they will be encoded with two bits. The inputs are numbers belonging to the set 0, 1, 2, 3, and will be encoded also with 2 bits. The working of the circuit is defined by he following graph, with 3 vertices, one for each state, and a set of directed edges. For example, if the current state is Q2, and if the inputs represent number 2, then the next stage will be Q1, and so on. The change of internal state will occur when there is a clock pulse of the synchronization signal. Now, what about the outputs? In the case of the outputs, there are two possibilities. If we choose the Moore model, then the output values are defined by the current state. In this example, there is only one output bit Y and its value is directly associated with the state. For example, if the current state is Q0, then the value of the output is 1; if the current state is Q2, the current value of the output is also 1, and if the current state is Q1, the output is equal to 0. But if the Mealy model is chosen, then the output values are defined not only by the current state, but also by the input values. So, the value of Y, in the second example, is associated with the edge that defined the state transition, that means that, for example, if the current state is Q2, and if the input value is 1, then the next state will be Q1, and the output will be Y = 1. Now, let us see an example. The objective is to define a circuit, that controls a robot "vacuum cleaner". It's input, there is only one input, it is an OB input signal, equal to 1 if an obstacle (some object) is detected in front of the robot. There is a sensor that detects whether there is an object, or not, in front of the robot. And the inputs control the movement of the robot. It can move forward; it can rotate 90 degrees to the right; and it can rotate 90 degrees to the left. They are three possibilities that will be encoded with two bits. The specification now: in case that an obstacle is detected in front of the robot, the first time, it turns to the right until there is no more obstacle in front of the robot, and after that, it moves forward. The second time that an obstacle is detected, it turns to the left, until there is no more obstacle, and after that it moves forward, and so on. Thus the sequential circuit has one input OB equal to 1 when there is an obstacle, and two outputs: RR equal to 1 when it rotates to the right, and RL equal to 1 when it rotates to the left. If both are equal to 0, that means that the robot moves forward. We can define the circuit with a 4-state sequential machine. Those 4 states correspond to the following situations: SAL: when the robot moves forward and the preceding, rotation was to the left; SAR when the robot moves forward but the preceding (or the latest) rotation was to the right; SRR when it rotates to the right, and SRL when it rotates to the left. So we get this circuit with one input, two outputs, and a memory that stores the four possible states. Now, let us define the transitions between the internal states. There are four internal states: SAR, SRL, SAL, and SRR. Assume that the current state is SAR. That means that it is moving forward and the preceding rotation was to the right. If there is no obstacle, then this state doesn't change. If there is an obstacle, the next state will be SRL, that means that it moves to the left because the preceding movement (or rotation) was to the right. Now it must rotate to the left, and as long as it detects the obstacle, it keeps moving or rotating to the left. If there is no more obstacle, then the new state will be SAL, that means that it moves forward and the preceding movement (or preceding rotation) was to the left, and it remains in this state as long as there is no detected obstacle, and so on. If there is an obstacle, it goes to this state, and if there is no obstacle any more, the next state will be SAR. Thus this is the final result. Now, an exercise: define the state transition graph of a sequential circuit with one binary input X, one binary output Y. It generate an output equal to 1 if the input sequence it has received up to the current time includes an odd number of 1's; for example, if the preceding sequence was 001011, then it must generate 1, but if the next input bit is 1, then it will generate 0 because now there is an even number of 1's within the input sequence. Let us see a solution. We define two states S0 and S1. S0 is the state of the circuit when the equence received up to now (up to the current time) has an even number of 1's. And S1 is the state of the circuit when the sequence received up to now has an odd number of 1's. Then, if the state is S0, that means that the sequence received up to the current time had an even number of 1's, and if the input is 0, the parity of the number of 1's doesn't change. So, the circuit remains in the same state. But, if the new input value is 1, then there was an even number of 1's within the input sequence; with this additional 1, now there is an odd number of 1's within the input sequence, so that the next state is S1. The same, if the current state is S1, and if the next input value is zero, the parity doesn't change, so that the system remains in the same state, but if the input value is 1, then the parity of the number of 1's changes (it changes from odd to even) and the circuit changes its internal state to S0. In this case, it's a Moore machine, obviously, because if the state is S0, then the output is 0 and in the state is S1, the output must be equal to 1. Instead of a graph, "next state" and "output" tables can be used to define the working of a sequential circuit. The "next state" table defines the next state in function of the current state and of the input values. And an output table defines the value of the outputs in function of the current state, in the case of the Moore model, and in function of the current state and of the input values, in the case of the Mealy model. Let us see, an example: this is the graph that defined the control circuit of the robot. The same information can be defined with those two tables. In this table, as you can see, we consider all states, and all combinations of input values. For example, state SAR and input 0, state SAR and input 1, and so on. And in every case, we define which is the next state of the sequential circuit. As it's a Moore model, the output table has as many rows as internal states. The number of rows, in general, is the number of states, multiplied by the number of input value combinations. As regards the preceding quiz, the correct solutions are 2 and 5. Why? They are three states and there is only one input signal X, so there are two input value combinations, so that the number of values is six. And as regards the number of columns, there are three columns, because there is one column that corresponds to the state, the current state, another one to the input X and the third one that corresponds to the next state. And finally, as it is a Mealy machine, the next state table and the output table have the same number of rows and columns. Summary. We have defined exhaustive functional specification of sequential machines. For that the main concept is that of state transition graph. It has been used (or it is used) to define both Moore and Mealy machines, and another way to specify the sequential circuit function is to use next state tables and output tables.
