A 1-input, 2-output synchronous sequential circuit behaves as follows : Let…
2003
A 1-input, 2-output synchronous sequential circuit behaves as follows : Let zk, nk denote the number of 0's and 1's respectively in initial k bits of the input (zk + nk = k). The circuit outputs 00 until one of the following conditions holds.
zk - nk = 2. In this case, the output at the k-th and
all subsequent clock ticks is 10.
nk - zk = 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?
- A.
5
- B.
6
- C.
7
- D.
8
Attempted by 19 students.
Show answer & explanation
Correct answer: A
Answer: 5 states.
Reason:
Track the difference d = (number of 0's) - (number of 1's) in the initial k bits.
Before reaching a magnitude of 2, d can be -1, 0, or +1. These three differences require distinct states, and while in these states the output is 00.
When d reaches +2, the machine enters an absorbing state that outputs 10 on that k-th and all subsequent clocks.
When d reaches -2, the machine enters an absorbing state that outputs 01 on that k-th and all subsequent clocks.
Thus the required states are:
State for d = 0 (output 00)
State for d = +1 (output 00)
State for d = -1 (output 00)
Absorbing state for d = +2 (output 10)
Absorbing state for d = -2 (output 01)
Transition summary:
From d = 0: input 0 -> d = +1; input 1 -> d = -1.
From d = +1: input 0 -> d = +2 (enter absorbing output-10 state); input 1 -> d = 0.
From d = -1: input 1 -> d = -2 (enter absorbing output-01 state); input 0 -> d = 0.
From either absorbing state (d = +2 or d = -2): remain in that absorbing state regardless of further inputs.
Because these five states are sufficient to represent all reachable differences and the output behavior (with the ±2 states absorbing), the minimum number of states required is 5.