Computational Logic – Building it from the Ground Up – Part 2

Published by Gaz on

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.

The Transistor

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

0
+
Instagram Followers

Instagram

0
+
Facebook Fans

Facebook

Saturation

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.

Schematic Symbol

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

Schematic drawing of a logic NOT gate using NPN BJT transistors

NOT Gate

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.

AND Gate

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.

Schematic drawing of a logic AND gate using NPN BJT transistors
Schematic drawing of a logic OR gate using NPN BJT transistors

OR Gate

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.

NAND Gate

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.

Schematic drawing of a logic NAND gate using NPN BJT transistors
Schematic drawing of a logic NOR gate using NPN BJT transistors

NOR Gate

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).

XOR Gate

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.

Schematic drawing of a logic XOR gate using NPN BJT transistors
Schematic drawing of a logic XNOR gate using NPN BJT transistors

XNOR 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.

We need;

ABOutput
000
101
011
112

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
ABSumCarry (Out)
0000
1010
0010
1101
Schematic drawing of a Half Adder.
Schematic of a Half Adder Circuit

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
ABCarry (In)SumCarry (Out)
00000
00110
01010
01101
10010
10101
11001
11111
Schematic drawing of a Full Adder.
Schematic of a Full Adder Circuit

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!


Gaz

Electronics and Audio nerd.

2 Comments

Computational Logic - A Beginners Guide - Part 1 - Hacker Space · September 24, 2019 at 11:44 pm

[…] Check our next instalment where we will discuss how to build these circuits in a little more detail.  […]

Schematics – Reading and Writing in Electronics. – Hacker Space · March 5, 2020 at 12:03 am

[…] Computational Logic – Building it from the Ground Up – Part 2 […]

Leave a Reply

Your email address will not be published. Required fields are marked *

en_GBEnglish
en_GBEnglish