Sequential Circuits

Overview

In our study of digital logic thus far, we have concentrated on combinational circuits, where the output is a direct function of the present inputs alone. We now advance to a more sophisticated class of circuits known as sequential circuits. The defining characteristic of these systems is memory; their outputs depend not only on the current input values but also on the past sequence of inputs. This history is stored internally as the circuit's "state." This ability to store information introduces the dimension of time into our analysis, enabling the design of systems that perform complex, time-dependent operations.

A mastery of sequential circuits is indispensable for success in the GATE examination. A significant portion of the Digital Logic syllabus is dedicated to this topic, with questions frequently appearing on the analysis of state machines and the design of counters, registers, and sequence detectors. This chapter provides the foundational principles required to tackle such problems systematically. We will develop a rigorous framework for understanding how information is stored and how state transitions are controlled, which are the core competencies assessed by the examination. Our exploration begins with the fundamental memory elements and progresses to the formal procedures for the analysis and synthesis of complete sequential systems.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Memory Elements | Fundamental building blocks: latches and flip-flops. |
| 2 | Design and Analysis | Systematic methods for circuit synthesis and evaluation. |

---

Learning Objectives

---

We now turn our attention to Memory Elements...
## Part 1: Memory Elements

Introduction

In our study of digital logic, we have thus far focused on combinational circuits, where the output at any instant is a function solely of the inputs at that same instant. Such circuits are memoryless. We now turn our attention to a more sophisticated class of circuits known as sequential circuits. The defining characteristic of a sequential circuit is its inclusion of memory; its output depends not only on the current inputs but also on the sequence of past inputs. This "memory" is achieved through the use of storage elements.

These fundamental storage units, capable of holding a single bit of information ($0$ or $1$), are the building blocks of all sequential logic. They are formally referred to as bistable multivibrators, as they possess two stable states that can be used to represent binary values. We will explore the two primary categories of these memory elements: latches, which are level-triggered, and flip-flops, which are edge-triggered. A thorough understanding of their operation, characteristic equations, and interrelationships is indispensable for the analysis and design of registers, counters, and finite state machines.

---

---

Latches: Level-Triggered Memory

Latches are the most fundamental type of memory element. Their defining feature is that their output can change in response to their data inputs as long as a control signal, often called an enable or gate, is at a specific logic level (e.g., HIGH). This behavior is termed level-triggering. While the enable signal is active, the latch is said to be "transparent."

1. The SR Latch

The Set-Reset (SR) latch is the most elementary bistable circuit. It can be constructed from two cross-coupled NOR gates or two cross-coupled NAND gates. We shall first examine the NOR gate implementation.

R

S

Q

Q'

The operation is defined by its inputs, $S$ (Set) and $R$ (Reset):

• Hold State ($S=0, R=0$): With both inputs at logic 0, the cross-coupled feedback maintains the current state. If $Q=1$, it remains $1$. If $Q=0$, it remains $0$. This is the memory-holding action.


