Day 13: TECS, Chapter 1, Part 2.

Zach gave me a suggestion that I thought would work.  After half an hour of Googling, it still did not work.  Back to the books!

I picked up exactly where I left off, on the testing scripts.  Here is a test script from the textbook (testing the Xor gate which I discussed yesterday):

load Xor.hdl,output-list a, b, out;   
set a 0, set b 0,   
eval, output;   
set a 0, set b 1,   
eval, output;   
set a 1, set b 0,   
eval, output;   
set a 1, set b 1,   
eval, output;

Oh, man.  This is easy, after understanding the chip itself!  Just load up the chip, specify what goes onto the output list (in this case, our values for a, b, and the evaluated outputs), then set a & b to all combinations they could be, evaluate the chip's function, and output it.  Like unto a pie.  Sure enough, we get:

a | b | out   
0 | 0 | 0   
0 | 1 | 1   
1 | 0 | 1   
1 | 1 | 0 

Hot cha.  What's next?

Next is what the chips are and how to build them.  Easy-peasy, quick an' breezy.  Well, up until we get to the 4-way 16-bit multiplexor, anyway.  The Alert Reader will recall that multiplexors gave me a small headache yesterday, but today I only got slightly narrowed eyes and increased attention.  Demultiplexors were a cinch after that; it's just the same thing, backwards!  Building these exclusively out of NAnd gates?  Ehh, not so much.

I just learned this yesterday.  Now you want me to build it with

two pop tabs and a paperclip?  CHALLENGE ACCEPTED.

(From The Elements of Computing Systems, by Noam Nisan & Shimon Schocker)

But that's the end of the chapter!  Now for the project:  build all the chips/gates mentioned in the chapter out of NAnd only (that would be Not, And, Or, Xor, Mux, DMux, Not16, And16, Or16, Mux16, Or8way, Mux4way16, Mux8way16, DMux4way, DMux8way).  If this were a real course, I'd have a week to do this, so let's see how I feel after doing Not, And, Or, Xor, and Mux.  Then I'll sleep on it and try the rest tomorrow.

Ready?  Go!

First up, Not via NAND.  Easy enough, right?
IN in;
OUT out;
PARTS:
Nand(a=in, b=in, out=out);
Ha ha, NAnd already does the heavy lifting for me!  Load the test script, and:  SUCCESS!  Now for And via NAnd.  Whoah, I almost thought I could just put a Not at the end, but herp-a-derp, that wouldn't work because NAnd isn't the...  Wait.  No, that's exactly what I want!
IN a, b;
OUT out;
PARTS:
Nand(a=a, b=b, out=r1) //the R is for RESULT, get it?
Not(in=r1, out=out); //let's make it more explicit, shall we?
Nand(a=r1, b=r1, out=out);
Load the test script, make sure I didn't do anything stupid, and... SUCCESS!  I'm on a fuckin' roll!  Now for the inclusive Or.  This will require gymnastics...wait, no it won't, because I can just put Nots after a & b before they go into NAND, and poof!  Let's be super explicit again:
IN a, b;
OUT out;
PARTS:
Nand(a=a, b=a, out=nota);
Nand(a=b, b=b, out=notb);
Nand(a=nota, b=notb, out=out);
Too sexy, too sexy!  This is going smoothly.  Now, I can't help cheating for Xor, since I was already given a diagram and the HDL for it; what I can help is whether I cheat further by simply copying, or instead translate the existing HDL into Super-Exciting Mega-Explicit NAnd-Only Language!  (I'm not shouting, the "!" is just part of the phrase.)  The tough part here is now no longer coming up with the HDL, but keeping my terms straight.  I'll make a new diagram and divide it up into three phases like the old one:  the Not phase, the And phase, and the Or phase, finally leading to the output.  Here it is:

I haven't felt this enlightened since I learned why

the square root of two is necessarily irrational.

Hey, r1 & r2 just get Not'ed twice - at the end of the And phase, and at the beginning of the Or phase - which means... carry the one... I can skip steps.  As long as I skip the right ones.  Now I'm actually learning!  Doing that, my new Optimized NAnd-Only Xor HDL is:
IN a, b;
OUT out;
PARTS:
Nand(a=a, b=a, out=nota);
Nand(a=b, b=b, out=notb);
Nand(a=a, b=notb, out=r1);
Nand(a=nota, b=b, out=r2);
Nand(a=r1, b=r2, out=out);
Instead of crossing my fingers, I'ma crack my knuckles.  Crackita-pop!  Plow!  Annnd... SUCCESS!  In the same number of lines of code as their original Xor gate, which needed Not, And, and Or!  HOO-HA!

