art with code

2013-04-27

Earth, the beautiful

Boolean Algebra, the crunchy version

First some ring axioms:
x + (y + z) = (x + y) + z
x + 0 = x
x + -x = 0
x + y = y + x

x * (y * z) = (x * y) * z
x * (y + z) = (x*y) + (x*z)
x * 1 = x
x * y = y * x


Let's define AND next:

a AND b = a * b

a AND 1 = a because x * 1 = x

a AND 0 = 0

x * 0 = 0 derives from
x * (y + z) = (x*y) + (x*z): call with z = 0 =>
x * (y+0) = (x * y) + (x * 0) <=>
x * y = (x * y) + (x * 0) <=>
x * 0 = 0

For 0 AND b = 0 and 1 AND b = b, apply x * y = y * x to the above.
Applying all the 0,1 combinations to AND we get the truth table:
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1


Then NOT:


NOT a = 1 + -a

NOT 0 = 1 + -0, apply -0 = 0 and x + 0 = x
NOT 0 = 1
-0 = 0 because 
(0 + -0) = 0, apply x + y = y + x
(-0 + 0) = 0, apply x + 0 = x
-0 = 0

NOT 1 = 1 + -1, apply x + -x = 0
NOT 1 = 0


When we combine NOT with AND, we get NAND:

a NAND b = NOT (a AND b)

NOT (0 AND 0) = 1
NOT (0 AND 1) = 1
NOT (1 AND 0) = 1
NOT (1 AND 1) = 0

Writing it out as an equation:

a NAND b = 1 + -(a * b)


NAND is functionally complete so we can write all the 16 possible (binary, binary) -> binary -functions using only NANDs. 

2013-04-21

Boolean Algebra

I started implementing the logic gates in JS for the heck of it. In the process I figured out an interesting algebra for logic circuits. Let's start off with writing some basic JS logic to simulate an abstract transistor. This crummy transistor should give out a 1 when its two input pins are 1. And if either of those is 0 it should return a 0. Let's see:

Transistor = function(control, input) {
  if (control) {
    return input;
  } else {
    return 0;
  }
};

Hmm, well, that does work but it's a bit ugly. And if you know about transistors, they're not really like that. You can use a transistor to amplify a signal. Hook up a faint signal to the control and a powerful input and the transistor scales the input by the control signal. Hey, it's like multiplication!

Transistor = function(control, input) {
  return control * input;
};

Ok, so a transistor is the multiplication operator. How does that work with binary logic? If we take the set {0, 1} as the type of the inputs for both control and input, all works fine: a 1 in the control passes the input through unchanged, a 0 in the control makes the input 0. From that you can see that 1 is the multiplicative identity and multiplying by 0 annihilates the other operand.

To make a NAND gate we need a bit more than just a transistor though. We either need inverse transistors (for a CMOS NAND) or a ground wire (for a NMOS NAND). The NMOS version is a bit simpler so let's write a ground function for it next. A grounded circuit returns a 0 if the ground wire is connected, otherwise it passes the input through untouched.

Ground = function(ground, input) {
  if (ground) {
    return 0;
  } else {
    return input;
  }
};

Again, that's a bit ugly. Let's turn that into an arithmetic representation on our {0, 1} algebra.

Ground = function(ground, input) {
  return (1-ground)*input;
};

Right, it seems we had to introduce a few new concepts there. Algebra-wise 1-ground is shorthand for 1 + -ground. Which means that we need a second operator for our algebra: the addition. And we also have the additive inverse, thanks to the minus sign there. And as 1-0 should return 1, we also get the additive identity. Add 0 to any input and what you get is the input, unchanged.

The algebra we have now has addition, additive identity, additive inverse, multiplication and a multiplicative identity. I think we also have to expand our set to include the additive inverses, netting us the set {-1, 0, 1}. I haven't found a use for the negative numbers in the binary logic though. The alternative would be to turn (1-x) into an axiomatic operation of some sort, I guess.

Oh, also, the inverse transistor has the same formula as the ground operator (if a different wiring implementation).

ITransistor = function(control, input) {
  return (1-ground)*input;
};

Ok, enough setup, let's make a NAND gate! A NAND gate takes two inputs and outputs a 0 if both its inputs are 1, in other cases it outputs a 1. An NMOS NAND gate has two transistors controlled between a voltage source and ground, with the idea that if both transistors are on, the source is connected to the ground and the output signal is zero. And if either of the transistors is off, the source is not connected to the ground and the output signal is the source voltage.

NAND = function(a, b) {
  return Ground(Transistor(b, Transistor(a, 1)), 1);
};

The thing about the NAND gate is that it's functionally complete. You can implement any of the other binary logic gates using NAND gates. Don't believe me? Watch this!

