It's all fu

August 13, 2018 12:37 PM

NandGame.com will take you though building a working computer, starting from the most basic components.

Inspired by From Nand to Tetris: Building a Modern Computer From First Principles.

posted by zamboni (46 comments total)

This was pretty much exactly my digital engineering class in college, from what I remember. Which is not much, because I got a B-
posted by muddgirl at 12:53 PM on August 13, 2018 [4 favorites]

hello, welcome to my undergraduate education. this is about $1000 worth of education at a top-tier engineering school. well, this plus a few lectures on boolean logic. They made us synthesize all the boolean operations by hand before we had to express them in gates, which honestly makes the hardware work way, way easier. Simulators like this make it too easy to just keep stabbing at it until you get it.

Do they eventually get to jump prediction or do they gloss over optimizations?
posted by GuyZero at 12:59 PM on August 13, 2018 [1 favorite]

For those seeking to learn with a little more polish and UI, I'd recommend the "game" MHRD (Steam link).

If you'd like a little more of a challenge, I'd recommend nand2tetris and its accompanying course.

Great ways to to flesh out one's knowledge and put another feather in your cap.
posted by Christ, what an asshole at 1:02 PM on August 13, 2018 [3 favorites]

The Elements of Computing Systems is a great book/course if this is excites you.
posted by Dr. Twist at 1:14 PM on August 13, 2018 [1 favorite]

If you'd like a little more of a challenge, I'd recommend nand2tetris and its accompanying course.

Right on the money! "The Nand Game is inspired by the amazing course From NAND to Tetris - Building a Modern Computer From First Principles which is hightly recommended."

---
Is there a way to save your progress and come back later?
posted by thelonius at 1:31 PM on August 13, 2018

Is there a way to save your progress and come back later?

Maybe it's saving a state cookie; I pasted the link into a new browser window, and it gives me the components I built in the old window.
posted by thelonius at 1:35 PM on August 13, 2018

Screw all this electrical stuff, if you really want to learn alchemical engineering I recommend Opus Magnum.
posted by Nelson at 2:20 PM on August 13, 2018 [2 favorites]

MHRD looks pretty cool, tho it's using more of a Verilog-type language than connecting graphical components with wires (although the concepts are the same). What a crazy time for games.
posted by RobotVoodooPower at 6:05 PM on August 13, 2018

I sincerely believe that if The Aliens have a similar understanding of little things like light and mathematics then they too must have parallel-invented Pong, Breakout, Pac-Man and Tetris.
posted by I'm always feeling, Blue at 6:38 PM on August 13, 2018 [2 favorites]

Yes, this is like my digital design class, though we had to actually hook up gates with wires and connect up LED displays.

For graduation from the lessons they should offer a kit of your actual final design in a programmable chip that you power up and run so you can develop a sense of the theory turned into something tangible.
posted by eye of newt at 11:32 PM on August 13, 2018 [1 favorite]

This is also largely my memories of Computer Architecture 101 and 102. I managed to blaze through, even though those classes are nearly two decades behind me, until I got to the subtraction puzzle. I managed to do that one by constructing a 1 out of unconnected values to correct the value of the inversion (which was off by one from the desired value). I wonder how I was supposed to do it?
posted by JHarris at 12:03 AM on August 14, 2018

I sincerely believe that if The Aliens have a similar understanding of little things like light and mathematics then they too must have parallel-invented Pong, Breakout, Pac-Man and Tetris.

Wait til you see what they've been up to since then.
posted by curious nu at 4:02 AM on August 14, 2018

Holy shit 20 years and I can still build a full adder... I've got an engineering scratch pad sitting to my left filled with shitty attempts at truth tables for a few of the bastardizations I attempted in between. At least one of them was something I remember being useful...
posted by Nanukthedog at 5:32 AM on August 14, 2018

It didn't seem to retain my half-adder in the toolkit, what's up with that? Am I just not supposed to need it, since it's equivalent to a full addder with a constant carry input of 0?
posted by thelonius at 6:10 AM on August 14, 2018

For those seeking to learn with a little more polish and UI, I'd recommend the "game" MHRD (Steam link).

