Build an adding machine using NAND logic gates

6

2

This is "programming" at its most fundamental.

Build a diagram of (two-wire) NAND logic gates that will take the input wires A1, A2, A4, A8, B1, B2, B4, B8, representing two binary numbers A to B from 0 to 15, and return values on the output wires C1, C2, C4, and C8 representing C, which is the sum of A and B modulo 16.

Your score is determined by the number of NAND gates (1 point per gate). To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

Lowest score wins.


Updates:

03-07 19:09: Due to discussions with Jan Dvorak, it came to my attention that the total number of gates, constants and splits is always determined solely by the number of gates. Because of this, I have simplified the score requirement back down to simply the number of gates required.

Joe Z.

Posted 2013-03-07T20:41:19.567

Reputation: 30 589

2

I don't think you can get much better than the classic full-adder design.

– Mr. Llama – 2013-03-07T20:52:58.327

That uses AND, OR, and XOR gates and would have a score of 29 per digit (minus a few for carrying in the end cases). Can you condense it into using fewer NANDs? – Joe Z. – 2013-03-07T21:08:14.893

Are multi-wire NANDs allowed? – John Dvorak – 2013-03-07T21:14:44.217

@JanDvorak Not sure what a multi-wire NAND is. – Joe Z. – 2013-03-07T21:17:11.110

@JoeZeng NAND(X,Y,Z) = NOT(AND(X,AND(Y,Z))) – John Dvorak – 2013-03-07T21:18:18.707

They don't seem like a standard construction. I think I'd only allow them with the score it takes to build them out of two-wire NANDs and splits. – Joe Z. – 2013-03-07T21:26:13.427

1They are quite standard. It emits true if any input is false. – John Dvorak – 2013-03-07T21:26:54.580

I understand that. What I meant is that multi-wire logic gates in general don't seem to be typical of logic gate diagrams, so I don't think I would allow them as one unit with a special score. – Joe Z. – 2013-03-07T21:28:42.007

But, if you can construct a multi-wire NAND using only regular NANDs and splits, feel free to reuse that construction with its equivalent score. – Joe Z. – 2013-03-07T21:29:21.397

Answers

7

31 gates

full adder

[created in Logisim]


The standard XOR-gate can be built with four NANDs. Tapping the first NAND provides us with a fairly compact half-adder with inverted carry:

hadder(A,B) => (sum, iCarry):

X = A^B   

sum = (A^X)^(B^X)
iCarry = X

These can be combined into a 9-gate full adder:

fadder(A,B,C) => (sum, carry):

DD1 = hadder(A,B)
DD2 = hadder(DD1.sum, C)

sum = DD2.sum
carry = DD1.iCarry ^ DD2.iCarry

These combined yield a naive 36-gate four-bit adder. Not bad.

Now, we inline all modules and perform these optimizations:

delete gates with no output (only the final gate)
0^x => 1                    (one gate, twice)
1^(1^x) => 0                (two gates, once)

for a grand total of 31 gates.


Note that the count of splits and NAND-gates are intimately connected: Each 2-input NAND (larger are explicitly forbidden) takes two inputs and produces one output. Each 2-way split (let's assume larger splits are forbidden) takes one input and produces two outputs. Also, there are no unused outputs or floating inputs (let's assume constants are not allowed). If there are N more inputs than outputs, there must be N more NANDs than splits.

Thus, a 31-NAND 8=>4 module will neccessarily have 27 2-way splits.

Here are the split cardinalities for the above adder just in case larger splits are allowed:

18x wire (no split)
  4x output
  14x XOR 2nd stage
16x 2-way split
  8x input
  6x H2 input
  2x last bit XOR 1st stage
4x  3-way split
  4x XOR 1st stage
1x  4-way split
  1x 1st bit XOR 1st stage; if constants are alloweed; this is a three-way split

John Dvorak

Posted 2013-03-07T20:41:19.567

Reputation: 9 048

The 27 splits each count as 1 point, so your total score is actually 58. – Joe Z. – 2013-03-07T23:57:23.240

@JoeZeng as I elaborated, if you count my diagram as 27 splits (2-way only, constants not allowed), then #splits = #gates - 4 – John Dvorak – 2013-03-07T23:58:45.620

So basically, the score only has one degree of freedom among the number of gates and the number of splits? – Joe Z. – 2013-03-08T00:00:10.627

Yup. Unless you allow constants. – John Dvorak – 2013-03-08T00:01:22.293

If I allow constants at 1 point each, will that affect anything? – Joe Z. – 2013-03-08T00:03:41.630

@JoeZeng if a constant has the same price as a split, then the score is a function of the number of gates. – John Dvorak – 2013-03-08T00:05:37.440

I see. In that case, I'll just count the number of gates. – Joe Z. – 2013-03-08T00:06:21.260

Minimum is indeed 31 NANDs. I searched a lot, and found none faster than this one at this size, but there were weird slower ones. This puzzle is solved by John Dvorak. – KimOyhus – 2019-01-05T11:44:31.370