{"id":4003,"date":"2022-12-20T08:58:34","date_gmt":"2022-12-20T13:58:34","guid":{"rendered":"http:\/\/www.goodmath.org\/blog\/?p=4003"},"modified":"2022-12-20T08:58:34","modified_gmt":"2022-12-20T13:58:34","slug":"how-computers-work-logic-gates","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2022\/12\/20\/how-computers-work-logic-gates\/","title":{"rendered":"How Computers Work: Logic Gates"},"content":{"rendered":"\n

At this point, we’ve gotten through a very basic introduction to how the electronic components of a computer work. The next step is understanding how a computer can compute<\/em> anything.<\/p>\n\n\n\n

There are a bunch of parts to this.<\/p>\n\n\n\n

    \n
  1. How do single operations work? That is, if you’ve got a couple of numbers represented as high\/low electrical signals, how can you string together transistors in a way that produces something like the sum of those two numbers?<\/li>\n\n\n\n
  2. How can you store<\/em> values? And once they’re stored, how can you read them back?<\/li>\n\n\n\n
  3. How does the whole thing run<\/em>? It’s a load of transistors strung together – how does that turn into something that can do things in sequence? How can it “read” a value from memory, interpret that as an instruction to perform an operation, and then select the right operation?<\/li>\n<\/ol>\n\n\n\n

    In this post, we’ll start looking at the first of those: how are individual operations implemented using transistors?<\/p>\n\n\n\n

    Boolean Algebra and Logic Gates<\/h2>\n\n\n\n

    The mathematical basis is something called boolean algebra<\/em>. Boolean algebra is a simple mathematical system with two values: true and false (or 0 and 1, or high and low, or A and B\u2026 it doesn’t really matter, as long as there are two, and only two, distinct values).<\/p>\n\n\n\n

    Boolean algebra looks at the ways that you can combine those true and false values. For example, if you’ve got exactly one value (a bit<\/em>) that’s either true or false, there are four operations you can perform on it.<\/p>\n\n\n\n

      \n
    1. Yes<\/strong>: this operation ignores<\/em> the input, and always outputs True.<\/li>\n\n\n\n
    2. No<\/strong>: like Yes, this ignores its input, but in No, it always outputs False.<\/li>\n\n\n\n
    3. Id<\/strong>: this outputs the same value as its input. So if its input is true, then it will output true; if its input is false, then it will output false.<\/li>\n\n\n\n
    4. Not<\/strong>: this reads its input, and outputs the opposite value. So if the input is true, it will output false; and if the input is false, it will output True.<\/li>\n<\/ol>\n\n\n\n

      The beauty of boolean algebra is that it can be physically realized by transistor circuits. Any simple, atomic operation that can be described in boolean algebra can be turned into a simple transistor circuit called a gate<\/em>. For most of understanding how a computer works, once we understand gates, we can almost ignore the fact that there are transistors behind the scenes: the gates become our building blocks.<\/p>\n\n\n\n

      The Not Gate<\/h2>\n\n\n\n
      Input<\/th>Output<\/th><\/tr><\/thead>
      1<\/td>0<\/td><\/tr>
      0<\/td>1<\/td><\/tr><\/tbody><\/table>
      The truth table for boolean NOT<\/figcaption><\/figure>\n\n\n\n

      We’ll start with the simplest gate: a not gate. A not gate implements the Not operation from boolean algebra that we described above. In a physical circuit, we’ll interpret a voltage on a wire (“high”) as a 1, and no voltage on the wire (“low”) as a 0. So a not gate should output low (no voltage) when its input is high, and it should output high (a voltage) when its input is low. We usually write that as something called a truth table<\/em>, which shows all of the possible inputs, and all of the possible outputs. In the truth table, we usually write 0s and 1s: 0 for low (or no current), and 1 for high. For the NOT gate, the truth table has one input column, and one output column.<\/p>\n\n\n

      \n
      \"\"<\/a>
      Circuit diagram of a NOT gate<\/figcaption><\/figure><\/div>\n\n\n

      I’ve got a sketch of a not gate in the image to the side. It consists of two transistors: a standard (default-off) transistor, which is labelled “B”, and a complementary transistor (default-on) labeled A. A power supply is provided on the the emitter of transistor A, and then the collector of A is connected to the emitter of B, and the collector of B is connected to ground. Finally, the input is split and connected to the bases of both transistors, and the output is connected to the wire that connects the collector of A and the emitter of B.<\/p>\n\n\n\n

      That all sounds complicated, but the way that it works is simple. In an electric circuit, the current will always follow the easiest path. If there’s a short path to ground, the current will always follow that path. And ground is always low (off\/0). Knowing that, let’s look at what this will do with its inputs.<\/p>\n\n\n\n

      Suppose that the input is 0 (low). In that case, transistor A will be on, and transistor B will be off. Since B is off, there’s no path from the power to ground; and since A is on, cif there’s any voltage at the input, then current will flow through A to the output.<\/p>\n\n\n\n

      Now suppose that the input is 1 (high). In that case, A turns off, and B turns on. Since A is off, there’s no path from the power line to the output. And since B is on, the circuit has connected the output to ground, making it low.<\/p>\n\n\n\n

      Our not gate is, basically, a switch. If its input is high, then the switch attaches the output to ground; if its input is low, then the switch attaches the output to power.<\/p>\n\n\n\n

      The NAND gate<\/h2>\n\n\n\n

      Let’s try moving on to something more interesting: a NAND gate. A NAND gate takes two inputs, and outputs high when any of its inputs is low. Engineers love NAND gates, because you can create any<\/em> boolean operation by combining NAND gates. We’ll look at that in a bit more detail later.<\/p>\n\n\n\n

      Input X<\/th>Input Y<\/th>Output<\/th><\/tr><\/thead>
      0<\/td>0<\/td>1<\/td><\/tr>
      0<\/td>1<\/td>1<\/td><\/tr>
      1<\/td>0<\/td>1<\/td><\/tr>
      1<\/td>1<\/td>0<\/td><\/tr><\/tbody><\/table>
      The truth table for NAND<\/figcaption><\/figure>\n\n\n\n
      \"\"<\/a><\/figure>\n\n\n\n

      Here’s a diagram of a NAND gate. Since there’s a lots of wires running around and crossing each other, I’ve labeled the transistors, and made each of the wires a different color:<\/p>\n\n\n\n