Chapter 5 - Sequential Logic & Flip-Flops

05 Chapter Map - Sequential Logic & Flip-Flops

Chapter 5 Overview & Map of Content (MOC)

Sequential logic systems, latches vs. flip-flops, RS/JK/D/T flip-flop mechanics, master-slave flip-flops, race-around condition, flip-flop conversions, clocked sequential circuit analysis & synthesis, and state reduction algorithms.

---

📚 Study Notes Index

• 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK)

• 5.02 Flip-Flop Variants (Master-Slave JK, T & D Flip-Flops) & Triggering Mechanics

• 5.03 Flip-Flop Conversions & Functional Transformation Mechanics

• 5.04 Synchronous Sequential Circuit Analysis & Synthesis

• 5.05 State Reduction Algorithms & Output Sequence Analysis

• 5.06 Chapter 5 Master PYQ Solutions & Synthesis Puzzles

---

🔗 Related Resources

• **Course Teaching Plan:** ECE 2103 - Digital Electronics and Logic Circuits

• **Instructor:** Foysal Sir (Instructor 2)

---

5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK)

Digital logic systems are broadly classified into Combinational and Sequential systems. While combinational circuits produce outputs solely determined by current inputs, sequential logic circuits incorporate memory elements and feedback paths. This enables the circuit to store binary states, making output values dependent on both present inputs and historical execution states.

1. Combinational vs. Sequential Logic Systems [PYQ: 2023, 2024, 2025]

1.1 Architectural Comparison

[Architectural diagrams for Combinational and Sequential Circuits]

1.2 Quantitative & Structural Differences [PYQ: 2023, 2024, 2025]

Feature	Combinational Circuit	Sequential Circuit [PYQ: 2023, 2024, 2025]
Output Dependency	Strictly function of Present Inputs X(t).	Function of Present Inputs X(t) AND Present State Q(t).
Memory Requirement	No memory elements present.	Requires Memory Elements (Latches or Flip-Flops).
Feedback Loop	Absent. Signals flow strictly input-to-output.	Present. Memory feedback path feeds present state Q(t) into logic.
Clock Synchronization	Asynchronous (no clock signal required).	Can be Synchronous (clocked) or Asynchronous.
Operating Speed	Faster (no storage element propagation delays).	Slower (governed by flip-flop delay tpd & clock period Tclk).
Design & Synthesis	K-map or Quine-McCluskey SOP/POS minimization.	State reduction, State assignment, Excitation table mapping.
Standard Building Blocks	Adders, Subtractors, Decoders, MUX, DEMUX.	Registers, Counters, RAM/ROM Memory, Shift Registers.

2. Fundamental Terminology & System Definitions

Key Terminology [PYQ: 2015, 2016, 2018, 2021, 2022, 2023, 2024, 2025]

1. Flip-Flop (1-Bit Memory Element) [PYQ: 2018, 2023, 2024, 2025]: A bistable multivibrator capable of storing exactly one bit of binary data (0 or 1). It maintains its stored state indefinitely as long as power is supplied and no trigger pulse is applied.
2. State Table (Transition Table) [PYQ: 2015, 2016, 2021, 2022]: A tabular mapping showing Present State (Qn), External Inputs (X), Next State (Qn+1), and Present Outputs (Y).
3. State Diagram [PYQ: 2015, 2016, 2021, 2022]: A directed graph where nodes represent discrete states and directed arrows denote transitions labeled as Input / Output.
4. State Equation (Characteristic Equation) [PYQ: 2015, 2016, 2021]: An algebraic Boolean expression defining Qn+1 = f(Qn, Inputs).
5. Register [PYQ: 2015, 2016, 2021, 2022]: An array of N flip-flops clocked simultaneously to store an N-bit binary word.

3. Latches vs. Flip-Flops (Triggering Mechanics)

Characteristic	Latch	Flip-Flop
Triggering Method	Level-Triggered (Active HIGH or Active LOW Enable signal).	Edge-Triggered (Positive/Rising or Negative/Falling Clock Edge).
Response Window	Output continuously tracks inputs throughout active clock level.	Output changes strictly at the discrete instant of clock transition.
Noise & Glitch Sensitivity	High (vulnerable to input glitches while Enable is HIGH).	Low (immune to input variations except during setup/hold time).
Primary Use Case	Temporary asynchronous data buffers.	Synchronous sequential logic, shift registers, counters.

4. Set-Reset (SR) Latch Mechanics

An SR latch is an asynchronous bistable circuit with two inputs: Set (S) and Reset (R), and two complementary outputs (Q and Q’).

4.1 NOR Gate SR Latch Realization

[Logic diagram representation of NOR SR Latch]

Truth Table (NOR SR Latch) [PYQ: 2015, 2018]

S	R	Qn+1	Q’n+1	Operation / State
0	0	Qn	Q’n	No Change (Hold)
0	1	0	1	Reset
1	0	1	0	Set
1	1	0	0	Forbidden / Invalid State (Violates Q = Q’)

5. Clocked Flip-Flops: SR and JK

5.1 Clocked SR Flip-Flop [PYQ: 2015, 2017, 2021]

Adding clock-gating AND/NAND logic forces state transitions to occur only when CLK = 1.

Step-by-Step Derivation of SR Characteristic Equation [PYQ: 2015, 2017, 2021]

1. Characteristic Table:

S	R	Qn	Qn+1	Minterm
0	0	0	0	m0
0	0	1	1	m1
0	1	0	0	m2
0	1	1	0	m3
1	0	0	1	m4
1	0	1	1	m5
1	1	0	X	m6 (Don’t Care)
1	1	1	X	m7 (Don’t Care)

2. K-Map Optimization:

Grouping terms m1, m5 and m4, m5, m6, m7:

Qn+1 = S + R’Qn subject to S * R = 0

5.2 Clocked JK Flip-Flop & Refinement Proof [PYQ: 2015–2022, 2023, 2025]

