GATE CSE 1996 | Question: 2.25

Question

A micro program control unit is required to generate a total of $25$ control signals. Assume that during any micro instruction, at most two control signals are active. Minimum number of bits required in the control word to generate the required control signals will be:

• A. $2$
• B. $2.5$
• C. $10$
• D. $12$

Comments

@Vishnathan in case of horizontal programming answer will be 25+25=50 because for every state we need one bit 

---

@Vishnathan , Yes there will be 25 bits in the control word in case of Horizontal Programming

---

25 control signals given, that requires 5 bits, among that five bit atmost 2 bits are used for activating 2 control signals, hence 5C2 combination can be made. 5c2 = 10

Answer 1

The best sense I can make of this question is that you want to transmit up to $2$ simultaneous signals out of a choice of $25$, and ask how many bits you need for that.
 
One solution would be to have $2$ groups of  $5-bits$, each can send one of $31$ signals (or the absence of signal). But it is not optimal.  The number of different states is

$1 \text{(no signal)} + 25 \text{(one signal)} + (25\times 24/2) \text{(two signals)} = 326\text{ states}.$  

You can transmit any of these states over $9 -bits$.  But it is more complex to encode/ decode, adding an extra bit would probably cost less.
Hence C is correct option.

Reference: https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1354778770

Comments

vnc  , Milicevic3306 

are you suggesting that 6 is the best answer...?

---

Ans=10 (c)

---

@vnc Sir , Please correct me if this is wrong !

 I think it can still be done with 9 bits.

Lets consider we are allocating each type a address pattern.

1. No signal instruction    = needs 1 address             [ nC0 ]

2. One signal instruction  = needs 25 addresses       [ nC1 ]

3. Two signal instruction  = needs 300 addresses     [ nC2 ]

We can allocate as follows:

1. 000XXXXXX = No signal ( 64 addresses)

2. 001XXXXXX = One signal  ( 64 addresses – needs only 25)

3. Now remaining are 010XXXXXX (64 addresses) , 011XXXXXX  (64 addresses)            1XXXXXXXX ( 256 addresses) So total (64+64+256 ) = 384 addresses.                             These can be given to Two signal instruction 

I just have one doubt, if such question is NAT then will the answer 9 or 10 both be accepted ?

---

https://www.youtube.com/watch?v=AZnBRqyYnXQ refer this 

Answer 2

To generate 25 different control signals 5 bits are required....at any time atmost 2 signals are active..so control word length=5+5=10 bits

Comments

1 query..although it is not in an opton but can we use 25bits(horizontal)?

---

@cse7 Its asking for minimum bits in question.

---

In question, minimum number of bits for control signals is asked therefore assume it is as vertical microprogrammed.

No. of bits required= lg(25)=5

Max control signals active = 2

∴ minimum number of bits required in the control word to generate control signal = 2x5=10.

Answer 3

since the question is talking about the minimum bits for control signals, it is only possible if we assume vertical microprogrammed. Now in vertical we take a decoder and with the help of decoder in order to generate 25 signal we require at least 5 bits, but with this we can generate only 1 signal to generate 2 signals we have to have other 5 bits thus all the combination of 2 signal can be generated.

Answer 4

The question says 

A micro program control unit is required to generate a total of 25 control signals. Assume that during any micro instruction, at most two control signals are active

 Here at most means the number of signals that can be active at a time can be 1 or 2 and we also have to consider the case when no signals are active.

As minimum number of bits is asked so we will go for vertical micro programming. There are 25 control signals any 2 at most can be active so no. of ways this can happen =

$^nC_0\ +\ ^nC_1\ +\ ^nC_2 $ here n = 5 so we get the value as 326 ways.

Now, 9 0s will represent no signal Let us try to divide the rest 325 ways on the basis of number of signals active (1 or 2) at a time.

Let's say we are using first and second bit to represent 1 active and 2 active signal.

CASE 1: Let us consider the first 2 bits as 10 represent "1 signal is active at a time" and 11 represents "2 signals are active at a time ".  Now we can see that we are left with 7 bits so no. of control signals in which 1 signal is active is $2^7 = 128$. Similarly, no. of control signals with 2 signals active at a time is also $128$. But the number of control signals we get for "2 signals are active at a time " is 300. so, we cannot use this process.

CASE 2: Let us consider 01XXXXXXX for "1 signal is active at a time" and 1XXXXXXXX for "2 signals are active at a time ". Even in this case we are getting the number of control signals for which 2 signals are active as $2^8 = 256$. So, we can see that we need to add an extra bit in order to differentiate between the two types (1 and 2) of control signals. 

 

So, answer is (C) 10 bits

 

Comments

@Pratyush+Priyam+Kuan

But the number of control signals we get for "2 signals are active at a time " is 300

can you please explain how we are getting 300 control signals? 

---

we also have to consider the case when no signals are active.

@Pratyush Priyam Kuan Surely, but i have one doubt. “No signals are active” means “no control signal is being generated” and the Question is asking for minimum number of bits required in the control word “to generate” the required control signal. So why are we considering this case?

---

can you please explain how we are getting 300 control signals? 

@Pranavpurkar It comes from the combination, where 2 control signals are active simultaneously, from the set of given 25 control signals. (25C2 = 300)

---

@Shubham Sharma 2 .

Yes , one edit is needed in the answer.

in place of  $n=5$ it should be $n=25$.