3
$\begingroup$

In the previous two years of the GATE exams, a question has been asked for finding number of flip flop's for counting sequence $0−1−0−2−0−3$ in 2016 and $0−0−1−1−2−2−3−3−0−0$ in 2015. But still, the approach discussed in these questions hasn't arrived at Common answer (or) solution.

For $0−1−0−2−0−3$, there are $6$ different states, and thus it acts as a mod−6, counter So, 3 FF's are suffice. In another approach it is said that $2$ bits are used to distinguish three $0$′s and $2$ for $1,2,3$. So number of FF's required =2+2=4

Similar is the case in $0−0−1−1−2−2−3−3−0−0$, one approach says setting clock such that output of FF will be sampled at twice the input frequency makes me think 2 FF's would suffice. But on the other-hand using 2 FF's for $1,2,3,4 $ and 1 FF for identifying which 1 out of two 1′s makes me think $3$ is also right.

So, I want to be sure in answering these type of questions as they have been asked in recent past [GATE][3] Exams.Please tell the general approach to solve these type of questions also please comment about minimum number of JK FF's required for following counting sequence so that i will be able to work out myself using the technique provided by you and evaluate my understanding.

  1. $0−0−0−1−1−2−2−3−3−...$
  2. $0−1−0−2−0−2−0−3−0−2−...$
  3. $1−2−3−0−0−1−0−2−2−...$
$\endgroup$
  • 2
    $\begingroup$ I may be missing something. If the sequence is cyclic with period $n$, why isn't the answer $\left\lceil \log_2 n \right\rceil$? You must have enough memory to store a number between $0$ and $n-1$. The rest can be done with combinatorial logic. $\endgroup$ – Pseudonym Nov 22 '16 at 3:53
  • $\begingroup$ You are editor of that commercial website. You should not post name of your commercial website here. gateoverflow.in/user/pC $\endgroup$ – 1 0 Jun 29 '17 at 11:40
  • $\begingroup$ You can give original reference(i.e., IIT websites). $\endgroup$ – 1 0 Jun 29 '17 at 11:41
1
$\begingroup$

The links you have provided (gateoverflow) are themselves quite helpful. However if you want a even more elaborate explanation then read further.

In the very first question you have sequence 0--1--0--2--0--3 now these numbers represented in binary are: 00--01--10-00-10--00-11 So clearly you would need 2 bits to determine each of those number so 2 FF for that. Moreover there are 3 similar states for that are 000,000,000 so in order to differentiate between them you further would require 3 combinations that would need log(3)base2 digits =2 digits. thereby 2 FF would be required here too.

So that is a total of 2+2 Flip flops required. Let me know if I could help you further.

$\endgroup$
  • $\begingroup$ I'm not quite sure how this answers the question. Does this method (which you haven't quite formulated in general) always result in the optimal number of flip-flops? $\endgroup$ – Yuval Filmus Dec 24 '18 at 9:57
  • $\begingroup$ Yes it will. you got a contrary example? $\endgroup$ – Anonymous Developer Dec 24 '18 at 10:01
  • $\begingroup$ No, and I won't be looking for one. But unless you prove that your method works, I see no reason to believe that it does. $\endgroup$ – Yuval Filmus Dec 24 '18 at 10:02
  • $\begingroup$ Well something works if you don't have a contrary example to it. moreover it's basic logic I don't understand why it wouldn't work $\endgroup$ – Anonymous Developer Dec 24 '18 at 10:04
  • 3
    $\begingroup$ You haven't formulated your method in general, so it's hard to say whether it works in general. But once you do, you should be able to prove that it always works - otherwise there is no reason to believe that it is more than a heuristic. $\endgroup$ – Yuval Filmus Dec 24 '18 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.