Exam Refinement Justification [PYQ: 2023, 2025]: In an SR flip-flop, S=1, R=1 results in an invalid/forbidden output state (Q=Q’=0). The JK Flip-Flop eliminates this illegal condition by feeding output lines Q and Q’ back to the input gates. When J=1, K=1, the circuit enters a deterministic Toggle state (Qn+1 = Qn’).

[Logic diagram representation of JK Flip-Flop with NAND gates]

Derivation of JK Characteristic Equation [PYQ: 2015, 2016, 2019, 2022]

1. Characteristic Table:

J	K	Qn	Qn+1	Operation
0	0	0	0	Hold
0	0	1	1	Hold
0	1	0	0	Reset
0	1	1	0	Reset
1	0	0	1	Set
1	0	1	1	Set
1	1	0	1	Toggle
1	1	1	0	Toggle

2. K-Map Optimization:

Grouping minterms m4, m5 (JQn’) and m1, m5 (K’Qn):

Qn+1 = JQn’ + K’Qn

Excitation Table (JK Flip-Flop) [PYQ: 2015–2022]

Qn	Qn+1	Required J	Required K
0	0	0	X
0	1	1	X
1	0	X	1
1	1	X	0

6. Key Exam Traps & Warning Checkpoints

1. SR Equation Constraint: Always write subject to S * R = 0 alongside Qn+1 = S + R’Qn. Omitting the constraint loses 1-2 marks.
2. NOR Latch Connections: In a NOR-gate SR latch, S=1 sets Q=1, but the S line physically connects to the lower NOR gate whose output is Q.
3. JK Refinement Proof: When asked why JK is a refinement of RS, explicitly show that for J=K=1: Qn+1 = (1)Qn’ + (0)Qn = Qn’. This replaces the illegal state with a deterministic Toggle state, proving that JK is the refinement of RS.

7. Past Year Master Questions & Solutions

PYQ Master Problem (2023, 2025): Refinement Justification

Question: “JK flip-flop is the refinement of RS flip-flop” — Justify the statement with necessary logic diagrams and truth tables. [6 Marks]

Solution:

1. Identification of RS Latch Limitation: In an RS flip-flop, when S=1 and R=1 are applied simultaneously, both NOR outputs are forced to 0 (Q=Q’=0), which violates the fundamental complementary property Q = Q’. When inputs return to 0, the final state is unpredictable (race condition).

2. Feedback Modification in JK: The JK flip-flop modifies the RS architecture by introducing cross-coupled feedback: S = J * Q’ and R = K * Q.

3. Mathematical Proof of Deterministic Toggle: Substitute J=1, K=1 into the derived characteristic equation Qn+1 = JQn’ + K’Qn: Qn+1 = 1 * Qn’ + 0 * Qn = Qn’. This replaces the illegal state with a deterministic Toggle state, proving that JK is the refinement of RS.

---

5.02 Flip-Flop Variants (Master-Slave JK, T & D Flip-Flops) & Triggering Mechanics

Related Concepts: 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) | 5.03 Flip-Flop Conversions & Functional Transformation Mechanics | 5.04 Synchronous Sequential Circuit Analysis & Synthesis

Overview

While basic SR and JK flip-flops provide foundation logic, practical digital circuits require specialized variants: the D (Data/Delay) Flip-Flop for temporary buffer storage, the T (Toggle) Flip-Flop for binary counters, and the Master-Slave JK Flip-Flop to resolve the severe physical limitation known as the Race-Around Condition.

1. D-Type (Data / Delay) Flip-Flop [PYQ: 2015, 2016, 2017, 2019, 2022]

The D flip-flop is derived from the SR flip-flop by inserting an inverter between the S and R inputs (S = D and R = NOT D), ensuring that S and R are never simultaneously equal to 1.

1.1 Logic Schematic & Characteristic Derivation

 +-------+

D ----| |---⇒ S -⇒[ Gated SR Latch ]---⇒ Q

| | NOT |

+⇒| Gate |---⇒ R

+-------+

Characteristic Table & Equation Derivation

D	Qn	Qn+1	Operation / State
0	0	0	Reset
0	1	0	Reset
1	0	1	Set
1	1	1	Set

Substituting S = D and R = NOT D into Qn+1 = S + (NOT R)Qn:

Qn+1 = D + NOT(NOT D)Qn = D + D · Qn = D(1 + Qn) = D

Qn+1 = D

Key Result: The Delay Property

The next state Qn+1 is strictly equal to the input D during the active clock edge. Thus, data at input D is delayed by exactly one clock period before appearing at output Q.

2. T-Type (Toggle) Flip-Flop

The T flip-flop is derived from the JK flip-flop by tying the J and K inputs together to a single terminal T (J = T and K = T).

2.1 Logic Schematic & Characteristic Equation

Substitute J = T and K = T into Qn+1 = J(NOT Qn) + (NOT K)Qn:

Qn+1 = T(NOT Qn) + (NOT T)Qn = T XOR Qn

Characteristic Table & Excitation Table

T	Qn	Qn+1	Operation
0	0	0	No Change (Hold)
0	1	1	No Change (Hold)
1	0	1	Toggle
1	1	0	Toggle

3. The Race-Around Condition in JK Flip-Flops [PYQ: 2017, 2020, 2021]

3.1 Definition & Physical Cause

Definition of Race-Around Condition [PYQ: 2017, 2020, 2021]

In a level-triggered JK flip-flop, if J = 1 and K = 1 while the clock pulse remains HIGH (CLK = 1) for a duration tp that is longer than the propagation delay of the gates tpd (tp > tpd), the output Q will toggle continuously back and forth (0 → 1 → 0 → 1 …) during the clock pulse width. At the end of the clock pulse, the final state of Q becomes unpredictable and uncertain. This physical defect is called the Race-Around Condition.

Clock Pulse (CLK): +------+ +------+

| tp | | |

+------+ +------+

Output Q (t_p > t_pd):

|-| |-| |-|

| |__| |__| |___ (Continuous Toggling / Racing)

3.2 Methods to Eliminate the Race-Around Condition [PYQ: 2017, 2020, 2021]

