[MUSIC] The preceding lesson dealt with finite state machines. In this lesson, we are going to see two examples of circuit designs based on finite state machine models. The first example is a programmable timer with 3 inputs: START, binary input; REFERENCE, reference is a square wave signal with a known period that we will call Treference, [BLANK_AUDIO] and the third input is an n-bit integer TIME. It has one output DONE and it works as follows: on a positive edge of the START signal the value TIME is read and stored within the circuit and at the same time the DONE output goes down and remains at low level for about N times the period of the reference signal. Here is a formal specification of the circuit working: it is an infinite loop. Initially DONE is set equal to 1. Then, the circuit waits for a positive edge of the START input. When there is a positive edge, DONE is reset equal to 0; the TIME value is stored within a COUNT variable; [BLANK_AUDIO] and then the system enters an internal loop, waiting for for a positive edge, in this case of the REFERENCE signal. When detected, the value of COUNT is updated: it is decremented, and if COUNT (after updating) is equal to 0 then the circuit exits (or it gets out of) the internal loop. It gets out of the external loop (the main loop) also, and then it goes back to this instruction, that is to say, setting DONE = 1. And this is a possible implementation: an n-bit register stores the value of TIME; an arithmetic circuit computes COUNT - 1, and this multiplexer allows to load the register with either the external value TIME or with COUNT - 1. Here a NOR circuit detects when COUNT = 0. Then it remains to control the sequence of operations, that means to control the multiplexer state and to control the EN input of the register, and this control is done in function of the values of the START input signal and of the ZERO signal generated by this NOR function. The control will also generate the DONE output. This control circuit can be easily modeled by a finite state machine. First the finite state machine waits for a positive edge of START, so that if START is still equal to 1, it waits for START being equal to 0; and when equal to 0 it waits for START being equal to 1. When in state 2, the value of TIME must be read and stored in the register. Then state 3 is a branch: if COUNT is already equal to 0 (in other word, if variable ZERO = 1), then it goes back to the initial states waiting for another START pulse; but if COUNT is not equal to 0, that is to say, if the variable ZERO = 0, then it goes to state 4. In state 4, it waits for REFERENCE = 0; in state 5, it wait for REFERENCE = 1, so that a positive edge of REFERENCE has been detected, and in state 6 it will update the contents of the register with COUNT - 1. Then it goes back to the state 3, the branch, and in function of the value of COUNT it goes back to the initial state or to state 4 waiting for another pulse on the REFERENCE signal. As regards the output function, in states 0 and 1 no operation is performed and DONE = 1. In state 2 [BLANK_AUDIO] then the value of TIME must be stored within the circuit so that variable operation_1 = 1 and the control signal (or variable) operation_0 = 1 (1 1), and DONE = 0. Then in states 3, 4 and 5, there is no operation and DONE is still equal to 0. Finally, in state 6, that corresponds to the updating of the COUNT value, then, the multiplexer control signal is equal to 0 and EN (the enable control signal of the register) is equal to 1. So 0 1 and DONE is still equal to 0. Finally, we get the following next_state process, VHDL next_state process. It is a straightforward translation from the transition graph. So, we assume that state 0 is the initial state. Then if RESET = 1, then the current state will be equal to 0. After that, every time there is a positive edge of the CLK signal, the "case" instruction is executed, and if the current state is equal to 0 and if START = 0 (this case), then the current state will be equal to 1 (the next current state will be equal to 1). If START = 1, it remains equal to 0; so it's not necessary to explicitly saying or writing that the next state is 0. And the same for all other current states. For example, state 3 is a branch, so that when the current state is equal to 3, if condition ZERO is TRUE, then the next value of the current state is 0, but if the condition ZERO is NOT TRUE then the next value of the current state is 4. The output_state process is the description of the table. For example, in the case the current state is 0 or 1, then the operations are 0 0 and the DONE output is equal to 1, and so on. Some comments: control circuits like the circuit that we have implemented, in this case, a circuit that controls a sequence of operations of a computation circuit, are an important application of finite state machines. Second comment: this programmable timer circuit is made up of a computation circuit (I mean the register and the arithmetic circuit that computes COUNT - 1). This part of the circuit is called the data path; and it's made up, also, of a finite state machine that controls the sequence of operations. This is a very common architecture of circuits that implement algorithms, and that sometimes are called Algorithmic State Machines. Third comment: a direct description of the complete programmable timer circuit, without an explicit partition into computations and control, could also be considered. And this is a description by means of a VHDL process of the complete circuit, not only the control unit. It is similar to a finite state machine, but it includes register operations such as in state 2: COUNT (an internal register) equal to TIME (an external value), or when in state 6 COUNT <= COUNT - 1. So, this VHDL process includes both the operations and the control of the sequence of operations, and this is the type of description that synthesis tools are able to translate to actual digital circuits using library components. Now, let us see a second example. Consider a mobile object that could be a part of a machine tool, with two optical sensors; and this object moves in front of a fixed ruler with black (or grey) and white areas. Then, whatever the optical system, we assume that in front of a grey area, a 1 is generated, and in front of a white area, a 0 is generated. Then, if the object moves to the right, starting from this position, the 2-bit values are 00, 01, 11, 10 nd back to 00; and if it moves to the left the sequence is 00, 10, 11, 01 and back to 00. The specification of the system to be implemented is that when the object moves to the right, then the output Z must be equal to 0 and it correspondents to the sequence of input signals 00, 01, 11, 10, 00, 01, 11, 10, and so on. When the, the object moves to the left, then the output must be equal to 1, and the input sequence is 00, 10, 11, 01, 00, 10, and so on. And you can check that to distinguish between these two sequences of 2-bit values the following Mealy machine can be used. For example, assume that the object moves to the right, and that the initial state is A. While the input bits are 00, the value of the output will be 0 and the next state will be A. Then when the input values are 01, from A it goes to state B. [BLANK_AUDIO] but with the same output 0. When in state B, while the inputs are still equal to 01 it remains in state B with output 0. But then if the inputs are equal to 11 (from B, to 11) we go to state C with output 0; in state C with inputs equal to 11 the circuit remains in state C with output 0. Finally, when in state C with the next input value 10 (C and 10), the next state is D, the output is still equal to 0, and D with inputs 10, we go to state D, still with the output equal to 0; then after 10 the next value of the input will be 00, and you can see that D and 00 corresponds to a transition to state A (excuse me: 00) with output equal to 0. And you can check that in the case of the other sequence, the sequence of states is this one: D 11/1, then 01/1 C, then state B, state A and back to state D. Thus this Mealy machine generates the output Z that detects if the object is moving to the right or to the left. The next_state VHDL process that corresponds to this Mealy machine is this one. Thus we start with a RESET. If RESET = 1, the current state will be A. Then, on each positive edge of the CLK signal, a "case" instruction is executed and, for example, if the current state is A, if the input state is 01, then the next state is B, and if the input state is 11, then the next state is D, and so on. [BLANK_AUDIO] And this is the output state. You can check that when current state is A then the output is equal to X1 (0 0 1 1 1 1), or also that if the current state is B, then the output value is X0 inverted: X0 = 0 and the output is equal to 1, 1 0, 0 1, 1 0, and so on. And now a quiz. Summary. Two examples of finite state machines have been presented. The first controls the sequence of operations of a computation circuit (a timer), and the second is used to distinguish between two sequences of input signals. An explicit decomposition into data path and control unit, the so-called Algorithmic State Machine, has been seen, but a direct description without explicit decomposition has also been onsidered. [BLANK_AUDIO]