Got pretty far into MHRD (right before the last puzzle I think) before getting stuck because the way I was doing things would no longer fit into the code length constraint. I posted a question with a screenshot to the game's Steam forum and the developer basically replied that the way I was doing things was wrong and bad. Yet it had worked the whole game. I never did untangle it.
posted by snuffleupagus at 6:49 AM on August 14, 2018

YOW! 2011 Damian Conway - Temporally Quaquaversal Virtual Nanomachine

NAND gates using rod logic implemented in Perl with a dash of quantum mechanics and temporal relativity.
posted by zengargoyle at 7:15 AM on August 14, 2018 [2 favorites]

I am living proof that you can get an advanced degree in engineering and have no idea how computer logic works.
posted by runcibleshaw at 11:10 AM on August 14, 2018 [1 favorite]

20 years and I can still build a full adder.

I got mine to work, but I have a bad feeling it isn't optimally efficient yet
posted by thelonius at 11:18 AM on August 14, 2018 [1 favorite]

snuffleupagus: I posted a question with a screenshot to the game's Steam forum and the developer basically replied that the way I was doing things was wrong and bad. Yet it had worked the whole game. I never did untangle it.

StackOverflow is leaking
posted by JauntyFedora at 11:48 AM on August 14, 2018 [2 favorites]

Ah, they got the Counter and Switch levels, um, switched, in order!
posted by JHarris at 12:01 PM on August 14, 2018

Also, count me disappointed that you don't get to build a 4 by 4 bit multiplier, which was my final project for Computer Architecture 102.
posted by JHarris at 12:03 PM on August 14, 2018 [1 favorite]

It didn't seem to retain my half-adder in the toolkit, what's up with that? Am I just not supposed to need it, since it's equivalent to a full addder with a constant carry input of 0?

The things you've given are based on what you need, it's not the sum of everything you've done, which would add a lot of clutter.
posted by JHarris at 12:04 PM on August 14, 2018 [1 favorite]

The things you've given are based on what you need, it's not the sum of everything you've done, which would add a lot of clutter.

I guess. In reality you end up making everything out of NAND gates so if you cheat and google for solutions they'll be all NAND gate based. I'm not sure you really need to retain the inverters and OR gates although I guess they don't hurt. If you need an XOR it is indeed a PITA to rebuild it every time.
posted by GuyZero at 12:46 PM on August 14, 2018 [1 favorite]

StackOverflow is leaking

Quite right. It's not that I couldn't have looked elsewhere, and I may at some point. I'd just keep in mind that MHRD is manifestly not intended as a teaching tool (in the way that some of these others are). It did a lot to improve my understanding of computing concepts, but not necessarily actual engineering practices.
posted by snuffleupagus at 1:16 PM on August 14, 2018

I found the half adder more misleading than helpful when figuring out the full adder. Is there a solution for full adder that uses more than one half-adder? I only found that one after figuring it out without that and then optimizing
posted by vibratory manner of working at 6:16 PM on August 14, 2018

I got mine to work, but I have a bad feeling it isn't optimally efficient yet

There it is! My least significant bit in the answer was computed by:

(p and not (q xor r)) or (not p and (q xor r))

which simplifies to :
p xor (q xor r)

a savings of 5 gates!
posted by thelonius at 6:58 PM on August 14, 2018 [2 favorites]

I started poking at this and after a few levels went "wait, fuck, this is just redstone from Minecraft!"

...I, uh, may learn things from odd places.
posted by Pope Guilty at 7:05 PM on August 14, 2018

Data flip-flop is telling me I'm not correct but either I'm misunderstanding the specification or it's just wrong

( cl latch ( st latch d ) )
posted by vibratory manner of working at 7:28 PM on August 14, 2018 [1 favorite]

I figured it out, I needed to prevent latch one from being set if cl = 1.
posted by vibratory manner of working at 9:25 PM on August 14, 2018 [3 favorites]

Also found an optimization on the most signifigant bit:

(p and (q or r)) or ((not p and q and r) ) simplifies to
(p and (q or r)) or (q and r)

which seems weird at first, but, if you have q and r, you have q or r, and there's no need for the not-p term, since the left side of the disjunction will be true if p is true and the right will be true if it is false
posted by thelonius at 9:58 PM on August 14, 2018 [1 favorite]

