Computational Logic – Building it from the Ground Up – Part 2
Welcome back to the computational logic series. If you haven’t read Computational Logic Part 1 then go have a look. It’s will give you a solid base on the topics covered here and is a great introduction into building logic gates.
Transistors were one of the most influential inventions of the 20th century. We’re not going to get too in depth as to the inner workings of a transistor, but we do need to cover some of the basics.
When we’re dealing with logic in computers and electronics we build up our logic gates out of a series of switches. Theoretically, we could line up a couple of thousand people and give them a set of instructions on when to turn on or off their switch. (Think shock collars). But the trade off in this, it can be very hard to find these people. Again separating theory from reality.
BJT, MOSFET, JFET, XKCD
Ok, so XKCD isn’t a type of transistor, it’s a fantastic Web Comic that you should check out if you don’t know it, but we felt the letters looked good in the heading.
BJT – Bipolar Junction Transistors
The bipolar junction transistor, or BJT, is the first transistors most of us encounter. They are common, they are cheap, and they come in two types, N-Type and P-Type.
Current applied to (or removed from) the base of a BJT transistor will open the path between collector and emitter. With a wide enough path, these transistors will “saturate” meaning that it won’t clamp the current passing through it will just let it fly through.
FET – Field Effect Transistors
For the sake of simplicity, I’m going to sum up the variants of FET’s under the one heading. The major difference between BJT and FET is that BJT’s are controlled by current whereas FET’s are controlled by voltage.
A voltage applied (or removed) from the gate is what causes the magic. The benefit of the FET is that it requires very little current to turn on or saturate in comparison to the BJT.
Get Social With Hacker Space
When we talk about saturating a transistor, we mean driving it into a state wherein the path of the electrons through it isn’t in any way hindered. This is how we’re going to ‘switch’ our circuit to create logical outputs. All the following examples use NPN BJT transistors.
When we’re reading or writing NPN transistors on a schematic we use this symbol. It’ is a circle with a plate inside, a line coming in from the collector, an arrow leaving from the emitter, and behind the plate is the line to the base.
Building the Gates
Looking at the NOT gate we can see that the voltage wants to go to the output, but because any output is going to have some form of load on it if we open the transistor we can open a path straight to ground.
With the signal on, no output and vice versa, rather simple when you break it down.
To build an AND gate we connect two transistors between Voltage and Ground.
If both of the transistors are driven to saturation, it opens the path.
Tapping below the last, in this case, the second transistor we can trigger an output.
Adding a high value resistor between our output and ground means that we can have a logic state that is stable and ready for reading without blowing out any components.
OR Gates are next on our list.
Again the concept behind this one is fairly straight forward. We connect both transistors to power and ground (Parallel) and if one input is high we drive the output
We also include a fairly hefty resistor to ground on this circuit too in order to drive the output in a stable fashion as before.
When we want to take a NAND Gate, we build something very similar to an AND Gate.
The main difference is we place a small current limiting resistor before the main circuit so we don’t fry whatever our output is, and we tap it above both of the transistors.
If we look at the OR Gate earlier on, you can see serious similarities here.
The difference, as with our other inversions is where we tap our output and the addition of a current limiting resistor (R1).
Ah, here it is, our first compound gate. You may have to open this image in another tab if you want to see it but in essence, this is a combination of three gates.
First, we check to see that we don’t have an AND state using a NAND Gate.
Then we check we do have an OR state. Using the OR Gate.
Finally, we add the two together with an AND gate.
Our final gate is another compound, the XNOR Gate.
It is similar to the XOR Gate above but features a NAND Gate on the output instead of the AND.
IC What you did there
Luckily we don’t need to build these gates every time. Manufactures have done us the massive favour of pre-building these circuits into IC’s or Integrated Circuits. And using combinations of these gates we can build complex machines such as the half adder. Which when combined with another half adder makes a full adder. Go figure.
Half the adder you used to be
If we want to add two numbers we can use the gates above. Let’s have a look at what might suit our needs.
Now I’ve tried. I really have, to invent and standardise the use of 2 in binary. It would simplify this a lot but alas no one is going to let it pass without bribing people I just can’t afford to bribe.
I guess we just have to work with what we’re given, but luckily, solutions have been found.
We use two outputs. One is the sum of the two numbers, the other is a ‘carry’ bit. So if A OR B then the Sum is 1. If A AND B then the Carry is one. Finally, if the Carry is 1, the sum must be 0 Meaning that we need A XOR B. Hmm…. This sounds familiar. Almost like we just built those two exact circuits.
|Half Adder Truth Table|
Using the circuit above we can Add 2 bits together! Imagine the possibilities. All four of them. Adding a carry bit input we can add complex numbers together and get real results. Adding carry bits and chaining two half adders together will give us a full adder. The results look a little bit like this.
|Full Adder Truth Table|
|A||B||Carry (In)||Sum||Carry (Out)|
So we’ve finally built our Full Adder. So to add 2, 4-bit numbers we can end up getting a result up to 25 or 32 as an output, or if we wanted to be fancy, we could declare the output as a signed number between -15 and +16. Or we could have a rudimentary colour value. Oh, this is ringing bells from Computational Logic – Part 1. Ah yes, assigning values to binary outputs.
Instruction sets to decode this is definitely the topic for another post. However, at least we know how to build the bones of an Arithmetic Logic Unit, or ALU. And with this, you’re now ready to get started on building your own breadboard computer. Leave a comment below and let’s see what you make!