GATE CS 2021 Set 2 Q.38 (CS Q.28): Sequential Circuits, Counters and Registers

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.

\text{Input sequence: } 00100011000011100

\text{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$ ?

$t = s + b$

$y = sb$

$t = b$

$y = sb$

$t = b$

$y = s\overline{b}$

$t = s + b$

$y = s\overline{b}$

Official answer and solution

Official answer: B
From: Official GATE 2021 answer key

Solution

Construct the state transition and output table of the two-state Mealy machine based on the required sequence transformation.

The circuit processes an input bit stream and replaces the first 1 of any consecutive sequence of 1's with a 0, while keeping subsequent 1's as 1, and keeping 0's as 0.

State $s = 0$ : Initial state, representing that the circuit is outside a run of 1's (or just saw a 0).
State $s = 1$ : Representing that the circuit is inside a consecutive run of 1's.

Determine the next state $t$ and output $y$ for each combination of current state $s$ and input bit $b$ :

Present state $s = 0$ , input $b = 0$ :
The bit is 0 outside a run. Output $y = 0$ , next state $t = 0$ .
Present state $s = 0$ , input $b = 1$ :
This is the FIRST 1 of a run. It must be replaced by 0: output $y = 0$ . The machine enters the run state: next state $t = 1$ .
Present state $s = 1$ , input $b = 0$ :
The run of 1's has ended. Output $y = 0$ , next state $t = 0$ .
Present state $s = 1$ , input $b = 1$ :
This is a SUBSEQUENT 1 in the run. It must remain 1: output $y = 1$ , next state $t = 1$ .

Summarizing the truth table:

$s$	$b$	$t$	$y$
0	0	0	0
0	1	1	0
1	0	0	0
1	1	1	1

From the table:

The next state column $t$ is exactly equal to the input bit $b$ : $t = b$ .
The output column $y$ is 1 only when both $s=1$ and $b=1$ : $y = sb$ .

Thus, $t = b$ and $y = sb$ , which matches option B.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 38 of 65, printed as CS Q.28
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source