3
$\begingroup$

How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)?

(This question was redirected to CS from Stack Overflow)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

A two's complement operation is simply a one's complement operation followed by the addition of 1 to the result. One's complement is easy: simply invert all of the input bits.

The addition of 1 must be done with a 4-bit adder. A 4-bit adder is constructed using four stages of a 1-bit full adder. The 1-bit full adder accepts two bits, plus a Carry input, and generates the sum of the two bits, plus a Carry output. The following diagram is a 1-bit full adder:

enter image description here

We can cascade four of the 1-bit full adder stages together, feeding the Carry output of each stage to the Carry input of the next stage. The inverted (one's complement) inputs are applied to the B inputs of the four stages. To perform an addition of 1, we apply the 4-bit binary value 0001 to the A inputs. The complete boolean circuit is shown below:

enter image description here

The above circuit can be reduced by noting that each XOR operation on the input of each adder stage can be replaced either with an inverter if the A input is a 0, or a NOP (no operation) if the A input is a 1. On further analysis, further reductions may be made to the circuit, as well.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ If you need to increment, one half adder per bit is enough (you'll have the same result if you simplify the above circuit by considering the constant input). $\endgroup$
    – AProgrammer
    Dec 22, 2015 at 15:58
  • $\begingroup$ Won't the Cout of each stage be generated from an OR gate? Can't help but notice you are using an X-OR gate to generate the Couts'. $\endgroup$
    – Shashata Sawmya
    Aug 6, 2017 at 5:38
  • $\begingroup$ You are very perceptive. The Cout can be generated by either an OR gate or an XOR gate. This is because the two inputs to that gate are never both 1 at the same time. (Create a truth table to convince yourself of this.) But you should post your question as a comment to my answer, and not as a new answer to the question. $\endgroup$
    – sifferman
    Aug 6, 2017 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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