I didn't bother trying to optimize any of my productions as soon as I figured out that the game was deliberately withholding the resources required to do so. And since gate golfing is pretty much the only interesting part of this game for me, the fact that it deliberately hides gates you "don't need" made me lose interest fairly quickly.
posted by flabdablet at 10:29 PM on August 14, 2018 [1 favorite]

I learned the Boolean logic side of this first, and I can't help myself but to worry about simplifying expressions; when I took a computer architecture class (20 years ago now!) I learned they had some method to optimize gates, not taught in logic class, that I can't recall how to do any more...Karnaough maps iirc.......I just figure if I make the simplest expression I can find, and translate it into gates, it's going to be better.......but I don't remember how to prove an expression is as simple as possible though (if I ever knew)

This is fun! It's a trip that it even works on paper, much less that it can be implemented at such tiny scales as they do.
posted by thelonius at 10:34 PM on August 14, 2018

It's a trip that it even works on paper, much less that it can be implemented at such tiny scales as they do.

Even more of a trip when it occurs to you that what's actually done on those tiny scales amounts to making tiny little inscriptions on tiny little stones using a highly specialized runic alphabet. We've actually figured out a system of magic writing that works.
posted by flabdablet at 10:45 PM on August 14, 2018 [5 favorites]

when I took a computer architecture class (20 years ago now!) I learned they had some method to optimize gates, not taught in logic class, that I can't recall how to do any more...

An exercise we were given in an early electronics engineering class was as follows: you have four inputs built from a pushbutton and a resistor each, and one output consisting of a LED and a current-limiting resistor.

Using only two-input NAND gates, design a circuit that lights the LED (which must be driven by just one gate output) only when three or more of the buttons are pushed.

I pretty quickly worked out the same eighteen-gate solution as most of my classmates, but it nagged me. Showed it to a good friend with actual working-EE skills, and he pretty quickly did it in ten. Can't remember how any more.
posted by flabdablet at 10:59 PM on August 14, 2018 [1 favorite]

So it seems I've learned something since then, because I just revisited that problem, solved it in eight gates and verified the result here.
posted by flabdablet at 12:46 AM on August 15, 2018 [2 favorites]

8 gate solution. This simulator doesn't offer NAND gates as primitives, so each of them is built from an AND and an inverter here.
posted by flabdablet at 5:06 AM on August 15, 2018 [1 favorite]

In logic class, we learned to prove that a minimal set of connectives was sufficient to do all of propositional logic. You can do everything with the connectives not and or, or not and and, and then there are the one-connective sets, which correspond to NAND and NOR gates. You can think of NAND as a primitive, but I think it basically always has to have internal components - logically, it combines two ideas, and I think it must do so electronically too.
posted by thelonius at 6:21 AM on August 15, 2018

I found the half adder more misleading than helpful when figuring out the full adder. Is there a solution for full adder that uses more than one half-adder?

You can do it with two half-adders and an OR gate. Use one of the half-adders to sum two of the input bits, yielding a two-bit result that can be either 00, 01 or 10. Use the second half-adder to sum the low bit of that result with the third input bit. The low bit of that result will then be the low bit of the sum of all three inputs.

If either of the half-adders generates a 1 on its high bit then there must be at least two inputs high and the full adder's high bit should be 1 as well; ORing the high bits from both half-adders yields the desired result.

Total size of this solution is 15 NAND gates, assuming optimal solutions for all the building blocks (it takes 3 NAND gates to build an OR gate and six to build each half-adder; four for the XOR inside it and two for the AND).

But starting from the full adder's truth table and messing about with Boolean logic, it's possible to generate a full adder in 14 NAND gates.

The process I used for that is as follows:

Start with the truth table:

a b c | h l
------+----
0 0 0   0 0
0 0 1   0 1
0 1 0   0 1
0 1 1   1 0
1 0 0   0 1
1 0 1   1 0
1 1 0   1 0
1 1 1   1 1

Read off the corresponding Boolean equation for output h:

h = ~a.b.c + a.~b.c + a.b.~c + a.b.c

The design is constrained to using two-input gates, so it will help to express all the equations in ways that apply each operator to exactly two inputs. Pull out some common factors in the equation for h:

h = c.(~a.b + a.~b) + a.b.(c + ~c)

(c + ~c) is always true, and ANDing with a true value is redundant, so we get

h = c.(~a.b + a.~b) + a.b

