1. The Design Procedure
| Step | What you do |
|---|---|
| 1. Specification | Describe the required behavior |
| 2. Formulation | Obtain a state diagram or state table |
| 3. State assignment | Give each state a binary code |
| 4. Flip-flop input equations | Choose FF type, derive input equations from next-state entries |
| 5. Output equations | Derive from the output entries |
| 6. Optimization | Minimize the equations (K-maps) |
| 7. Technology mapping | Map to the available gates and flip-flops |
| 8. Verification | Check 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
- Start in an initial (reset) state where none of the sequence has occurred.
- Add a state recognizing the first symbol.
- Add a state for each successive symbol.
- The final state represents the sequence (possibly minus the last symbol, for Mealy).
- Add arcs for symbols not in the proper sequence.
- 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)
| Present | Next x=0 | Next x=1 | Z x=0 | Z x=1 |
|---|---|---|---|---|
| A | A | B | 0 | 0 |
| B | A | C | 0 | 0 |
| C | D | C | 0 | 0 |
| D | A | B | 0 | 1 |
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
| Present | Next x=0 | Next x=1 | Output |
|---|---|---|---|
| A | A | B | 0 |
| B | A | C | 0 |
| C | D | C | 0 |
| D | A | E | 0 |
| E | A | C | 1 |
⚠️ 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=0 | Next x=1 | Z x=0 | Z x=1 | |
|---|---|---|---|---|
| 00 | 00 | 01 | 0 | 0 |
| 01 | 00 | 10 | 0 | 0 |
| 10 | 11 | 10 | 0 | 0 |
| 11 | 00 | 01 | 0 | 1 |
Assignment 2 – Gray code (A=00, B=01, C=11, D=10)
| Next x=0 | Next x=1 | Z x=0 | Z x=1 | |
|---|---|---|---|---|
| 00 | 00 | 01 | 0 | 0 |
| 01 | 00 | 11 | 0 | 0 |
| 11 | 10 | 11 | 0 | 0 |
| 10 | 00 | 01 | 0 | 1 |
K-maps ( rows, X columns):
| (X=0, 1) | (X=0, 1) | (X=0, 1) | |
|---|---|---|---|
| 00 | 0, 0 | 0, 1 | 0, 0 |
| 01 | 0, 1 | 0, 1 | 0, 0 |
| 11 | 1, 1 | 0, 1 | 0, 0 |
| 10 | 0, 0 | 0, 1 | 0, 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).
| State | Next x=0 | Next x=1 | Z x=0 | Z x=1 |
|---|---|---|---|---|
| 0001 | 0001 | 0010 | 0 | 0 |
| 0010 | 0001 | 0100 | 0 | 0 |
| 0100 | 1000 | 0100 | 0 | 0 |
| 1000 | 0001 | 0010 | 0 | 1 |
Each = OR of (source state · input) of all arcs entering state :
Gate-input cost = 15, but 2 extra flip-flops.
| Assignment | Flip-flops | Gate-input cost |
|---|---|---|
| Counting order | 2 | 22 |
| Gray code | 2 | 9 |
| One-hot | 4 | 15 |
⚠️ 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)
| 00 | 01 | 11 | 10 | ||
|---|---|---|---|---|---|
| A (00) | 00 | 01 | X | 10 | 00 |
| B (01) | 01 | 10 | X | 00 | 01 |
| – (11) | X | X | X | X | 11 |
| C (10) | 10 | 00 | X | 01 | 10 |
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
| Descriptor | Used for | Gives |
|---|---|---|
| Characteristic table | Analysis | Q(t+1) from inputs and Q(t) |
| Characteristic equation | Analysis | Q(t+1) as a Boolean function |
| Excitation table | Design | Required inputs for a Q(t)→Q(t+1) change |
D flip-flop
| D | Q(t+1) | Op. | Q(t+1) | D needed | |
|---|---|---|---|---|---|
| 0 | 0 | Reset | 0 | 0 | |
| 1 | 1 | Set | 1 | 1 |
T flip-flop
| T | Q(t+1) | Op. | Q(t)→Q(t+1) | T needed | |
|---|---|---|---|---|---|
| 0 | Q(t) | No change | Q → Q | 0 | |
| 1 | Complement | Q → | 1 |
S–R flip-flop
| S | R | Q(t+1) | Q(t) | Q(t+1) | S | R | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Q(t) | 0 | 0 | 0 | X | |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | |
| 1 | 1 | ? | 1 | 1 | X | 0 |
J-K flip-flop
| J | K | Q(t+1) | Q(t) | Q(t+1) | J | K | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Q(t) | 0 | 0 | 0 | X | |
| 0 | 1 | 0 | 0 | 1 | 1 | X | |
| 1 | 0 | 1 | 1 | 0 | X | 1 | |
| 1 | 1 | 1 | 1 | X | 0 |
⚠️ 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.