NOT = function(v) {
  return NAND(v, v);
};

BUFFER = function(v) {
  return NOT(NOT(v));
};

AND = function(a, b) {
  return NOT(NAND(a, b));
};

Got that? NAND with the same signal to both inputs is a 1 if the signal is 0 and a 0 if the signal is a 1. And AND is the inverse of NAND. Still not enough? Let's do OR, NOR and XOR as well.

NOR = function(a, b) {
  return AND(NOT(a), NOT(b));
};

OR = function(a, b) {
  return NOT(NOR(a, b));
};

XOR = function(a, b) {
  return AND(OR(a, b), NAND(a, b));
};

With that we have functions to generate the truth tables 1110, 0001, 0111, 1000 and 0110 (I'm writing the entries as the outputs for the 2-bit numbers 00, 01, 10 and 11. So 1110 means the function returns the following: 00 -> 1, 01 -> 1, 10 -> 1, 11 -> 0.) But hey, there are 16 different permutations for those truth tables. Let's write more functions.

// 0000
ZERO = function(a, b) {
  return AND(AND(a, b), NAND(a, b));
};

// 0001 = AND
// 0010
XLEFT = function(a, b) {
  return AND(a, NOT(b));
};
// 0011
LEFT = function(a, b) {
  return AND(a, ONE(b, b));
};
// 0100
XRIGHT = function(a, b) {
  return AND(b, NOT(a));
};
// 0101
RIGHT = function(a, b) {
  return AND(b, ONE(a, a));
};
// 0110 = XOR
// 0111 = OR
// 1000 = NOR
// 1001
XNOR = function(a, b) {
  return NOT(XOR(a, b));
};
// 1010
NRIGHT = function(a, b) {
  return NOT(RIGHT(a, b));
};
// 1011
XNRIGHT = function(a, b) {
  return NOT(XRIGHT(a, b));
};
// 1100
NLEFT = function(a, b) {
  return NOT(LEFT(a, b));
};
// 1101
XNLEFT = function(a, b) {
  return NOT(XLEFT(a, b));
};
// 1110 = NAND
// 1111
ONE = function(a, b) {
  return OR(AND(a, b), NAND(a, b));
};

As you can see from the above, you can implement all the binary functions in {0, 1} using only NAND gates. And since our definition of NAND is in terms of a transistor and a ground operator, which are grounded in some basic arithmetic operations, you can actually write the gates as arithmetic functions.

NAND = function(a, b) {
  //   (1 - (b * (a * 1)) * 1
  // = 1 - (b * a)
  return 1 - b*a;
};

NOT = function(v) {
  // 1 - v*v (v*v = 0 when v = 0, v*v = 1 when v = 1)
  // so in {0,1}, 1-v*v = 1-v
  return 1 - v;
};

AND = function(a, b) {
  //   1 - (1 - b*a)
  // = 1 - 1 + b*a
  return b*a;
};

NOR = function(a, b) {
  // (1-b) * (1-a)
  return (1-b) * (1-a); 
};

OR = function(a, b) {
  //   1 - ((1-b) * (1-a))
  // = 1 - (1*1 + 1*-a + -b*1 + -b*-a)
  // = 1 - (1 - a - b + ba)
  // = 1 - 1 + a + b - ba
  // = a + b - ba
  return a+b - b*a;
};

XOR = function(a,b) {
  // (1-ba)*(a+b-ba)
  return (1-b*a)*(a+b-b*a);
};

And so forth.

Oh, and one more thing. You know the CPU inside your computer? It's made up of NAND gates. Lots and lots of NAND gates hooked up together to compose all the logic in the CPU. And if you think of each NAND as the equation 1-ab, you could think of the CPU as one humongous equation etched onto a silicon chip.

I've got the code for the logic gates and some adder generator code up on GitHub.

2013-04-18

NAND gates

And this should ground the previous to transistors and voltage planes.

I wonder if the implementation of an actual adder circuit would be more complicated. Probably lots of implementation details to consider. But yeah, hook the input pins of the adder to switches, put LEDs on the output pins.

2013-04-17

Circuit diagrams

I was listening to a Feynman lecture on what computers are and started doodling logic circuits based on that. First I made a 1-bit adder, then extended that into a 2-bit adder, doodled a 3-bit adder and generalized from there to arbitrary n-bit adders. Then I made a 4-bit adder out of two 2-bit adders and drew this thing in Photoshop that generalizes the idea to 2n-bit adders. And tried building the rest of the logic gates using just NAND gates. Fun fun :)

I tested the logic gates and the 1-bit and 2-bit adders in JavaScript but haven't tested the 4-bit and n-bit adders.

Blog Archive