1. Keep tp < tpd: Make the clock pulse width tp smaller than the propagation delay tpd of the gates. (Impractical in high-speed IC manufacturing).
2. Edge-Triggering: Use edge-triggered flip-flops (transitional RC differentiating circuits) so triggering occurs strictly at the edge instant.
3. Master-Slave Architecture: Use a Master-Slave JK Flip-Flop setup where clock inversion isolates input sampling from output updates.

4. Clocked Master-Slave JK Flip-Flop [PYQ: 2015, 2017, 2019, 2020, 2021]

4.1 Circuit Architecture

A Master-Slave JK Flip-Flop consists of two clocked SR/JK latches connected in series:

1. Master Stage: Clocked directly by CLK.
2. Slave Stage: Clocked by the inverted clock signal NOT CLK.

 +-----------------------+ +-----------------------+

| MASTER LATCH | | SLAVE LATCH |

J -⇒| NAND 3 NAND 1 |---⇒ NAND 7 NAND 5 |---⇒ Q ----+

CLK ⇒| (CLK) | Y | (CLK’) | |

Q’ ⇒| NAND 4 NAND 2 |---⇒ NAND 8 NAND 6 |---⇒ Q’—+ |

+-----------------------+ Y’ +-----------------------+ | |

^ ^ ^ ^ | |

K -------|---------------+ | | | |

| | | | |

+--------------[ NOT Gate ]---+ | | |

| (CLK’) | | |

+---------------------------------------------|----------------+ |

| | |

+---------------------------------------------+------------------+

4.2 Operational Walkthrough

1. When CLK = 1 (NOT CLK = 0): The Master is ENABLED. Inputs J and K update intermediate outputs Y and Y’. The Slave is DISABLED. Output Q remains unchanged.
2. When CLK transitions from 1 → 0 (NOT CLK = 1): The Master becomes DISABLED, locking inputs Y and Y’. The Slave becomes ENABLED, copying intermediate signals Y and Y’ to final outputs Q and Q’.
3. Why it eliminates Race-Around: Since Master and Slave are never active at the same time, feedback from Q cannot return to input gates while output is updating. Toggling occurs at most once per clock cycle.

5. Summary & Comparison of All 4 Primary Flip-Flops

Flip-Flop	Inputs	Char. Equation	Excit (0-0)	Excit (0-1)	Excit (1-0)	Excit (1-1)
SR	S, R	Qn+1=S+(NOT R)Qn	S=0, R=X	S=1, R=0	S=0, R=1	S=X, R=0
JK	J, K	Qn+1=J(NQn)+(NK)Qn	J=0, K=X	J=1, K=X	J=X, K=1	J=X, K=0
D	D	Qn+1=D	D=0	D=1	D=0	D=1
T	T	Qn+1=T XOR Qn	T=0	T=1	T=1	T=0

6. Past Year Master Questions & Solutions

PYQ Master Problem (2017, 2020, 2021): Race-Around Condition & Master-Slave

Question: What is the “Race-around condition” in JK flip-flops? Why does it occur, and how is it resolved using a Master-Slave arrangement? [8 Marks]

Solution:

1. Definition & Cause: Refer to Section 3.1. State the inequality tp > tpd where clock pulse width exceeds logic gate delay.
2. Master-Slave Architecture: Draw the two-stage Master-Slave schematic (Section 4.1).
3. Operation & Isolation Proof: Explain that during CLK=1, Master accepts J,K inputs while Slave is isolated. At CLK → 0, Master shuts off and Slave passes state to Q. Because output feedback cannot re-enter the Master while the Slave is updating, the circuit toggles exactly once, successfully eliminating race-around.

---

5.03 Flip-Flop Conversions & Functional Transformation Mechanics

Related Concepts: 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) | 5.02 Flip-Flop Variants (Master-Slave JK, T & D Flip-Flops) & Triggering Mechanics | 5.04 Synchronous Sequential Circuit Analysis & Synthesis

Overview: Flip-flop conversion is the process of synthesizing combinational drive logic to convert an available Source Flip-Flop into a desired Target Flip-Flop. This systematic design technique allows any flip-flop type (SR, JK, D, or T) to emulate the operational characteristics of any other flip-flop type.

1. The Systematic 4-Step Conversion Algorithm [PYQ: 2017, 2018, 2024]

The conversion process follows a structured methodology: construct a combined conversion table, append source flip-flop excitation requirements, derive drive logic via K-Maps, and finally draw the logic diagram.

2. SR-to-JK Flip-Flop Conversion [PYQ: 2017, 2018]

• Available (Source) FF: SR Flip-Flop

• Desired (Target) FF: JK Flip-Flop

2.1 Conversion Table

Target Inputs (J, K)	Present State (Qn)	Next State (Qn+1)	Source SR Excitation (S, R)
0 0	0	0	0 X
0 0	1	1	X 0
0 1	0	0	0 X
0 1	1	0	0 1
1 0	0	1	1 0
1 0	1	1	X 0
1 1	0	1	1 0
1 1	1	0	0 1

2.2 K-Map Optimization for Drive Inputs S and R

1. For Input S(J, K, Qn): Grouping minterm m4 (100) and m6 (110) yields: S = J · Qn’

2. For Input R(J, K, Qn): Grouping minterm m3 (011) and m7 (111) yields: R = K · Qn

2.3 Synthesized Circuit Schematic

The SR flip-flop is driven by two 2-input AND gates where J is ANDed with Q’ to drive S, and K is ANDed with Q to drive R.

3. JK-to-SR Flip-Flop Conversion [PYQ: 2024]

• Available (Source) FF: JK Flip-Flop

• Desired (Target) FF: SR Flip-Flop

3.1 Conversion Table

Target Inputs (S, R)	Present State (Qn)	Next State (Qn+1)	Source JK Excitation (J, K)
0 0	0	0	0 X
0 0	1	1	X 0
0 1	0	0	0 X
0 1	1	0	X 1
1 0	0	1	1 X
1 0	1	1	X 0
1 1	0	X	X X
1 1	1	X	X X

3.2 Drive Logic Equations

From K-map simplification: J = S and K = R.

