GATE CSE 2011 | Question: 15

Question

The minimum number of $\text{D}$ flip-flops needed to design a mod-258 counter is

• A. 9
• B. 8
• C. 512
• D. 258

Comments

how same? pattern different for both

One have 1 input another 2 input

https://gateoverflow.in/8054/gate2015-2-7

---

https://gateoverflow.in/84803/self-doubt-modulus-counter

---

An n-bit binary counter consists of n flip-flops and can count in binary from 0 to 2^n - 1.

-Morris Mano (Digital logic and computer design)

whether we use JK or D flipflops the number of flip flops will not change.

Answer 1

Mod $258$ counter has $258$ states. We need to find no. of bits to represent $257$ at max. $2^n \geq 258 \implies n \geq 9$. 

Answer is A.

Comments

Doubt why we need conversion? why D flip flop can't count.if we use some combinatory ckt before giving input to D Flip flop then it is possible to count 0 to 2^n-1.

---

Is this count same for a synchronous and asynchronous counter?

---

yes, count sequence  for is for both synchronous counter and asynchronous counter

Answer 2

Flip -Flop is a binary cell capable of storing 1-bit of information. so to store n-bit we need n Fli-Flip.

---

n-bit Ring Counter can have n different output states.

n-bit Twisted ring counter(Johnson Ring Counter) can have 2n different output states.

n-bit ripple counter (mod-2ⁿ counter) can have 2ⁿ  different output states.

---

so i mean to say

A Ring Counter that consist n Flip-Flip will have n-states.

3-bit ripple counter is called as MOD-8 counter. So in general, an n-bit ripple counter is called as modulo-N counter. Where, MOD number = 2ⁿ.

so MOD-258 counter needs 9 bit to store all states so ultimately 9 Flip-Flop.

Tell me if i went wrong somewhere.

Comments

Yes we get the same answer because we can have a combinational circuit which will give the inputs to the D FFs

---

In Ring counter for N flip flops-->Mod(N) counters are possible, in Johnson counter for N flip flops--> Mod(2N) counters are possible..

---

I have a doubt. Why are we not considering that it can be a ring counter? In that case for N states, we will require N D FF. So for 258 states we need 258 D FF.

Answer 3

Following is the $mod-4$ counter using two D-flip flops:

Using the same technqiue we can build $mod-258$ counter using $nine$ D-Flip Flops.

Hence, Answer is (A).

Comments

@Manu Thakur can we say to count 2^n states, we need n flip flops(any flip flop) as we can design a combinational circuit which will provide input such that it will count those many number of states.

@joshi_nitish 

---

Yes , i think 
Combinational logic decides the next state,
flip-flops store the state,
and n flip-flops can represent up to 2^n states.

Answer 4

mod 258 will have 258 states from 0 to 257 so number of bits needed is log 257=9 bits hence the answer is 9.

Answer 5

In general, the minimum no of Flip-flop needed to count a number N = ceil( logN) base2.
So, Mod 258 counter needs = ceil(log 258)= 9 flipflops. It could be mod-258 up/down/random counter.

Although Asynchronous counters use T flip-flops for counting but can be designed by other flip-flops(j-k, D....) and combinational circuits using same no. of flip-flops(9) only.

Note- Only Asynchronous counters can count mod-N using only (log N) flip-flops. If we use any Synchronous counter is surely going to take more than (log N)flip-flops. There are many Synchronous counters which can be designed using a different type of flip-flop(J-K,T...) and combinational circuits which take lesser no. of flip-flops than ring and johnson counter to count mod N. So for Synchronous counters this no. could be (log N)<m<N.

Comments

@Nitesh Singh 2

yes , good for asynchronous counter, but possible for both counters.

right??

because number of FF of ring counter is $N$, and number of FF Johnson counter is $N/2$, while asynchronous counter takes FF $log_{2}N$ (for $N$ number states), right??

---

@Nitesh Singh 2

@srestha

I think we can construct a MOD-n counter using ceil(log N) states using both synchronous and asynchronous counters.(using any type of FF either JK or T or D).

---

@Doraemon

I havenot got what u want to say.

Answer 6

An n-bit binary counter consists of n flip-flops and can count in binary from 0 to 2^n-1

2^n ≥ 258