Let me introduce you to fundamental building blocks used in our digital world.
Logic is a method of decision making based on facts and rules.
To avoid mistakes, the facts and the rules of the logic must both be sound, but experience tells us that facts are not always clear, and logic is often short of being universally understood.
I was first introduced to TTL logic ICs through making and repairing 'Sequential Lighting Effects' used on stage by 1970s Rock and Roll bands.
Some were simply 'Light Chasers' but the more interesting used analogue electronics (op-amps) to detect pulses of bass frequencies, which we then used to increment TTL counters and drivers for the SCR/Triac switched coloured lights (sometimes called a colour organ).Digital Logic quite quickly got my attention and I simply had to learn more.
FACTS
In electronics, facts are easier to define if they are like some kind of switch that has two positions, on and off. We often, especially in digital electronics, use the binary representation of ‘0’ for off and ‘1’ for on, or perhaps it is sensible to say ‘0’ is false, and ‘1’ is true.
Remember that these representations are human delegations. We simply say that ‘1’ is true, and allocate a positive voltage to represent the idea of ‘True’.
Most of our readers recognise the idea that 5V is a TTL logic level taken to mean ‘true’ and zero volts represents ‘false’ logic state. In the beginning of home computers, TTL (Transistor-Transistor Logic) was the standard for all parts used, but in some newer computers, 3.3V logic also exists, and in CMOS (Complementary Metal-Oxide-Semiconductor) logic the voltage representing true may be much higher.
The important fact to learn from this is that the rock-solid appearance of “Digital Logic” is, in fact, an “Analogue Level” recognised as ‘true’ or ‘false’ only in the minds of the designers, and the design of the electronics.
There are no digital integrated circuits, just analogue circuits working in a digital workspace - and you can quote me on that!
LEVELS
We have discussed logic levels in the Logic Probe article way back in Issue 4, however in summary, all logic works on analogue levels with defined voltage levels representing a certain logic ‘1’ or a certain logic ‘0’.
Electronics that has an output voltage between the positive and negative rail voltages are using power, therefore, good digital logic will attempt to make a logic ‘0’ level as close to ‘0 volts’ as possible, and a logic ‘1’ level as close to the rail voltage as possible; ‘3.3 volts’, ‘5 volts’ or whatever the rail voltage is for the logic system in use (Old industrial systems once used 48 Volt Relay Logic!).
CMOS logic uses much less power than TTL because it has levels much closer to the rail voltages.
TRANSITIONS
The second fallacy about digital logic is that it is always either zero volts or rail volts, yet the fastest types of logic still must get from ‘0’ to ‘1’. ECL logic (Emitter-coupled logic), considered to be the fastest type of logic, can work in the high GigaHertz range, yet it still has to get from ‘0’ to ‘1’ and back again.
As per the above comment, analogue states burn energy, so as logic gets faster and faster, the transition time becomes more important than the levels in generating heat. One important specification for logic is the dV/dT figure, i.e. the change in voltage over the change in time.
LOGIC FAMILIES
Logic families refer to a range of logic devices that work on the same parameters. Without attempting to describe each family, or the many sub-families of TTL for example, these following families have been used in approximate order of their invention. Switch Logic, Relay Logic, RTL, DTL, ECL, TTL, IIL(I2L), CMOS, HCMOS, BiCMOS and no doubt others that this writer has never become aware of.
This article is basically referring to TTL or CMOS working on 5V, as TTL. We will be looking only at the logic from now on and, for the purposes of this class, assume that our logic devices are perfect.
LOGIC GATES
The term “Logic Gate” most likely pre-dates George Boole, the mathematician who formalised the mathematics of Logic, now known as Boolean Logic.
In effect, before electric switches, the basic ideas of logic began with a fence preventing passage, except via gates. When two gates are side by side along the fence (gates A and B), a person can enter through either gate. i.e. Enter via gate A or gate B. If two gates were placed on a path one after the other (gates C and D), the person could only enter if both gates were open. i.e. Enter via gate C and gate D.
The term "Gates" remains, but it is only conjecture on my part that this is where the term began. In Digital Logic, we generally rely upon six types of gate, each of which we will describe with examples, and represent as symbols, logic expressions, and a truth table. The gates we will cover are the Inverter (‘INV’), ‘AND’ Gate, ‘OR’ gate, ‘NAND’ gate, ‘NOR’ gate, and finally the ‘XOR’ gate.
Some sources like to include a buffer, and others the ‘XNOR’ gate, but I have not seen an IC with such a critter!
COMBINATIONAL LOGIC
In the example of a fence above, you may notice that a person can enter via 'A' OR 'B', or via 'C' AND 'D'. This is a combination of two types of gates, resulting in a simple Boolean expression Q(entry) = A OR B or C AND D, where C AND D take precedence over OR as multiplication does over addition in algebra. However, we're leaving the Boolean Algebra for another time.
INPUTS
In Boolean form, we consider inputs as ‘A’, ‘B’, ‘C’ etc. for as many inputs as we are likely to require. Almost never requiring all 26 letters of the alphabet, thankfully, and no IC would have that many inputs anyway.
OUTPUTS
Gates usually require just one or two outputs, labelled and known as ‘Q’ and NOT‘Q’. NOT’Q’ represents the inverted value of ‘Q’, and some digital ICs, such as ‘Flip Flops’ offer both outputs; concurrently.
INVERTER GATE
The easiest gate to understand is the ‘Inverter’ Gate, which, as it says, inverts the logic. That is, it makes a logic ‘0’ become a logic ‘1’, and vice versa. Therefore, it is sometimes referred to as a ‘NOT’ gate.
In logic with only two options, say ‘me’ and ‘you’; NOT ’me’ must mean ‘you’ right? Hence NOT‘0’ is ‘1’ and NOT‘1’ is ‘0’.
In Boolean, NOT‘Q’ and other inverted values are written with a bar over the letter .
Therefore, Q = , means Q = NOT ‘A’
The symbol for an inverter, traditional ANSI symbol at least, is a triangle usually representing an amplifier followed by a small circle representing an inverted logic pin. The small circle may at times be shown at the input to gates and ICs representing that the pin is activated by a low signal ‘0’.
Note that there are several opinions on logic symbols, and perhaps using the conventional logic symbols over decades makes them second nature, but the alternatives don’t look ‘logical’ to me. However, we show them in the following figures for you to decide, and allowing you to read odd circuits you may come across.
TRUTH TABLES
A truth table is a chart of all of the possible input combinations and the resulting outputs. The inverter has only one input and only one output, but the input may be a ‘0’ or a ‘1’, resulting in the output being a ‘1’ or a ‘0’ respectively.
Other gates and indeed larger circuits may have many inputs, each input with 2n possibilities, so a truth table requires 2n possible conditions, and the outputs where ‘n’ is the number of inputs. For a 2-input gate, the truth table should have one column for each variable, and one for the output, and 2 × 2 rows; i.e. 4 rows.
Although, all inputs should only ever have an input of ‘0’ or ‘1’, sometimes we see an ‘X’ in a truth table, which represents “Don’t Care”. i.e. That input value doesn’t matter when the other inputs are in the state/s shown. It’s a way to simplify the understanding of a large Truth Table. You will learn more about Truth Tables if you continue to study Digital Electronics. Although the truth tables in this article may look very simple, be aware they can get a little tricky.
‘AND’ GATE
A common digital logic function is the AND function. As simple as it sounds that’s exactly what it does. If ‘A’ AND ‘B’ are True (‘1’) then the output ‘Q’ will be true. If either or both ‘A’ or ‘B’ are false, then Q will be false.
Consider your car; if (A) a gear is selected, AND (B) the handbrake is off, AND (C) the clutch is engaged, AND (D) the engine is running, then (Q) the car should be moving; is true. (This also proves that although the Logic is True, the car may not understand the logic!)
Logic decisions often require a number of conditions to be true before an action is taken.
The AND function is a Boolean Product, so Q = ‘A’ AND ‘B’ can be written as Q = A•B. Some texts alternatively use the caret (or inverted ‘V’) as in ‘A^B’ but this confuses mathematicians as it appears to mean A raised to the power of B. Other texts use the Ampersand (&) symbol as in ‘A&B’ as a good search engine should. If there is a standard, unfortunately, we don’t all accept the same standard!
THE ‘AND’ TRUTH TABLE
We decided above that a truth table requires a column for each input and one for the output, and 2n rows allowing for every combination of the input logic. To read it out to you, there are four possible conditions, with ‘AB’ = 00, 01, 10, 11 (Pronounced zero zero, zero one, one zero, one one). The output Q = A•B, will only be true when ‘AB’ = 11, and the first three rows will result in a ‘0’ at ‘Q’.
Those astute enough to recognise binary is the language of logic, will also notice that 00,01,10,11 is a binary count. If there were three inputs, A, B, and C, then there would need to be 8 rows, 000,001,010,011,100,101,110,111 being the eight possible input combinations for three inputs. Can you see how many rows you need for 5 inputs?
You have 5 fingers, allowing your thumb to call itself a finger for a moment. Now as dexterously as possible, what number can you count to on 5 fingers? If you only think 5, then you’re not thinking in binary. I can count to 31, making 32 numbers if I count 0 as the first number. Using both hands I can count 1024.
‘NAND’ GATE
Logic Gates work better when we can add them together to form another logic circuit. For example, if we connect an Inverter after the AND gate, we form a “NotAND’ or NAND Gate. NAND gates are arguably the most common of all logic gates which form the basis of almost every more complex circuit, including computers.
The truth table has the same inputs as the AND Gate, and in fact, every device with 2 inputs has 4 rows. Note however that you might have an AND gate or NAND gate with 8 inputs on a single gate requiring how many logic conditions? The last line would still be the only true output, 11111111=0 for an 8-input NAND gate.
The NAND Truth Table simply has the output levels inverted, giving three true, and only one false condition, when Q = . Notice that we still refer to the output as Q by convention.
For reasons you will learn about over time, every type of gate can be made from one or more NAND Gates.
Look closely and you can start by making an inverter from a single NAND Gate, Why? Because you may need a single inverter in a logic circuit but not have much space remaining on the PCB, and inverters come in a 6-pack, so you would have a 14 pin IC with five inverters left unused. However, if you have a single unused NAND; you can turn it into an inverter simply by joining all of its inputs together. The NAND is the basic building block of digital electronics.
‘OR’ GATE
It can’t be difficult when the name of a device describes exactly what it does. If ‘A’ OR ‘B’ is true, ‘Q’ will be true. i.e. Q = ‘A’ OR ‘B’, or in Boolean Q = A+B; the sum of A and B. More correctly in Boolean, the sum of A and B does not equal zero if either is true.
In Boolean Logic it is called the ‘Inclusive OR’ in that Q is true if A is true, or B is true, or both are true; meaning Q is true, inclusive of any situation where either or any inputs are true.
The truth table shows this with only the first row resulting in Q being false.
Consider a burglar alarm (Q) that you want to activate when (A) a door is open, (B) a window is open, (C) a movement detector notices something move, (D) a smoke alarm detects fire. Q = A+B+C+D.
‘NOR’ GATE
By this time you will probably already see that a NOR Gate is an inverted output OR Gate. Bravo for you as that’s perfectly correct. Add an inverter after the original Q output, to make the new Q output be the inverse of the OR Gate.
NOR = OR + INV, therefore Q = . It’s hopefully getting simple now, and with only one gate to go, maybe you can relax a little.
The NOR truth table with a two-input NOR will obviously, by now, require four rows, AB = 00,01,10,11. resulting in Q = 1,0,0,0.
Some logic can be built entirely from NOR Gates. Once again, make an inverter from a single NOR gate. However, can you see how to make an AND Gate from three NOR Gates? I’ll leave that to you, but please use a truth table for help.
‘XOR’ GATE
We’re almost there for this class, but remember, we stated that the OR Gate is truly an Inclusive OR Gate? That implies that there is another kind of OR Gate, and there is. The XOR Gate is an exclusive OR Gate, which is best defined as follows. The output will be true when any one of the inputs is true, but not both, which covers the most common two input gates.
The symbol for the XOR gate is a ‘+’ inside a circle, ‘⊕’ so that the XOR can be written as Q = A⊕B. A⊕B reads as 'A' eXclusive OR 'B', meaning 'A' OR 'B' but not 'A' AND 'B'.
The XOR function can also be built from either NAND or NOR gates, if we look at the truth table and make a circuit from the true outputs, thus: Q = A⊕B = A&+B&, being the two states that result in a true output. We’ll leave the implementation of that Boolean expression for another Classroom, however, but you are welcome to try it as an experiment into ‘Combinational Logic’ meaning combining gates to fit a logic expression.
XOR APPLICATIONS
I am not aware of any XOR Gates with more than two inputs, but one special application of the XOR Gate is within a Parity Checker as was used in older computers, including the IBM PC-XT, to confirm memory validity. The parity chip compared all of the 8-bits creating a 9th bit called the parity bit, that was a result of the other 8-bits XOR’d together in such a way that the sum of the 9 bits was always odd (or was that even? It was quite a while ago.)
Another use was for simple encryption in very early computers. The user would pass their 8-bit ASCII* data into an encryption box that was nothing more than eight XOR gates with one input set by the user to their “Encryption Key”, which was simply an 8-bit combination lock.
Note: ASCII (American Standard Code for Information Interchange) is a standardised way to represent letters, digits and characters as an integer value.
The person receiving the file would pass the data back through an identical box, and as long as their ‘Encryption Key’ was the same as that switched into the sending box, the data would return to the original text.
Would-be “Secret Squirrel” types might like to experiment by writing a short simple message and converting it to ASCII, then to encrypted code. The message, perhaps simply a single word (password), is passed to a second person, who is aware of the “Encryption Key” for conversion back to readable ASCII. Good fun for bored students on a slow afternoon before going home.
Note that for a 5 letter word and 8-bits (extended ASCII) there will be a binary string of 40 bits to be encoded (and decoded) against a single 8-bit keycode (the encryption key).
Let’s prove it with a single letter ‘A’ (Hexadecimal 41 or ‘01000001’) encoded by XORing it with ‘X’ (Hexadecimal 58 = ‘01011000’)...
Now, at the receiving end, the code is decoded the same way...
Returning the original hex code of 41H, or the ASCII letter ‘A’.
Of course, instead of a single keycode, you could use a keystring of many characters to create a more difficult encoding for avoiding hackers. You may have heard of 128-bit encryption, which is no doubt more complex than this simple example.
BOOLEAN DOUBLE NEGATION
Finally, let me show you a couple of tricks using Boolean Algebra and something else known as De Morgan’s Law.
NEGATION
Let us invert the output of an inverter, making Q = , which becomes Q = A, and two inverters become simply a buffer.
DE MORGAN’S LAWS
If I invert the inputs to a NAND, the circuit becomes Q = .
If I invert the inputs to a NOR gate, the circuit becomes Q = .
The truth tables for these three circuits are given in the following diagrams. Inspect them and see if you notice something interesting?
We also made a NAND gate from an AND gate and a NOR gate from an OR gate by adding an inverter to the output. NAND = and NOR = . What would become of an AND gate if we inverted the inputs instead? Q = AND . The truth table rows would be 11,10,01,00 making the outputs 1,0,0,0, the same outputs as a NOR gate! What’s going on here?
These are examples of De Morgan’s Laws, which enable us to convert circuits between NAND and NOR quite easily, but also introduces a notion of ‘Negative Logic’.
At times, circuits are easier to solve when the logic is inverted, using negative going inputs instead of positive going inputs, and inverting the output if necessary.
It’s an admission on our part that True and False are simply voltage levels that we decided upon arbitrarily, and if we can get our minds around it, negative logic is also a useful tool.
Just to leave you thinking, De Morgan’s Laws are:
WHERE TO FROM HERE?
Now I stirred the pot giving you a taste of Boolean, perhaps you might like a future classroom on Boolean Logic and simplification of combinational logic expressions! (Anybody still with me?)
We have barely touched the surface of digital logic. A complete computer can be built from just NAND gates, and that leads to another technology the FPGA.
In some universities, Digital Logic is now taught by programming an FPGA which is a ‘Field Programmable Gate Array’, basically a lot of NAND gates, and other more complex parts assembled into a single IC, that can be programmed, not by computer language statements, but logic statements.
We could delve into Boolean Logic, Karnaugh Maps, Combinational Logic, Sequential Logic, and State Machines.
You can see, Digital Logic is simply knocking on the door of a much greater world.
Part 2: Digital Logic Gates Explained