1. The Design Procedure

StepWhat you do
1. SpecificationDescribe the required behavior
2. FormulationObtain a state diagram or state table
3. State assignmentGive each state a binary code
4. Flip-flop input equationsChoose FF type, derive input equations from next-state entries
5. Output equationsDerive from the output entries
6. OptimizationMinimize the equations (K-maps)
7. Technology mappingMap to the available gates and flip-flops
8. VerificationCheck the final circuit is correct

2. Specification

Possible forms: written description, mathematical description, HDL*, table*, equations*, operation diagram*.

If the specification is already exact at the binary level (the * forms), part or all of the formulation step is already done.


3. Formulation – Finding a State Diagram

Definition – State

A state is an abstraction of the history of past inputs (including reset). Inputs are only “seen” during the setup–hold window around the clock edge.

  • State A: “a 1 has occurred among past inputs”.
  • State B: “the last two inputs were 0 then 1”.

States remember exactly the properties of the past needed to predict future outputs.

Definition – Sequence Recognizer

A sequential circuit that produces a distinct output whenever a prescribed pattern of input symbols occurs in sequence.

Procedure – Building a recognizer state diagram

  1. Start in an initial (reset) state where none of the sequence has occurred.
  2. Add a state recognizing the first symbol.
  3. Add a state for each successive symbol.
  4. The final state represents the sequence (possibly minus the last symbol, for Mealy).
  5. Add arcs for symbols not in the proper sequence.
  6. Point those arcs to the state matching the longest suffix of the input seen so far that is still a prefix of the sequence.

⚠️ Step 6 is what handles overlapping sequences — the circuit must recognize the pattern wherever it occurs.

Example – Recognize 1101 (Mealy)

Overlap cases to handle: 111101 (extra leading 1s) and 1101101 (the last 1 starts the next match).

State meanings:

  • A: no useful prefix
  • B: “1” seen
  • C: “11” seen
  • D: “110” seen
stateDiagram-v2
  [*] --> A
  A --> A : 0/0
  A --> B : 1/0
  B --> A : 0/0
  B --> C : 1/0
  C --> C : 1/0
  C --> D : 0/0
  D --> A : 0/0
  D --> B : 1/1
  • D —1/1—> B: the final 1 of 1101 is itself a “1” prefix.
  • C —1—> C: “111” still ends in “11”.

Formulation – State table (Mealy)

PresentNext x=0Next x=1Z x=0Z x=1
AAB00
BAC00
CDC00
DAB01

Example – Recognize 1101 (Moore)

Outputs attach to states, so a new state E (output 1) is needed for “1101 just completed”. E behaves like B in the future but has a different present output.

stateDiagram-v2
  [*] --> A
  A: A / 0
  B: B / 0
  C: C / 0
  D: D / 0
  E: E / 1
  A --> A : 0
  A --> B : 1
  B --> A : 0
  B --> C : 1
  C --> C : 1
  C --> D : 0
  D --> A : 0
  D --> E : 1
  E --> A : 0
  E --> C : 1
PresentNext x=0Next x=1Output
AAB0
BAC0
CDC0
DAE0
EAC1

⚠️ Memory aid: “Moore is More” — Moore machines usually need more states. Also note E —1—> C (not B): after 1101, another 1 gives “11”.


4. State Assignment

Rule – Number of bits

For states, the minimum number of flip-flops satisfies

There are unused codes. Using more than the minimum bits (e.g., one-hot) can still be worthwhile.

Example 1 – Two states

Only two assignments (A=0, B=1 or the reverse) — they differ only by inverting the variable, so cost barely changes.

Example 2 – The 1101 Mealy recognizer (4 states)

There are possible 2-bit assignments, and they do affect cost. Three are compared below (state variables , D flip-flops).

Assignment 1 – Counting order (A=00, B=01, C=10, D=11)

Next x=0Next x=1Z x=0Z x=1
00000100
01001000
10111000
11000101



Assignment 2 – Gray code (A=00, B=01, C=11, D=10)

Next x=0Next x=1Z x=0Z x=1
00000100
01001100
11101100
10000101

K-maps ( rows, X columns):

(X=0, 1) (X=0, 1) (X=0, 1)
000, 00, 10, 0
010, 10, 10, 0
111, 10, 10, 0
100, 00, 10, 1

✅ Selected to complete the design.

Assignment 3 – One-hot (A=0001, B=0010, C=0100, D=1000)

One flip-flop per state (=A, =B, =C, =D). In equations, write only the variable that is 1 for that state (all other codes are don’t-cares).