• Set State ($S=1, R=0$): A logic 1 on the $S$ input forces the output $Q$ to 1 (and $Q'$ to 0).


• Reset State ($S=0, R=1$): A logic 1 on the $R$ input forces the output $Q$ to 0 (and $Q'$ to 1).


• Forbidden/Invalid State ($S=1, R=1$): For a NOR latch, this input condition forces both $Q$ and $Q'$ to 0. This violates the complementary nature of the outputs. Furthermore, if $S$ and $R$ then transition to 0 simultaneously, the final state of the latch is unpredictable, leading to a race condition. This input combination is therefore disallowed.

The behavior is summarized by the characteristic equation. Let $Q$ represent the current state and $Q_{next}$ represent the next state.

2. The D Latch (Gated Latch)

To overcome the invalid state problem of the SR latch, we introduce the D (Data) latch. It has a single data input, $D$, and an enable input, $E$ (or sometimes labeled $G$ for gate). The D latch ensures that the $S$ and $R$ inputs to its internal, underlying SR latch are never simultaneously active.

When $E=1$, the latch is "transparent," meaning the output $Q$ follows the data input $D$. Whatever value is on the $D$ line is passed directly to the output $Q$. When $E=0$, the latch is "closed" or "opaque." The output $Q$ holds the last value it had just before $E$ transitioned to 0, irrespective of any subsequent changes in the $D$ input.

A very common and elegant implementation of a D latch uses a 2-to-1 multiplexer with a feedback connection, a configuration directly relevant to GATE questions.

Consider the circuit below:

2x1 MUX

0
Q


1
D

E

Q

Let us analyze this circuit. The select line of the multiplexer is the enable input $E$, and the data input is $D$.

Worked Example:

Problem: Derive the characteristic equation for the circuit shown above, which consists of a 2x1 MUX with its output $Q$ fed back to its '0' input. The '1' input is driven by $D$ and the select line by $E$.

Solution:

Step 1: Write the general equation for a 2-to-1 multiplexer. The output $Y$ is given by $Y = S' \cdot I_0 + S \cdot I_1$, where $S$ is the select line and $I_0, I_1$ are the data inputs.

Step 2: Map the variables from the given circuit to the general MUX equation.

• The output $Y$ is $Q_{next}$.


• The select line $S$ is the enable input $E$.


• The input $I_0$ is connected to the output $Q$.


• The input $I_1$ is the data input $D$.

Step 3: Substitute these mappings into the MUX equation.

Result: The characteristic equation is $Q_{next} = ED + E'Q$. This is precisely the characteristic equation of a D Latch.

We can analyze this equation further:

• If $E=0$: $Q_{next} = (0) \cdot D + (1) \cdot Q \implies Q_{next} = Q$. The circuit holds its current state.


• If $E=1$: $Q_{next} = (1) \cdot D + (0) \cdot Q \implies Q_{next} = D$. The output follows the input $D$.

This confirms that a 2x1 MUX with this specific feedback configuration functions as a D Latch.

---

Flip-Flops: Edge-Triggered Memory

While latches are useful, their transparent nature can be problematic in more complex synchronous systems where we need state changes to occur at precise, discrete instants in time. Flip-flops solve this by being edge-triggered. A flip-flop changes its state only at a specific transition of a control signal called the clock ($CLK$). This transition can be either the rising (positive) edge or the falling (negative) edge of the clock pulse.

0
1



Rising
Edge



Falling
Edge

This edge-triggered property ensures that all state changes in a synchronous system occur simultaneously, synchronized by the clock edge, preventing the timing issues that can arise with transparent latches.

1. The D Flip-Flop

The D flip-flop is the most widely used flip-flop. It is a simple, edge-triggered memory element that captures the value of its $D$ input at the active clock edge and stores it.

Its operation is straightforward: on the active clock edge (e.g., the rising edge), the output $Q$ becomes equal to the value of the input $D$ at that instant. At all other times, including during changes in $D$ when the clock is stable, the output $Q$ remains unchanged. This behavior is captured by a very simple characteristic equation.

2. The JK Flip-Flop

The JK flip-flop is a more versatile element, often called a "universal" flip-flop because it can be configured to emulate other types (like D or T). It has two inputs, $J$ and $K$.

• Hold ($J=0, K=0$): The flip-flop holds its current state.
• Reset ($J=0, K=1$): The flip-flop is reset to $Q=0$.
• Set ($J=1, K=0$): The flip-flop is set to $Q=1$.
• Toggle ($J=1, K=1$): This is the unique feature. The flip-flop's output inverts its current state (if $Q=0$, it becomes $1$; if $Q=1$, it becomes $0$). This toggle behavior is crucial for building counters.

3. The T Flip-Flop

The T (Toggle) flip-flop has a single input, $T$. It is a simplified version of the JK flip-flop.

• If $T=0$: The flip-flop holds its current state ($Q_{next} = Q$).
• If $T=1$: The flip-flop toggles its state ($Q_{next} = Q'$).

A T flip-flop can be easily constructed from a JK flip-flop by connecting the $J$ and $K$ inputs together to form the single $T$ input.

---

Characteristic and Excitation Tables

For analysis, we use characteristic tables, which define the next state ($Q_{next}$) based on current inputs and the current state ($Q$). For design, we use excitation tables, which work in reverse. An excitation table specifies the necessary input(s) to cause a particular state transition (from $Q$ to $Q_{next}$).

Summary of Characteristic Tables:

| Type | Inputs | $Q_{next}$ | Comment |
| :--- | :--- | :--- | :--- |
| D | $D$ | $D$ | Stores D |
| T | $T, Q$ | $T \oplus Q$ | Toggles if T=1 |
| SR | $S, R, Q$ | $S+R'Q$ | $SR=0$ |
| JK | $J, K, Q$ | $JQ'+K'Q$ | Universal |

Summary of Excitation Tables:

| Transition | D Input | T Input | S Input | R Input | J Input | K Input |
| :--- | :---: | :---: | :---: | :---: | :---: | :---: |
| $Q \to Q_{next}$ | $D$ | $T$ | $S$ | $R$ | $J$ | $K$ |
| $0 \to 0$ | 0 | 0 | 0 | X | 0 | X |
| $0 \to 1$ | 1 | 1 | 1 | 0 | 1 | X |
| $1 \to 0$ | 0 | 1 | 0 | 1 | X | 1 |
| $1 \to 1$ | 1 | 0 | X | 0 | X | 0 |

(Note: 'X' denotes a "don't care" condition, which is extremely useful for logic minimization during circuit design.)

---

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A T flip-flop is created by modifying a JK flip-flop. How should the inputs of the JK flip-flop, $J$ and $K$, be connected to form the T input?" options=["$J = T, K = T'$","$J = K = T$","$J = T', K = T$","$J = 1, K = T$"] answer="$J = K = T$" hint="Recall the characteristic equations. The goal is to make the JK flip-flop's behavior match the T flip-flop's behavior for both $T=0$ and $T=1$." solution="
Step 1: Write the characteristic equation for a T flip-flop.

Step 2: Write the characteristic equation for a JK flip-flop.

Step 3: We need to find connections for $J$ and $K$ in terms of T such that the JK equation becomes the T equation. Let's test the option $J = K = T$.

Step 4: Substitute $J = T$ and $K = T$ into the JK equation.

Step 5: Compare the resulting equation with the T flip-flop's equation.

The equations match. Therefore, connecting J and K together to form the T input converts a JK flip-flop into a T flip-flop.

Result: The correct connection is $\boxed{J = K = T}$.
"
:::

:::question type="NAT" question="A clock signal with a frequency of 20 MHz is applied to the clock input of a D flip-flop. The $Q'$ output of the flip-flop is connected to its $D$ input. What is the frequency of the signal at the $Q$ output, in MHz?" answer="10" hint="When $Q'$ is fed back to $D$, the D flip-flop behaves as a specific type of flip-flop. Analyze its behavior on each clock cycle." solution="
Step 1: Analyze the circuit configuration. The $D$ input is connected to the $Q'$ output.

Step 2: Write the characteristic equation of a D flip-flop.

Step 3: Substitute the connection from Step 1 into the equation from Step 2.

Step 4: This resulting characteristic equation, $Q_{next} = Q'$, signifies that the flip-flop will toggle its state on every active clock edge. This is the behavior of a T flip-flop with its $T$ input tied to logic 1.

Step 5: A device that toggles on every clock pulse acts as a frequency divider by a factor of 2. The output waveform will have a period twice as long as the input clock waveform.

Step 6: Calculate the output frequency.

Result: The frequency of the signal at the Q output is $\boxed{10 \text{ MHz}}$.
"
:::

:::question type="MSQ" question="Which of the following statements about an $SR$ latch constructed from two cross-coupled NOR gates are correct?" options=["When $S=1$ and $R=0$, the output $Q$ is set to 1.","When $S=0$ and $R=0$, the latch holds its previous state.","When $S=1$ and $R=1$, both outputs $Q$ and $Q'$ become 0.","The input combination $S=1, R=1$ is a valid operating condition."] answer="When $S=1$ and $R=0$, the output $Q$ is set to 1.,When $S=0$ and $R=0$, the latch holds its previous state.,When $S=1$ and $R=1$, both outputs $Q$ and $Q'$ become 0." hint="Evaluate the behavior of the NOR latch for each given input combination. Recall the definition of the forbidden state." solution="

• Option A ($S=1, R=0$): This is the SET condition. The output of the lower NOR gate ($Q$) becomes $(S+Q)' = (1+Q)' = 0' = 1$. The output of the upper NOR gate ($Q'$) becomes $(R+Q)' = (0+1)' = 1' = 0$. So, $Q$ is set to 1. This statement is correct.


• Option B ($S=0, R=0$): This is the HOLD condition. If $Q$ was 1, $Q'$ is 0. The inputs to the lower gate are $S=0, Q'=0$, so $Q$ remains $(0+0)'=1$. The inputs to the upper gate are $R=0, Q=1$, so $Q'$ remains $(0+1)'=0$. The state is held. This statement is correct.


• Option C ($S=1, R=1$): For the upper NOR gate, the output $Q'$ is $(R+Q)' = (1+Q)' = 0$. For the lower NOR gate, the output $Q$ is $(S+Q')' = (1+Q')' = 0$. Both outputs become 0. This statement is correct.


