edited by
11,734 views
26 votes
26 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$
edited by

5 Answers

Best answer
50 votes
50 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
3 votes
3 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 votes
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
2 votes
2 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
Answer:

Related questions

29 votes
29 votes
5 answers
1
Ishrat Jahan asked Nov 1, 2014
11,161 views
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$
44 votes
44 votes
5 answers
3
Kathleen asked Sep 18, 2014
18,991 views
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...
24 votes
24 votes
2 answers
4