Register

GATE CSE 2004 | Question: 58

• edited by
19,973 views
46 46 votes

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?

  1. $2$
  2. $3$
  3. $4$
  4. $5$

5 Answers

Best answer
74 74 votes

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.

• edited by
9 9 votes

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) )

• edited by
5 5 votes
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.
2 2 votes

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.

• reshown by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2004 | Ques...Next → · GATE CSE 2004 | Ques...
← Previous in category · GATE CSE 2004 | Ques...Next in category → · GATE CSE 2004 | Ques...
Position:
Show:

Related questions

41 41 votes
5 answers 5 answers
17.0k
17.0k views
Ishrat Jahan asked Nov 1, 2014
16,967 views
GATE IT 2004 | Question: 8
What is the minimum number of $\text{NAND}$ gates required to implement a $2\text{-input EXCLUSIVE-OR}$ function without using any other logic gate?$2$$4$$5$$6$
123 123 votes
23 answers 23 answers
57.0k
57.0k views
Kathleen asked Sep 18, 2014
57,007 views
GATE CSE 2004 | Question: 62
A 4-bit carry look ahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both com...
55 55 votes
5 answers 5 answers
27.6k
27.6k views
Kathleen asked Sep 18, 2014
27,621 views
GATE CSE 2004 | Question: 61
Consider the partial implementation of a $2-bit$ counter using $T$ flip-flops following the sequence $0-2-3-1-0,$ as shown below.To complete the circuit, the input $X$ sh...
39 39 votes
4 answers 4 answers
12.3k
12.3k views
Kathleen asked Sep 18, 2014
12,338 views
GATE CSE 2004 | Question: 60
Consider a multiplexer with $X$ and $Y$ as data inputs and $Z$ the as the control input. $Z=0$ selects input $X$, and $Z=1$ selects input $Y$. What are the connections re...