• Option D ($S=1, R=1$): This condition forces $Q=Q'=0$, which violates the fundamental property that the outputs should be complementary. It is known as the forbidden or invalid state. Therefore, this statement is incorrect.

"
:::

:::question type="MCQ" question="Consider a circuit built with a 2-to-1 multiplexer where the output $Y$ is connected to an AND gate along with the select line $S$. The MUX inputs are $I_0=A$ and $I_1=B$. The MUX select line is $S$. The final output $Z$ of the circuit is $Z = Y \cdot S$. What is the simplified Boolean expression for $Z$?" options=["$AS$","$BS$","$A'S + BS$","$AS' + BS$"] answer="$BS$" hint="First, find the expression for the MUX output $Y$. Then, compute $Z$ using the given AND operation." solution="
Step 1: Write the expression for the output $Y$ of the 2-to-1 multiplexer.

Step 2: Substitute the given inputs $I_0=A$ and $I_1=B$.

Step 3: The final output $Z$ is given by the expression $Z = Y \cdot S$. Substitute the expression for $Y$.

Step 4: Apply the distributive property of Boolean algebra.

Step 5: Simplify the terms. We know that $S' \cdot S = 0$ and $S \cdot S = S$.

Result: The simplified Boolean expression for Z is $\boxed{BS}$.
"
:::

---

Summary

---

What's Next?

---

