1
\$\begingroup\$

enter image description here

It seems that a half adder (there are 2 inside a full adder) can't output both HIGH values for sum and carry, it's either Sum is 1 and Carry is 0 or the inverse. It's never Sum = 1 and Carry = 1.

To make it more explicit, the truth table of a half adder:

 IN               OUT
 A | B (or Cin) | S | C
 0 | 0          | 0 | 0
 0 | 1          | 1 | 0
 1 | 0          | 1 | 0
 1 | 1          | 0 | 1

The carry of the full adder is made with an OR gate, which can never receive 1 in both ins in this context. The difference between an OR and a XOR is that if both ins are HIGH the OR returns 1 and the XOR 0.

So an OR gate seems (at least to me, for now) to be inappropriate for that logic because it would act as if we were supposed to have that possibility, an OR gate outputs 1 if it receives both 1 in, right? Which a XOR gate wouldn't. I suppose it doesn't change anything as it's not supposed to happen so both components would work.

So why use an OR gate instead of a XOR? Is it because it's a less complex component? Is it some kind of convention? Or is it that if in any ("impossible") case both values are HIGH the output should be HIGH? (and possibly cause an error?)

Or did I miss something? I'm new to electronics and it bugged me...

edit: updated with image from @hacktastical and tried to clarify the question.

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

tl; dr version: The full adder is really two half-adders in cascade. In this case they're re-using the first XOR (the first half-adder output) to reduce the full-adder carry-out logic from 3 terms to 2 terms. It saves a bit of hardware (more about this below.)

Breaking it down...

It may be helpful to examine a cascaded pair of half-adders arranged as a full adder:

schematic

simulate this circuit – Schematic created using CircuitLab

Look familiar? That's the classic full-adder, same as you have.

The and-or combo, plus the first XOR, decode the following two conditions that can result in a sum greater than 1 for A,B and Cin:

  • A & B
  • (A != B) & Cin

With the complete Sum and Cout expressions for the full adder written as:

  • Sum = (A != B) != Cin
  • Cout = (A & B) | ((A != B) & Cin)

We see this from the truth table as follows:

 Cin  A  B   => Sum, Cout   Carry-out terms
 0    0  0   =>  0  , 0
 0    0  1   =>  1  , 0
 0    1  0   =>  1  , 0
 0    1  1   =>  0  , 1     A & B
 1    0  0   =>  1  , 0
 1    0  1   =>  0  , 1     (A != B) & Cin
 1    1  0   =>  0  , 1     (A != B) & Cin
 1    1  1   =>  1  , 1     A & B

The table shows by inspection that the second term (the one highlighted in your diagram) is needed to capture the cases where the A,B sum is 1 with a carry-in, and propagate this to Cout.

What if the carry-out OR were instead an XOR?

In this case it would make no logical difference because the two AND terms are never on at the same time. So why wouldn't they use the XOR? An XOR is at least 2 gate delays, while and the OR is just one. In a ripple-carry (and pretty much any) adder, that delay matters: it's a timing critical path. More below.


How to make a full-add go faster.

You can also encode Cout directly from the 3 inputs using 3 terms, noting that any two inputs high results in a carry. So the logic could be:

  • Sum = (A != B) != Cin
  • Cout = (A & B) | (A & Cin) | (B & Cin)

Which would look like this:

schematic

simulate this circuit

This realization would actually have less delay than the cascaded half-adder, at the expense of one more term for Cout. So it's an area-vs-speed tradeoff.

This type of carry logic - looking at the inputs directly - is the basic idea used in a carry-lookahead adder. The idea to minimize the carry-out gate delay from one adder stage to the next. There are many variations on this, but the basic approach is the same: use more logic to look farther up the addition chain to reduce the delay.

More here: http://www.eecs.umich.edu/courses/eecs370/eecs370.w20/resources/materials/17-FastAdders-ch06aplus.pdf

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your detailed answer, this is interesting. I must have not be very clear in my question though because this is not what I meant. I meant, from your diagram AND1 and AND2 NEVER output 1 at the same time. So why use an OR instead of a XOR? \$\endgroup\$
    – mikmikmik
    Apr 11 '20 at 8:04
  • \$\begingroup\$ An XOR is 2 gate delays, while an OR is just one. So speed and complexity - both are better with the OR. \$\endgroup\$ Apr 11 '20 at 8:06
1
\$\begingroup\$

Check your truth tables again. Both outputs are high if all three inputs are high. The top AND gate represents what we call a "carry propagate", meaning that the sum of A and B is one so there is only a carry out if there is a carry in. The bottom AND gate represents a "carry generate"...if both A and B are one there is definitely a carry out of this adder. If either one of these carry conditions is met, then the final carry out is one.

\$\endgroup\$
6
  • \$\begingroup\$ You missed my question, it's not about the full adder outputs. I know you have both outs high with both ins high. I'm talking about before the OR gate. \$\endgroup\$
    – mikmikmik
    Apr 10 '20 at 20:10
  • \$\begingroup\$ OK, but you gave a diagram of a full adder. Why are you asking about a half-adder, and what do you mean by the "second half-adder"? The diagram is not simply two half-adders, it is a single full-adder. \$\endgroup\$ Apr 10 '20 at 21:11
  • \$\begingroup\$ This is a pair of half-adders in cascade, wired to form a full adder. The ask, I believe, is about how the carry works without an XOR. The fact is, for this configuration the first XOR is a factor in the carry , though it's not the only way to make carry. \$\endgroup\$ Apr 11 '20 at 3:32
  • \$\begingroup\$ Thanks guys for your replies. As @hacktastical pointed out this is 2 half adder with an OR at the end. I'm sorry my question was not explicit enough. I'm only asking about why the OR after the 2 half adder is not a XOR, as I think it should be, even though both would work. \$\endgroup\$
    – mikmikmik
    Apr 11 '20 at 7:47
  • \$\begingroup\$ Yes, I see that. I'll add that in to my answer. \$\endgroup\$ Apr 11 '20 at 8:01

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.