A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, …, 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 AND, OR and NOT gates may be used, what is the minimum number of gates required?

My Solution: After analyzing the patterns of the 4 bits ABCD

$\\0000\\ 0001\\ 0010\\ 0011\\ 0100\\ 0101\\ 0110\\ 0111\\ 1000\\ 1001\\$

I've come up with this Combinational Circuit

enter image description here

But it took me 5 gates realzize the given output. I was wondering, can we realize the given output with less number of gates ($<$ 5 gates)

  • $\begingroup$ If the triangle is an inverter, you should draw a 'bubble'. Did you try a Karnaugh table ? I get /(/A * (/B + /C./D)) $\endgroup$ – TEMLIB Jan 27 '15 at 21:31

You can solve this problem on your own by writing a program to enumerate all circuits with fewer than 5 gates, and for each one, test whether it has the right truth table. The running time should be minimal, as there aren't that many circuits with fewer than 5 gates.

  • $\begingroup$ By using K-Map I got this function A+BD+BC. Now what steps should I follow to make Combinational Circuit, Is there any article I can read. I've trouble implementing combinational circuit from a boolean function. $\endgroup$ – Atinesh Jan 28 '15 at 12:01
  • $\begingroup$ @Atinesh, did you read my answer? My answer tells you what steps you can take. $\endgroup$ – D.W. Jan 28 '15 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.