Practical Insight: Since J = S and K = R, connecting S directly to J and R directly to K transforms a JK flip-flop into an SR flip-flop without requiring any external logic gates!

4. JK-to-D & JK-to-T Conversions [PYQ: 2024]

4.1 Converting JK to D Flip-Flop

Goal: Force J = D and K = D’. Drive Equations: J = D and K = D’. Implementation: Pass D directly to J, and pass D through a NOT gate to K.

4.2 Converting JK to T Flip-Flop

Goal: Force J = T and K = T. Drive Equations: J = T and K = T. Implementation: Tie J and K together and connect them to a common input signal T.

5. Master Summary Table of Conversion Equations

Source FF	Target FF	Drive Logic Equations
SR	JK	S = J·Qn’, R = K·Qn
SR	D	S = D, R = D’
SR	T	S = T·Qn’, R = T·Qn
JK	SR	J = S, K = R
JK	D	J = D, K = D’
JK	T	J = T, K = T
D	T	D = T ⊕ Qn = T·Qn’ + T’·Qn
T	D	T = D ⊕ Qn = D·Qn’ + D’·Qn

6. Past Year Master Questions & Solutions

PYQ Master Problem (2017, 2018): SR to JK Conversion

Question: Convert an S-R flip-flop to a J-K flip-flop. Show all conversion tables, K-maps, and final logic diagrams. [8 Marks]

Solution:

1. Conversion Table Construction: Construct the 8-row table mapping target J,K and Qn to source S,R excitations (Section 2.1).

2. K-Map Derivation: Show 3-variable K-maps for S and R: S(J,K,Qn) = J·Qn’ and R(J,K,Qn) = K·Qn.

3. Circuit Diagram: Draw the SR flip-flop driven by two 2-input AND gates (Section 2.3).

---

5.04 Synchronous Sequential Circuit Analysis & Synthesis

Overview: The study of clocked sequential circuits involves two complementary procedures: Analysis (extracting state tables and state diagrams from a given logic schematic) and Synthesis (designing a gate-level logic schematic from verbal specifications, state equations, or state diagrams).

1. Mealy vs. Moore State Machine Models

Clocked sequential circuits are categorized based on how output signals are generated:

1.1 Structural Comparison

Feature	Mealy Machine	Moore Machine
Output Dependency	Function of Present Inputs AND Present State (Y = f(X, Q)).	Function of Present State ONLY (Y = f(Q)).
State Diagram Labels	Arcs labeled as Input / Output (X / Y).	State nodes labeled as State / Output (Q / Y).
Number of States	Requires fewer states for a given specification.	Requires more states (or equal) compared to Mealy.
Response Speed	Output changes asynchronously with input changes during active state.	Output changes synchronously strictly at active clock edge.
Glitch Susceptibility	Higher (input glitches propagate directly to output).	Lower (output is isolated from input glitches by state registers).

2. Analysis Algorithm for Clocked Sequential Circuits [PYQ: 2015, 2016, 2019, 2020, 2022]

Step 1: Extract Flip-Flop Input Equations & Output Equations from Schematic

Step 2: Substitute Input Equations into FF Characteristic Equations to get State Equations Q(t+1)

Step 3: Construct State Table for all Input/State combinations

Step 4: Draw State Diagram with Node Transitions

2.1 Master Analysis Example [PYQ: 2015, 2016, 2019, 2020, 2022]

Given Circuit Equations:

• Flip-Flop A (JK type): J_A = x · B, K_A = x’
• Flip-Flop B (JK type): J_B = x’, K_B = A ⊕ x
• Output Equation: Y = A · B · x

Step 1: Derive Next-State Equations

1. For Flip-Flop A (A_{t+1}): A_{t+1} = J_A A’ + K_A’ A = (xB)A’ + (x’)‘A = xA’B + xA = x(A + B)

2. For Flip-Flop B (B_{t+1}): B_{t+1} = J_B B’ + K_B’ B = (x’)B’ + (A ⊕ x)‘B

Step 2: Construct the State Table

Present State (A B)	Input (x)	Next State (A_{t+1} B_{t+1})	Output (Y)
0 0	0	0 1	0
0 0	1	0 0	0
0 1	0	0 1	0
0 1	1	1 0	0
1 0	0	0 0	0
1 0	1	1 1	0
1 1	0	0 0	0
1 1	1	1 0	1

3. Synthesis Algorithm for Clocked Sequential Circuits [PYQ: 2021, 2023, 2024, 2025]

Step 1: State Diagram / Verbal Spec

Step 2: State Table & Excitation Table Mapping

Step 3: K-Map Simplification for FF Drive Logic

Step 4: Draw Logic Diagram

3.1 Design Example: Synthesis from State Equations [PYQ: 2021, 2023, 2024, 2025]

Design Task: Synthesize a sequential circuit using D flip-flops for state equations: A_{t+1} = x A B + y A’ C + x y; B_{t+1} = x A’ + B C’

Synthesis Solution: Since the characteristic equation of a D flip-flop is Q_{n+1} = D, the required flip-flop input logic is obtained directly: D_A = x A B + y A’ C + x y; D_B = x A’ + B C’.

Implementation: Drive input D_A with a 3-input OR gate fed by AND terms (xAB), (yA’C), and (xy). Drive input D_B with a 2-input OR gate fed by (xA’) and (BC’).

4. Sequential Serial Adder Design [PYQ: 2019]

A Serial Adder adds two multi-bit binary numbers bit-by-bit sequentially using a single Full Adder circuit and a D flip-flop to store the carry bit between clock cycles.

4.1 State & Excitation Table for Serial Adder

Let Q_n be the present carry stored in the D flip-flop. Inputs are A and B.

Inputs (A B)	Present Carry (Q_n)	Next Carry (Q_{n+1} = D)	Sum Output (S)
0 0	0	0	0
0 0	1	0	1
0 1	0	0	1
0 1	1	1	0
1 0	0	0	1
1 0	1	1	0
1 1	0	1	0
1 1	1	1	1

4.2 Derived Logic Equations

