A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1…
2004
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 ≥ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?
- A.
2
- B.
3
- C.
4
- D.
5
Attempted by 102 students.
Show answer & explanation
Correct answer: B
Solution
Name the input bits A B C D where A is the 8's bit, B is the 4's bit, C is the 2's bit and D is the 1's bit. The digits 5 through 9 have binary representations 0101, 0110, 0111, 1000, 1001.
Key expression: Output = A OR (B AND (C OR D))
Compute C OR D with one OR gate.
AND that result with B using one AND gate to form B AND (C OR D).
OR that result with A using one OR gate to get A OR (B AND (C OR D)).
Total gates required: 3 (two OR gates and one AND gate). No NOT gates are required.
Minimality justification: the expression contains an inner OR (C OR D) whose result must be available to an AND with B, and then that result is ORed with A. With only AND, OR and NOT gates, this two-level structure requires at least three gates; therefore 3 is the minimum.