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$
5
  • 3
    $\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, 2016 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$ Jun 29, 2017 at 11:40
  • $\begingroup$ You can give original reference(i.e., IIT websites). $\endgroup$ Jun 29, 2017 at 11:41
  • 1
    $\begingroup$ The second one, does that have 8 states (and the first two repeated states are listed) or 10 states ( with four consecutive zeroes)? $\endgroup$
    – gnasher729
    Nov 16, 2021 at 21:16
  • $\begingroup$ What do you call "counting sequence" ? $\endgroup$
    – user16034
    Jul 11, 2023 at 16:23

1 Answer 1

0
$\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$
8
  • $\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$ Dec 24, 2018 at 9:57
  • $\begingroup$ Yes it will. you got a contrary example? $\endgroup$ Dec 24, 2018 at 10:01
  • 1
    $\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$ Dec 24, 2018 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$ Dec 24, 2018 at 10:04
  • 5
    $\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$ Dec 24, 2018 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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