2
$\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)

$\endgroup$
1
$\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.

$\endgroup$
  • 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 '15 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 '17 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 '17 at 11:05

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.