Skip to main content
Engineering LibreTexts

10.3: Implementing a State Machine

  • Page ID
    26878
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \(\PageIndex{1}\) Mod 4 counter

    A mod (or modulus) 4 counter is a circuit that counts from 0..3. It is also called a 2-bit counter because the numbers from 0..3 can be represented using 2-bits (e.g. 00, 01, 10, 11) 9. The state of the counter is represented in 2-bits, and so is stored in 2 flip-flops (or latches). Because the two flip-flops combine to make a single value, they are often called a 2-bit register.

    The state transitions of this machine, as a counter, are 00->01->10->11->00. The machine just counts from 0 to 3 and starts over. This is represented in the following state diagram.

    Figure \(\PageIndex{1}\): State diagram for a mod 4 counter

    Screen Shot 2020-06-27 at 3.25.59 AM.png

    This state diagram can be written as a state transition table, as shown below.

    Figure \(\PageIndex{2}\): State transition table for a mod 4 counter

    Screen Shot 2020-06-27 at 3.27.36 AM.png

    This table says that if the clock does not pulse, Q1 and Q0 retain their old values. When the clock generates an rising edge (↑), the values of Q1 and Q0 transition to the next value in the counter, or their next state.

    \(\PageIndex{2}\) Implementation of a state transition diagram

    The following is a generic implementation of a state machine. There are two components. The first is a n-bit register, which is a collection of n 1-bit D flip-flops or D latches. These n 1-bit data values store the current state of the machine, and can store up to 2n states. The register changes state when the clock generates a positive edge trigger, causing the flip-flops to take on a new value.

    The register will output some set of values, and at the same time recycle its state back into a set of gates which will determine how to change the register to the next state. This set of gates will be called the next state logic. The output of the next state logic will be connected to the input to the registers so that when the clock pulses (or ticks), the register is loaded with the new values. This logic is represented in the following figure.

    Figure \(\PageIndex{3}\): Circuit overview for a state machine

    Screen Shot 2020-06-27 at 3.31.28 AM.png

    As this diagram shows that the input to the next state logic comes from the previous state. The next state logic uses the previous state to calculate the next state to store into the register. The clock tick then causes the register to store new state, which is feed back into the next state logic to calculate a new next state.

    This overview explains how a state machine works, but has left open the question of how to implement the next state logic? There are two basic ways to implement this logic, either through hardware or using a micro program. A hardware implementation uses gates to calculate the new state. A micro program is implemented in using Read Only Memory (or ROM), and the next state is retrieved from an address given by the current state. These will be explained in the next two sections.

    \(\PageIndex{3}\) Hardware implementation of next state logic

    The next state logic must take as input the current state and convert it to the next state. The state transition diagram in Figure \(\PageIndex{2}\) is very similar to a truth table, where Q0old and Q1old are the inputs to the circuit, and Q0new and Q1new are the outputs. From the state transition diagram, it is simple to solve for the Boolean expressions, which are Q0new = (Q0old' * Q1old') + (Q0old' * Q1old), and Q1new = (Q0old XOR Q1old). The circuit diagram for this next state logic is shown in the following figure.

    Figure \(\PageIndex{4}\): Hardware implementation for a mod 4 counter

    Screen Shot 2020-06-27 at 3.35.49 AM.png

    In this figure, the next state logic is implemented using NOT, AND, OR, and XOR gates. It is actually a type of micro program which is implemented in hardware. This is called hard wired because the actual circuit to calculate the next state is wired into the circuit.

    The problem with hard wired programs is that they cannot be easily changed. Modern computers generally do not implement the micro programs by hard wiring them, but use some type of read only memory.

    \(\PageIndex{4}\) Read Only Memory

    Read Only Memory (ROM) is memory that is never written after it is first programmed 10. It can be used to store programs that are used to initially boot a computer, or to store static data tables or micro programs used to specify how the internal hardware of the CPU works. The following is an example of the Mod 4 Counter shown using a ROM chip to implement the next state logic as a micro program.

    Figure \(\PageIndex{5}\): ROM implementation of a mod 4 counter

    Screen Shot 2020-06-27 at 3.38.56 AM.png

    The ROM chip contains the micro program which implements the Mod 4 Counter. The next state for the mod 4 counter (1, 2, 3, and 0, or 002, 012, 102, 112) is stored at an address corresponding to the current state of the mod 4 counter. Thus at address 0 the ROM program stores 1, to state that the next state from 0 is 1.

    The address is the current state of the counter, which is the value currently stored in the registers. At address 0, the value 1 is stored, which says that when Q0 and Q1 are 002, the ROM will read the value 012 from memory. Each time the clock ticks, the ROM chip sends the next value to the registers, which transitions to the next state in the counter.

    ROM chips are a very good way to implement state transition tables, but require special hardware to create and program the ROM chips. So a simple trick will be used to implement ROM for our circuits, as was done in the switch mirroring circuit in section 8-6. This trick is to use a multiplexer with hard wired input for the micro program, and the select bits used to specify the address. This design is shown in Figure \(\PageIndex{6}\).

    To understand this circuit, realize that each MUX chooses 1-bit for each of the 4 states. So when the state is 002, the bottom MUX will choose the 0 bit and the top MUX will select a 1 bit, which gives a new state of 012.

    This circuit using the two MUXes to implement the micro program will be shown in the next section.

    Figure \(\PageIndex{6}\): Mux implementation of next state logic for a mod 4 counter

    Screen Shot 2020-06-27 at 3.42.40 AM.png

    \(\PageIndex{5}\) Implementation of the Mod 4 counter

    Figure \(\PageIndex{9}\) implements the Mod 4 counter. Steps 1 and 2 are needed to implement the debouncing for the circuit, and are presented with no explanation of how they work. This circuit generally works well if the button is pressed sharply and cleanly, but multiple signals will at times still be generated by the push button.

    1. Place the push button switch on the board. The switch does have direction, so it must be inserted properly to work. The easiest way to get the direction correct is to put the switch across the center cut out in the breadboard. Because the legs on the button are hooked, there is only one direction to insert the push button, and that is the correct direction.

      Connect the input of the chip to the negative rail. The output of the push button switch should be connected to the input of the 7414 Schmitt inverter in step 2. The output of the switch must also be connected to the negative rail by a 0.1μf capacitor. This capacitor is absolutely necessary for the circuit to work properly.

    2. Place the 7414 Schmitt inverter chip on the board, and power it. The output from the 7414 chip is the two clock inputs for the 7474 chip in step 7.
    3. Place the 74153 multiplexor chip on the board, and power it. The pin layout for the 74153 multiplexor is shown in Figure \(\PageIndex{7}\). Step 7 will discuss how to wire the chip to connect it to the circuit. The steps below discuss how to wire it.
      1. Power the chip with GND on pin 8 and Vcc on pin 16, as usual.
      2. Pins 1 and 15 are enable low. These enable the output from each MUX. We always want the output from the MUXes, so enable them by connecting these pins to low.
        Figure \(\PageIndex{7}\): 74153 pin layout diagram

        Screen Shot 2020-06-27 at 1.22.16 PM.png

      3. Pins 3...7 and pins 10...14 are the inputs to each MUX. These pins are set to implement the program.

        Note

        The pins are set from I0...I3 in an upward direction, not a downward direction. Implement the program in Figure \(\PageIndex{6}\) using 1I values of 0110 and 2I values of 1010.

        Figure \(\PageIndex{8}\): 7474 pin layout

        Screen Shot 2020-06-27 at 1.26.08 PM.png

    4. Place the 7474 2-bit D flip-flop chip on the board and power it. The pin layout of the 7474 chip is in Figure \(\PageIndex{8}\). Step 8 will discuss how to wire the chip to connect it to the circuit. The steps below discuss how to wire it.
      1. Power the chip with GND on pin 7 and Vcc on pin 8, as usual.
      2. Pins 1, 4, 10, and 13 are for asynchronous set and reset. They are enabled low, so connect these pins to the positive rail to disable them.
    5. Connect the push button switch to the input to a gate (pin 1) on the 7414 Schmitt inverter. The output of this gate (pin 2) will be used to both clocks on the 7474 2-bit D flip-flop chip.
    6. Connect the 74153 chip (step 3) into the circuit. The inputs S1 and S0 (pins 2 and 14) are the outputs from the previous state, stored in the D flip-flops in step 4. These inputs use green wires to show that they are recycled from the output of a chip further down in the circuit. The outputs of the 74153 chip (pins 7 and 9) are the D input for the next state to the registers.
    7. Connect the D inputs for the 7474 2-bit D flip-flop to pins 2 and 12. The clock inputs from step 2 are connected to pins 3 and 11. The outputs are the current state on 1Q and 2Q, pins 6 and 9. These output are used as inputs to the next state logic implemented in the MUX (step 6, the green wire), and to show the current state represented in the output LEDs.
      Figure \(\PageIndex{9}\): Mod 4 counter

      Screen Shot 2020-06-27 at 1.31.22 PM.png

    When the push button switch is pressed, the LED lights should cycle through the states for 00->01->10->11->00.


    9 The name mod 4 counter is more accurate because the 2-bit counter could be used to implement a mod 3 or mod 4 counter. This is more a problem with a 4-bit counter because it is often used as a decade (mod 10) counter or a hex (mod 16) counter.

    10 ROM and PROM chips are never changed once they are written. Some types of chips similar to ROM chips, such as EPROM or EEPROM, can be written in order to store a new program. But even these types of ROM chips are written to infrequently, and not meant to store transient data.


    This page titled 10.3: Implementing a State Machine is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Charles W. Kann III via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.