Home
Writing
My Resume
Programming
Some Candid Photos
About this site

Table of Contents

  1. Introduction
  2. Boolean Functions
  3. Truth Tables
  4. Logic Gates
  5. Electronic Implementation of Logic Gates
  6. Spreadsheet Implementation of Logic Gates
  7. Circuit Building With Logic Gates
  8. Spreadsheet Implementation of Logic Circuits
  9. Spreadsheet Implementation of a Computer
  10. Downloads

Introduction

In 1995 I was in the Computer Based Information Systems program at McGill University, and one of the courses was "An Introduction to Information Systems Technology". This course was a study of computers and their operations at the binary level; that is, how a bunch of on/off switches are organized in order to do the things that computers do. One of the tools used in this study was the spreadsheet. It turns out that most spreadsheets have the ability to deal with 1's and 0's as Boolean elements (as opposed to mathematical elements). This ability, plus the spreadsheet functions AND, OR, and NOT, allow us to simulate elementary logic functions which can then be strung together to create logic circuits which in turn can be strung together to create a simulation of an entire microprocessor.

What follows below is a brief outline of how this is done. I start out with a few Boolean functions and how they can be represented in truth tables, and then go on from there to show how truth tables can be used as a basis for creating elementary circuits which can perform binary addition. Next comes how these circuits can be implemented in a spreadsheet. Finally, I outline how they can be combined and organized in order to create a working device.

Keep in mind that there is not nearly enough information presented here for anyone to be able to sit down and crank out their own version of a microprocessor. It is just a quick sketchy outline that attempts to show how such a thing can be done. However, I did try to include links to other sites that better explain the concepts involved.

For the "Introduction to Information Systems Technology" course, the profs Glen Matthews and Philip Troy created a hypothetical 16 bit microprocessor which they called the IST-16. The last assignment for the class was to create a spreadsheet simulation of this processor. My version, for which I got an A, is available for download.

[Table of Contents]

Boolean Functions

A Boolean function is a function whose inputs (and output) can take only one of two values. These values can be expressed as TRUE/FALSE, ON/OFF, BLACK/WHITE, 1/0, and so on.

There are many Boolean functions, but the ones we are interested in here are OR, AND, NOT, and XOR. With the exception of the NOT function, each takes at least two inputs. If we use the numbers 1 and 0 from the binary number system as the two possible values for each of the inputs, we can express the just mentioned Boolean functions like this:

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1
NOT 0 = 1
NOT 1 = 0

Note: XOR stands for eXclusive OR, and is sometimes called EOR.

[Table of Contents]

Truth Tables

It is convenient sometimes to represent Boolean functions in the form of truth tables. In the tables below, the columns labeled "I1 and I2" represent the input values, and the column labled "O" represents the values that are output given the inputs (I1 and I2) and the specified boolean operation (OR,XOR, etc)

OR
I1 I2 O
0 0 0
0 1 1
1 0 1
1 1 1
XOR
I1 I2 O
0 0 0
0 1 1
1 0 1
1 1 0
AND
I1 I2 O
0 0 0
0 1 0
1 0 0
1 1 1
NOT
I O
0 1
1 0

When we perform the arithmetic addition of two binary numbers, the possibilities are 0+0=0, 0+1=1, 1+0=1, (each with a carry out of 0), and 1+1=0 with a carry out of 1. Notice that addition in binary arithmetic can be accomplished by applying the Boolean functions expressed in the XOR and AND truth tables. If the two numbers to be added are used as inputs I1 and I2 in each of these tables, then the result of the addition can be read from the output column of the XOR table, and the carry out from the output column of the AND table. Thus Boolean functions can be used to perform mathemetical operations on binary numbers. Binary math is described better here: Binary Math

[Table of Contents]

Logic Gates

Logic gates are an even more convenient method of representing Boolean functions, as they are more graphical, and can be used to build up logic circuits. These are the gates for the Boolean functions under discussion here:

OR XOR AND NOT

In the orientation shown, the inputs are at the top and the outputs are at the bottom. To use a logic gate, imagine that one input appears at each upper vertical line, and that the indicated Boolean function is carried out, and the output appears at the bottom line. For example, if we were to use the OR logic gate to represent the logical OR operation 1 OR 0 = 1, we would imagine 1 at the left line, 0 at the right line, and the result, 1 at the bottom line.

We can show graphically the arithmetic addition of two binary numbers by building up a little circuit using an XOR gate and an AND gate and connecting up the lines in the proper way.

I1 and I2 are the two numbers to be added. The result of the AND operation, OC, is the carry out. The result of the XOR operation, O, is the sum. You can see that when the input is 1 + 1, the output OC and O combine to provide the binary answer 10 which is decimal 2.

I2I1OCOMath
0 0 0 00 + 0 = 00
0 1 0 10 + 1 = 01
1 0 0 11 + 0 = 01
1 1 1 01 + 1 = 10

