Question

Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Consider the following example.
Input sequence: 00100011000011100
Output sequence: 00000001000001100
A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input. The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables $s$, $t$, $b$ and $y$ respectively. Assume the initial state of the Mealy machine is 0. What are the Boolean expressions corresponding to $t$ and $y$ in terms of $s$ and $b$?

• A. $t = s + b$
  \; $y = sb$
• B. $t = b$
  \; $y = sb$
• C. $t = b$
  \; $y = s\bar{b}$
• D. $t = s + b$
  \; $y = s\bar{b}$

Hint:

In Mealy machines, carefully interpreting what the state remembers about past inputs is key to deriving correct Boolean expressions.

Answer 1

The Correct Option is B

Step 1: Understanding the required behavior.
The circuit must replace only the first 1 in every consecutive block of 1's by a 0, and allow the remaining 1's in that block to pass unchanged. This means the machine must remember whether it has already encountered a 1 in the current run of consecutive 1's.

Step 2: Interpretation of the state variable $s$.
Let $s = 0$ indicate that the machine has not yet seen a 1 in the current sequence of consecutive 1's. Let $s = 1$ indicate that the first 1 has already been seen and processed.

Step 3: Determining the next state $t$.
Whenever the input bit $b = 1$, the machine should move to state 1, indicating that a 1 has been encountered. When $b = 0$, the machine should reset to state 0. Hence, the next state depends only on the input bit: \[ t = b. \]

Step 4: Determining the output $y$.
The output should be 1 only when the machine is already in state $s = 1$ and the input bit $b = 1$ (i.e., not the first 1 of the block). In all other cases, the output is 0. Thus, \[ y = sb. \]

Step 5: Conclusion.
The Boolean expressions for the next state and output are \[ t = b \text{and} y = sb, \] which corresponds to option (B).