GATE CSE 2015 | Set 2 | Question: 7

Question

The minimum number of $\text{JK}$ flip-flops required to construct a synchronous counter with the count sequence $(0, 0, 1, 1, 2, 2, 3, 3, 0, 0, \ldots)$ is _______.

Comments

ans is 3 as it is mod 8 counter the no of same sequence is repeated twice therefore from, 2 bit 4 combination but we have to add 1 extra bit to satify this sequence

---

0,0,0,0, 1,1,1,1 , ...............  --> for this we need 3 FF ?
0,0,0,0 , 1,1,1,1, 2,2,2,2, .................... -> for this we need 4 FF ?

---

yes i think if the sequence is:

i) (0,0,0,0,1,1,1,1,0,0,0,0) => 3 FF's required coz no. of states = 8 (output can be considered ignoring 2 MSB bits)

ii) (0,0,0,0,1,1,1,1,2,2,2,2,0,0,0,0) => 4 FF's required coz no. of states => 12 (output can be considered ignoring 2 MSB bits)

Answer 1

First, lets design a counter for $0, 1, 2, 3$. It is a MOD - $4$ counter. Hence, number of Flip Flops required will be two. Count sequence will be:

$00 \to 01 \to 10 \to 11$
 
Count sequence mentioned in question is:

$00 \to 00 \to 01 \to 01 \to 10 \to 10 \to 11 \to 11$
 
Now, two flip flops won't suffice. Since we are confronted with repeated sequence, we may add another bit to the above sequence:

$000 \to 100 \to 001 \to 101 \to 010 \to 110 \to 011 \to 111$
 
Now each and every count is unique, occurring only once. Meanwhile, our machine has been extended to a MOD - $8$ counter. Hence, three Flip Flops suffice.

Just neglect the MSB flip flop output and take the o/p of other two only. So, we have :

$0,0,1,1,2,2,3,3,\ldots$

So, correct answer: $3.$

Comments

Such a cool explanation Mithlesh

---

cool stuff...

---

Can we use total no of states (N) >= 2^n
here the total states are 8 ,  8>=2^n n=3 means 3-bit counter .
To generate 3-bit counter we need 3 JK flip-flops.

Can we apply that method here?

Answer 2

People are asking for explaination , I am not giving full solution but an approach how to handle these kind of questions .

First for creating  counter for any sequence we need to identify the states .

Lets say we are taking a sequence of 0-1-2-3 then the states of flip flop (counter design) will be (ff1-ff0) 00->01->10->11-> , only 2 flipflop will be sufficient to give output in 2 bits.

but for the above sequence as you see there are two digits of same kind  0,0,1,1,2,2,3,3 , for which binary values will be 00,00,01,01,10,10,11,11 we cant diffrenciate first 00 from 2nd 00 or third 01 from fourth 01 using only 2 bits so we will add 3rd bit as follow

000,100,001,101,010,110,011,111 here if you see i have just added one extra bit and we can now differenciate between each number seperately , if we made a counter for this sequence and take output of only  first two flipflops (ff1,ff0) from (ff2,ff1,ff0) then our sequence is realized.

 

(PS for futher clearance on the topic refer Morris Mano book )

Answer 3

Here it appears to have 8 discrete states. That requires 3 bits, therefore 3 flip-flops. From inspection, there are 4 groups of 2 identical bits per group. I'd break that down to into a divide by two (1 flip-flop) followed by a divide by four (2 flip-flops).

Comments

Explain plz??

---

pls explain.!!!!!!!!

...getting confused by your answer.

---

how to realize the circuit. for this problem

---

If $A,B, C$ are the bits of present input and $A^+,B^+,C^+$ are the bits of next output, the steering logic in the counter design will be :

$A^+=\bar{A}$

$B^+=B\bar{C}+\bar{A}B+AB\bar{C}$

$A^+=A\bar{C}+\bar{A}C$

Answer 4

question is slightly ambigus.the thing is we can get sequence 0,0,1,1,2,2,3,3, by 2 FF.

how?

the o/p of the FF will be sampled at twice the i/p clock frequency.

e.g. let my FF retains a state for 2 seconds and i sample o/p at 1 second interval.

and this is quite possible.

and other cases users have already discussed

Comments

But that way, it will be an asynchronous counter.

Answer 5

Found something interesting. Guys at MadeEasy were able to do this with 2 flip flops using an additional clock.

Although I would like to clarify that the answer in the official sheet is 3.

 

Comments

gmrishikumar Couldn't deny it, this is actually very interesting.
 

---

i am not able to understand this solution can anyone plz explain me this ?

---

But how can X be varied like that 0,1,0,1...?

Answer 6

The patter can be generated by a mod 8 counter so the answer is 3.

Comments

how?? plz explain

---

Pls explain it...