The circuit shown above is what's known as a half-adder, as opposed to a full-adder. A full-addder has additional circuitry to accommodate an additional input, the carry-in. Single-bit full-adders can be strung together with the carry-out of one circuit connected to the carry-in of the adjacent circuit to build multi-bit digital adders. More detailed information and a better explanation of how this is done can be found here: Combinatorial Logic: Binary Adder

Note that the simple adder circuit shown above is only one of the many useful circuits that can be built with the use of logic gates. Selectors, counters, and memory circuits are also possible (and common), but more about that later.

[Table of Contents]

Electronic Implementation of Logic Gates

We can implement logic gates electronically, and therefore we can perform logic functions electronically. And since we can combine logic functions into logic circuits to perform simple mathematics, then it follows that we can build electronic circuits to perform mathematical operations. There are different ways to do this, but the transistor circuit is the most well known. (To see more about what transistors are and how they work, see Elementary Building Blocks: The Transistor).

The presence of a voltage in an electronic circuit can be defined as one of the two states required in Boolean logic, and the absence of a voltage as the other. If we equate a voltage level of 5V with 1, and 0V with 0, then by using properly sized transistors and resistors connected together in a circuit, a variety of logic gates can be implemented. Here is an example of an OR gate:


If a voltage is applied to either one (or both) of the inputs I1 and I2, then a voltage will appear at the output O.
[Table of Contents]

Spreadsheet Implementation of Logic Gates

All of the logic gates described above can be implemented in any spreadsheet that provides Boolean functions. The samples below are implemented with Microsoft Excel 97 simply because that is the spreadsheet that I have installed on my computer. Excel 97 defaults to displaying Boolean results as TRUE/FALSE instead of 1/0. This can be changed by going to Tools on the main menu and selecting Options... When the dialog box appears, select the Transition tab, then make sure that the "Transition formula evaluation" check box is checked. I don't know if this option is available on earlier or later versions of Excel.

If you want to experiment with spreadsheet implementation of logic gates, use the screenshot below as a guide.

Note the formula in cell D5, the XOR cell. The spreadsheet only implements the OR, NOT and AND Boolean functions, so we need some other way of obtaining the XOR results. This can be done by using the OR, NOT and AND functions in the manner shown. More about this technique later in the next section. As a matter of fact, the AND function can be implemented by using only the OR and NOT functions, so it's possible to implement all of the Boolean functions needed to build a computer with only the OR and NOT Boolean functions. In the example above, the formula NOT(OR(NOT(B7),NOT(C7))) in cell D7 is equivalent to the formula AND(B7,C7).

[Table of Contents]

Circuit Building With Logic Gates

So far only some of the more elementary and simple truth tables have been presented, along with their associated logic gates. But much more complicated truth tables can be constructed, and for these tables there are no corresponding logic gates, so their functions must be implemented by linking two or more gates into a circuit. We have already seen a small example of this in the 1-bit half-adder above. Truth tables can be constructed that describe counters, decoders, multiplexers, and even memory elements. These tables are a bit more involved than the ones described so far. Fortunately, there is a simple set of rules that can be applied in order to map any truth table onto a logic circuit. Such a circuit ends up being composed of only OR, NOT and AND gates.

Here are the rules, followed by an example:

  1. First, construct the truth table.
  2. Next, draw one OR gate for each output column.
  3. Add one AND gate for each row in the truth table that has a 1 in the output column.
  4. Add one line for each input column into each AND gate.
  5. Place an inverter (a NOT gate) on each input line that has a 0 at the intersection of the input column and selected row of the truth table.
  6. Complete the circuit by connecting each AND gate input line to the circuit inputs.

Now for a simple example using the truth table for the XOR function.

  1. First, construct the truth table for the XOR function, with its two input columns and one output column:
    I1 I2 O
    0 0 0
    0 1 1
    1 0 1
    1 1 0
    When constructing circuits from truth tables, only the rows with a 1 in the output column are relevant.
  2. Next, draw one OR gate for each output column.
    Since the XOR truth table has only one output column, only one OR gate needs to be drawn.
  3. Add one AND gate for each row in the truth table that has a 1 in the output column.
    There are two rows where a 1 appears in the output column, so we have two AND gates, one for each row. Let's call these two rows the "selected rows" so that we can refer to them later.
  4. Add one line for each input column into each AND gate.
    There are two input columns in the XOR truth table, so each AND gate gets two lines drawn on its input side.
  5. Place an inverter (a NOT gate) on each input line that has a 0 at the intersection of the corresponding input column and selected row of the truth table.
    There is a 0 at the intersection of the I1 column of the truth table and the first selected row, so the first AND gate gets an inverter drawn on its I1 input line. Similarily for the other AND gate and its I2 input line.
  6. Complete the circuit by connecting each AND gate input line to the circuit inputs.
    The completed circuit. If you apply each of the four pairs of inputs and carefully trace through the circuit, you will see that the output exactly matches the Boolean XOR function.