• Sum Equation: S = A ⊕ B ⊕ Q_n
• Carry (Flip-Flop Input) Equation: D = A B + A Q_n + B Q_n

5. Past Year Master Questions & Solutions

PYQ Master Problem (2019): Serial Adder Synthesis. Question: Design a Serial Adder using a sequential logic procedure. Show state table, logic equations, and block diagram. [8 Marks]

Solution:

1. System Definition: State that a serial adder requires 1 Full Adder + 1 D Flip-Flop for carry storage.

2. State Table: Draw the 8-row table mapping inputs A, B and carry Q_n to Sum S and Next Carry D.

3. Logic Expressions: S = A ⊕ B ⊕ Q_n and D = AB + BQ_n + AQ_n.

4. Block Diagram: Draw Full Adder block connected to D Flip-Flop feedback path.

---

5.05 State Reduction Algorithms & Output Sequence Analysis

Related Concepts: 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) | 5.04 Synchronous Sequential Circuit Analysis & Synthesis | 5.03 Flip-Flop Conversions & Functional Transformation Mechanics

5.05 State Reduction Algorithms & Output Sequence Analysis

Overview In sequential circuit design, initial state diagrams derived from verbal specifications often contain redundant states. State Reduction is a systematic optimization algorithm that eliminates equivalent states without altering the input-output behavior. Reducing the total number of states decreases the required number of flip-flops (N = ⌈log₂ M⌉), significantly reducing hardware complexity and cost.

1. Concept of State Equivalence [PYQ: 2015, 2016, 2018]

Definition of Equivalent States [PYQ: 2015, 2016, 2018] Two states Si and Sj in a sequential circuit are defined as equivalent (Si ≡ Sj) if and only if for every possible input sequence applied to the circuit:

1. They produce identical output sequences.
2. They transition to identical or equivalent next states.

2. The Row-Elimination State Reduction Algorithm [PYQ: 2015–2025]

• Step 1: Inspect State Table for rows with identical Next States and Outputs • Step 2: Identify Equivalent Pair (Si = Sj) • Step 3: Remove Row Sj from State Table • Step 4: Replace all occurrences of Sj with Si throughout the table • Step 5: Final Reduced State Table Complete

3. Master Worked Example: 7-State Table Reduction [PYQ: Heavily Tested: 2016, 2018, 2022, 2023, 2024, 2025]

3.1 Unreduced Initial State Table

Present State	Next State (x=0)	Next State (x=1)	Output (x=0)	Output (x=1)
a	a	b	0	0
b	c	d	0	0
c	a	d	0	0
d	e	f	0	1
e	a	f	0	1
f	g	f	0	1
g	a	f	0	1

3.2 Step-by-Step Reduction Execution

Step 1: Identify First Equivalent Pair Look at states e and g: • Next State (x=0): Both go to a. • Next State (x=1): Both go to f. • Outputs: Both produce 0 for x=0 and 1 for x=1. Therefore, e ≡ g • Action: Eliminate row g. Replace all occurrences of g with e in the state table.

3.3 Final Reduced State Table

Present State	Next State (x=0)	Next State (x=1)	Output (x=0)	Output (x=1)
a	a	b	0	0
b	c	d	0	0
c	a	d	0	0
d	e	d	0	1
e	a	d	0	1

Hardware Optimization Result The original state table required 7 states (⌈log₂ 7⌉ = 3 flip-flops). The reduced table requires only 5 states (⌈log₂ 5⌉ = 3 flip-flops), reducing state transitions and logic gate complexity significantly.

4. Output Sequence Tracking Analysis [PYQ: 2016, 2024]

Input Sequence (X): 0 1 1 1 0 0 1 0 0 1 1 State Sequence: a → a → b → d → d → e → a → b → c → a → b → d Output Sequence (Y): 0 0 0 1 0 0 0 0 0 0 0

5. State Assignment Rules & Methods

Assignment Method	Description	Code for 4 States (S₀…S₃)	Advantage
Binary Assignment	Standard sequential binary numbers.	00, 01, 10, 11	Minimum number of flip-flops used.
Gray Code Assignment	Adjacent states differ in only 1 bit position.	00, 01, 11, 10	Reduces switching noise and glitches.
One-Hot Assignment	Dedicated flip-flop for each state.	0001, 0010, 0100, 1000	Simplifies combinational logic (no decoders).

---

5.06 Chapter 5 Master PYQ Solutions & Synthesis Puzzles

Dedicated problem-solving supplement for Chapter 5 (Sequential Logic & Flip-Flops). Contains step-by-step worked derivations for advanced 3-variable state equations, minterm state synthesis, and state diagram conversion puzzles asked in past university exams.

Related Concepts: 5.04 Synchronous Sequential Circuit Analysis & Synthesis | 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) | 5.05 State Reduction Algorithms & Sequence Analysis

1. 3-Variable JK State Equation Synthesis [PYQ: 2024, 2025]

PYQ Master Problem (2024, 2025): 3-Flip-Flop JK Circuit Synthesis

Question: Design a sequential circuit described by the following state equations using JK flip-flops [12 Marks]:

A(t+1) = x A B + y A’ C + x y

B(t+1) = x A C + y B’ C’

C(t+1) = x’ B + y A’ B’

1.1 Derivation Methodology

For any JK flip-flop, the characteristic equation is: Q(t+1) = J Q’ + K’ Q

To find J and K for a given target expression Q(t+1), expand the target expression into two terms: one multiplied by Q’ (which gives J) and one multiplied by Q (which gives K’).

1. Derive Inputs JA and KA for Flip-Flop A:

Target: A(t+1) = x A B + y A’ C + x y = A’ (y C + x y) + A (x B + x y)

• 1. Coefficient of A’ is JA: JA = y C + x y = y (C + x)
  2. Coefficient of A is KA’: KA’ = x B + x y = x (B + y) ⇒ KA = (x (B + y))’ = x’ + B’ y’

2. Derive Inputs JB and KB for Flip-Flop B:

Target: B(t+1) = x A C + y B’ C’ = B’ (y C’) + B (x A C)

