edited by
11,754 views
54 votes
54 votes

A $\text{1-input}$, $\text{2-output}$ synchronous sequential circuit behaves as follows:

Let $z_k, n_k$ denote the number of $0’s$ and $1’s$ respectively in initial $k$ bits of the input

$(z_k+n_k=k)$. The circuit outputs $00$ until one of the following conditions holds.

  • $z_k-n_k=2$. In this case, the output at the k-th and all subsequent clock ticks is $10$.
  • $n_k-z_k=2$. In this case, the output at the k-th and all subsequent clock ticks is $01$.

What is the minimum number of states required in the state transition graph of the above circuit?

  1. $5$
  2. $6$
  3. $7$
  4. $8$
edited by

5 Answers

Best answer
71 votes
71 votes
Though the question is from digital logic, the answer is purely from automata. As per the question, we just need to count the difference of the number of $0'$s and $1'$s in the first $k$ bits of a number. And we just need to count till this count reaches $2$ or $-2$ (negative when the number of $0's$ is less than the number of $1's$). So, the possibilities are $-2, -1, 0, 1,$ and $2$ which represent the five states of the state transition diagram.

For state $-2$, the output of the circuit  will be $01$, for state $2$, the output will be $10$ (both these states not having any outgoing transitions) and for other $3$ states, the output will be $00$ as per the given description of the circuit.

Correct Answer: $A$
edited by
123 votes
123 votes

The Automaton will look like this. 😎

edited by
8 votes
8 votes

Zk - Nk.  = { -2,-1,0,1,2 }

Z-N = 2 ( no of zeros - number of ones =2 )

Z-N = -2 (no of ones - number of zeros =2 )

So there will be a total of 5 states i.e -2,-1,0,1,2 . With initial state as 0 ( output 00 ) as number of ones and number of zeros are 0.

Final states as -2 ( output 01 ) and 2 (output 10 ) with self loop for all the subsequent inputs.

-1 and 1 are intermediate states.

4 votes
4 votes

It can be solved using concept of TOC hence total no of states is  5

Answer:

Related questions

65 votes
65 votes
9 answers
3
Kathleen asked Sep 17, 2014
17,924 views
The following is a scheme for floating point number representation using $16$ bits.Let $s, e,$ and $m$ be the numbers represented in binary in the sign, exponent, and man...
48 votes
48 votes
4 answers
4
Kathleen asked Sep 16, 2014
15,057 views
Consider an array multiplier for multiplying two $n$ bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is$\Theta(1)$$\Theta(\lo...