Suppose we want to design a synchronous circuit that processes a string of 0’s…
2021
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.
\(\begin{array}{l} t=s+b \\ y=sb \end{array} \\\) - B.
\(\begin{array}{l} t=b \\ y=sb \end{array} \\\) - C.
\(\begin{array}{l} t=b \\ y=s \overline{b} \end{array} \\\) - D.
\(\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}\)
Attempted by 39 students.
Show answer & explanation
Correct answer: B
State interpretation: Let s = 1 mean we are currently in a run of 1s (previous input was 1); s = 0 means we are not in a run.
Next state (t): t = b. The machine is in a run in the next step exactly when the current input bit is 1, so the next state must equal the current input b.
Output (y): y = s b. Output should be 1 only when the current bit is 1 and it is not the first 1 of a consecutive run. That happens exactly when b = 1 and we were already in a run (s = 1), so y = s AND b.
Therefore the correct expressions are t = b and y = s b.
A video solution is available for this question — log in and enroll to watch it.