Uh-oh.  Now for Mux.  OK, there's a reason I decided to make this the last one for the night, and it's not just that it's 10:22.  You're on a roll, just keep it going, man.  Think out loud.  Or on paper.  Erm, in type.  Whatever.  You've got your a in, your b in, and your selector, and the selector decides which input comes through.  I can do this.  Think of it in terms of the shortcuts, first.  Then blow it up into NAnd-Only, then simplify (if you can).  OK.

Dammit, now it's 10:42, and I've been staring at this for 20 minutes and thinking, "No, this won't work.  No, that won't work.  Shit, what am I gonna do?"  Urge... to cheat... rising... WAIT.  Re-draw the truth table so it's less confusing.  OK, now it looks like an Or for a & sel when sel=0, and it looks like an And for b & sel when sel=1.  Good, you can work with this.  Keep going.  All right, it can't trigger the And for b & sel when sel=0, so... run an And from sel & b (result:  selAndb).  Duh.  Keep going.  Run an Or from sel & a (result:  selOra).  Now we've got selAndb which gives b when sel=1 and 0 when sel=0; and we've got selOra which gives 1 when sel=1 and a when sel=0.  Good.  Paragraph break.

Now compare your "mini" truth tables with each other.  Wait.  Duh.  You're barking up the wrong tree here.  Stop trying to make it explicitly perform based on why you know it ought to go, and make it perform based on why it needs to go. Back up and brute force the fucker, then clean it up in post.  You'll be fine.  OK.  Start with sel&a&b=1.  Work up from there.  Run them all to And gates, then make those come out how they ought to do.  Then funnel them into bottlenecks so that you get what you need at the end.

OK, finally.  I got it.  It's 11:50, and I fucking got it.  First, I just did everything in terms of "and," "not," and "output" - not HDL-wise, just logic-wise.  Like, I wrote on a piece of paper:
s&a&b=1
s&a&~b=0
s&~a&b=1
...and so on.  Then I drew up HDL-like parsings of those functions, and tried to make them as similar as possible.  I noticed that I could capture three correct outputs with only (s*a)*b (call it x), four more with (s+a)*b (call it y), and the last one with (s+a)*~b (call it z).  (For the uninitiated, + = or, * = and, ~ = not.)  Then I drew up a truth table for s, a, b across from x, y, z, and also drew up the output.  I noticed that y predicted three of four outputs of 1, and z got the other one when s=0.  The x function was useless, so I discarded it, and made x':  y+(z*~s).  (Fun Fact:  I accomplished this step by folding over the s/a/b section, MAD Magazine fold-in style!  Now that's thinking outside the box!)  Finally, I drew up a schematic for a, b, and s inputs, into y and z functions using And, Or, and Not gates, then put it all through to the x' function, and that gives the output.  So we have:
IN a, b, sel;
OUT out;
PARTS:
Or (a=a, b=sel, out=sva);
And (a=sva, b=b, out=y); //these lines describe the y function
Not (in=b, out=notb);
And (a=sva, b=notb, out=z); //these lines describe the z function, and I can re-use sva from above
Not (in=sel, out=nots);
And (a=z, b=nots, out=zAndNots);
Or (a=y, b=zAndNots, out=out); //these three lines describe the x' function, which is just output
OK, let's see if that runs... SUCCESS!  Holy carp, that was insane.  OK, that's my proof of concept, now to break it down into NAnd-Only.  Picture first?  Picture first!

And to think, this is still the easy part...

Whoops, that "&s" at the bottom coming out of the first NAnd should read "~s"; and I need to label some results r1, r2, and r3; and I should also label that bit that comes out notzAndNots when you come anticlockwise around the lower-right corner.  Not taking another picture, though.  Now for code:
IN a, b, sel;
OUT out;
PARTS:
Nand (a=a, b=a, out=nota);
Nand (a=sel, b=sel, out=nots);
Nand (a=nota, b=nots, out=sva);
Nand (a=sva, b=b, out=r1);
Nand (a=r1, b=r1, out=y); //BAM!  That's y, now for z.
Nand (a=b, b=b, out=notb);
Nand (a=sva, b=notb, out=r2);
Nand (a=r2, b=r2, out=z); //Sweet.  Now to wrap it all up!
Nand (a=z, b=nots, out=r3);
Nand (a=r3, b=r3, out=zAndNots);
Nand (a=y, b=y, out=noty);
Nand (a=zAndNots, b=zAndNots, out=notzAndNots);
Nand (a=noty, b=notzAndNots, out=out); //done!
Plug & chug, and... BAM!  Success on the first try!  And it only took me - TWO AND A HALF HOURS?!  Whatever, I'm done now.  By the stars, I've got a lot to do tomorrow, though... I'm starting to see why hardware designers burn out and how programming conventions become insane.