• 1. Coefficient of B’ is JB: JB = y C’
  2. Coefficient of B is KB’: KB’ = x A C ⇒ KB = (x A C)’ = x’ + A’ + C’

3. Derive Inputs JC and KC for Flip-Flop C:

Target: C(t+1) = x’ B + y A’ B’ = C’ (x’ B + y A’ B’) + C (0)

• 1. Coefficient of C’ is JC: JC = x’ B + y A’ B’
  2. Coefficient of C is KC’: KC’ = 0 ⇒ KC = 1

2. Minterm State Equation Synthesis [PYQ: 2021, 2023]

PYQ Master Problem (2021, 2023): Minterm State Equations

Question: Design a sequential circuit whose state equations are given below [12 Marks]:

A1(t+1) = Sigma m(4, 6)

A2(t+1) = Sigma m(1, 2, 5, 6)

y(A1, A2, x) = Sigma m(3, 7)

Where inputs are A1, A2, x (3-variable domain: A1 is MSB, x is LSB).

2.1 State Minimization via K-Maps

1. For A1(t+1) = Sigma m(4, 6): Minterms m4 (100) and m6 (110): A1(t+1) = A1 . x’
2. For A2(t+1) = Sigma m(1, 2, 5, 6): Minterms m1 (001), m2 (010), m5 (101), m6 (110): Grouping m1, m5 gives A2’ x. Grouping m2, m6 gives A2 x’. A2(t+1) = A2’ x + A2 x’ = A2 XOR x
3. For Output y(A1, A2, x) = Sigma m(3, 7): Minterms m3 (011) and m7 (111): y = A2 . x

2.2 D Flip-Flop Drive Expressions

Since Q(t+1) = D:

D1 = A1 . x’

D2 = A2 XOR x

y = A2 . x

---

Related Concepts: 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) | 5.02 Flip-Flop Variants (Master-Slave JK, T & D Flip-Flops) & Triggering Mechanics | 5.08 Flip-Flop Mathematical Derivations & Transformation Proofs

5.07 Sequential Architecture, Triggering Mechanics & Race-Around Analysis

Overview

Sequential circuits combine combinational logic with memory storage elements in a closed feedback loop. Understanding the internal gate-level construction of edge-triggered devices, clock setup/hold windows, and eliminating the unstable Race-Around Condition via Master-Slave architectures is fundamental to digital system design.

---

1. Generic Sequential Circuit Architecture [PYQ: 2017, 2019]

A sequential circuit consists of a Combinational Logic Block and Memory Elements (latches or flip-flops) connected in a closed feedback loop.

 +---------------------------------------+

| COMBINATIONAL LOGIC BLOCK |

External Inputs -⇒| |-⇒ External Outputs

X(t) | Next-State Equations Y(t) = f(X, Q) | Z(t) = g(X, Q)

+---------------------------------------+

| ^

| Next State | Present State

v Y(t) | Q(t)

+---------------------------------------+

| MEMORY ELEMENTS |

System Clock ----⇒| (Flip-Flops / Latches) |

CLK +---------------------------------------+



1.1 Structural Components

• 1. Inputs $X(t)$: External digital signals applied to the circuit.
• 2. Combinational Logic: Computes next-state signals $Y(t)$ and external outputs $Z(t)$.
• 3. Memory Elements: Array of flip-flops storing the present state $Q(t)$.
• 4. Feedback Path: Returns $Q(t)$ to combinational inputs, establishing memory hysteresis.
• 5. Clock Line ($CLK$): Synchronizes state updates across all memory elements.

---

2. Clock Triggering Mechanics & Setup/Hold Windows

Triggering Mode	Waveform Condition	Operational Behavior
Active-HIGH Level	$CLK=1$	Output continuously tracks inputs while clock is HIGH.
Active-LOW Level	$CLK=0$	Output continuously tracks inputs while clock is LOW.
Positive Edge (Rising)	$CLK\uparrow (0\to 1)$	Output transitions strictly at the rising edge instant.
Negative Edge (Falling)	$CLK\downarrow (1\to 0)$	Output transitions strictly at the falling edge instant.

2.1 Setup ($t\_su$) and Hold ($t\_h$) Time Constraints

Key Exam Checkpoint: Timing Windows

* Setup Time ($t\_su$): Minimum time data input $D$ must remain stable BEFORE the active clock edge.

* Hold Time ($t\_h$): Minimum time data input $D$ must remain stable AFTER the active clock edge.

* Violation Result: Entering a metastable state where output oscillates unpredictably between $0$ and $1$.

---

3. Internal Gate-Level Construction of Edge-Triggered D Flip-Flop [PYQ: 2015, 2016, 2017, 2019, 2022]

An edge-triggered D flip-flop uses three interconnected NAND-gate latches to sample input $D$ strictly during the rising edge of $CLK$.

 +------------+

D —⇒| NAND 1 |----+

| | | +------------+

CLK -⇒| NAND 2 |----+⇒| NAND 3 |---⇒ Output Q

+------------+ | (SR Latch) |

| +------------+

v ^

+------------+ |

| NAND 4 |--------------+---⇒ Output Q’

+------------+



3.1 Operational Phases

• 1. $CLK=0$: Gates 2 and 3 outputs are held at logic $1$. The output SR latch holds its previous state $Q$.
• 2. $CLK\uparrow (0\to 1)$ Transition: Gate 2 output drops to $0$ if $D=1$, setting output $Q\to 1$. Gate 4 output drops to $0$ if $D=0$, resetting output $Q\to 0$.
• 3. $CLK=1$ (Level Held): Gate 2 or 4 locks out further changes in $D$, rendering the device immune to input noise until the next clock edge.

---

4. In-Depth Race-Around Condition Analysis [PYQ: 2017, 2020, 2021]

4.1 The Timing Inequality

In a level-triggered JK flip-flop, setting $J=1,K=1$ causes output $Q$ to toggle ($Q\_n+1=\overline{Q\_n}$). If clock pulse width $t\_p$ exceeds propagation delay $t\_pd$:

$t\_pd<t\_p<T$