---

---

Part 2: Design and Analysis

Introduction

In our study of digital logic, we have thus far primarily concerned ourselves with combinational circuits, where the output is a pure function of the present inputs. However, to construct systems of greater complexity, such as processors and memory, we require circuits that possess a "memory" of past events. This necessity leads us to the domain of sequential circuits. A sequential circuit's output depends not only on the current inputs but also on the sequence of past inputs, a history that is stored internally as the circuit's "state."

The fundamental distinction, therefore, is the presence of memory elements, which are typically implemented using flip-flops. These elements hold the state of the circuit, and their values are updated in response to input signals and a controlling clock signal. We will find that sequential circuits can be broadly categorized into two types: synchronous, where all state changes are coordinated by a global clock signal, and asynchronous, where state changes can occur at any time in response to changing inputs. For the GATE examination, a thorough understanding of synchronous sequential circuits is paramount, as they form the bedrock of modern digital design.

---

Key Concepts

1. Flip-Flops: The Building Blocks of Memory

The simplest memory element capable of storing one bit of information is the flip-flop. Its ability to maintain a binary state (0 or 1) indefinitely, until directed by an input signal to switch states, makes it the fundamental component of all sequential logic. For the purpose of circuit analysis and design, it is essential to be proficient with the behavior of the most common types: D, T, and JK flip-flops. This behavior is concisely described by their characteristic equations.

The characteristic equation for a flip-flop defines its next state, denoted $Q(t+1)$ or $Q_{next}$, as a function of its current state, $Q(t)$ or $Q$, and its inputs.

---

2. Analysis of Synchronous Sequential Circuits

The analysis of a sequential circuit involves determining its functional behavior by deriving its state table and state diagram from the circuit schematic. This process follows a methodical, step-by-step procedure.

Derive Input Equations: Express the inputs to each flip-flop (e.g., $D_A, T_B, J_C, K_C$) as Boolean functions of the circuit's present state variables (e.g., $Q_A, Q_B, Q_C$) and external inputs.

Derive Next-State Equations: Substitute the input equations from Step 1 into the corresponding flip-flop characteristic equations to obtain the next-state equations for each state variable.

Construct the State Transition Table: Create a table that lists all possible present states and inputs. For each entry, compute the corresponding next state using the equations from Step 2, and also compute the circuit's output values.

Draw the State Diagram: Create a graphical representation of the state table, where each state is a node and directed edges represent transitions between states.

Let us consider an example to illustrate this procedure.

Worked Example:

Problem: Analyze the sequential circuit shown below. Derive its state transition table and determine the sequence of states it cycles through, assuming it starts in state $Q_1Q_0 = 00$.

CLK

T0
Q0
Q0̅

D1
Q1
Q1̅











1

Solution:

Step 1: Derive the input equations for each flip-flop.
The input to the T flip-flop, $T_0$, is tied to a high logic level. The input to the D flip-flop, $D_1$, is the output of an XOR gate whose inputs are $Q_0$ and $Q_1$.

Step 2: Derive the next-state equations using the characteristic equations.
For the T flip-flop ($Q_{0,next} = T_0 \oplus Q_0$) and the D flip-flop ($Q_{1,next} = D_1$).

Step 3: Construct the state transition table.
We list all possible present states $(Q_1Q_0)$ and use the next-state equations to find the corresponding next state $(Q_{1,next}Q_{0,next})$.

| Present State ($Q_1Q_0$) | $T_0$ | $D_1 = Q_1 \oplus Q_0$ | Next State ($Q_{1,next}Q_{0,next}$) |
| :---: | :---: | :---: | :---: |
| 00 | 1 | 0 | 01 |
| 01 | 1 | 1 | 10 |
| 10 | 1 | 1 | 11 |
| 11 | 1 | 0 | 00 |

Step 4: Determine the state sequence.
Starting from state 00, we trace the transitions using the state table.

Answer: The circuit is a modulo-4 counter that cycles through all four possible states: $00, 01, 10, 11$.

---

3. Counters

Counters are a specialized and ubiquitous class of sequential circuits designed to cycle through a prescribed sequence of states.

Asynchronous (Ripple) Counters

In an asynchronous counter, the flip-flops are not triggered by a common clock signal. Instead, the output of one flip-flop serves as the clock input for the next, creating a "ripple" effect as the count propagates through the chain. While simple to construct, this design suffers from cumulative propagation delay.

The most important characteristic of an $n$-bit ripple counter for GATE is its frequency division property. The output of the first flip-flop ($Q_0$) has a frequency that is half of the input clock frequency. The output of the second ($Q_1$) is half of $Q_0$'s frequency, and so on.

Synchronous Counters

In a synchronous counter, all flip-flops are triggered simultaneously by the same clock signal. This eliminates the ripple delay problem. The logic for state transitions is implemented by combinational circuits connected to the flip-flop inputs. The analysis of such counters follows the general procedure outlined in the previous section.