The only gates available are NAND, so those OR operations can't be implemented directly in hardware. Use the Boolean identity X + Y = ~(~X.~Y) that forms the basis for the OR gate made of NANDs, and rewrite:

Put X = ~a.b, Y = a.~b. We then have
h = c.(X + Y) + a.b
h = c.(~(~X.~Y)) + a.b
h = c.(~(~(~a.b).~(a.~b))) + a.b

Now put X = c.(~(~(~a.b).~(a.~b))), Y = a.b. We then have
h = X + Y
h = ~(~X.~Y)
h = ~(~(c.(~(~(~a.b).~(a.~b)))).~(a.b))

and that's an expression for h made entirely out of two-input NAND operations so it can be implemented directly in two-input NAND gates.

Now work similarly on the equation for l. Reading off from the truth table:

l = ~a.~b.c + ~a.b.~c + a.~b.~c + a.b.c

Pull out common factors to reduce operators to two inputs. There's a lot of symmetry in this equation and it can be factorized in several ways, but doing it this way generates some terms involving combinations of a and b that have already been seen in the equation for h and that will save gates:

l = ~c.(~a.b + a.~b) + c.(~a.~b + a.b)

Using the Boolean identity for OR, this becomes

l = ~c.~(~(~a.b).~(a.~b)) + c.~(~(~a.~b).~(a.b))
l = ~(~(~c.~(~(~a.b).~(a.~b))).~(c.~(~(~a.~b).~(a.b))))

That initially looks pretty horrendous, but there are subexpressions there that occur in the equation for h as well:

~(a.b)
~(~(~a.b).~(a.~b))

and these can share gates.

To translate the equations to circuitry, the first step is to notice that they refer to all of a, ~a, b, ~b, c and ~c. So as well as the three input signals, the circuit will need all their complements and that takes three NAND gates wired as inverters. Those are the leftmost three in the circuit as drawn, and they feed a set of six vertical lines carrying a, ~a, b, ~b, c and ~c in that order.

The ~(a.b) signal that both outputs need comes from the second gate down in the middle block, the shared ~(~(~a.b).~(a.~b)) signal comes from the three below that, and every other ~(x.y) sub-operation corresponds to a NAND gate with its inputs wired to x and y.

That was fun! If anybody can make a full adder in less than 14 gates, please do share.
posted by flabdablet at 9:54 AM on August 15, 2018 [2 favorites]

You can think of NAND as a primitive, but I think it basically always has to have internal components - logically, it combines two ideas, and I think it must do so electronically too.

Turns out that it kind of doesn't. In both CMOS and TTL, it takes more transistors to make an AND gate than it does to make a NAND.

In the case of TTL you can kind of see a separate inverter stage in the NAND gate if you squint, but the main purpose of that stage is to regenerate proper logic levels, and that turns out to be more complicated if you don't allow the amplifier involved to be inherently inverting.

Any attempt to break the NAND function down into something "more primitive" involves re-interpreting the logical meaning you're assigning to any given range of voltage and current levels inside the chip, so it's at least arguable that gates working on well-defined and standardized voltage ranges for 0 and 1 are indeed the primitives of electronic digital logic.
posted by flabdablet at 10:05 AM on August 15, 2018 [3 favorites]

Turns out it's possible to make a half adder from five NAND gates, and a full adder from nine.

Trick is that the leftmost gate in this four-NAND implementation of the XOR gate that you need for the low bit of a half adder also generates a value that just needs inverting to turn it into a half-adder high bit.

And once you've used a pair of two-input XOR gates to make the three-input XOR required for a full adder's low bit output, you've already got both the half-adder high bits you need to OR together for the full-adder high bit, already in the inverted form that you need for an OR achieved via the X + Y = ~(~X.~Y) rule. Neat!
posted by flabdablet at 11:43 AM on August 15, 2018 [2 favorites]