Output $Q$ toggles continuously ($0\to 1\to 0\to 1\dots$) during $t\_p$. The state when $CLK$ falls to $0$ is unpredictable.

4.2 Methods of Elimination

• 1. Propagation Delay Increase: Ensure $t\_p<t\_pd$ *(unrealistic in high-speed systems)*.
• 2. Edge-Triggering: Sample inputs strictly at edge transitions.
• 3. Master-Slave Architecture: Isolate input sampling from output updates using dual cross-coupled latches.

---

5. Master-Slave JK Flip-Flop NAND Logic Schematic [PYQ: 2015, 2019]

 +-----------------------+ +-----------------------+

| MASTER LATCH | | SLAVE LATCH |

J -⇒| NAND 3 NAND 1 |---⇒ NAND 7 NAND 5 |---⇒ Q ----+

CLK ⇒| (CLK) | Y | (CLK’) | |

Q’ ⇒| NAND 4 NAND 2 |---⇒ NAND 8 NAND 6 |---⇒ Q’—+ |

+-----------------------+ Y’ +-----------------------+ | |

^ ^ ^ ^ | |

K -------|---------------+ | | | |

+--------------[ NOT Gate ]---+ | | |

(CLK’) +----------------+ |

|



5.1 Step-by-Step Operation Proof

• * $CLK=1$ ($\overline{CLK}=0$): Master latch active; $Y,Y^{\prime }$ update based on $J,K$. Slave latch isolated ($CL{K}^{\prime }=0$). Output $Q$ remains constant.
• * $CLK\downarrow (1\to 0)$ ($\overline{CLK}=1$): Master latch turns OFF; Slave latch turns ON, loading $Y,Y^{\prime }$ to final output $Q$. Since Master is OFF, output $Q$ cannot feed back to change $Y$, eliminating race-around completely.

---

Related Concepts: 5.01 Sequential Logic Fundamentals, Latches & Flip-Flops (SR & JK) | 5.03 Flip-Flop Conversions & Functional Transformation Mechanics | 5.07 Sequential Architecture, Triggering Mechanics & Race-Around Analysis

5.08 Flip-Flop Mathematical Derivations & Transformation Proofs

> [!abstract] Overview> Rigorous algebraic derivations for flip-flop characteristic equations, structural inversion proofs (forming D and T flip-flops from JK units), and step-by-step conversion logic synthesis tables.

1. K-Map Derivations of Characteristic Equations

1.1 SR Flip-Flop Characteristic Equation

• Minterm Mapping: Minterms $m\_1(001)$, $m\_4(100)$, $m\_5(101)$, and Don’t Care terms $m\_6(110),m\_7(111)$.
• Grouping:
  • Group 1 ($m\_1,m\_5$): $\overline{R}Q\_n$
  • Group 2 ($m\_4,m\_5,m\_6,m\_7$): $S$

$Q\_n+1=S+\overline{R}Q\_n\text{subject to }S\cdot R=0$

1.2 JK Flip-Flop Characteristic Equation

• Minterm Mapping: Minterms $m\_1(001)$, $m\_4(100)$, $m\_5(101)$, $m\_6(110)$.
• Grouping:
  • Group 1 ($m\_4,m\_5$): $J\overline{Q\_n}$
  • Group 2 ($m\_1,m\_5$): $\overline{K}Q\_n$

$Q\_n+1=J\overline{Q\_n}+\overline{K}Q\_n$

1.3 T Flip-Flop Characteristic Equation

• Minterm Mapping: $m\_1(01)$, $m\_2(10)$.

$Q\_n+1=T\overline{Q\_n}+\overline{T}Q\_n=T\oplus Q\_n$

2. Inversion Properties & Structural Proofs [PYQ: 2024]

> [!example] Proof: Forming T and D Flip-Flops from JK Units [PYQ: 2024]> Part A: Tying Inputs Together ($J=K=T$)

Substitute $J=T$ and $K=T$ into $Q\_n+1=J\overline{Q\_n}+\overline{K}Q\_n$: $Q\_n+1=T\overline{Q\_n}+\overline{T}Q\_n=T\oplus Q\_n$ This matches the characteristic equation of a **T Flip-Flop**.

**Part B: Tying Inputs via Inverter ($J=D,K=\overline{D}$)** Substitute $J=D$ and $K=\overline{D}$ into $Q\_n+1=J\overline{Q\_n}+\overline{K}Q\_n$: $Q\_n+1=D\overline{Q\_n}+\overline{(\overline{D})}Q\_n=D\overline{Q\_n}+DQ\_n=D(\overline{Q\_n}+Q\_n)=D(1)=D$ This matches the characteristic equation of a **D Flip-Flop**.

3. Systematic Conversion Mechanics & Circuits [PYQ: 2017, 2018, 2024]

3.1 SR-to-JK Conversion

• Drive Logic: $S=J\overline{Q\_n},R=KQ\_n$
• Schematic: SR flip-flop driven by two 2-input AND gates.

3.2 JK-to-SR Conversion

• Drive Logic: $J=S,K=R$
• Schematic: Direct wiring ($S\to J$ and $R\to K$).

3.3 D-to-T and T-to-D Conversions

• D-to-T Conversion: $D=T\oplus Q\_n$ (Drive D input with XOR gate fed by $T$ and $Q\_n$).
• T-to-D Conversion: $T=D\oplus Q\_n$ (Drive T input with XOR gate fed by $D$ and $Q\_n$).

---

5.09 Sequential Design Blueprints, Serial Adder & State Algorithms

Complete engineering blueprint for sequential circuit synthesis, serial adder design, state reduction algorithms, and output sequence tracking for arbitrary bitstreams.

Related Concepts: 5.04 Synchronous Sequential Circuit Analysis & Synthesis | 5.05 State Reduction Algorithms & Output Sequence Analysis | 5.06 Chapter 5 Master PYQ Solutions & Synthesis Puzzles

1. 7-Step Sequential Design Blueprint [PYQ: 2024]