A notable subtype is the Johnson Counter (or twisted-ring counter). An $n$-bit Johnson counter is a shift register where the inverted output of the last flip-flop is fed back to the input of the first. It has a distinct state cycle of length $2n$. Recognizing a circuit as a Johnson counter can be a significant shortcut in analysis. The circuit in PYQ 2 is a 4-bit Johnson counter, which will therefore have $2 \times 4 = 8$ distinct states.

---

4. Finite State Machines (FSMs)

A Finite State Machine (FSM) is an abstract model of computation used to design sequential logic circuits. We primarily distinguish between two types: Mealy and Moore machines.

The structural difference is illustrated below.

Mealy Machine

Combinational Logic(Next State)

State Register (FFs)

Combinational Logic(Output)


Input










State


Output


Moore Machine


State Register (FFs)

Combinational Logic(Next State)

Combinational Logic(Output)

Input

State

Output

Notice that in the Mealy machine, the input directly affects the output logic, whereas in the Moore machine, it does not.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="NAT" question="An 8-bit asynchronous (ripple) binary counter is clocked by a 12.8 MHz signal. The time period of the waveform at the 5th flip-flop output ($Q_4$) in nanoseconds is ______." answer="2500" hint="Recall the frequency division formula for ripple counters. The 5th flip-flop corresponds to $k=4$ (0-indexed). Calculate the frequency first, then the period." solution="
Step 1: Identify the given parameters.
Input clock frequency, $f_{in} = 12.8$ MHz.
We need the period at the output of the 5th flip-flop, which is $Q_4$ (0-indexed).

Step 2: Apply the frequency division formula for the output of the 5th flip-flop ($k=4$).

Step 3: Calculate the frequency at $Q_4$.

Step 4: Calculate the time period, which is the reciprocal of the frequency.

Answer: $\boxed{2500}$
"
:::

:::question type="MCQ" question="For the synchronous circuit shown, with initial state $Q_A Q_B = 00$, what is the state after 4 clock pulses?"



J
K
CLK

QA
QA'

D
CLK

QB
QB'





CLK

options=["01","10","11","00"] answer="10" hint="Derive the next-state equations for $Q_A$ and $Q_B$. Then, trace the states starting from $00$ for four clock cycles." solution="
Step 1: Derive the input equations for the flip-flops.
$J_A = \overline{Q_B}$, $K_A = \overline{Q_B}$, $D_B = Q_A$.

Step 2: Derive the next-state equations.
For JK-FF: $Q_{A,next} = J_A\overline{Q_A} + \overline{K_A}Q_A$.
For D-FF: $Q_{B,next} = D_B$.

Step 3: Trace the state transitions starting from $Q_A Q_B = 00$.

• Pulse 0 (Initial): State = $(0, 0)$


• Pulse 1: Current state is $(0,0)$.

$Q_{A,next} = \overline{0}\overline{0} + 0 \cdot 0 = 1$.
$Q_{B,next} = 0$.
Next state is $(1, 0)$.

• Pulse 2: Current state is $(1,0)$.

$Q_{A,next} = \overline{0}\overline{1} + 0 \cdot 1 = 0$.
$Q_{B,next} = 1$.
Next state is $(0, 1)$.

• Pulse 3: Current state is $(0,1)$.

$Q_{A,next} = \overline{1}\overline{0} + 1 \cdot 0 = 0$.
$Q_{B,next} = 0$.
Next state is $(0, 0)$.

• Pulse 4: Current state is $(0,0)$.

$Q_{A,next} = \overline{0}\overline{0} + 0 \cdot 0 = 1$.
$Q_{B,next} = 0$.
Next state is $(1, 0)$.

The state sequence is $00 \rightarrow 10 \rightarrow 01 \rightarrow 00 \rightarrow 10 \rightarrow \dots$. The state after 4 clock pulses is $10$.

Answer: $\boxed{10}$
"
:::

:::question type="MSQ" question="A Mealy machine has one input $x$ and one output $y$. The machine is designed to produce an output $y=1$ if and only if the input sequence since reset contains '110' as a substring. Which of the following state diagrams correctly represent this machine?" options=["Diagram A with 3 states","Diagram B with 4 states","Diagram C with 4 states","Diagram D with 3 states"] answer="B" hint="Define states based on the prefix of '110' that has been matched so far. S0: empty prefix, S1: '1' matched, S2: '11' matched. The output is 1 on the transition caused by '0' from state S2." solution="Let's design the state machine. We need states to remember how much of the target sequence '110' we have seen.

• S0: Initial state. No prefix of '110' seen. This is also the state we return to if the sequence is broken.


• S1: We have just seen a '1'.


• S2: We have just seen '11'.


• S3: We have seen '110'. The problem statement implies the output is $1$ for the input that completes the pattern.

Let's trace transitions:

• From S0 (Initial):

- Input 0: We haven't seen '1'. Stay in S0. Output $y=0$.
- Input 1: We have the first part of the pattern. Go to S1. Output $y=0$.

