3
\$\begingroup\$

Given a full adder with inputs $$A, B \text{ and } C_{in}$$ The formulas for the outputs are $$S = A \oplus B \oplus C_{in} \text{ , Where } \oplus \text{means XOR}$$ and $$C_{out} = AB + AC_{in} + BC_{in}$$

But when a Full Adder is created by combining two half-adders, the obtained equation for carry out is $$C_{out} = AB + (A \oplus B)C_{in}$$

The two expressions have equivalent Truth Tables, but the reason for their equality is not obvious.
Can someone please help me understand how it can easily be seen they're equal?

\$\endgroup\$
2
\$\begingroup\$

Boolean Algebra Approach
The equivalence of the two forms may be proven using boolean identities

Start off with the second expression $$C_{out} = A B + (A \oplus B)C_{in}$$ Using the expansion, $$A \oplus B = \bar AB + A \bar B \quad \text{ for XOR}$$ The right hand side becomes $$AB + \bar A B C_{in} + A \bar B C_{in} \tag{1}$$ Taking B common between the forst two terms, we get (Property of Boolean Algebra) $$B(A + \bar AC_{in})$$ Using the fact that addition distributes over multiplication (In boolean Algebra) $$A + BC = (A + B)(A + C) \tag{2}$$ Hence the term becomes $$B((A + \bar A)(A + C_{in})) = AB + BC_{in}$$ Plugging this back into (1) and reusing property (2) with $$B+ \bar B C_{in}$$ We get the alternate form $$AB + BC_{in} + C_{in} \tag {3}A$$ Intuitive Approach

The form (3) is true or 1, if any two among the 3 inputs are 1. This is the case since there will be a carry if and only if (iff) we add at least 2 1's.

The XOR form, on the other hand, suggests a different viewpoint. It treats the input carry differently than the other 2 inputs A and B. Effectively it is saying that the carry will be 1 iff both A and B are 1 (The AB term) or Exactly one among A and B is 1 and Cin is 1. Note that this is being unnecessarily specific and instead we could say part 2 of the condition is that Either A or B (or both) are 1 and Cin is also 1.

In boolean form this would be, $$AB + (A+B)C_{in}$$ Which is the same as (3)

The OP is advised to refer to the properties and Axioms of Boolean Algebra to prove similar equivalences.

\$\endgroup\$
1
  • \$\begingroup\$ Where does 𝐡+𝐡¯πΆπ‘–𝑛 come from? I thought the term in question would be 𝐴𝐡¯πΆπ‘–𝑛? \$\endgroup\$ – 360ueck Nov 18 '19 at 0:54

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.