Exploring How Computers Work

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!

Channel: Sebastian Lague

Views: 1,180,707

Keywords:

Id: QZwneRb-zqA

Length: 18min 12sec (1092 seconds)

Published: Mon Nov 16 2020

Reddit Comments

[u/falconfetus8]

What software are you using to simulate those circuits? I want it!

[u/falldeaf]

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/

[u/BenJuan26]

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.

[u/EtcEtcWhateva]

This is a fantastic book if you want to know more

Computer Systems: A Programmers Perspective https://archive.org/details/ComputerSystems/

[u/hak8or]

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

[u/Iggyhopper]

Ok when do we get to segmentation fault and blue screens?

[u/Robanix]

Cat power.

[u/Velieth]

for those interested in a similar software to follow along.

theres Logisim (no longver beign developed) http://www.cburch.com/logisim/index.html

[u/_quarkboy_]

Who are you ,so wise in ways of science?