• From S1 (Seen '1'):

- Input 0: The pattern is broken. Go back to S0. Output $y=0$.
- Input 1: We now have '11'. Go to S2. Output $y=0$.

• From S2 (Seen '11'):

- Input 0: We have '110'. Pattern complete! Output $y=1$. Where to go next? The '0' does not start a new pattern. Go to S0.
- Input 1: We have '111'. The last two '1's still match the prefix '11'. So we can stay in S2. Output $y=0$.

This requires 3 states (S0, S1, S2). The output is associated with the transition.
Let's check the options.
Diagram A (3 states): Let's assume it has these transitions.
Diagram B (4 states): A 4-state machine might be needed for overlapping patterns, e.g., '110110'. Let's see if we can do it with 3. Yes.
Maybe the question implies a Moore machine? No, it says Mealy.
Let's reconsider the states.
S0: 'reset' state.
S1: last input was '1'.
S2: last two inputs were '11'.
From S2, if input is '0', output is $1$. We go to S0.
This is a 3-state machine.
The options might present different state assignments or redundant states. A 4-state machine (S0, S1, S2, S3 where S3 is a terminal state) could also work, but S3 would be equivalent to S0 if the machine continues to operate.
Let's assume there is a correct 4-state diagram among the options. Let's call the states A, B, C, D.
A: Reset
B: Seen '1'
C: Seen '11'
D: Seen '110' (maybe this is a state)
Let's try again.
A (Reset): input 1 -> B/$0$. input 0 -> A/$0$.
B (Seen '1'): input 1 -> C/$0$. input 0 -> A/$0$.
C (Seen '11'): input 1 -> C/$0$ (for '111'). input 0 -> A/$1$ (for '110').
This is a perfectly valid 3-state machine. If one of the options is a 4-state machine that is equivalent (e.g., contains an unreachable state or an equivalent state), it could still be correct.
The question is MSQ, maybe there are multiple correct implementations.
Without seeing the diagrams, I can only state that the minimal machine has 3 states. Let's assume option B is a correct 4-state implementation, perhaps with a state for '110' before resetting. For example:
C (Seen '11'): on 0 -> D/$1$.
D (Seen '110'): on 0 -> A/$0$, on 1 -> B/$0$.
This is a valid 4-state machine. It is not minimal because state D is not strictly necessary; its outgoing transitions could be merged into state C's transition. So a 4-state machine can be correct.
Let's assume Diagram B is the correct one to make the question solvable.
Final Solution:
The problem asks for a Mealy machine that detects the sequence '110'. We can define states based on the longest prefix of '110' that has been received as a suffix of the input string.

• State S0: The suffix of the input does not end in '1' or '11' (initial/reset state).


• State S1: The suffix of the input is '1'.


• State S2: The suffix of the input is '11'.

The state transitions and outputs are as follows:

• From S0: On input '1', go to S1 (output $0$). On input '0', stay in S0 (output $0$).


• From S1: On input '1', go to S2 (output $0$). On input '0', go to S0 (output $0$).


• From S2: On input '1', stay in S2 (the new suffix is '11'). On input '0', the sequence '110' is complete, so we output $1$. The new suffix '0' doesn't match any prefix, so we return to S0.

This defines a minimal 3-state machine. However, a non-minimal but functionally equivalent machine is also a correct implementation. For instance, a 4-state machine could be constructed. If Diagram B correctly implements this logic, possibly with a redundant state, it would be a correct answer. Without the visual diagrams, we must assume that one of them correctly models the specified behavior. Based on common problem patterns, it's plausible that a 4-state diagram is presented which is a correct, albeit non-minimal, implementation."
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="A 2-bit synchronous binary up-counter is designed using JK flip-flops ($Q_A$ is MSB, $Q_B$ is LSB). The counter progresses through the state sequence $00 \to 01 \to 10 \to 11$ and then repeats. What is the minimized logic expression for the input $J_A$?" options=["$Q_B$","$Q_B'$","$Q_A \oplus Q_B$","$1$"] answer="A" hint="First, construct the state transition table for a 2-bit binary up-counter. Then, use the JK flip-flop excitation table to determine the required values for $J_A$ for each transition. Finally, use a K-map to simplify the expression for $J_A$." solution="

State Transition Table:

The counter follows the binary sequence. The present state is $(Q_A, Q_B)$ and the next state is $(Q_{A,next}, Q_{B,next})$.

| Present State ($Q_A Q_B$) | Next State ($Q_{A,next} Q_{B,next}$) |
| :---: | :---: |
| 00 | 01 |
| 01 | 10 |
| 10 | 11 |
| 11 | 00 |

Excitation Table for Flip-Flop A:

We focus on the transitions of $Q_A$ to determine the required inputs $J_A$ and $K_A$. The JK flip-flop excitation table is:

