Computational Logic - A Beginners Guide to Logic Gates - Part 1
Every article needs to start somewhere. This would be the logical place to do it. Logic in electronics and computer science is all about answering questions posed by 1’s and 0’s. So before we get stuck in lets have a quick refresher on how binary logic works.
Bit’s and Pieces
Binary is, at it’s heart, one of two options. 1 or 0, ‘Yes’ or ‘No’, True or False. Using combinations of these options we can encode a wealth of information.
Learning to Count - Easy as 01, 10, 11
Binary - Decimal Table
As the table above shows, the bit furthest to the right is the least significant bit. This will come into play later. This is all well and good but it’s quite hard to decipher for a human, so we often group these bits into groups of 8 (bytes) and sub-divide them still into groups of 4 (nibbles). Therefore, 0100 1001 translates to 73! And 49, and Capital i… and just a bit less than 29% fully red. Ok what’s going on
Let me ASCII you something
As we mentioned above, the binary input means only what we tell it it means. So when we encode or decode binary it’s ‘meaning’ is all dependant on its encoding.
One of the most famous examples of binary encoding is the American Standard Code for Information Interchange, more commonly called, ASCII. The idea of ASCII was to encode the most commonly used characters like Letters, Numbers, Symbols and a handful of control characters. We only had 128 addresses in the original encodings of ASCII so it’s nowhere near as fleshed out as unicode is today, but it still got the job done back in the day.
Theres a really smart thing I like about how ASCII characters were encoded. Numbers 0 – 9, letters A-Z and their lowercase counterparts, all have rather logical binary codes. The 4 least significant bits of the digits 0 – 9 are actually the same as the value of the number in binary. ie. 5 = 0101. The letters are similar in that both upper and lower case ‘A’ begins on 0001. However the three most significant bits denote what the number or letter is. ie. 5= 011 0101, uppercase ‘A’ is 100 0001 and lowercase ‘a’ is 110 0001. People proficient in counting in binary can quickly convert a letter or a number in their heads, Now theres a party trick.
And? Now what
Ok, so back to logic. Sometimes we need to find out what the result of some binary inputs would be after performing a certain function. The simplest operation we can perform is called the ‘NOT’. This is simply an inversion of the signal going in. If a is High we pull it low, if it’s low we pull it high. Pseudo-code to follow.
// A C-like representation of a NOT gate
bool a = true; // boolean operator set to true
bool q; // boolean variable q setup to give an output
if(a == true) // Check to see if a is true, if it is do the following condition
q = false; // q set to false
else // Check to see if a is true, if it isn't, then do this part
q = true; // q set to true
The NOT gate, or as it’s often called, an inverter does as its name suggests. It inverts the signal it receives. This means if we input a low we get a high and vice-versa.
The symbol is on the left and has an input on the left, an output on the right and a little node just before the output. This is what signifies that this is an inverse output, we’ll see more of this soon.
Our first multiple, in this case 2, input gate. Some might consider this the beginning of the ‘true’ logic gates. The AND Gate compares all its inputs and returns true if, and only if, they are all high.
Quite useful if you want to check if all signals are high such as ‘task complete’ signals before beginning the next.
The symbol is bullet shaped with it’s input on the flat side and output on the round outer side.
The OR Gate is less picky that the AND gate. It will allow high if ANY of its inputs, Including multiple or all inputs run high.
This can be useful to see if a task has ended and an output has been found. Or if you want a number of ways to trigger something.
Its symbol, is different from both of the above. It’s pointier. That’s the official term. And has a concave input side.
The NAND Gate, as you may have guessed from the symbol, is the inverse of our AND Gate. If it gets any input, or even none, it gives a signal and only stops if ALL its inputs are high.
This is sometimes called the universal logic gate as all other logic gate can be built up with the right series of these.
The symbol, is very similar to the AND Gate and if we remember our NOT gate we also have a little circle at the front showing it has an inverted output.
For every logic gate, there must be an equal and opposite logic gate– Unknown, possibly made up.
The NOR Gate is, as you may have surmised the inverse of the OR Gate and gives us a signal if NONE of it’s inputs are high.
It’s symbol features the concave input side and the ring on the output indicating it is inverse.
The XOR Gate, the Exclusive OR Gate, is similar to the OR Gate we discussed earlier. The only difference being instead of being high if ANY of the inputs are high, this Gate returns high if just ONE input is high.
The symbol is almost identical to the OR Gate with the exception of a line on the input side to denote exclusivity.
Finally we have the XNOR Gate. The Exclusive Not OR Gate. Bit of a mouthful. The XNOR Gate will give an output as long as ONLY one is not high. If no inputs or more than one input are high we get an output.
The symbol is nearly identical to the XOR however our little circle friend on the output is back. And again, it denotes a negated output again this time.
Logic Gates - Practically
So we’ve looked at binary, We’ve looked at the different types of gates available. Lets look now and finding a practical use for logic gates.
Pick a number, Any number
One of the simplest decoders one can build is using NOT Gates. If we take a signal, and the inverse of the signal we can check if parallel lines create a state. This, in conjunction with an AND gate can give us an output if the condition is met.
Let’s take a simple 4 bit counter, and try and find the number 13. If the number is 13 this counter will trigger another circuit to ring a buzzer or release the hounds, whatever it is you need it to do.
So the first thing we look for is the signal coming from the output of our Binary Lines, 13 in binary would be made up of 8 + 4 + 1, therefore, we’re looking for 1101 on our output.
Now we know an AND gate will only go high if ALL the inputs are active, So lets invert our 1101. Now we’ve got 0010. Wait. That’s not all the inputs either! Sure, it would be simpler just to invert the 0, but if we invert all the signals we can take outputs for any number of different states.
So in this case we take the first two outputs as they are. The third bit we take the inverted version, and for the least significant bit we take the normal output again. Now we have, (when our counter hits 13) 4 lines that are all in the active state. All thanks to our NOT logic gate and our counter.
Now, if we take a Quad Input AND Logic Gate – yes, it is a thing – and feed our ’13’ signal in, we get a positive output to whatever we need to send it too. Simple! It is even expandable enough that when we need to tap more numbers for different instructions we’ve already set up the infrastructure.
To Sum Up
One of the most popular circuits for beginners in the world of engineering and computational logic is building a “half adder” and a “full adder”.
Addition and subtraction are the two most fundamental mathematic operations one can perform. So it’s only natural that in a world of computers, smart phones and increasingly popular “Calculators”, we have discovered an efficient way to add binary numbers together using logic gates.
Check our next instalment where we will discuss how to build these circuits in a little more detail.