[MUSIC] The subject of this lesson is Finite State Machines. In fact, finite state machines are nothing else than a generic algebraic model of sequential circuit. So, part of this lesson, will sound as a repetition of already seen subjects. Apart from the definition, we will make some comments about their implementation, and we'll see how they can be specified in VHDL, our favorite hardware description language. The specification of a finite state machine is based on the definition of a set Sigma of input states; it's the set of possible value combinations of the input signals; a set Omega of output states, that is to say the set of possible value combinations of the output signals; a set S of internal states; and then two functions that define the working of the circuit. The mapping F that associates an internal state to every pair (internal state, input state) and a mapping h that associates an output state to every pair (internal state, input state). Let us see a very simple example. A 3-bit counter with a Count Enable input signal. It can be modeled by a finite state machine whose set Sigma is {0, 1} (Count Enable can be equal to 0 or to 1), with a set Omega equal to the set of 3-bit vectors; the same as regards the set S of internal states; the next state function f is equal to s when count enable is equal to 0 and to s+1 when count enable is equal to 1 (s+1 modulo 8) and the output function h always returns the value of the current state. Here is a straightforward implementation. It consists of a 3-bit register, a combinational circuit that implements function f, this function, for example a multiplexer and an adder that computes q+1. Thus, as I already commented at the beginning of this lesson, Finite Sstate Machines can be seen as just another name for a sequential machine. Nevertheless, they are mainly used to specify the working of circuits that control sequences of operations rather than to specify the working of circuits that actually execute operations. Now, some comments about their implementation. We already know the difference between Moore and Mealy models, and first consider a Moore model. Then the circuit will consist of a first combinational circuit that computes the next state, in function of the internal state and of the input state, and we will assume that its delay is equal to T1 seconds. Another combinational circuit computes the output state, in function of the internal state, and we will assume that its delay is equal to T2. We will also assume that the input state, that generally comes from another synchronized circuit, is stable, some time, tSUinput (SU means setup) tSUinput second after the active clock edge. Then, this is a time diagram of what occurs during the state transition. We will assume that the register delay is negligible, so that the new internal state, here, is available from the beginning of the clock cycle. The output state will be stable after T2 seconds. It's what we see here: after T2 seconds, the output state is stable. We assume that the input state is stable after tSUinput seconds. As a matter of fact, tSUinput could be the value of T2 of another finite state machine. So that the next state will be stable after tSU + T1 seconds (here). Conclusion: the clock period must be greater than both tSUinput + T1 and T2 in order that the next clock edge occurs after that output state and next state are stable. In the case of a Mealy model, the only difference is that the output state also depends on the input state. The conclusion is that the setup time of the input state must be taken into account when computing the time necessary to get a stable output state (here). Here the value is tSUinput + T2. t. The clock period must be greater than both tSUinput + T1 and tSUinput + T2. Third point of this lesson: how can we describe a finite state machine in VHDL? The generic architecture is this one. So we could define two processes: one that defines the next state function and the synchronization of the machine, and another one to define the output function. We could define a package that includes several definitions and functions, a package called for example my_fsm. It defines the set of internal states. So, a type STATE is defined equal to, for example, S0, S1, S2, and so on. In the package, we define the number N of input signals (I mean, the number of bits necessary to encode the input state), a number M of output signals (that means the number of bits that encode the output state), and we could define in some way, by tables or by algebraic expressions, the next state function F, and the output function H. Then, we define an entity MooreFsm with input ports CLK, RESET and X. CLK and RESET our bits, and X is an N-bit vector, and with one output port Y, an M-bit vector. The architecture includes the declaration of a signal current_state, whose type STATE has been defined in the package. A first process next_state, sensitive to RESET and CLOCK is the following: (it's easy to understand) if reset is equal to 1, then current_state will be equal to S0 (we assume that S0 is the initial state of the finite state machine); then, if there is a positive edge of the clock signal (it is the way VHDL defines this condition) if there is a positive edge of the clock signal then the current state is replaced by the function F of the current state and of the input state. Nothing else. The output process, sensitive to the current state computes Y, a function of the current state, using for that function H defined within the package. In fact, instead of defining F and H within a separate package, they could also be directly defined within the processes. Then the next_state process could be based on a "case" statement. So, here is the next_state process, sensitive to RESET and CLCK, the same as before: if reset is equal to 1 then current_state is equal to S0; else, if there is a positive edge of the clock signal, then, in the case that current_state is S0 then (here) you will insert a set of instructions that update the current state of the machine, that is to say, a set of instruction that execute current_state = F(S0, X). The same when the current state is S1, S2, and so on. And the same as regards the output state process, sensitive to the current state, and then the body of the process is a "case" statement: when the current state is S0, we insert here a set of instructions that execute Y = H(S0). The same when the current state is S1, and so on. Let us see an example. Again, the 3-bit counter. So, we assume that we have previously defined the type STATE equal to 0, 1, 2, 3, and so on, up o 7, that we have declared an input port count_enable, a bit, and an output port Y, a 3-bit vector. The next state process is as follows: it's a process sensitive to RESET and CLK. If reset is equal to 1, next state is 0; else, if there is a positive edge of CLK, then if the current state is 0, then if count_enable is equal to 1, then current state will be equal to 1, and it's not necessary to say that else current_state is equal to 0 (not necessary), because within a process it's as in a programming language, so that if the value of current_state doesn't change, it's not necessary to explicitly write that the current_state has the same value as before. When the current_state is equal to 1, then, if count_enable is equal to 1, the next value of current_state is 2, and so on (2 to 3), and, finally, if the current_state is 7, the next state will be 0. So, you can see that we have just inserted within the next_state process, the computation of the next state of the finite state machine. And the output process is this one: if the current_state is 0, then the output y is the 3-bit vector that represents 0; if the current state is 1, the output is the 3-bit vector that represents 1, and s on up to 7. As we already know, in the case of a Mealy machine the only difference is that the output function also depends on the input state, so that the output state process has this structure: it is sensitive to both the current state and the input state, and for every value of the current state we must insert within this "case" statement the set of instructions that execute the updating of the output port Y, and the same for all other states. Summary. We have defined the concept of Finite State Machine. We could say that practically it's just another name for sequencial machine. As regards their implementation, maximum clock frequencies, have been computed. And finally, generic VHDL models, with two concurrent processes have been described.