We look at how simple gates combine to become much more impressive modules, even to VLSI; Very Large Scale Integration.
Logic, especially electronic (digital) logic, provides us with the building blocks of the Computer Age; from the simplest ‘AND’ Gate to the most impressive Super Computers ever built, down to the humble Smartphone, or the diminutive Raspberry Pi.
In case you missed last month’s issue, we discussed the six common Digital Logic building blocks; the Inverter, AND gate, OR gate, NAND gate, NOR gate and finally the XOR gate. We also showed you what a digital ‘True’ and a digital ‘False’ is; what ‘Truth Tables’ are, and how they are used. While you may already know of these functions, if you are not fully aware of their purpose, you might like to revisit the last issue #019, if you need to.
This month we will look at how logic gates are combined to form more complex circuits, and how to simplify these circuits to use fewer gates. We will also look at the common ‘Sum of Products’ (SOP) method of circuit building, and how to reduce complex logic circuits to the simplest forms to reduce the necessary number of gates. We will provide a brief introduction to the family of ‘Programmable Digital Logic’ devices, in concept at least, and introduce you to other similar devices and the reason for their being.
COMBINATION VS SEQUENTIAL LOGIC
Logic circuits fall into two rough categories, Combinational Logic, and Sequential Logic, sometimes called State Logic.
Sequential Logic will probably contain combination logic, but to be sequential, a circuit must contain some form of time management or memory, even as simple as flip-flops, latches etc.
Other circuits used in computers, such as half-adders, full-adders, full-subtractors, multiplexers, demultiplexers, encoders, and decoders are made by using combinational logic. This article only intends to give you a preview of these devices as a full course would require a formal education!
The most mathematical part of a computer, the ALU (Arithmetic Logic Unit) is merely a collection of combinational and sequential logic circuits made from gates you have already read about in the previous issue. We will concentrate on Combination Logic in this article.
COMBINATION LOGIC
In the last issue, we looked briefly at how examples of one or more types of gates could be combined to form another type of gate. We discussed how ‘AND’ gates are changed into ‘NAND gates, ‘OR’ made into ‘NOR’ and even how complete circuits requiring a mix of gate types can be made entirely from NAND gates or NOR gates.
However, we can do much more as well. Take as an example, a simple circuit known as a half adder, which is found within all computers to add two binary bits.
BINARY ADDITION OF TWO BITS
For each combination of bit values for a two input truth table, the maths is simple, yet we must remember what we learned in primary school. The first three additions shown as columns 1, 2 and 3, are as simple as adding any two decimal numbers, until the result in decimal becomes greater than 9. Above that, you remember we need to account for what we call the ‘Carry’, and you remember you must add the two original numbers in the next column plus the carry.
We usually call the two inputs, bits ‘A’ and ‘B’ although they can be called Mike and Mal if you like. The output ‘Q’ can only be 0 or 1, but even in binary, the result of the sum can be greater than the maximum value of that column as you remember from primary school decimal maths. If a decimal sum becomes greater than 9, you must add another column, right?
Likewise, if both binary input bits are 1 the output will be 10. i.e. in binary; 1 plus 1 = 10.
Remember: “There are 10 types of people in this world; those that understand binary and those that don’t!”. Get it?
The two bit binary input requires a truth table with four rows, just like an AND gate would. However, our truth table requires a column for both the ‘Q’ output and, as we have just discovered, the ‘Carry Out’ (‘Co’) output, giving the truth table with two output columns.
HALF ADDER
Therefore, we can make a half adder using just two gates. Can you see what they are from the truth table? The output ‘Q’ is the same as for an ‘XOR’ gate, which can be written as Q = A⊕B, or Q = A(XOR)B, or Q=(A&!B)+(!A&B). (Remember ‘!’ means ‘NOT’)
The carry (Co) is even easier, being a common ‘AND’ gate. Can you see what it is in the truth table? Therefore the circuit for a half adder is shown below and you (or your class) can make one with two ICs. (7408 and 7486 would do nicely. Using those two ICs you could make four Half-Adders.)
FULL ADDER
The problem with a half adder is that there is no provision for a carry in from the previous binary digit, which would be needed if we were adding two hexadecimal numbers! We require one more input, Cin, so the truth table needs to show three inputs, or 3-bits (23 = 8), so there are 8 possible conditions for each of the two outputs. The outputs can all be worked out in boolean maths. (Using the same rules as adding decimal numbers, without a calculator!)
Reading the truth table is a little harder now, but still requires each line one at a time as ‘AND’ed conditions within brackets, and all rows are to be “OR’ed together in what is known as SOP (Sum Of Products) form, as shown in the next two formulae.
Q = (!Cin&!A&B)+(!Cin&A&!B)+(Cin&!A&!B)+(Cin&A&B). (Whew!)
Co = (!Cin&A&B)+(Cin&!A&B)+(Cin&A&!B)+(Cin&A&B).
Each ‘AND’ed term within brackets represents a ‘1’ in the table under ‘Q’ or ‘Co’.
FULL ADDER CIRCUIT
Therefore, we can use two half-adders and one OR gate to make one ‘Full-Adder’. Referring to the diagram above, bits A and B are inputs to the first half-adder with the sum provided to the second half adder as an input. The Carry In bit is the second input to the second half-adder giving the final output as Q, the result of the three inputs. If we simply look at the three inputs (A,B,Cin) on the truth table, and the output Q, we should note that Q is true (1) when there is an odd number of true inputs.
To get the Carry Out (Co) we need an OR gate with the two half-adder Carry Out bits ‘OR’ed together in a separate OR gate with the output becoming the new Co.
MORE BITS
The purpose of this discussion is to help you realise just how rapidly logic circuits can grow in complexity. So far we have merely added two bits, and allowed for a carry in and a carry out. Although some early computers only allowed for 4-bits, we currently work with 64-bit computers, so imagine adding two 64-bit numbers using just logic gates. That’s when squeezing the logic down to VLSI, (Very Large Scale Integration), becomes vitally important. However, the people who design computer chips use exactly the same basic building blocks as the six basic gates we are using here. Computers, being made from logic, are pedantic, especially at maths. So adding two 4-bit binary numbers requires four full-adders, making our logic circuit already four times more complex. In this article, we will limit our efforts to 4-bits for now as that’s enough to explain how it works yet not require the whole magazine to show you a circuit.
HEXADECIMAL VS BINARY CODED DECIMAL
Four bits is enough to represent a decimal number, from 0 to 9, yet the 4-bits allows 16 logic states for a 4-bit binary number. We have two usually accepted options, one to use just 10 of the 16 logic states as what is called Binary Coded Decimal (BCD), or do the maths in hexadecimal, using the 16 value scale “0-1-2-3-4-5-6-7-8-9-A-B-C-D-E-F”. You often see numbers in a form like FE86 when using computers, especially when actually using a computer rather than a mouse and a GUI. These numbers are called Hexadecimal, which doesn’t mean 6x10 as some may occasionally suggest, but the decimal number 16.
So how do you know what you are using? Unfortunately, that depends on the OS, and the hardware makers. Typically 66 would be assumed as decimal as most numbers we see are decimal, but 66H, or 66h reads as ‘sixty six hex’ although the ‘C’ computer language would require us to write 0x66. Others might write ‘66x’. In maths, it is 6616 is the way to go. So unless one of these methods is used, we would not know it is hex unless you see an A-F in the number.
We will only work on full Hexadecimal numbers here, for now.
ADDING TWO HEX NUMBERS
It took longer to explain what Hexadecimal is than it takes to add them together. In this example, let us add the hexadecimal numbers 6H and AH.
First, we want the hexadecimal numbers as binary numbers, so we need to remember the binary values for each binary column. We are only using 4-bits, so four columns with the values ‘8’, ‘4’,’2’,’1’.
Therefore, 6H will become 0110, meaning 0+4+2+0 where a binary zero results in no value for that column.
The Hexadecimal AH is actually decimal 10, resulting in the binary number of 1010, or 8+0+2+0. Simple right?
To add the two binary numbers 0110b and 1010b, just as in primary school maths, we write the two numbers, and a spare line for the carry, an underline and then the answer.
0110b
+1010b
11100
10000b
Noting that 6H + AH = 6 + 10 =16, (10H) which results in an answer of 0000b and a carry out (Overflow Error).
4-BIT FULL-ADDER
The circuit shown below shows four full-adder blocks connected as a ‘4-bit Full-Adder’, as is implemented in the TTL logic IC; 74LS283N. Note that the carry out of one digit (bit) is the carry into the next digit (bit). There is also an external carry in and carry out. Teachers might like to use this IC as a demo of this topic.
In TTL, generational upgrades to Logic ICs often results in a hundreds column. For example, a 4-bit counter known as the DM7493 progressed as follows; making a 7493 > 74193 > 74293 > 74393 series of numbers. So 74LS283 is an upgraded 74LS83. The basic operations are the same, and the pinout is usually the same, though added functions may at times require more pins.
DECODERS
Another combinational logic device is known as the ‘Decoder’. A common example of a decoder is the BCD-7-segment LED decoder, which means a TTL IC such as the TTL 7447. Note that the term BCD is expected here as most uses of a 7-segment LED display requires only the digits 0-9. One IC labelled the DM9368 was capable of decoding full Hexadecimal numbers (0-F) to the 7-segment display, but perhaps I have the last few examples in my own stock, as I couldn’t find any for sale. Later we will look at other options.
The 7447 has four inputs being a binary number from 0000b to 1001b, the decimal numbers or digits from 0-9, and we could simply give you a truth table with 10 rows, but for just 6 more rows, as the ad says, you get a full hexadecimal decoder.
Note that it is a modified truth table as it shows the 4-bit inputs and 7-bit display outputs. Column 5 gives the character to be displayed for the binary input, and we have included a labeled 7-seg display as well.
The decoder is basically a Sum Of Products (SOP) circuit requiring 10x7=70 AND gates for a BCD display, or 16x7=112 AND gates for a Hex display. The seven outputs require an OR gate with either 10 or 16 inputs making a minimum of 77 gates for the BCD device, or 119 gates for the Hex device. Of course, an actual circuit uses Boolean Algebra to minimise the number of gates.
The circuit also typically uses 4 input buffers, and 7 driver outputs so a possible 130 gates for the Hex decoder. You can see why gate density becomes a big issue, as the 7447 decoder is the same size as a Quad-AND gate IC. There must be a better way!
PROGRAMMABLE DIGITAL LOGIC
Discrete logic gates, and even multiple gate logic ICs can take up a lot of space on a PCB. My first Microbee Computer had an interesting IC on the PCB called a PAL device. As the only device not known to my friends and I, we did some research which at the time was hindered by having no internet, and only a few BBS’s that we knew of. My first Microbee had no modem either but interestingly it had the sockets for the AM7910 IC. Another story for another time.
Somehow, I came into possession of a databook on Programmable Array Logic, from “Monolithic Memories” now itself a memory. In it, was a device I was looking for, a PAL12 I believe. It is really a programmable decoder with an SOP table that decoded a collection of memory address and control bus lines that in turn controlled the computer. I’ll leave the details but it was the first realisation that a memory device could be used as a Programmable Logic Device.
That’s now an interesting way to make an unavailable HEX to 7-Seg decoder in a single IC. A modern version of the PAL would be a GAL which like an Arduino is a re-programmable device, except working on logic rather than a program. The GAL has one advantage over a microcontroller, everything happens in parallel, at an astonishing speed compared to even a 20MHz controller. The upper range for the GAL IC is 250MHz but it doesn’t have to think (compute); it simply does! We may take a deeper look if there is enough interest but if you want to get ahead of me look up the GAL16V8, now V8 got your attention right? GAL is old technology but simple by comparison to the Programmable Logic that has followed, sPAL, PLD, SPLD, CPLD, FPGA.
HOW PROGRAMMABLE LOGIC WORKS
Briefly, very briefly, every input passes through a buffer and also in parallel, an inverting buffer. making both upright logic and inverted logic available to a matrix, two columns for every input, so 8 inputs require 16 columns on the matrix.
Every output requires an OR gate followed by a buffer to protect the internals from overload. The outputs may also be ‘re-entrant’ returning to the matrix as more inputs, also as upright and inverted forms, adding to the number of columns.
The matrix also has a number of AND gates with rows that cross the matrix columns. The intersection of the matrix rows and columns can be set or reset, originally by burning “fuses”, then UV erasable EPROM type cells, and now by Electrically Erasable Programmable Read Only Memory (EEPROM) type cells.
PROGRAMMING THE IC
The circuit must be drawn, or truth table written, or a VHDL (VHSIC Hardware Description Language) or similar programming script written. Then an Assembler converts the raw instructions to a file in the same form as a hex file, as used in a common Arduino. Finally, a programmer installs the binary (hex) file to create the joints between matrix rows and columns. Now in minutes, you have your own personal Logic IC.
PROGRAMMABLE LOGIC USES
The most recent technology I am aware of is the FPGA, which I have to admit I have never even seen although my oscilloscope has one and also my Signal Generator I believe! The latest FPGA based devices may have specialised analogue functions as well as digital, some with a computer core as well, and have some other features such as volatile memory, USB and even Graphic LCD drivers. Hobbyists have made the FPGA emulate old world microprocessors, and even complete computers, all on a single IC. One supplier has a FPGA based test instrument that provides an Oscilloscope/Spectrum Analyser/Logic Analyser/Signal Function Generator and many other test equipment options all in the one Arduino sized PCB.
MORE COMPLEX?
Of course, complexity in digital logic is based on continuous integration. Logic is best understood when practiced, and especially in hands-on TTL or CMOS circuits using actual Logic Gates. Even if all you do is recreate the famous Arduino “Blinky”, you know you did it!
IN SUMMARY
We have looked at technology based upon the standard 6 Logic Gates, combined to form complex circuits with complex ‘super-powers’. You have seen how computers do their math homework, and how circuits without a microprocessor can display a number. Finally, we introduced the world of Programmable Logic, and how they may be used to replace large arrays of logic circuits.
Part 1