| $Q \to Q_{next}$ | J | K |
| :---: |:-:|:-:|
| $0 \to 0$ | 0 | X |
| $0 \to 1$ | 1 | X |
| $1 \to 0$ | X | 1 |
| $1 \to 1$ | X | 0 |

Now, we determine the required inputs for flip-flop A ($J_A, K_A$) based on the transition $Q_A \to Q_{A,next}$.

| $Q_A$ | $Q_B$ | $Q_{A,next}$ | Transition ($Q_A \to Q_{A,next}$) | $J_A$ | $K_A$ |
| :---: | :---: | :---: | :---: | :---: | :---: |
| 0 | 0 | 0 | $0 \to 0$ | 0 | X |
| 0 | 1 | 1 | $0 \to 1$ | 1 | X |
| 1 | 0 | 1 | $1 \to 1$ | X | 0 |
| 1 | 1 | 0 | $1 \to 0$ | X | 1 |

K-Map Simplification for $J_A$:

We create a 2-variable K-map for $J_A$ as a function of the present state variables $Q_A$ and $Q_B$.

To find the minimal expression, we must cover the '1' at position $(Q_A, Q_B) = (0, 1)$. We can group this '1' with the don't care ('X') at position $(1, 1)$. This vertical group corresponds to the condition where $Q_B=1$.

Therefore, the simplified logic expression is $J_A = Q_B$.

Answer: $\boxed{Q_B}$
"

:::question type="NAT" question="Consider a synchronous sequential circuit where the flip-flops are connected in a chain. The signal path between any two consecutive flip-flops consists of a combinational logic block. The timing parameters are as follows:

• Propagation delay of each flip-flop ($t_{pd,ff}$) = 3 ns


• Setup time of each flip-flop ($t_{su}$) = 2 ns


• Hold time of each flip-flop ($t_h$) = 0.5 ns


• Propagation delay of the combinational logic block ($t_{pd,comb}$) = 5 ns

What is the maximum clock frequency (in MHz) at which this circuit can operate reliably?" answer="100" hint="The maximum clock frequency is determined by the minimum clock period ($T_{min}$). The minimum clock period must be greater than or equal to the sum of the flip-flop propagation delay, the combinational logic propagation delay, and the flip-flop setup time. $T_{min} \ge t_{pd,ff} + t_{pd,comb} + t_{su}$." solution="

Calculate the minimum clock period ($T_{min}$):

The minimum clock period is the sum of the flip-flop propagation delay, the combinational logic propagation delay, and the flip-flop setup time.

Given values:
* $t_{pd,ff} = 3 \text{ ns}$
* $t_{pd,comb} = 5 \text{ ns}$
* $t_{su} = 2 \text{ ns}$

Calculate the maximum clock frequency ($f_{max}$):

The maximum clock frequency is the reciprocal of the minimum clock period.

(Note: The hold time $t_h$ is used to check for hold time violations, but it does not directly affect the maximum clock frequency.)

Answer: $\boxed{100}$
"

:::question type="MCQ" question="A sequential circuit is implemented with two D flip-flops, A and B. The input equations to the flip-flops are $D_A = Q_B$ and $D_B = \overline{Q_A \oplus Q_B}$. If the initial state of the circuit is $Q_A Q_B = 00$, what is the sequence of states the circuit goes through?" options=["$00 \to 01 \to 11 \to 10 \to 00 \dots$","$00 \to 11 \to 01 \to 10 \to 00 \dots$","$00 \to 10 \to 11 \to 01 \to 00 \dots$","$00 \to 01 \to 10 \to 00 \dots$"] answer="D" hint="Starting from the initial state, calculate the next state by substituting the current state values into the flip-flop input equations ($D_A$ and $D_B$). Repeat this process for each subsequent state until the sequence repeats." solution="
We will trace the state transitions using the given input equations:
$D_A = Q_B$
$D_B = \overline{Q_A \oplus Q_B}$

Initial State: $Q_A Q_B = 00$

* $D_A = Q_B = 0$
* $D_B = \overline{Q_A \oplus Q_B} = \overline{0 \oplus 0} = \overline{0} = 1$
* Next State: $Q_A Q_B = 01$

Current State: $Q_A Q_B = 01$

* $D_A = Q_B = 1$
* $D_B = \overline{Q_A \oplus Q_B} = \overline{0 \oplus 1} = \overline{1} = 0$
* Next State: $Q_A Q_B = 10$

Current State: $Q_A Q_B = 10$

* $D_A = Q_B = 0$
* $D_B = \overline{Q_A \oplus Q_B} = \overline{1 \oplus 0} = \overline{1} = 0$
* Next State: $Q_A Q_B = 00$

The sequence repeats from $00$.

The sequence of states is $00 \to 01 \to 10 \to 00 \dots$

Answer: $\boxed{00 \to 01 \to 10 \to 00 \dots}$
"

:::question type="NAT" question="Consider the following state table for a Mealy machine with one input $x$ and one output $z$. The states are $\{S_0, S_1, S_2, S_3, S_4, S_5\}$. What is the number of states in the minimized state table?

