Applied Electronics (UFMFHT-30-1) Finite State Machines Simulation Equipment Lab Objectives Upon completion of this lab, you should be able to design, implement, and simulate of a Moore-type Finite State Machine

in both schematic and VHDL. 1. Quartus Prime Allocated Time: 2 hours OO TEXAS Panasonic TRUMENTS வசலசலக்கம் DO AMAKARA DEO-CV Cyclone terasIC AUTERA. ISSI AUSTIER 1 FPGA RESET யார் அற Figure 1: DE0-CV Development Board DANS OP 10 T Year 2023/2024 del Lab 8 Applied Electronics (UFMFHT-30-1) Introduction Synchronous sequential circuits are realised using combinational logic and one or more flip-flops. The general structure of such a circuit is shown in the figure 1 below. W Clock Combinational circuit Flip-flops Combinational circuit Year 2023/2024 ㅏ 2 Z Figure 1: FSM The circuit has a set of primary inputs, W, and produces a set of outputs, Z. The values of the outputs of the flip-flops are referred to as the state, Q, of the circuit. Under control of the clock signal, the flip-flop outputs change their state as determined by the combinational logic that feeds the inputs of these flip-flops. Thus, the circuit moves from one state to another. To ensure that only one transition from one state to another takes place during one clock cycle, the flip-flops must be of the edge-triggered type. They can be triggered either by the positive (0 to 1 transition) or by the negative (1 to 0 transition) edge of the clock. We will use the term active clock edge to refer to the clock edge that causes the change in state. The combinational logic that provides the input signals to the flip-flops derives its inputs from two sources: the primary inputs, W, and the present (current) outputs of the flip- flops, Q. Thus, changes in state depend on both the present state and the values of the primary inputs. Figure 1 indicates that the outputs of the sequential circuit are generated by another combinational circuit, such that the outputs are a function of the present state of the flip- flops and of the primary inputs. Although the outputs always depend on the present state, they do not necessarily have to depend directly on the primary inputs. Thus, the connection shown in pink in the figure may or may not exist. To distinguish between these two possibilities, it is customary to say that sequential circuits whose outputs depend only on the state of the circuit are of Moore type, while those whose outputs depend on both the state and the primary inputs are of Mealy type. These names are in honor of Edward Moore and George Mealy, who investigated the behavior of such circuits in the 1950s. Applied Electronics (UFMFHT-30-1) Sequential circuits are also called finite state machines (FSMs), which is a more formal name that is often found in technical literature. The name derives from the fact that the functional behaviour of these circuits can be represented using a finite number of states. Basic Design Steps We will introduce the techniques for designing sequential circuits by means of a simple example. Suppose that we wish to design a circuit that meets the following specification: Year 2023/2024 1. The circuit has one input, w, and one output, z. 2. All changes in the circuit occur on the positive edge of a clock signal. 3. The output z is equal to 1 if during two immediately preceding clock cycles the input w was equal to 1. Otherwise, the value of z is equal to 0. Thus, the circuit detects if two or more consecutive 1s occur on its input w. Circuits that detect the occurrence of a pattern on its input(s) are referred to as sequence detectors. From this specification it is apparent that the output z cannot depend solely on the present value of w. To illustrate this, consider the sequence of values of the w and z signals during 11 clock cycles, as shown in Figure 2. The values of w are assumed arbitrarily; the values of z correspond to our specification. These sequences of input and output values indicate that for a given input value the output may be either 0 or 1. For example, w = 0 during clock cycles t2 and t5, but z = 0 during t2 and z = 1 during t5. Similarly, w = 1 during t1 and t8, but z = 0 during t1 and z = 1 during t8. This means that z is not determined only by the present value of w, so there must exist different states in the circuit that determine the value of z. Clock cycle: to t₁ t3 t4 t5 t6 0 1 0 1 1 0 0 00 001 w: Z: Figure 2: Sequence of input and output signals tg tg t10 1 0 1 1 0 1 001 State Diagram The first step in designing a finite state machine is to determine how many states are needed and which transitions are possible from one state to another. There is no set procedure for this task. The designer must think carefully about what the machine must accomplish. A good way to begin is to select one particular state as a starting state; this is the state that the circuit should enter when power is first turned on or when a reset signal is applied. For our example let us assume that the starting state is called state A. As long as the input w is 0, the circuit need not do anything, and so each active clock edge should result in the circuit remaining in state A. When w becomes equal to 1, the machine should recognize this, and move to a different state, which we will call state B. This transition Applied Electronics (UFMFHT-30-1) Year 2023/2024 takes place on the next active clock edge after w has become equal to 1. In state B, as in state A, the circuit should keep the value of output z at 0, because it has not yet seen w = 1 for two consecutive clock cycles. When in state B, if w is 0 at the next active clock edge, the circuit should move back to state A. However, if w = 1 when in state B, the circuit should change to a third state, called C, and it should then generate an output z = 1. The circuit should remain in state C as long as w = 1 and should continue to maintain z = = 1. When w becomes 0, the machine should move back to state A. Since the preceding description handles all possible values of input w that the machine can encounter in its various states, we can conclude that three states are needed to implement the desired machine. Now that we have determined in an informal way the possible transitions between states, we will describe a more formal procedure that can be used to design the corresponding sequential circuit. Behavior of a sequential circuit can be described in several different ways. The conceptually simplest method is to use a pictorial representation in the form of a state diagram, which is a graph that depicts states of the circuit as nodes (circ ) and transitions between states as directed arcs. The state diagram in Figure 3 defines the behavior that corresponds to our specification. States A, B, and C appear as nodes in the diagram. Node A represents the starting state, and it is also the state that the circuit will reach after an input w = 0 is applied. In this state the output z should be 0, which is indicated as A/z=0 in the node. The circuit should remain in state A as long as w = 0, which is indicated by an arc with a label w = 0 that originates and terminates at this node. The first occurrence of w = = 1 (following the condition w = 0) is recorded by moving from state A to state B. This transition is indicated on the graph by an arc originating at A and terminating at B. The label w = 1 on this arc denotes the input value that causes the transition. In state B the output remains at 0, which is indicated as B/z=0 in the node. When the circuit is in state B, it will change to state C if w is still equal to 1 at the next active clock edge. In state C the output z becomes equal to 1. If w stays at 1 during subsequent clock cycles, the circuit will remain in state C maintaining z = 1. However, if w becomes 0 when the circuit is either in state B or in state C, the next active clock edge will cause a transition to state A to take place. 4 Applied Electronics (UFMFHT-30-1) w = 0 State Table Reset A/z = 0 w = 0 w = 1 Present state W = 0 A B C C/z = 1 W = 1 Figure 3: state Diagram of a simple sequential circuit In the diagram we indicated that the Reset input is used to force the circuit into state A, which is possible regardless of what state the circuit happens to be in. We could treat Reset as just another input to the circuit and show a transition from each state to the starting state A under control of the input Reset. This would complicate the diagram unnecessarily. States in a finite state machine are implemented using flip-flops. Since flip- flops usually have reset capability, we can assume that the Reset input is used to clear all flip-flops to 0 by using this capability. We will indicate this as shown in Figure 3 to keep the diagrams as simple as possible. w=0 A A A B/z = 0 w = 1 Although the state diagram provides a description of the behavior of a sequential circuit that is easy to understand, to proceed with the implementation of the circuit, it is convenient to translate the information contained in the state diagram into a tabular form. Figure 4 shows the state table for our sequential circuit. The table indicates all transitions from each present state to the next state for different values of the input signal. Note that the output z is specified with respect to the present state, namely, the state that the circuit is in at present time. Note also that we did not include the Reset input; instead, we made an implicit assumption that the first state in the table is the starting state. Next state w = 1 B C C Output Z Year 2023/2024 0 0 1 Figure 4: State table for the sequential circuit in Figure 3