Same here, vibratory manner of working :(
posted by motty at 6:48 PM on August 15, 2018

In both CMOS and TTL, it takes more transistors to make an AND gate than it does to make a NAND.

Very interesting - I did not know that!
posted by thelonius at 6:59 PM on August 15, 2018

I emailed the creator of simulator.io to ask for a NAND gate to be added to the available circuit elements, and he wrote back and pointed out that the tool already has the ability to toggle inversion on any input or output of any element just by clicking on it with the wiring tool. So I've tidied up all the NAND circuits I linked above:

Four-input majority detector in 8 gates
Full adder in 14 gates

Full adder in 9 gates made from a half adder in 5 and an XOR in 4
posted by flabdablet at 4:45 AM on August 16, 2018 [1 favorite]

Something odd happened to the majority detector. Here it is again.

Four-input majority detector in 8 gates
posted by flabdablet at 5:43 AM on August 16, 2018 [1 favorite]

This subexpression that occurs in the design of the 14-gate full adder

~(~(~a.b).~(a.~b))

bears closer examination. Given that it contains ~a and ~b terms, and we'll be using a whole NAND gate to do each of those inversions, is there some way to make more productive use of both that gate's inputs?

What happens if instead of ~a and ~b, we use ~(a.b) for both? That would make the first of the inner subexpressions look like ~(~(a.b).b) instead of ~(~a.b).

If either input of a NAND operation is false, the output will be true. If b is false, then ~(~a.b) is true regardless of what a is. In other words, the only time the ~a term actually matters if if the b term is true. But if the b term is true, then a.b is the same as a, and ~(a.b) is the same as ~a. So the new form of the subexpression actually does the same job as the old one.

Similar reasoning applies to replacing ~(a.~b) with ~(a.~(a.b)); that works too.

So now the whole subexpression looks like this:

~(~(~(a.b).b).~(a.~(a.b)))

and only needs a single gate to generate ~(a.b) instead of two to make ~a and ~b separately.

This subexpression occurs in the equations for both outputs, so we can generate it just once and wire its output to two places. Miight as well give the intermediate signal a name and plug that back into the equations instead. That tidies them up a bit:

x = ~(~(~(a.b).b).~(a.~(a.b)))
h = ~(~(c.x).~(a.b))
l = ~(~(~c.x).~(c.~(~(~a.~b).~(a.b))))

So now the only place that ~a and ~b still exist is in the ~(~a.~b) subexpression. Can anything be done about that? What happens if we try the same trick, replacing both ~a and ~b with ~(a.b)?

~(~a.~b) is false only if both ~a and ~b are true; that is, only if both a and b are false. On the other hand, ~(~(a.b).~(a.b)) reduces to ~(~(a.b)) = a.b, which is false if either of a or b is false. If a and b are the same, this difference doesn't matter, but it does if they're different.

But wait! This subexpression is itself getting NANDed with ~(a.b); and if a and b are different, then a.b will be false and ~(a.b) will be true, which means we do care about the state of the thing we're NANDing with it. So that's a dead end.

What's this thing's truth table look like anyway?

a b | ~(~a.~b) | ~(a.b) | ~(~(~a.~b).~(a.b))
----+----------+--------+-------------------
0 0 |     0    |    1   |        1
0 1 |     1    |    1   |        0
1 0 |     1    |    1   |        0
1 1 |     1    |    0   |        1

Looks like an inverted XOR. What about the other thing, the one that ended up as x?

a b | ~(~a.b) | ~(a.~b) | ~(~(~a.b).~(a.~b))
----+----------+--------+-------------------
0 0 |    1    |    1    |        0
0 1 |    0    |    1    |        1
1 0 |    1    |    0    |        1
1 1 |    1    |    1    |        0

Hmmm. A normal XOR.

But hold on a second. That makes the first thing equal to ~x, and substituting it into the equation for l makes

l = ~(~(~c.x).~(c.~x))

and that has the same form as the subexpression we started with. So we already know how to implement that without separate inverters for c and x, the same way we did it before, and we end up with the following set of equations that don't need to invert any of their inputs:

x = ~(~(~(a.b).b).~(a.~(a.b)))
l = ~(~(~(c.x).x).~(c.~(c.x)))
h = ~(~(c.x).~(a.b))

Those equations contain 13 NAND operations, but ~(a.b) and ~(c.x) occur three times each and only need generating once, so that saves four gates and we have our nine-gate full adder. QED.
posted by flabdablet at 12:48 PM on August 17, 2018

The thing I loved about logic class best was the day when the professor told us that a tautology is like running down the street yelling "TRUE!"
posted by thelonius at 6:44 PM on August 17, 2018 [1 favorite]