GATE CSE 2004 | Question: 58

Question

A circuit outputs a digit in the form of $4$ bits. $0$ is represented by $0000, 1$ by $0001, \ldots, 9$ by $1001$. A combinational circuit is to be designed which takes these $4$ bits as input and outputs $1$ if the digit $\geq$ $5$, and $0$ otherwise. If only $\textsf{AND}, \textsf{OR}$ and $\textsf{NOT}$ gates may be used, what is the minimum number of gates required?

• A. $2$
• B. $3$
• C. $4$
• D. $5$

Comments

Prateek's answer is right, Since min no. of gates have been asked so we can assume 3-i/p gate is available and for the don't care part , he has taken 1s in place of don't care.

or A + BC + BD => A + B(C + D) only 2 i/p gates are required.

---

$f(A,B,C,D) = A+BD+BC = A+B(C+D)$

---

when the output of circuit is till 9 (1001). then why the combinational circuit is taking 16 combination of inputs?

means i know from 4 bits 2^4 =16 combination possible

Answer 1

Answer should be (B). As according to question, truth table will be like: $$\begin{array}{c c c c |c} \hline A & B & C & D & f \\\hline 0 & 0 & 0 & 0 & 0 \\ 0&0&0&1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1   & 0 \\ 0 & 1 & 0 & 0  & 0 \\ 0 & 1 & 0 & 1  & 1 \\ 0 & 1 & 1 & 0  & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & \text{don’t care} \\ 1 & 0 & 1 & 1 & \text{don’t care} \\ 1 & 1 & 0 & 0 & \text{don’t care} \\ 1 & 1 & 0 & 1  & \text{don’t care} \\ 1 & 1 & 1 & 0  & \text{don’t care} \\ 1 & 1 &1 & 1 & \text{don’t care} \end{array}$$

Using this truth table we get  $3$ sub cube which are combined with following minterms  $A (8,9,10,11,12,13,14,15)$, $BD( 5,13,7,15)$ and $BC(6,7,14,15)$ 

So, $f = A+ BD +BC= A+ B(C+D)$

So, minimum gate required $2$ OR gate and $1$ AND gate $= 3$ minimum gates.

Comments

@MiNiPanda

Sir used it, just encountered in one of the vid. But comments above saying it wrong.

---

0001,…,90001,…,9 by 1001

the important to is to see that they are only considering digits upto 9 . so after 9 any no will be dont care ony .

---

Damn we are so primitive ppl that we didn't recognize that 10-15 are not digits 😂

Answer 2

We should get output 1 for values>=5

Making truth table for problem
A     B     C     D     Op
0     0     0     0     0
0     0     0     1     0
0     0     1     0     0
0     0     1     1     0
0     1     0     0     0
0     1     0     1     1
0     1     1     0     1
0     1     1     1     1
1     0     0     0     1
1     0     0     1     1
1     0     1     0     X
1     0     1     1     X
1     1     0     0     X
1     1     0     1     X
1     1     1     0     X
1     1     1     1     X

Putting this in kmap and solving

 

49

Here crucial point is that we need to make pair of 8 elements using don’t cares also…so final expression is

A+BD+BC

    A+B(C+D)

Hence we’ll use two OR gate and one AND gate so total 3 gates.

Ans (B) part.

Answer 3

We should get output 1 for values>=5

Making truth table for problem

A	B	C	D	Op
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	1
1	0	1	0	X
1	0	1	1	X
1	1	0	0	X
1	1	0	1	X
1	1	1	0	X
1	1	1	1	X

Putting this in kmap and solving

Here crucial point is that we need to make pair of 8 elements using don’t cares also…so final expression is

A+BD+BC

• A+B(C+D)

Hence we’ll use two OR gate and one AND gate so total 3 gates.

Ans (B) part.

Answer 4

An intuitive solution,

let ABCD be 4bit input, A being most significant bit, D being least significant..

Nice thing here is to observe that if A is 1, then given input will always be greater than 5 irrespective of what other bit says,(because weight of A is 8)

if B is 1, then we are sure that number is at-least 4, but we need it to be at-least 5, so together with B, if any of C or D is true than it does our job..  (assuming A as don’t care )

B(C+D) will ensure that it is >= 5,

IF both A,B are false, there no way we can make our condition true, (x>=5)

so possible ways are either A is one, or B,C both are one, or B,D both are one, which gives

f = A + BC + BD

we need 3 gates to realize this function, ( two 2-input AND gates, and one 3-input OR gate, using form A+BC+BD) / ( two 2-input OR gates, and one 2-input AND gate, using form A+ B(C+D) )

Comments

Great one!