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

I have basic doubt here

what is sequence here ?

is it

0, 0, 1, 1, 2, 2, 3, 3, 0, 0 (in this case 4 FF needed )

or

0, 0, 1, 1, 2, 2, 3, 3 (in this case three FF needed)

---

@mehul vaidya same doubt occuring here,

---

For 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3,... we will require 4 FF. Right?

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

@ayush.5 

Synchronous counter without combinational circuit can count 2N states.

but with combinational circuit can count upto 2^N state.

Check it out.....below circuit works for the above question.

---

Can someone tell me how is it possible to use 3 flipflops and consider the output from 2 flipflops only?? Please help me.

---

Such a cool explanation Mithlesh

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.