Definition
A Half Adder is a logic component that takes in two inputs, and outputs a binary (base 2) representation of how many are set (0, 1, or 2).
Like any good logic designer working on a small part, we’ll start by making a truth table:
iA |
iB |
oSum |
oCarry |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
Design
The first step of getting from truth table to gates is to generate Sum-of-Product logic equations, even with NCL.
oSum = (iA*iB')+(iA'*iB)
oCarry = iA*iB
Now begins the difference: We don’t treat iA'
the same as we would in standard boolean logic. In standard boolean logic, we get the compliment by inverting the single signal. In NCL, we have to use an entirely different signal. In addition, we need logic functions to generate the compliments of our outputs.
oSum.1 = (iA.1*iB.0)+(iA.0*iB.1)
oSum.0 = (iA.1*iB.1)+(iA.0*iB.0)
oCarry.1 = iA.1*iB.1
oCarry.0 = (iA.0*iB.0)+(iA.1*iB.0)+(iA.0*iB.1)
Looking at these functions, it looks like we need 4 2-input gates that each check if both inputs are set (C-Element/TH22), and several gates that check if any inputs are set (OR/TH1n). Lets start by setting up the 4 TH22 gates (the ‘AND plane’):
The gates represent iA'*iB'
, iA*iB'
, iA'*iB
, and iA*iB
from top to bottom. For each of these, if both inputs are set (remember that setting iA.Data0
means iA==0
) the output is set; if both are clear, the output is clear. Since oCarry
is just iA*iB
, we can wire that output up directly. The others use multiple pairs, that are OR’ed together: if any one is set, the output line is set. Sounds like a TH1n gate.
So, that’s the basic Half Adder. I double checked it by annotating the gates to make sure I got the same thing:
Looks good. Now, let’s get fancy.
Optimizing
Optimizing NCL functions should be similar to optimizing standard logic functions. I’m going to try to optimize for logic levels, to see if I can make it all flat.
oCarry.0
By observation, we have symmetry between iA
and iB
, and iA'
and iB'
, Since we don’t want iA*iB
to be enough to trip the gate, lets consider weighting iA'
and iB'
at 2. This gives a THm4W22 gate. Now to figure out m:
- If
iA
and iB
are set, then the total is 2, so we need to be larger than 2.
- If any other 2 lines are set, we have ≥3 (either 2+1 or 2+2)
Three it is. We will use oCarry.0 = TH34W22(iA.0, iB.0, iA.1, iB.1)
oSum
Looking through the table here, I don’t see a matching function for the gates I’ve studied, but there is a XOR gate: THxor0. This gate picks out the first two, and last two inputs as an SOP function.
oSum.0 = THxor0(iA', iB', iA, iB)
oSum.1 = THxor0(iA, iB', iA', iB)
Together
Implementation
I’ll save this for another post.