1. Introduction to Sequential Circuits
Definition – Sequential Circuit
A sequential circuit = combinational logic + storage elements (latches or flip-flops).
- Inputs / Outputs: signals from / to the outside.
- State (Present State): outputs of the storage elements, fed back into the logic.
- Next State: outputs of the logic fed into the storage elements.
flowchart LR IN[Inputs] --> CL[Combinational logic] CL --> OUT[Outputs] CL -- Next state --> SE[Storage elements] SE -- State --> CL
Definition – Next-State and Output Functions
| Model | Output function |
|---|---|
| Mealy | |
| Moore |
The output type is fixed by the specification and strongly affects the design.
2. Types of Sequential Circuits
Classified by when storage elements observe their inputs and change state.
| Type | Behavior |
|---|---|
| Synchronous | Behavior defined at discrete instants; storage elements change only relative to a clock |
| Asynchronous | Behavior depends on inputs at any instant and on the order in which they change |
⚠️ Strictly, if the clock is treated as just another input, every circuit is asynchronous. The synchronous abstraction is what makes large designs manageable.
3. Discrete Event Simulation
Rules
- Each gate = ideal instantaneous function + fixed gate delay.
- Any input change is evaluated to see whether it changes the output.
- An output change is scheduled one gate delay after the input change.
- At the scheduled time the output (and every input it drives) changes.
Example – 2-input NAND with 0.5 ns delay
A = B = 1 for a long time; A drops to 0 at and returns to 1 at ns.
| (ns) | A | B | F (instant.) | F | Comment |
|---|---|---|---|---|---|
| −∞ | 1 | 1 | 0 | 0 | Steady |
| 0 | 1→0 | 1 | 0→1 | 0 | Ideal output changes |
| 0.5 | 0 | 1 | 1 | 0→1 | Real output follows 0.5 ns later |
| 0.8 | 0→1 | 1 | 1→0 | 1 | Ideal output changes |
| 1.3 | 1 | 1 | 0 | 1→0 | Real output follows |
⚠️ The slide prints the last time as “0.13” — it is 1.3 ns (0.8 + 0.5).
Circuit delay model – 2-to-1 MUX glitch
built with an inverter (0.2 ns), ANDs (0.4 ns) and OR (0.5 ns). When S switches, the inverted path is 0.2 ns late, so for a moment both AND gates can be 0 → a short glitch on Y.
Storing state – feedback
Connect Y back to A:
- S = 1: Y = B (load).
- S = 0: Y keeps its old value (store).
The circuit is now sequential: its output depends on the history of inputs.
| B | S | Y | Comment |
|---|---|---|---|
| 1 | 0 | 0 | Y remembers 0 |
| 1 | 1 | 1 | Y = B |
| 1 | 0 | 1 | Y remembers 1 |
| 0 | 0 | 1 | B changes, Y does not |
| 0 | 1 | 0 | Y = B |
| 0 | 0 | 0 | Y remembers 0 |
| 1 | 0 | 0 | No change |
Unstable circuit – oscillator
Adding an inverter in the feedback path: for S = 0, Y flips every 1.1 ns (0.2 + 0.4 + 0.5) forever → the circuit is unstable, an oscillator (basic clock source).
4. Latches
Definition – NAND S–R Latch (–, active-LOW)
Two cross-coupled NAND gates. Inputs are active-LOW.
| R | S | Q | Comment | |
|---|---|---|---|---|
| 1 | 1 | ? | ? | Unknown at power-up |
| 1 | 0 | 1 | 0 | Set |
| 1 | 1 | 1 | 0 | Remembers 1 |
| 0 | 1 | 0 | 1 | Reset |
| 1 | 1 | 0 | 1 | Remembers 0 |
| 0 | 0 | 1 | 1 | Both HIGH (not complements) |
| 1 | 1 | ? | ? | Unstable / unpredictable |
⚠️ S = R = 0 is forbidden for the NAND latch: Q and become equal, and releasing both together leaves the state unpredictable.
Definition – NOR S–R Latch (active-HIGH)
Two cross-coupled NOR gates.
| R | S | Q | Comment | |
|---|---|---|---|---|
| 0 | 0 | ? | ? | Unknown |
| 0 | 1 | 1 | 0 | Set |
| 0 | 0 | 1 | 0 | Remembers 1 |
| 1 | 0 | 0 | 1 | Reset |
| 0 | 0 | 0 | 1 | Remembers 0 |
| 1 | 1 | 0 | 0 | Both LOW |
| 0 | 0 | ? | ? | Unstable |
⚠️ For NOR the forbidden input is S = R = 1 — the opposite of the NAND version.
Definition – Clocked S–R Latch
Two extra NAND gates gate S and R with control C (clock/control). S and R are observed only while C = 1.
| Q(t) | S | R | Q(t+1) | Comment |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | No change |
| 0 | 0 | 1 | 0 | Clear |
| 0 | 1 | 0 | 1 | Set |
| 0 | 1 | 1 | ??? | Indeterminate |
| 1 | 0 | 0 | 1 | No change |
| 1 | 0 | 1 | 0 | Clear |
| 1 | 1 | 0 | 1 | Set |
| 1 | 1 | 1 | ??? | Indeterminate |
Definition – D Latch
Clocked S–R latch with , (one inverter) → no indeterminate state.
| C | D | Q(t+1) | Comment |
|---|---|---|---|
| 0 | X | Q(t) | No change |
| 1 | 0 | 0 | Clear |
| 1 | 1 | 1 | Set |
While C = 1 the latch is transparent (Q follows D).
⚠️ The slide’s D-latch table rows are scrambled; the correct behavior is: C = 0 → hold, C = 1 → Q = D.
5. Flip-Flops
The Latch Timing Problem
Paths exist through combinational logic from a storage element back to itself (possibly just a wire). With a transparent D latch, while C = 1 the output keeps feeding back and changing:
flowchart LR Q[D latch Q = Y] --> INV[NOT] --> D[D input] D --> Q CLK[Clock = 1 → transparent] --> Q
As long as C = 1, Y toggles repeatedly (limited only by loop delay). Desired: Y changes once per clock pulse. Fix: break the loop inside the storage element → master–slave or edge-triggered flip-flop.
Definition – S–R Master–Slave Flip-Flop
Two clocked S–R latches in series; the slave’s clock is inverted.
- C = 1: master observes inputs; slave holds.
- C = 0: slave copies master; master holds.
Input and output are never connected through at the same time.
Flip-Flop Problems: delay and 1s catching
- Output changes only after the pulse ends → slower (delayed by pulse width).
- 1s catching: S/R may change while C = 1.
- Q = 0, S pulses 1→0 with R = 0 → master sets → 1 transferred to slave.
- Q = 0, S pulses then R pulses → master sets then resets → 0 transferred.
The master “catches” a 1 that was not present at the end of the pulse.
Definition – Edge-Triggered Flip-Flop
Ignores the clock while it is at a constant level; triggers only on a clock transition.
- Negative-edge D flip-flop: master–slave with the first latch replaced by a D latch. No S/R → no 1s catching; output changes at the falling edge.
- Positive-edge D flip-flop: add an inverter to the clock input. Q takes the value of D at the rising edge. This is the standard flip-flop used for most sequential circuits.
Standard symbols
| Element | Symbol marking |
|---|---|
| Latch | Plain C input (bubble = active-0 control) |
| Master–slave | Postponed-output indicator (┐) on outputs |
| Edge-triggered | Dynamic indicator (▷) on C; bubble + ▷ = negative edge |
Direct (asynchronous) inputs
At power-up/reset, flip-flops must start in a known state, outside clocked behavior. Direct inputs (preset) and (clear), typically active-LOW:
- → Q = 0
- → Q = 1
6. Sequential Circuit Analysis
General model
- Present state at time is stored in flip-flops.
- Next state = Boolean function of state and inputs.
- Outputs at = function of state (and sometimes inputs).
Example 1 – Two D flip-flops, input x, output y
From the logic diagram:
Output depends on x → Mealy circuit.
Definition – State Table
Four sections: Present State, Input, Next State, Output. Viewed as a truth table: inputs = (present state, input); outputs = (next state, output).
Example 1 – State table (1-D form)
| A | B | x | A⁺ | B⁺ | y |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Example 1 – State table (2-D form, K-map friendly)
| AB | A⁺B⁺ (x=0) | A⁺B⁺ (x=1) | y (x=0) | y (x=1) |
|---|---|---|---|---|
| 00 | 00 | 01 | 0 | 0 |
| 01 | 00 | 11 | 1 | 0 |
| 10 | 00 | 10 | 1 | 0 |
| 11 | 00 | 10 | 1 | 0 |
Timing – where are inputs, outputs and states defined?
State is sampled at each clock edge (t, t+1, t+2 …). Inputs must be stable just before the edge; the next state appears just after it. A Mealy output is valid between edges and can change whenever the input changes.
Definition – State Diagram
- Circle per state (state name inside).
- Directed arc present → next state.
- Label with the input causing the transition.
- Output written:
- in the circle as
state/output→ Moore, - on the arc as
input/output→ Mealy.
- in the circle as
Example 1 – State diagram (Mealy, labels x/y)
stateDiagram-v2 s00: AB = 00 s01: AB = 01 s10: AB = 10 s11: AB = 11 s00 --> s00 : 0/0 s00 --> s01 : 1/0 s01 --> s00 : 0/1 s01 --> s11 : 1/0 s11 --> s00 : 0/1 s11 --> s10 : 1/0 s10 --> s00 : 0/1 s10 --> s10 : 1/0
Diagrams are easy to read for small circuits; tables scale better for large ones.
7. Equivalent States
Definition – Equivalent States
Two states are equivalent if, for every possible input sequence, they produce the identical output sequence.
Practical test: for each input symbol, they give the same output and go to the same (or equivalent) next state.
Example – Reducing a 4-state diagram
Original (Mealy, input/output):
| State | x=0 → next / out | x=1 → next / out |
|---|---|---|
| S0 | S0 / 0 | S1 / 0 |
| S1 | S0 / 1 | S2 / 0 |
| S2 | S0 / 1 | S2 / 0 |
| S3 | S0 / 1 | S2 / 0 |
- S2 and S3: same outputs (1 on 0, 0 on 1) and same next states (S0, S2) → merge S3 into S2.
- Now S1 and S2: same outputs, next states S0 and S2 → merge S2 into S1.
stateDiagram-v2 [*] --> S0 S0 --> S0 : 0/0 S0 --> S1 : 1/0 S1 --> S0 : 0/1 S1 --> S1 : 1/0
4 states → 2 states (one flip-flop instead of two).
⚠️ Merging is iterative: merging one pair can make another pair equivalent.
8. Moore and Mealy Models
Sequential circuits are Finite State Machines (FSMs).
| Moore (E.F. Moore) | Mealy (G. Mealy) | |
|---|---|---|
| Output depends on | State only | State and inputs |
| Output written on | States (circles) | Transition arcs |
| Typical state count | More | Fewer |
Example – Moore vs Mealy tables
Moore (output on state):
| PS | NS x=0 | NS x=1 | Output |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 1 | 0 | 2 | 0 |
| 2 | 0 | 2 | 1 |
Mealy (output on transition):
| PS | NS x=0 | NS x=1 | y x=0 | y x=1 |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
Both detect two consecutive 1s; Moore needs an extra state to “hold” the output.
stateDiagram-v2 direction LR state "Moore" as M { m0: 0 / 0 m1: 1 / 0 m2: 2 / 1 m0 --> m0 : 0 m0 --> m1 : 1 m1 --> m0 : 0 m1 --> m2 : 1 m2 --> m2 : 1 m2 --> m0 : 0 }
Mixed outputs
Real designs may mix: e.g., state 00 has a Moore output while states 01, 10, 11 have Mealy outputs — whatever makes the specification simplest.
9. Example 2 – Analysis of a 3-Flip-Flop Circuit
Three D flip-flops A, B, C with asynchronous Reset to 000; no inputs; output Z.
From the logic diagram (standard version of this example):
⚠️ Read the equations off the diagram from your slides to confirm — the extracted slide text left them blank.
State table
| ABC | A⁺B⁺C⁺ | Z |
|---|---|---|
| 000 | 001 | 0 |
| 001 | 010 | 0 |
| 010 | 011 | 0 |
| 011 | 100 | 0 |
| 100 | 000 | 1 |
| 101 | 010 | 1 |
| 110 | 010 | 1 |
| 111 | 100 | 1 |
State diagram
stateDiagram-v2 [*] --> s000 : Reset s000 --> s001 s001 --> s010 s010 --> s011 s011 --> s100 s100 --> s000 s101 --> s010 s110 --> s010 s111 --> s100
- Used states: 000 → 001 → 010 → 011 → 100 → 000.
- Function: a modulo-5 counter (counts 0–4); Z = 1 once every 5 clocks → divide-by-5.
- Unused states 101, 110, 111 return to the main cycle within one clock (self-correcting).