Digital electronics

Question

Given the sequence 010202010 is generated from a sequential circuit of n flip-flops. And these flip-flops generate the sequence respectively. What is the minimum value of n?

Comments

this is same as https://gateoverflow.in/39670/gate-2016-1-8 question.

do u agree?

then 4 FF is enough

---

I agreed but then 5 should be answer . how 4.??

---

It is 4 only. I already gave the explanation for it.

Answer 1

Distinct states =0,1,2 = 2 bit sufficient

For 5 0's we need another 3 bits

0-00-000

1-01

0-00-001

2-10

0-00-010

2-10

0-00-011

1-01

0-00-100

So total 5 bits are sufficient.

----------------------------------------------------------------------------------------------------------------------------------

only 010202 this is the sequence needs to generated than 

0 - 00 - 00

1 - 01

0 - 00 - 01

2 - 10

0 - 00 - 10

2- 10

To distinquish 0,1 and 2 we need 2 bits and to distinquish 3 0's we need additional 2 bits. So 4 bits are flipflops are sufficient.

Comments

Why didn't you took additional 1 bit for two 2's?

---

Because I have already taken 3 extra bits for 0's ...after 10-xxx you can put anything it generates new sequence for two...

---

in these type of questions every state is represented by representation of bits( can't we map to other bits)??

Why didn't we did ceil(log2(9)) ??

---

Good explaination..that is right

Answer 2

The sequence is 010202............

Now, see them in binary sequence

0 -00

1-01

2-10

Now, 3 0's are there.

To differentiate among 3 0's we do

$0-{\color{Blue} 0}000$

$0-{\color{Blue} 0}100$

$0-{\color{Blue}1}100$

All 0's are separated here.

So, maximum binary digits required 4. Minimum number of flipflops will be 4 also

Comments

Why didn't you added extra bit to distinguish two $2's$?

---

010202010 this sequence is given in the question ....

---

Ans is 5 

Answer 3

When ever you are answering such questions just try to find out the pattern:
0-->1-->0-->2-->0-->2--->(initial 0 i.e starting sate and then sequence repeats)

so the moment we see the decimal outputs till 2, we need atleast 2 bits for representing(0,1,2).
But now the catch is here 0 has non-determinism, to avoid such nondeterminism we need to add padding bits to
differentiate 3 0s.

Now one bit can differentiate only 2 0s. Hence 2 padding bits are needed to represent 3 0s.

3 0s now can be XX00,XX00,XX00. Such that the pair XX is unique for each 0; it can be any binary sequence.
1 can be reprsented as XX01, 2 as XX10.

So 4 Flipflops needed