State Machine Design and Programmable Logic

Counters are one kind of sequential circuit. In general, a finite state machine (FSM) circuit remembers its history in flip-flops and changes state on each clock edge. This lesson shows the complete design method, then the programmable chips used to build logic.

Design steps

• n states need at least ⌈log₂ n⌉ flip-flops.
• State minimisation: two states are equivalent if, for every input, they give the same output and go to equivalent states (the same partition method as DFA minimisation).
• State assignment: binary, Gray code (adjacent states differ in one bit) or one-hot (one flip-flop per state, simpler logic, more flip-flops).

Example: detect two 1s in a row (Moore)

States: A (no 1 yet), B (last input 1), C (last two inputs 1, output 1).

Three states need 2 flip-flops. With D flip-flops, the next-state table gives the D inputs directly.

The same behaviour as a Mealy machine needs only 2 states, because the output can be produced on the transition. See Mealy and Moore Machines.

Memories

• ROM (read-only memory) with n address lines and m data lines stores a 2ⁿ × m truth table: it can implement any m functions of n variables, by storing the truth table.
• Types: mask ROM, PROM (one-time programmable), EPROM (UV erasable), EEPROM and Flash (electrically erasable).
• RAM: SRAM (flip-flop cells, fast, used in caches) and DRAM (capacitor cells, dense, needs refresh, used in main memory).
• Capacity: a memory with A address lines and D data lines holds 2ᴬ × D bits.

Programmable logic devices

A full adder stored in a ROM, and the detector simulated

rom = []
for address in range(8):                       # address bits: a b c
    a, b, c = address >> 2 & 1, address >> 1 & 1, address & 1
    total = a ^ b ^ c                          # sum
    carry = (a & b) | (b & c) | (a & c)
    rom.append((total, carry))
print("ROM contents (address: sum carry):")
for address, (s, cy) in enumerate(rom):
    print(f"{address:03b}: {s} {cy}")

next_state = {"A": {"0": "A", "1": "B"},       # the Moore 11-detector
              "B": {"0": "A", "1": "C"},
              "C": {"0": "A", "1": "C"}}
state, out = "A", ""
for x in "0110111010":
    state = next_state[state][x]
    out += "1" if state == "C" else "0"
print("11-detector output:", out)

ROM contents (address: sum carry):
000: 0 0
001: 1 0
010: 1 0
011: 0 1
100: 1 0
101: 0 1
110: 0 1
111: 1 1
11-detector output: 0010011000

GATE-style practice questions