Note that these rules work fine for simple circuits such as the one described. For more complex circuits though, some slight modifications and enhancements are required. This is especially true when it comes to counters and memory cells which depend on feedback in order to operate.

[Table of Contents]

Spreadsheet Implementation of Logic Circuits

As seen above in the section Spreadsheet Implementation of Logic Gates, the XOR function was implemented as a spreadsheet simulation of a logic circuit. The inputs were typed into cells B5 and C5, and the formula was typed into the output cell D5. With such an arrangement, whenever new values are entered into the input cells followed by a spreadsheet recalculation, the formulae are re-evaluated and the new outputs displayed. So how is a spreadsheet formula created for any given circuit? Well, it turns out that just as there is a method of creating logic circuits from truth tables, there is also a method of creating spreadsheet formulae from truth tables. But before we get to the method, note that each spreadsheet program has its own syntax when it comes to spreadsheet formulas. In Excel, the AND function syntax is AND(expr1,expr2), where expr1 and expr2 are any Boolean expressions that evaluate to TRUE or FALSE. (In order for the formulae to work, Excel needs to be changed to work with 1/0 instead of TRUE/FALSE. Do this by going to Tools on the main menu and selecting Options... When the dialog box appears, select the Transition tab, then make sure that the "Transition formula evaluation" check box is checked.) There is a similar syntax for the OR and NOT functions.

Here is how to build the formula to simulate an XOR circuit:

  1. Draw the truth table
    I1 I2 O
    0 0 0
    0 1 1
    1 0 1
    1 1 0
    As when constructing circuits from truth tables, when constructing spreadsheet formulae, only the rows with a 1 in the output column are relevant.
  2. Select the spreadsheet cells that will be used for the inputs and the ouputs.

    In our example here, I1 will be cell B5, I2 will be cell C5, and the cell into which the formula is typed, the ouput cell, will be cell D5.

  3. In cell D5, type one OR function skeleton for each output column.

    =OR( , )

  4. Within that OR function skeleton, type one AND function skeleton for each row with 1 in the output column.

    =OR(AND( , ),AND( , ) )

  5. Within each AND function skeleton, type a NOT function skeleton for each 0 that appears in the truth table input column where it intersects with a selected row.

    =OR(AND(NOT( ), ),AND( ,NOT( ))

  6. Type in the input cell names.

    =OR(AND(NOT(B5),C5),AND(B5,NOT(C5))

This all looks pretty difficult, and it is, but with some practice, you can get fairly good at it. Quite often it's easier to draw a circuit first, and then build the formula from there. This is especially true when you get into truth tables with three or more input columns and three or more output columns - things get very scary very fast.

[Table of Contents]

Spreadsheet Implementation of a Computer

Simulating a microprocessor in a spreadsheet is a very involved and complicated process. I would imagine that it's almost as complicated and involved as building the real thing. For one thing, the flow of data through the system must be managed very carefully so that the output of each circuit is properly directed to the input of the appropriate next circuit. And there are also timing issues to deal with - not only must the data arrive at the right place, it must also be there at the right time.

Spreadsheet characteristics must also be taken into consideration. The recalculation of a spreadsheet typically takes place row by row. This means that any element or circuit with dependents must appear above those dependent elements or circuits. For example, the cells which act as the inputs for an adder circuit must be in row above the cells which contain the formulas that perform the actual calculation. If, however, a spreadsheet were set to calculate by column, then the cells which act as the inputs must be in a column to the left of the cells which contain the formulas. An additional issue is the number of iterations. Typically, the spreadsheet is recalculated with as many iterations as are needed to bring all cells to their final values. This is a problem in circuits such as memory and counter circuits which depend on feedback in order to operate. Most spreadsheets will detect these as circular references and refuse to operate unless the spreadsheet iterations are set to 1.

[Table of Contents]

Downloads

  1. The first download is a little demo that shows how a selector circuit is connected to a 16-bit adder and a 16-bit subtractor in order to allow the user to select which operation is performed on the inputs. The circuits are implemented in a Microsoft Excel spreadsheet.

    Add-SubtractDemo.zip

  2. A complete microprocessor simulation is the second download available. It implements the IST-16 processor in a Lotus 1-2-3 Version 5 for Windows 3.1 spreadsheet. I originally wrote it in Lotus, but have not yet converted it to Excel. The reason is that by setting the spreadsheet to calculate the formulas by column, it was possible to implement the processor horizontally instead of vertically. Unfortunately, this option is not available in Excel, so it would take some doing to rearrange the whole thing vertically.

    The download also includes a brief description and set of instructions for using the model. I scanned these in, so they are in graphic format (.gif) - eventually I'll get them into a text or HTML format.

    IST-16_SpreadsheetSim.zip

[Back to Top]
Contact:

Last Update: Oct 1, 2000