Nand chip

[throwaway]

As far as implementation goes, and if I read correctly, this is the only one that cannot be implemented by itself?  It is essentially an atom (Democritus' definition)?

The statement in the book that And, Not, Xor and Or can all be built from Nand, leads me to believe that I should not use those chips when describing each other, rather I should use Nand only when implementing primitive types.  Is this the approach you would recommend for a full understanding?

[cadet1620]

throwaway wrote

As far as implementation goes, and if I read correctly, this is the only one that cannot be implemented by itself?  It is essentially an atom (Democritus' definition)?

The statement in the book that And, Not, Xor and Or can all be built from Nand, leads me to believe that I should not use those chips when describing each other, rather I should use Nand only when implementing primitive types.  Is this the approach you would recommend for a full understanding?

You will want to build the chips in the order presented in 1.3. The idea is to learn how to use abstraction.

To begin with, your toolbox only contains Nand gates. Then you build a Not using only Nand gates. Now your toolbox contains Nand and Not gates. Use them to make an And gate.  Use Nand, Not and And gates to make Or.

By the time you get to the ALU in chapter 2, you have a nice toolbox of parts to choose from. It will take you about 15-20 of them to make the ALU.  If you were to build the ALU out of nothing but Nand gates, you'd need nearly 500 of them.  See this post.

--Mark

[throwaway]

Thank you for the quick response and holy crap that's a lot of nands!

I think I'll start with the 'not' now. Cheers!

[Jacob Zimmerman]

Just because this is how I am, I'm going to build the ALU using only NANDS, just like I have been so far.  My biggest reason for doing this is due to the fact that using the AND, OR, and NOT gates would make the XOR and Mux take 4 more NAND gates than a refactored one that uses straight NANDs.
First, I'll design it using the easier gates, but then I'll break them down into NANDs and optimize after than.  I'm kind of an overachiever that way. :)

[cadet1620]

Jacob Zimmerman wrote

Just because this is how I am, I'm going to build the ALU using only NANDS...

It's an interesting challenge.  Most parts need to be repeated 16 times with only the bus indices changed, with lots of opportunity for typos. I wrote an HDL preprocessor that does the require replication.  Here's what Add16.hdlx looks like:

CHIP Add16 {
    IN  a[16], b[16];
    OUT out[16];
    PARTS:
?<1     HalfAdder(a=a[0],  b=b[0],         sum=out[0], carry=c0);
?>0<15  FullAdder(a=a[*],  b=b[*],  c=c*-, sum=out[*], carry=c*);
?>14    FullAdder(a=a[15], b=b[15], c=c14, sum=out[15]);
}

The output from the hdlx preprocessor is the standard Add16 implementation.

"Puzzling out the syntax is left as an exercise for the student."

--Mark

[Jacob Zimmerman]

I just made a Nand16 and will use that for some of the 16-bit operations.  

I already found a slight improvement to the full adder due to breaking it down.  The carryout value from each of the half adders is an And, which is a Nand, then Not(which is just a special case with Nand).  Then when you Or the carryouts to get the full carryout value, it has to Not each of the half-carryouts again as the first step in the Or.  I can remove both of those Nots and save myself several gates.  Multiply by the number of full adders to make a 16-bit adder, and I've saved myself a handy chunk of gates.

[cadet1620]

Good observation. Did you notice that the Nands required for the half-carries are the same as the first Nands in the 4-Nand implementation of Xor that generates the half-sums. You can save another 2 gates per bit by combining them.

What I save by using the conditional capability in my HDLX preprocessor is that I can use a half-adder for bit 0 and don't need to generate a carry from bit 15.

--Mark

[Jacob Zimmerman]

If I had realized that you could do a 4-nand xor, I actually WOULD have noticed that.  :)

I decided to give up my quest to write it all in NANDS when I realized I couldn't come up with a decent naming scheme to keep track of all the inner pins.  If I could write hdl so that the outputs could be used as the input of an encompassing part - like this: Nand(a = Not(in = a), b = Not(in = b), out = out); - I could maybe pull it off without pulling my hair out just to find out what I want to name the pin.
I realize this can get very difficult to read, especially if you're nesting really deep, but the ability to not have to name an output pin would be nice.  

Now, this could obviously only work for certain cases:
1. The inner part could only have 1 output pin.  (There are ways one could program the emulator to get around this, but we'll keep it simple)
2. Input type and output type match (1 bit vs 16-bit bus)
3. You would not want to be using the output from that inner part anywhere else (i.e. the output doesn't fork) - if you did, you would have to rewrite the same part, but it would be simulated and build as an additional part.

That's my rant :P

[Jacob Zimmerman]

So I've implemented using the first Nand in my OHalfAdder (my optimized Half Adder that can only be used in my OFullAdder in order to remove the double Not that is present in the traditional sense) like this:

//Calculate Carry - Nand(a, b)
Nand(a = a, b = b, out = carry);
       
//Calculate Sum - Xor(a, b)
Nand(a = a, b = carry, out = one);
Nand(a = carry, b = b, out = two);
Nand(a = one, b = two, out = sum);

But I'm not allowed to use carry as an input bit, since it's the chip's output bit.
Do you know how to work around that?
Seriously, this software is bugging me with its restrictions.

[cadet1620]

Jacob Zimmerman wrote

So I've implemented using the first Nand in my OHalfAdder (my optimized Half Adder that can only be used in my OFullAdder in order to remove the double Not that is present in the traditional sense) like this:

//Calculate Carry - Nand(a, b)
Nand(a = a, b = b, out = carry);
       
//Calculate Sum - Xor(a, b)
Nand(a = a, b = carry, out = one);
Nand(a = carry, b = b, out = two);
Nand(a = one, b = two, out = sum);

But I'm not allowed to use carry as an input bit, since it's the chip's output bit.
Do you know how to work around that?
Seriously, this software is bugging me with its restrictions.

It's mostly liited documentation.  If you look carefully at appendix section A.5.3 you will see examples showing multiple connections to output pins. This makes sense if you think about soldering multiple wires to a pin.

Another thing that the simulator can do that is not documented (and I don't recommend for normal use) is to use '.' and '-' as non-initial characters in wire names.

Signals like this inverted carry, which means a carry is present when the physical value of the signal is 0, are called active low signals. There are several naming conventions used for active low signals; one of them works particularly well here: append '.N' to the signal name. (In cases where both the true and inverted signal are present, some books add '.T' to the true signal, but I don't like that.)

So OHalfAdder becomes

IN a,b;
OUT sum, carry.N
PARTS:
Nand(a=a, b=b, out=c, out= carry.N);
Nand(a=a, b=c, out=ac);
Nand(a=b, b=c, out=bc);
Nand(a=ac, b=bc, out=sum);

Just because this is how I am, I'm going to build the ALU using only NANDS, just like I have been so far.

You've built everything so far with just Nands? A major goal of this course is to learn abstraction. You might want to take the opposite extreme as a parallel challenge. How few lines of HDL does it take to write each part, using only the chips specified in the book? This really make you think about abstraction.

--Mark

[Matt Keenan]

Actually the three basic CMOS gates are Not (2 transistors), Nand (4 transistors), and Nor (4 transistors). A Not gate is pretty straight forward and is almost never implemented as a Nand with the two inputs wired together, it would just mean more current flow during switching with almost no extra benefit (in reality it provides a slight speed benefit at twice the current draw). Nand gates are very useful due to the electrical properties of the pFET (positively doped Field Effect Transistor) during a rising input signal, and the nFET (negatively doped Field Effect Transistor) during a falling input signal. In a Nand gate the pFETs are wired in parallel, and the nFETs are wired in series; due to the characteristics of the pFET the transistor will shut down current quicker in parallel but will be slower let current flow again once the signal goes low, the converse is true of the nFET; in effect combined this means the Nand gate uses the best of both worlds and transition to either state quicker because it relies on the pFET when the signal goes high and the nFET when the signal goes low. In the case of the Nor gate the opposite is true, it is slower to rise and slower to fall.

All logic gates can be made from entirely Not gates and Nand gates or from Not gates and Nor gates; it is just that normally the Nand gates are quicker, however in some cases it can be quicker to use a Nor gate than several sequential Nand gates.

Then there are some gates such as Xor that quite often use custom wiring; rather than using one Not gate and 3 Nand gates (14 transistors with 2.5 levels of slew delay) you can wire it up with only 6 transistors (with one level of slew delay), there is the down side of slightly reduced output voltage however that may require a double Not gate boost if you wish to use the output of the Xor gate to feed into a fan out (one gate output that drives many other gates' inputs).

At the end of the day the thing to remember is that logic gates are inherently analog, as a software developer it is extremely beneficial to know how computers actually work rather than just guessing, but you need to draw the line somewhere as the rabbit hole is very deep.