1. Step 1: Verbal Specification to State Diagram: Draw state nodes and directed transition arrows (X / Y).
2. Step 2: State Table Formulation: List Present State Q(t), External Inputs X, Next State Q(t+1), and Outputs Y.
3. Step 3: State Reduction: Apply row elimination (Si ≡ Sj) to eliminate redundant states.
4. Step 4: State Assignment: Assign binary codes (00, 01, 10, …) to reduced state letters.
5. Step 5: Excitation Table Mapping: Map required Qn → Qn+1 transitions to target flip-flop inputs.
6. Step 6: K-Map Logic Minimization: Simplify flip-flop drive equations J, K, D, T and output Y.
7. Step 7: Logic Schematic Drawing: Connect combinational logic gates to flip-flop clock and data inputs.

2. Serial Adder Design Procedure [PYQ: 2019]

A Serial Adder adds two multi-bit binary numbers bit-by-bit over consecutive clock cycles using 1 Full Adder and 1 D Flip-Flop (to store the carry bit).

 Serial Input A ---⇒[ FULL ADDER ]---⇒ Sum Output (S)

Serial Input B ---⇒[ ]

^ | Carry Out (C_out)

| v

+[ D FLIP-FLOP ] (Stores Carry Q_n for next bit)

2.1 State & Logic Equations

• Sum Output Equation: S = A ⊕ B ⊕ Qn
• Next Carry (D Input) Equation: D = AB + AQn + BQn

3. Formal State Reduction Algorithm & Sequence Tracking [PYQ: 2016, 2024]

Equivalent State Condition: Two states Si and Sj are equivalent (Si ≡ Sj) if for every possible input string, they yield identical outputs and transition to identical or equivalent next states.

3.1 Sequence Tracking Tutorial

For input bitstream X = 01110010011 on reduced state table starting at state a:

• State Sequence: a → a → b → d → d → e → a → b → c → a → b → d
• Output Sequence: Y = 0 0 0 1 0 0 0 0 0 0 0

---

00 Chapter 5 Active-Recall Diagnostic Quiz (Sequential Logic)

Test your conceptual understanding and exam readiness before reading the full study notes. Attempt each question mentally or on scrap paper before expanding the solution box.

Question 1: Combinational vs. Sequential Feedback

Why can a combinational circuit never store binary state information?

Solution

A combinational circuit has no memory elements and no feedback path from output to input. Output values are strictly determined by current inputs X(t). Storing state requires a bistable feedback loop where past outputs feed back into the combinational logic.

Question 2: Flip-Flop Memory Property

Why is a flip-flop specifically defined as a “1-bit memory element”?

Solution

A flip-flop is a bistable multivibrator that has two stable operating states (Q=1 or Q=0). Once set into a state by a trigger signal, it remains in that state indefinitely (storing 1 bit of data) as long as power is maintained, until another trigger signal changes its state.

Question 3: Latch vs. Flip-Flop Glitch Sensitivity

Why are latches more susceptible to input noise glitches than edge-triggered flip-flops?

Solution

Latches are level-triggered, meaning their output continually tracks inputs throughout the entire duration that the Enable clock signal remains HIGH. Any noise glitch during this active level propagates to the output. Edge-triggered flip-flops sample inputs strictly at the discrete instant of a clock transition (0 1 or 1 0), ignoring input noise outside this setup/hold window.

Question 4: SR Latch Invalid State

In a NOR-gate SR latch, why is S=1, R=1 considered a forbidden/invalid input condition?

Solution

Applying S=1, R=1 forces both NOR outputs to 0 (Q=0 and Q’=0), violating the fundamental complementary property Q = NOT Q’. When inputs return to 00, the final state is unpredictable because it depends on which NOR gate turns off first (a race condition).

Question 5: JK Refinement Proof

Mathematically prove why the JK flip-flop eliminates the invalid state of the SR flip-flop.

Solution

Substitute J=1, K=1 into the JK characteristic equation Qn+1 = J(NOT Qn) + (NOT K)Qn: Qn+1 = (1)(NOT Qn) + (NOT 1)Qn = NOT Qn + 0 = NOT Qn. The output toggles deterministically to its complement, completely replacing the illegal state.

Question 6: Race-Around Condition Threshold

Under what exact physical condition does the Race-Around Condition occur in a JK flip-flop?

Solution

It occurs in a level-triggered JK flip-flop when J=1, K=1 and the clock pulse width tp is greater than the propagation delay tpd of the logic gates (tp > tpd). The output toggles repeatedly (0 1 0 1 …) during the clock pulse, leaving the final output state uncertain.

Question 7: Master-Slave Inversion Isolation

How does a Master-Slave JK flip-flop prevent race-around without reducing clock pulse width?

Solution

It uses two latches clocked by inverted clock signals (CLK and NOT CLK). During CLK=1, the Master accepts inputs while the Slave is disabled. When CLK falls to 0, the Master shuts off and the Slave updates final output Q. Because output feedback cannot reach the Master while the Slave is updating, toggling occurs at most once per clock pulse.

Question 8: D Flip-Flop Characteristic Equation

Derive the characteristic equation of a D flip-flop starting from the SR characteristic equation Qn+1 = S + (NOT R)Qn.

Solution

Insert S = D and R = NOT D into Qn+1 = S + (NOT R)Qn: Qn+1 = D + NOT (NOT D)Qn = D + D Qn = D(1 + Qn) = D. Therefore, Qn+1 = D.

Question 9: Flip-Flop Conversion Rule

What is the general 4-step procedure for converting a Source Flip-Flop into a Target Flip-Flop?

Solution

1. 1. Construct the Target FF characteristic table (Target Inputs + Qn Qn+1).
2. 2. Append required Source FF excitation inputs for each Qn Qn+1 transition.
3. 3. Minimize Source inputs as functions of Target inputs and Qn using K-maps.

4. Draw the combinational drive logic driving the Source FF terminals.

Question 10: State Reduction Equivalence Condition

What two criteria must be satisfied for two states Si and Sj in a state table to be declared equivalent (Si Sj)?

Solution

For every possible input sequence applied to the circuit, states Si and Sj must: 1. Produce identical output sequences. 2. Transition to identical or equivalent next states.