# Realization of divide by 78 counter

I am unable to pick the right option from the below

A divide by 78 counter can be realized using?
a) 6 number of mod 13 counters
b) 13 number of mod 6 counters
c) one mod-13 counter followed by one mod 6 counter
d) 13 number of mod-13 counters


I know a divide by 78 counter has 78 states so I decided that answer cannot be C because a mod-13 counter has 13 states and mod-6 has 6 states total making up only 20 states and then the next option is D that has 13 *13 = 169 states more than required. I think it must be a or b and the is b according to the book I solved but my question is why it can't be a?

  mod-6 counter has 6 states so total 13*6 = 78 . this was the explanation
but mod-13 counter has 13 states so total 6*13 = 78 both are same


Iam unable to find out the reason why the answer is B. kindly help me with this. Thanks

## 1 Answer

The book is wrong. The right answer is C. 78=13*6. The mod-13 counter will be incremented with each pulse of the incoming signal, and will overflow every 13 counts of such pulses. The mod-6 counter will be incremented each time that the mod-13 counter overflows. The mod-6 counter will overflow every 6 of its counts. Therefore, the mod-6 counter will overflow every 6*13=78 pulses of the incoming signal.

In other words, for each state of the mod-6 counter, the mod-13 counter counts 13 states. So, in total, you will have 6*13=78 different "global" states. That's why, if you have them one after the other (so that counter k increments one unit when counter k-1 overflows), you have to multiply the numbers of states, not add them.

These will be the count values for each of the two counters, before each pulse at the input.

{(mod-13 counter value) (mod-6 counter value)}
{0 0}
{1 0}
...
{12 0}
{0 1}
{1 1}
...
{12 1}
{0 2}
{1 2}
...
...
{12 5}
<-- Here is the overflow for the global counter formed. Above this line, there are 78 different states.
{0 0}
...


Also:
a) and d) are wrong, because there is no integer N such that $13^N=78$.
b) is wrong, because there is no integer N such that $6^N=78$.

• Incidentally, because six and thirteen are relatively prime, one could also have both counters increment on every clock cycle, and have the output go high when both counters are simultaneously zero. – supercat May 22 '12 at 21:09
• @supercat Right, but then you would need an extra gate, which is not offered. – Telaclavo May 22 '12 at 21:36
• The approach is a useful one to know when designing logic to go in a PLD, since large-fan-in gates are cheap, but simulating count-enable or latch-enable signals is expensive. If one needs to use a separate macrocell to produce the output anyway (e.g. because one wants an output which is high for one pulse out of 78) it may be worthwhile to simplify all the other counters and just watch for them to fire 'in sync'. – supercat May 22 '12 at 22:06