Hi everyone, I spend a lot of time mashing
away at a keyboard, trying to tell the computer what I would like it to do. Even
my oddly shaped computer (that constantly gets teased for looking like a trash can) is
unbelievably good at following instructions. Unfortunately I’m not so good at giving them,
so the results are inevitably a little wonky, but nevertheless it’s always been such a
mysterious thing to me, that this inanimate lump of metal and sand and whatever else, arranged in
an some extremely clever way, is able to do maths, and logic and remember things, and ultimately
allows us to create pretty much anything we set our minds to. It’s kinda bizarre, and I’d
really like to understand better how it works. So here’s a little circuit with a light
and two switches A and B, and clearly, the light can only go on if I close both of these
switches. Already this is a kind of simple logic: we’re testing if two conditions are true:
switch A is closed, AND switch B is closed. If we represent an open switch with
a zero, and closed switch with a 1, these are the different configurations we could
have, and here’s the output: 0 meaning the light would be off, and 1 meaning it’d be on. Since
that’s only the case when A AND B are 1, this is known as the logical AND operation. This kind
of table, by the way, is called a truth table. Here’s a bit of a different circuit — this time
we only have 1 switch, and even though it’s open, the light is currently on. If I close the switch,
now the light will go off, because we’ve created an easier path for the current to travel. So we’re
essentially inverting the input: if the state of the switch is 0, the output is 1 and vice versa,
and this is known as the logical NOT operation. Now I’ve been controlling these switches
with my fingers, which computers sadly lack, so in the very early days, electromagnets
were used to open and close the switches, but this was kinda clunky and slow, so then came
fancier technologies like vacuum tubes and finally transistors. As a tiny example of what transistors
do, this is essentially that same NOT thing from before, just setup on a breadboard, and with a
transistor in the place of the paperclip switch. If we think of the current flowing in this
circuit, it would look something like this. It can’t flow through the transistor at the
moment, because its currently acting as an open switch. However, if we send power to to the
middle pin of the transistor, establishing a small flow of current like this, the fancy physics of
the transistor will make it act like a closed switch instead, allowing the main current to flow
through it like so. Like before, the light has turned off because we’ve created a much easier
path for the current to take. So essentially, the transistor is a switch, which we can open and
close with electricity instead of our fingers. ### Simulation
I’d love to one day try and build a simple computer out of components like this — which is
what Ben Eater has done in his very cool 8bit breadboard computer series, but that’s a little
intimidating for me at the moment, so instead I’ve made a simplified and abstracted little simulation
where we have our two logical building blocks: AND and NOT, and we can play around and try
figure some stuff out. So on the left here are some inputs, which can be turned on and off,
or we can also think of it as true and false, or 1 and 0, it doesn’t really matter — but I’ll wire
these up to the inputs of the AND gate, and if you recall my sophisticated circuitry from earlier,
the two inputs simply control whether these switches are open or closed, which should achieved
used transistors, not paperclips of course. Now I’ll connect the result of this AND
operation up to my output node over here, and so this will only light up if both inputs are
on. Let’s get the NOT gate participating as well, so I’ll connect it up over here, and wire
the result of THAT to the output instead. So the output is now inverted: it’s off when
both inputs are on, but in all other cases its on. Here’s a truth table for this thing we’ve just
built, and it actually has a name: this is the NOT AND, or rather — NAND gate. If I click on this
Create button down here, it’ll package that up into its own little chip, and we now have a nand
gate to mess about with. I guess this is a good moment to mention NAND2Tetris, which along with
Ben’s videos is a fantastic free resource I’ve been using to learn more about this stuff. So I
recommend checking that out if you’re interested. Anyway, to take this a little further we
could maybe try inverting both of the inputs before feeding them into the nand gate, and let’s
see what that does. So with both inputs off, the output is off, if I turn either of them
on, the output goes on, and if both are on, the output is still on. So we’ve created what’s
called an OR gate, and I’ll turn that into its own little chip as well, because it seems pretty
useful. And here is the truth table for that. All right, let’s take a moment to think about
something that’s pretty important to computers: numbers. In the decimal system that we know and love,
there are 10 digits, zero through nine, and if we want to go higher than that,
we need to add another place to the left, where each digit actually represents 10
times as much as those in the previous spot. And we can have as many places as we need, so
here would be 100s, then thousands, and so on. With electronics though, it’s easier to work
with just two digits, because they can be naturally represented with a low voltage
or a high voltage. So the binary system works in the exact same way as the decimal
system, its just that once we reach one, we’ve already run out of digits, and
so we increment the place to the left. Because there’re only two digits in binary:
0 and 1, each place is worth 2x more than the last. So if the first place is worth 1, then
this place is worth 2, then 4, then 8 and so on. So let’s say we want to figure out what this
sequence: 1101 would be in decimal. Well, we can write it out as 8x1 + 4x1 +
2x0 + 1 x 1. And that comes out to 13. Alright, now what I’d like to do is design
something that’s able to add 2 binary numbers together. So let’s work through a quick example
by hand, say we want to add these two together: starting on the right here, 1 + 1 is is two, which
in binary is 10. So I’ll write the zero down here, and then carry the one over up here, because
we’ll need to add it together with these other two to figure out what goes in this spot.
By the way, this part that we wrote down here straight away I’ll refer to as the sum
bit, and this one up here is the carry bit. Anyway, let’s continue 1 + 1 is 2, plus the carry
is gives us 3 in decimal, or 11 in binary. So I’ll write one over here - that’s the sum bit, and
carry the other one over to the left. Now we have 0 plus 1, plus the carry bit is 2 again,
so I’ll put 0 down here, and 1 up here. This’ll just give us 1, so I’ll write that down
here. Then 0 plus 0 is just 0, and finally, 1 plus 0 is one. In case you care to know,
what we’ve just calculated here is 35 + 7. It’s a little daunting to try start thinking about
how we can wire our logic gates together to do all of this, so let’s start small with adding together
just two single bits. For example, if we’re adding a zero and a zero together, then naturally both
the carry bit and the sum bit will be zero. But, if the first bit is zero and the second is
one, or the other way around, then the carry bit will be zero and the sum bit will will be 1.
Finally if both bits are 1, then the carry will be 1, and the sum bit will
be zero. So if we look at the carry column here, it might look familiar, because it’s actually
an exact match with the AND operation. The sum column on the other hand doesn’t match
exactly with anything we’ve already seen, but it’s quite close to the OR gate we created earlier, it
just has a 0 in this last spot instead of a 1. So, let’s take that OR gate as a starting point,
and we just need to turn the output to a zero when both inputs are one. So I’m going to take a
nand gate, and connect it up here, and this will check if both inputs are one, and then invert the
result, so that it’s outputting zero in that case. We can then use an AND gate to test if either of
the inputs, but not both of them, is one. Let’s test this quickly. With both inputs off, or zero,
the output is zero. With just a single input set to one, the output is one, but crucially
when both inputs are one, the output will be zero again. This operation has a special name as
well, it’s called an exclusive OR. XOR for short. Okay, so I now have an empty chip with two inputs,
which we want to add together, and two outputs: the sum bit, and the carry bit. So, we can use
our new xor gate to calculate the sum bit of the two inputs, and then remember that if both
inputs are 1, then the carry bit should be one, and so as we saw, we can simply use an AND gate
to test for that. So that’s everything we need to add two bits together, but of course in some of
the steps we actually had 3 bits we needed to add together, because there was a carry bit from the
previous step to deal with. And in fact we could think of these other places as having zero in the
carry spot, so really we’re always adding 3 bits together. So, I’ll introduce a third input to the
chip over here for the carry input, and we need to add this to the sum of the first two bits which we
calculated up here. So, we can simply use another XOR gate, and I’ll wire that up to that carry
input, and to the sum of the first two inputs. We’ll then need a second AND gate as well,
because if sum of the first two bits is 1, AND the carry input is one, then we’ll
need to carry 1 to the next step. So if either of our two AND gates detect that
we should be carrying one to the next step, then we’ll want to output one to the carry
output, which I’ll do using an OR gate. Let’s check that this is working properly. So
with all of the inputs off, or zero, both the sum and carry output bits should be zero. Then,
if any single input is 1, the sum should be 1, and the carry should be zero. So far, so good. Next,
if any two inputs are 1, then the sum bit should be zero, and the carry should be 1. And finally,
if all three inputs are 1, the sum should be 1, and the carry should be 1. And it looks like its
all working, so I’ll give it a name, and then what I’d like to do is take this ADDER we’ve made, and
construct a 4BIT ADDER, capable of taking these two 4-bit numbers that we have here as our inputs,
and calculating the 4bit sum as the output. I’ve added little displays by the way to
tell us what all these values are in decimal, just so it’s a bit easier to
tell if this thing is working. We’ll need four adders to construct this,
and I’ll wire each one up to the outputs. Then there’s a carry input here, just in case
we want to string two 4bit adders together to make an 8bit adder, for example, so that can
go into the carry input of the first adder, and then its carry output goes into
the carry input of the next one, and so on down the chain. Finally I’ll
need to connect up the two 4bit inputs. Let’s test this out, so right now we have 0 +
0 = 0, which is a good start. Let me try 1 + 1, I believe 2 is correct! 5 + 1 is 6, and 7 + 1 is
8. So, it looks like we can add numbers together, which is pretty cool. Of course with just 4 bits,
if we try do 15 + 1 for example, it will overflow to zero because we don’t have enough bits to store
16, and the carry bit will light up over here. If we want to extend this to handle subtraction,
we’ll need a way to represent negative numbers in binary. I always assumed that this last spot
was used to indicate the ‘sign’ of the number. So what we have here would be positive 7, and this would be -7. But of course you’d expect that if
we added 7 to negative 7, we’d end up with 0, but that’s clearly not the case here. So one way
we could try thinking about this, is what would we have to add to 7, in order to get 0 as the result?
Well in order to get a zero in the first spot, this would need to be a one, because
remember 1 + 1 gives us a sum bit of zero. Of course we also now have to carry 1 to the
next spot. So now we know that there should be a zero here, so that we’ll again have 1+1 giving
us zero for our sum bit. And a carry of 1. So we can deduce that there should be a zero here
as well, and we can continue like this, to end up with all zeros for our 4 bits. There is a one
that ends up over here, but since we’re working with just four bits, that can be discarded.
So we’ve figured out that -7 must be 1001 That might seem weird, but it actually makes
some sense if we think of this last spot as the -8 place, because then we could write this out as
-8 x 1 + 4 x 0 + 2 x 0 + 1 x 1. Which gives us -7. Let’s start at zero and see what
it looks like now if we count up. So as you can see seven is now the
largest number we can have with 4 bits, and then it flips over to the smallest number,
-8. And from there we have -7, -6, -5, -4, -3, -2, and finally all ones would be -1. So it’s a
bit of a funky system, but it allows us to add negative and positive numbers together without
any fuss, so it’s totally worth the weirdness. There’s actually a simple two-step
procedure for making any positive number negative. Take the number positive 6
for example, 0110 in binary. The first step is to invert all the bits, so where there’s a
zero we write a 1, and vice versa, giving us 1001. At this point if we were to add these two together
we’d obviously get all ones. We want it to be all zeros though. And we saw a few minutes ago
that if we take this, and just add one to it, we’ll end up with zero for the 4 bits we’re
interested in. This tells us that clearly our inverted number is just one too little to give
us all zeros. So the second step, as you might predict, is to take the inverted number, and
add one to it. So in this case we’d take 1001 and add one, giving us 1010. And if we look back
at the number wheel, that is indeed negative six. So, using that 4bit adder we built, we can of
course add these two 4bit numbers together, but if this subtract signal over here is on, then I
want to subtract the second number from the first, which we can do by making the second number
negative. And remember we do that by inverting the bits, and then adding one. So to invert the
bits, we need something that looks at the subtract signal, and if that’s off, the input bit should
be unchanged, but if the subtract signal is on, then the bit should be inverted. This table
actually matches the Exclusive OR we made earlier, so we can just use 4 of those to invert these
4 bits only if the subtract signal is on. The last step of negating a number was
to add one, so we can just feed the subtract signal into the carry input of the
adder, and that’ll do that for us. Alright, I’ll quickly go ahead and wire up the rest
of the inputs, and then output the result. I also have these 3 extra outputs, and these are
just for flagging some stuff about the result. This one over here for example tells us if the
result was zero, and we can test for that like so. This other output tells us if the result
was negative, which is true if our -8 bit is set to one. And finally there’s
the carry, which I can just take from her. So these flags just give us some information about
the result, which’ll be useful to us later on. Let’s test if this actually doing what we want, so
I’ll try doing 3 + 4, and that’s 7 so we haven’t broken addition at least. Now I’ll try turning
on the subtract signal, so we’re now doing 3 + negative 4, which is the same thing as saying
3 minus 4, and the result is indeed negative 1, so that’s good. Let me try negative 2 - 4, and
that gives us negative 6. Let’s see if it can handle subtracting a negative number, so I’ll try
negative 2 minus negative 4. Even that seems to work, we get positive 2. I want to test one last
thing - adding two negative numbers together. And once again, the maths checks out. So this
is going to be our Arithmetic and logic unit. Although to be honest it doesn’t actually do any
logic, that would just be things like doing the AND operation on the inputs and outputting
that for example, but we can expand this later if necessary. For now I’ll call it ALU for
short, and package it up into a tiny little chip. So that’s going to be all for this first episode,
I hope you found it interesting. In the next one I want to look at how memory works, I’m very curious
to learn more about that. Until then, cheers!
What software are you using to simulate those circuits? I want it!
Ben Eaters videos, which he mentioned, are so satisfying. I'd definitely recommend them. I ended up grabbing a circuit simulator and was able to follow along with some parts of it.
https://eater.net/8bit/
That was the best explanation of Two's Complement I've ever seen. The first time I learned about it I just kind of faked my understanding and I could see how it worked so I just went with it. But this explanation really made it clear why we use it.
This is a fantastic book if you want to know more
Computer Systems: A Programmers Perspective https://archive.org/details/ComputerSystems/
For those who want more, nand2tetris goes through all the wys from transistors to building playing a tetris game, from scratch. It's an amazing resource and I cannot reccomend it enough.
https://www.nand2tetris.org
For those of you who already know how to code but want more in depth content, destroy all software has many utterly amazing Screencasts showing simplified versions of many complex topics, like compilers, allocates, etc. I am actually going to use that as a Christmas wishlist item for myself.
https://www.destroyallsoftware.com/screencasts
Ok when do we get to
segmentation faultand blue screens?Cat power.
for those interested in a similar software to follow along.
theres Logisim (no longver beign developed) http://www.cburch.com/logisim/index.html
Who are you ,so wise in ways of science?