StateNext x=0Next x=1Z x=0Z x=1
00010001001000
00100001010000
01001000010000
10000001001001

Each = OR of (source state · input) of all arcs entering state :

Gate-input cost = 15, but 2 extra flip-flops.

AssignmentFlip-flopsGate-input cost
Counting order222
Gray code29
One-hot415

⚠️ One-hot gives simple, readable logic but costs more flip-flops — cheaper only sometimes.


5. Technology Mapping

Library: D flip-flops with (non-inverted) Reset, NAND gates up to 4 inputs, inverters. The AND–OR equations of the Gray-code design are converted to NAND–NAND form (two-level AND–OR = NAND–NAND), with inverters where complemented variables are needed. Reset drives the flip-flop reset inputs so the circuit starts in A = 00.

flowchart LR
  X[X] --> L[NAND–NAND logic<br/>D1 = Y1Y2 + XY2<br/>D2 = X<br/>Z = X·Y1·Y2']
  L --> FF1[D FF Y1]
  L --> FF2[D FF Y2]
  FF1 --> L
  FF2 --> L
  L --> Z[Z]
  RST[Reset] --> FF1
  RST --> FF2

6. Example 3 – Modulo-3 Accumulator

Specification

  • Modulo-n adder: result = remainder of the sum divided by n (e.g., ).
  • Accumulator: adds each new input to the stored sum (initially 0).
  • Stored sum , input , output = stored sum (Moore).

State diagram

States A = 0 (00), B = 1 (01), C = 2 (10). Next state .

stateDiagram-v2
  [*] --> A : Reset
  A: A / 00
  B: B / 01
  C: C / 10
  A --> A : 00
  A --> B : 01
  A --> C : 10
  B --> B : 00
  B --> C : 01
  B --> A : 10
  C --> C : 00
  C --> A : 01
  C --> B : 10

State table ( rows, columns in Gray order)

00011110
A (00)0001X1000
B (01)0110X0001
– (11)XXXX11
C (10)1000X0110

Input 11 (= 3) and state 11 are don’t-cares.

Flip-flop input equations (D flip-flops)

is 1 for minterms 2, 5, 8; for 1, 4, 10 (variables ). Using don’t-cares:



Check: state B (01) + input 01 → , → 10 = 2 ✅

⚠️ Without the don’t-cares (input 11, state 11) these equations would be much larger — always mark them.


7. Other Flip-Flop Types

Definition – J-K Flip-Flop

Like S–R (J ≈ S, K ≈ R) but J = K = 1 is allowed and toggles the state.

  • A master–slave J-K still has 1s catching (a falsely set master cannot be reset in the same cycle).
  • Fix: build it around an edge-triggered D flip-flop: .

Definition – T (Toggle) Flip-Flop

Single input T: T = 0 → hold; T = 1 → complement. Equivalent to J-K with J = K = T. Built with an edge-triggered D: .

⚠️ A T flip-flop cannot be initialized through T — a reset input is essential.

Basic descriptors

DescriptorUsed forGives
Characteristic tableAnalysisQ(t+1) from inputs and Q(t)
Characteristic equationAnalysisQ(t+1) as a Boolean function
Excitation tableDesignRequired inputs for a Q(t)→Q(t+1) change

D flip-flop

DQ(t+1)Op.Q(t+1)D needed
00Reset00
11Set11

T flip-flop

TQ(t+1)Op.Q(t)→Q(t+1)T needed
0Q(t)No changeQ → Q0
1ComplementQ → 1

S–R flip-flop

SRQ(t+1)Q(t)Q(t+1)SR
00Q(t)000X
0100110
1011001
11?11X0

J-K flip-flop

JKQ(t+1)Q(t)Q(t+1)JK
00Q(t)000X
010011X
10110X1
1111X0

⚠️ J-K excitation has a don’t-care in every row — that’s why J-K designs often give simpler logic than S–R or D.

Flip-flop behavior example (waveforms)

Method: at each active clock edge, read the inputs just before the edge, apply the characteristic table to the current Q, and hold the result until the next edge.

flowchart LR
  E[Active clock edge] --> R[Read D/T or S,R or J,K just before edge]
  R --> T[Apply characteristic table to current Q]
  T --> H[Hold new Q until next edge]
  H --> E
  • D: Q copies D. T: Q toggles when T = 1.
  • S–R: watch for S = R = 1 (undefined, ”?”). J-K: same inputs toggle instead.