| Present State | Next State, Output ($z$) |
| :--- | :--- |
| | $x=0$ | $x=1$ |
| $S_0$ | $S_1, 0$ | $S_2, 0$ |
| $S_1$ | $S_3, 0$ | $S_2, 0$ |
| $S_2$ | $S_4, 1$ | $S_5, 0$ |
| $S_3$ | $S_0, 0$ | $S_5, 0$ |
| $S_4$ | $S_4, 1$ | $S_5, 0$ |
| $S_5$ | $S_3, 0$ | $S_2, 0$ |
" answer="4" hint="Use the partition method for state minimization. Start by grouping states with identical output behavior. Then, iteratively refine the partitions by checking if states within a group transition to equivalent groups for all possible inputs. The process stops when no further refinement is possible." solution="
We will use the partition method for state minimization.

Partition $P_0$ (based on output behavior):

We group states that produce the same output for each input.
* States with output (0, 0) for ($x=0, x=1$): $S_0, S_1, S_3, S_5$
* States with output (1, 0) for ($x=0, x=1$): $S_2, S_4$

So, $P_0 = \{(S_0, S_1, S_3, S_5), (S_2, S_4)\}$.
Let's label these groups: $G_1 = (S_0, S_1, S_3, S_5)$ and $G_2 = (S_2, S_4)$.

Partition $P_1$ (refine $P_0$ based on next state groups):

For each group in $P_0$, we check if all states within that group transition to the same groups for each input.

* Check $G_1 = (S_0, S_1, S_3, S_5)$:
* $S_0$: Next states are $(S_1, S_2)$. Group transitions: $(G_1, G_2)$.
* $S_1$: Next states are $(S_3, S_2)$. Group transitions: $(G_1, G_2)$.
* $S_3$: Next states are $(S_0, S_5)$. Group transitions: $(G_1, G_1)$.
* $S_5$: Next states are $(S_3, S_2)$. Group transitions: $(G_1, G_2)$.
States $S_0, S_1, S_5$ have the transition pattern $(G_1, G_2)$, while $S_3$ has $(G_1, G_1)$. Thus, $G_1$ must be split.
New groups: $G_{1a} = (S_0, S_1, S_5)$ and $G_{1b} = (S_3)$.

* Check $G_2 = (S_2, S_4)$:
* $S_2$: Next states are $(S_4, S_5)$. Group transitions: $(G_2, G_1)$.
* $S_4$: Next states are $(S_4, S_5)$. Group transitions: $(G_2, G_1)$.
States $S_2$ and $S_4$ have identical transition patterns. They remain in the same group.

So, $P_1 = \{(S_0, S_1, S_5), (S_3), (S_2, S_4)\}$. There are 3 groups.
Let's label these new groups: $H_1 = (S_0, S_1, S_5)$, $H_2 = (S_3)$, $H_3 = (S_2, S_4)$.

Partition $P_2$ (refine $P_1$):

* Check $H_1 = (S_0, S_1, S_5)$:
* $S_0$: Next states are $(S_1, S_2)$. Group transitions: $(H_1, H_3)$.
* $S_1$: Next states are $(S_3, S_2)$. Group transitions: $(H_2, H_3)$.
* $S_5$: Next states are $(S_3, S_2)$. Group transitions: $(H_2, H_3)$.
State $S_0$ has a different transition pattern from $S_1$ and $S_5$. Thus, $H_1$ must be split.
New groups: $H_{1a} = (S_0)$ and $H_{1b} = (S_1, S_5)$.

* $H_2 = (S_3)$ and $H_3 = (S_2, S_4)$ are either singletons or already checked as equivalent, so they don't split further in this step.

So, $P_2 = \{(S_0), (S_1, S_5), (S_3), (S_2, S_4)\}$. There are 4 groups.
Let's label these new groups: $K_1 = (S_0)$, $K_2 = (S_1, S_5)$, $K_3 = (S_3)$, $K_4 = (S_2, S_4)$.

Partition $P_3$ (refine $P_2$):

* Check $K_2 = (S_1, S_5)$:
* $S_1$: Next states are $(S_3, S_2)$. Group transitions: $(K_3, K_4)$.
* $S_5$: Next states are $(S_3, S_2)$. Group transitions: $(K_3, K_4)$.
States $S_1$ and $S_5$ have identical transition patterns. They remain in the same group.

* All other groups ($K_1, K_3, K_4$) are singletons, so they cannot be split further.

So, $P_3 = \{(S_0), (S_1, S_5), (S_3), (S_2, S_4)\}$. There are 4 groups.

Since $P_3 = P_2$, the minimization process terminates. The final minimized partitions are $(S_0)$, $(S_1, S_5)$, $(S_3)$, and $(S_2, S_4)$.
The number of states in the minimized state table is 4.

Answer: $\boxed{4}$
"