Ever wondered how computers work? In this tutorial, I attempt to explain this from the ground up. First, we'll look at how a machine can add numbers.
The Computer – By Nick Fletcher (nickeax)r
For people who have seen C or C++ code before, but not necessarily know a real lot about it.
To me, computers represent a very important human achievement. Computers were theorised over
for a long time (centuries), and it was only until the 1930’s that what we today recognise as
a computer, was first ‘blue printed’. Even though this was still mainly theory.
That’s enough for the intro because we have a lot to get through. What I plan to do with this
tutorial(s) is cover many aspects of computing. I want to show you how computers perform operations on
data at the most basic and close up levels and I also want to teach you about C and C++ programming!
How am I going to do that???
I want to let you know that this is a follow along type tutorial. You can just read along and read the C and
C++ code that I present, but it will be much better to have a compiler sitting there, ready to try out
and use the code!
I will be using DJGPP and LCC(for win32) to build the examples. The examples will eventually form a complete piece of software.
Firstly, you will need to know a little bit about C programming. Not much though! After all, the idea is to
teach you that as well. Secondly, you’ll need plenty of time. We are going to cover a lot of areas and do quite a bit of programming! Also, you will end up with a useful piece of software at the end of this. Not to mention a very good understanding of what’s going on inside your own computer. (I hope…)
Our project begins with an outline of what we hope to achieve:
- Part 1 – Understand how a basic microprocessor completes some basic tasks
- Part 1 – Build some software to replicate some low (ultra low) level electronics
- Part 2 – Forget how the electronics work and wrap up that stuff in a box!
- Part 2 – Model a simple computer system that can process our own computer language
- Part 3 – Model some features for the computer, like HD, floppy drive and monitor
Ok, let’s begin. A computer is basically a big calculator. It can add numbers together, very
quickly and accurately. I was always fascinated by this fact. I always used to think to myself,
“Hmm… They say a computer can add numbers together. How can a machine add numbers
together? They would then say, ‘Oh… That’s easy. They use binary instead of decimal…'”
Well, that wasn’t good enough for me. Everyone knows that computers use binary. But that’s a lie. It’s just a way to make it easier for humans to think about what a computer is doing. In fact, computers don’t use binary, they use electricity!
What they meant when they said computers use binary was really,
“Oh, computers use electricty and we ‘map’ the voltage readings to abstract values like, TRUE FALSE ONE ZERO
But this wasn’t really helpful either. What I wanted to know was how a machine could be given an input of voltage somewhere and then, somewhere else, output a correct answer without any help from a human! To me, this was simply amazing.
As it turns out, the mechanics of how this is achieved are quite simple. The simple, easy way of doing this has been left behind in the cobwebbed annals of computer history. The simple way I am going to show you would be waaay too slow for any modern system. But, the principles are the same still.
Now we are going to learn a bit about how a machine can add numbers, then we’ll build a model of such a machine in C++ code. Ok? You’ve probably seen a binary number before. It’s a group of one or more 1’s and 0’s set out like any decimal number. I won’t dwell too much on why computers use binary, because really, they don’t have to. It’s just simpler that way, which translates to cheaper!
The whole business of machines that can add(and subract which is just adding a negative number to a positive) comes down to electronic switches called gates. Imagine a house with a long passageway and a light halfway along the passage. In this situation, you normally have a light switch at each end of the passage. The switches are wired so that they can operate the light regardless of what each individual switch is set to(on or off). You could say that the light will turn on if one switch or the other, or both are switched to on. Now, this works, because of the way the switches are wired to the power and the light itself. Imagine a ‘Y’ shaped arrangement where the light is at the base the ‘Y’. The two light switches are each ‘branch’ of the ‘Y’. Power can only make it’s way to the light through either branch of the ‘Y’.
You can imagine now that as long as one switch is turned on, power can make it to the base of the ‘Y’ and light the globe. Notice, when I described how the switches may be used that I used the word OR to indicate that either one switch OR the other OR both can be used to light the lamp? This arrangement
of switches is known as an OR GATE. The OR GATE may have two or more inputs and one output. In this
case, there are two light switches for the inputs and a light globe representing the output.
Something called a truth table can be used to describe an OR GATE’s various input and ouput results. It looks like this:
| The OR Truth Table | ||
|---|---|---|
| input 1 | input 2 | output |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
From two possible input values, 1 or 0, you can have four possible input combinations. The output of an
OR GATE is always ONE or TRUE etc as long as at least one of the imputs is 1. You can see this from the
table.
Getting back to our lights and switches, lets look at another wiring scheme. Imagine a wire with two switches on it. One switch follows the other and there is a lamp at the end. The lamp then connects back to a battery.
Which switch(s) need(s) to be ‘on’ for power to light the lamp? Of course, the answer is both. If either switch is off(or it could be an input value of 0 remember) the lamp will not be able to receive power from the battery(ouput of 0). So, the first switch AND the second switch must be on/closed/input of 1 for any output/lit lamp/TRUE. This gate is of course the AND GATE. Below, is the AND GATE’s truth table for your viewing pleasure:
| The AND Truth Table | ||
|---|---|---|
| input 1 | input 2 | output |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Once again, the AND GATE may have two or more inputs and one output. In an AND GATE arrangement, all the inputs must be 1/voltage/TRUE for there to be any output.
What has this got to do with a machine being able to add numbers you ask? Well, machines cannot add numbers! Machines don’t consider numbers or anything else. BUT… Machines can respond to mechanical signals, and electronic machines like a computer can respond to electronic signals. Inside a CPU and all over the motherboard, voltages are constantly flying around. It is a common mis-conception that zero volts is considered FALSE or ZERO and 5 volts is considered TRUE or ONE. Computers actually work with
threshold voltages. This means there are cut off points where a meaning is implied. For instance, anything below say .2 volts is considered OFF/ZERO/FALSE; or anything above say, 3.2volts, is considered TRUE/ON/ONE etc. The only catch is that certain components inside the computer operate at different threshhold levels! This is overcome by using amplifiers to interface modules that differ in threshhold ratings.
I’ve gotten a bit off track there. Back to our GATES. By the way, the correct name for these GATES is LOGIC GATES. Imagine a bank of three lamps. We can say that the three lamps can represent a three bit binary number. Note that people
are the ones who interpret what the meanings of a pattern of bits are. This is a vital point to note. If we interpret the three lamps as binary digits, we would call the ‘bit’ on the right the LEAST SIGNIFICANT BIT
or LSB and the ‘bit’ on the left the MOST SIGNIFICANT BIT or MSB. The bit in the middle doesn’t get a
special moniker! Well, the bit/lamp in the middle of three would be called bit one. The numbering starts at the right at zero. Using only the on/off quality of the lamps, we can make 8 different codes and then map those codes to numbers. We chose to interpret the lamp codes as numbers. Here is a table of the code:
| Lamps as codes! | |||
|---|---|---|---|
| lamp2(MSB) | lamp1 | lamp0(LSB) | numeric value(Decimal) |
| Off | Off | Off | 0 |
| Off | Off | On | 1 |
| Off | On | Off | 2 |
| Off | On | On | 3 |
| On | Off | Off | 4 |
| On | Off | On | 5 |
| On | On | Off | 6 |
| On | On | On | 7 |
Using the above table, we can set our bank of lights to any number between 0 and 7. Now, to save me some nasty HTML table work, just trust me that adding one more light to our existing three will allow us to increase the combinations by 2. Thus, we could have 16 combinations if we introduced a four lamp panel. The combinations could be mapped to the numerals from 0 to 15. And, you guessed it, this pattern continues ad-infinitum.
That is how electricity thresholds can be used to store and manipulate data! Simple eh? You’ve heard of a byte, well a byte has eight bits. It’s just like a bank of eight lamps, but instead of lamps, we have voltage thresholds that we humans map to numbers. Think about that for a minute, then move on to the good stuff.
I still haven’t explained how machines manipulate those bytes to produce the addition of numbers… Well, let’s start small and work our way up.
Think back to our LOGIC GATES. The secret to machines being able to add numbers is in those gates and it starts with the OR GATE. The OR GATE is the addition operator between two bits! Think about it. If you have an OR GATE that has two bits as input, the output of that OR GATE is the sum of the two inputs. Ah…… Not so I here you scream. The OR GATE will lose one of the input bits if there are two of them. Did I lose you?! Think of the TRUTH TABLE, or better yet, refer to it above.
Let’s imagine you wish to add 0 and 1. Having those two values as the input to an OR GATE will give the output of 1, which is correct! But… If we are trying to input two 1’s into the OR GATE, the output is ONE!!! Wrong answer…
(Please note that I use 1 to represent anything above the threshhold voltage and 0 for below it. You can imagine what I’m describing as a real light switch, a bit in a computer or a fantasy world re-enactment…! To us, they may as well be the same.). And in our code, there is no provision to have a ‘2’ in one of the columns! Our code can only be made of 1’s or 0’s or on lamps or off lamps! There is no doubly bright lamp to represent the number 2 in a column, and it wouldn’t make sense anyway…
“Quite the conundrum.”
All is not lost, we just have to ask the AND GATE if it can help us out. You see, binary numbers behave the same way as decimal numbers. It’s like magic really. In decimal, we have symbols that we map to real life amounts. The symbols range from 0 through 9.
Using these 10 symbols, we can represent any amount of things. The key to this representation lies in how we display those numeric symbols.
(If this is starting to put you to sleep, trust me, it gets very interesting, very soon!)
We arrange our symbols/numerals into columns and each column has a ‘weight’ associated with it. The rightmost column has the units weight. We multiply any symbols in that column by 1. Moving left, we have the ‘tens’ and then the hundreds and so on. Each column can display all the numerals from 0 to 9, but when a column ticks over past 9, we have a carry over into the next column. This happens every ten ticks for each column. It’s exactly the same principle in binary notation, with a different amount of ‘ticks’. There are only two symbols in binary, 0 and 1. And remember, we can map those values to anything we like, including the reading of voltages above and below certain thresholds.
To count in binary notation, you start as with decimal, at zero. Then comes one, then… Then, we carry over to the next column and leave a zero in the first column.
0000 00
0001 01
0010 02
0011 03
0100 04
0101 05
0110 06
0111 07
1000 08
1001 09
1010 10
1011 11
1100 12
1101 13
1110 14
1111 15Now here’s an idea! What if we attach an AND GATE plus an OR GATE to the inputs and run ’em side by side??? Remember that the AND GATE only gives an output of 1 if all inputs are 1? And in binary, what happens if you have to represent 2 bits in the same column? Nothing. It’s not possible. You have to carry a bit to the next column and leave what’s left.
This is the setup we now have. We have two inputs, both going to an OR GATE and an AND GATE. Whatever comes out of the OR GATE is the result of the addition. Whatever comes out of the AND GATE is the carry! We now have a machine that can add two binary digits together and arrive at the correct answer. Here is a run down of what will happen.
Let’s say, we wish to add together 1 and 0. Our sum will look like this:
1 + 0 = ?To get the machine to do this, we put the two inputs through it like this:
INPUT #1(1)----------->|INPUT #1
| |OR GATE -----> 1
INPUT #2 | (0)------->|INPUT #2
| |
| |
| |
| ------>|INPUT #2
| |AND GATE -----> 0
----------->|INPUT #1Sorry if that looks really confusing, but it is just supposed to represent that we send both inputs through both the AND GATE and the OR GATE at the same time. It’s not very useful in this form though. What we would really like is to send the output from the AND GATE into the next ‘column’ to show that a carry was produced. Remember, this will only be the case if both inputs were 1’s. There is another problem with our little machine, but we should understand something important first.
What we are trying to achieve here is a machine that can add a bank of binary digits or bits to another bank of bits. Particularly a bank of 8 bits! The above diagram describes a single column from that bank. To make a machine that can add eight bits to eight other bits, you would need eight OR GATES and eight AND GATES connected as shown above. The output from the AND GATE in each column will be sent to the input of the AND GATE/OR GATE arrangement to it’s left to effect the carry. This way, the carry can be part of the equation also, and we’ll examine that soon. For now, let’s look at the major flaw in my circuitry!
If we run another set of bits though the wonderful electric adding machine, we will discover that it gives incorrect results.
Why? Consider the follow sum:
1 + 0 = ?To get the machine to do this, we put the two inputs through it like this:
INPUT #1(1)----------->|INPUT #1
| |OR GATE -----> 1
INPUT #2 | (1)------->|INPUT #2
| |
| |
| |
| ------>|INPUT #2
| |AND GATE -----> 1
----------->|INPUT #1Can you see the error? It’s in the OR GATE. When we add binary 1 with binary 1 we should carry a one over to the left and leave 0 in the original column. We are doubling up on work here. The OR GATE is actually telling us about the carry also, but it’s output stays in the column. What we need is an OR GATE that only outputs a one if one or the other inputs is a 1.
This can be done, but first we need another type of gate called the NOT GATE. The NOT GATE only accepts one input and gives one output. Whatever you input is output as the opposite value. If you input 1, you’ll get the output of 0 and vice-versa.
We will use the NOT GATE to build something called an EXCLUSIVE OR GATE. The EXCLUSIVE OR GATE or XOR GATE is very important as you may now realise! Here is it’s truth table:
| The XOR Truth Table | ||
|---|---|---|
| input 1 | input 2 | output |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Only when the inputs are different will we see an output from this gate. How can we build one using
an AND GATE, OR GATE and a NOT GATE? We use the truth table and place gates to correspond to the
results we want. For inputs of (1)(1), we want an output of 0. For either (1)(0) and (0)(1) we need
an output of 1. Let’s put two AND GATES side by side:
INPUT1
AND
INPUT2
INPUT1
AND
INPUT2
INPUT1|--------------IN1
| AND1-----IN1
---+--------NOT1--IN2 OR------------->OUTPUT
| | ---IN2
| | |
| NOT2----IN1 |
| AND2----------
INPUT2--------IN2This amazing contraption(!) is my own design based on a sketchy memory of one I saw a long time ago! Let’s test it with some sums:
1 XOR(mine) 0 = 1(trace through the above diagram to find the answer(I know it's a bad diagram!))
1 XOR 1 = 0
0 XOR 1 = 1
0 XOR 0 = 0The two inputs are split into four, two for each input. One branch of the the split input is sent to an AND GATE unchanged, but the other branch is inverted and sent to the other AND GATE. This means that the two split portions of the input can never be the same as each other. Using the logic of the AND GATE, we see that only when the inputs are different can we see an output. If the inputs are both 1, they will cancel each other out! That’s exactly what we want. Also, the OR GATE at the end there is a way to tie the double output to one output. An OR GATE can never show less than what is input to it. The OR GATE is saying, “I don’t care which AND GATE produced an output, either is good enough for me!”. What a nice OR GATE. We also cover the event of both inputs being zero. This would mean that a zero and a one are sent to each AND GATE, and we know that AND GATEs need all inputs to be 1 before they give an output of 1.
We can hide the implementation of the XOR GATE because we know how it works. Let’s place it back into the original adding machine and check the results.
INPUT #1(1)----------->|INPUT #1
| |XOR GATE -----> 0
INPUT #2 | (1)------->|INPUT #2
| |
| |
| |
| ------>|INPUT #2
| |AND GATE -----> 1
----------->|INPUT #1Fingers crossed… SUCCESS!Fingers crossed… SUCCESS!
Let’s do some programming now. I want to show you these gates in action. We’ll be doing some C++ code, and I must warn you, I am a novice C programmer who doesn’t use C++ very much. But, like all good things, practice makes better. The program I am going to write will simulate the four gates (OR, AND, NOT and XOR) we have been looking at. We can then put them to the test in a software version of a real adding machine. (Consider the irony of what we are doing…)
We can then give the adding machine eight bits at a time and let it add ’em together. Go and make a nice drink of something, I’m going to write the code now and de-bug it etc. It may take a while… I’ll yell out when I’ve got it working.
#include
using namespace std;
typedef unsigned short int USI;
//class declarations
class OR{
public:
OR(){}; //OR's default constructor
~OR(){}; //Nothing to release - empty destructor
USI ShowOutput(USI in1, USI in2);
};
class AND{
public:
AND(){}; //AND's default constructor
~AND(){}; //Nothing to release - empty destructor
USI ShowOutput(USI in1, USI in2);
};
class NOT{
public:
NOT(){};
~NOT(){};
USI ShowOutput(USI in1){
return !(in1);
}
};
int main(int argc, char* argv[]){
OR or1;
AND and1;
cout << or1.ShowOutput(0,0) << endl;
cout << or1.ShowOutput(0,1) << endl;
cout << or1.ShowOutput(1,0) << endl;
cout << or1.ShowOutput(1,1) << endl;
return 0;
}
//class definitions
USI OR::ShowOutput(USI in1, USI in2){
return in1|in2;
}
USI AND::ShowOutput(USI in1, USI in2){
return in1 & in2;
}PROGRAM OUTPUT:
0
1
1
1
This simple program uses C/C++’s BITWISE operators to perform the logic. This version is really
just a rudimentary test to see that all is going smoothly. And it seems to be. Just to make sure, I want to expand a bit on the single method of each class. Let’s make them more PR savvy.
#include
#include
using namespace std;
typedef unsigned short int USI;
//class declarations
class OR{
public:
OR(){};
OR(string nme); //OR's default constructor
~OR(){}; //Nothing to release - empty destructor
USI ShowOutput(USI in1, USI in2);
private:
string m_name;
};
class AND{
public:
AND(){};
AND(string nme); //AND's default constructor
~AND(){}; //Nothing to release - empty destructor
USI ShowOutput(USI in1, USI in2);
private:
string m_name;
};
class NOT{
public:
NOT(){};
NOT(string name);
~NOT(){};
USI ShowOutput(USI in1){
cout << endl << this->m_name << " performing NOT on " << in1 << " = ";
return !(in1);
}
private:
string m_name;
};
//main
int main(int argc, char* argv[]){
int i;
cout << "
The inputs given are: ";
for(i = 0; i < argc -1; i++){
cout << atoi(argv[i+1]) << " ";
}
cout << endl;
OR or1("Or1");
AND and1("And1");
NOT not1("Not1");
cout << or1.ShowOutput((USI)atoi(argv[1]),(USI)atoi(argv[2]));
cout << and1.ShowOutput((USI)atoi(argv[1]),(USI)atoi(argv[2]));
cout << and1.ShowOutput(or1.ShowOutput((USI)atoi(argv[1]),(USI)atoi(argv[2])),
or1.ShowOutput((USI)atoi(argv[1]),(USI)atoi(argv[2])));
cout << not1.ShowOutput(1);
cout << not1.ShowOutput(0);
return 0;
}
//class definitions
OR::OR(string nme){
m_name = nme;
}
USI OR::ShowOutput(USI in1, USI in2){
cout << endl << this->m_name << " performing " << in1 << " OR " << in2 << " = ";
return in1|in2;
}
USI AND::ShowOutput(USI in1, USI in2){
cout << endl << this->m_name << " performing " << in1 << " AND " << in2 << " = ";
return in1 & in2;
}
AND::AND(string nme){
m_name = nme;
}
NOT::NOT(string nme){
m_name = nme;
}PROGRAM OUTPUT WHEN CALLED WITH - c:???>gates2 1 0
The inputs given are: 1 0
Or1 performing 1 OR 0 = 1
And1 performing 1 AND 0 = 0
Or1 performing 1 OR 0 =
Or1 performing 1 OR 0 =
And1 performing 1 AND 1 = 1
Not1 performing NOT on 1 = 0
Not1 performing NOT on 0 = 1Now the classes provide some info about what they are doing, and I also made provisions to allow us to give the inputs at the command line. This can be handy for rapid evaluation of various parameters. I generalised this so that more than two inputs can be used, incase that’s a future requirement. Also notice that I have sent as function parameters an object that’s calling one of it’s methods. This works because the method returns an appropriate type to use for the parameter. Also note that where those two calls are made, the actual output is not displayed. Do you know why?
It’s because the output is returned to main() to be displayed.
There is nowhere in main() that calls for these two returned
values to be displayed, so we have a blank.
This does not affect us, so let’s just ignore it!
This is how I will implement the fourth gate we have studied. The XOR GATE.
To construct the XOR GATE, we need to refer to the diagram above and translate that into C++ code…GROAN. Once we get this working, we’ll be able to build our adding machine, then we’ll leave gates for good. It’s important to know about them, but it’s essentially useless information. You will never work at such a low level. The transistors that make up these gates are microscopic and there are hundreds of millions of them inside most home computers. It’s enough to know that the gates work, then, we can build on that knowledge without worrying about how they work. I already did that with the XOR above.
Going by the poor excuse for a schematic diagram, we can work out how to place our inputs/outputs and objects to simulate the circuit. We will need two NOT GATEs, two AND GATES and an OR GATE.
NOT not1("Not1"), not2("Not2");
AND and1("And1"), and2("And2");
OR or1("Or1");The two AND GATEs receive their input from a NOTed input and a normal input. The output from this process is given to the lone OR GATE and it’s this output that we want.
or1.ShowOutput(
and1.ShowOutput(not1.ShowOutput(atoi(argv[1])),atoi(argv[2])),
and2.ShowOutput(not2.ShowOutput(atoi(argv[2])),atoi(argv[1])));Wow! That’s a MESS… But it should work! Here is the code:
#include
#include
using namespace std;
typedef unsigned short int USI;
//class declarations
class OR{
public:
OR(){};
OR(string nme); //OR's default constructor
~OR(){}; //Nothing to release - empty destructor
USI ShowOutput(USI in1, USI in2);
private:
string m_name;
};
class AND{
public:
AND(){};
AND(string nme); //AND's default constructor
~AND(){}; //Nothing to release - empty destructor
USI ShowOutput(USI in1, USI in2);
private:
string m_name;
};
class NOT{
public:
NOT(){};
NOT(string name);
~NOT(){};
USI ShowOutput(USI in1){
//cout << endl << this->m_name << " performing NOT on " << in1 << " = ";
return !(in1);
}
private:
string m_name;
};
//main
int main(int argc, char* argv[]){
int i;
cout << "
The inputs given are: ";
for(i = 0; i < argc -1; i++){
cout << atoi(argv[i+1]) << " ";
}
cout << endl;
OR or1("Or1");
AND and1("And1"), and2("And2");
NOT not1("Not1"), not2("Not2");
cout << "
The XOR result is: " << or1.ShowOutput(
and1.ShowOutput(not1.ShowOutput(atoi(argv[1])),atoi(argv[2])),
and2.ShowOutput(not2.ShowOutput(atoi(argv[2])),atoi(argv[1])));
return 0;
}
//class definitions
OR::OR(string nme){
m_name = nme;
}
USI OR::ShowOutput(USI in1, USI in2){
//cout << endl << this->m_name << " performing " << in1 << " OR " << in2 << " = ";
return in1|in2;
}
USI AND::ShowOutput(USI in1, USI in2){
//cout << endl << this->m_name << " performing " << in1 << " AND " << in2 << " = ";
return in1 & in2;
}
AND::AND(string nme){
m_name = nme;
}
NOT::NOT(string nme){
m_name = nme;
}PROGRAM OUTPUT WHEN CALLED WITH - c:???>gates3 1 0
The inputs given are: 1 0
The XOR result is: 1
PROGRAM OUTPUT WHEN CALLED WITH - c:???>gates3 1 1
The inputs given are: 1 1
The XOR result is: 0
PROGRAM OUTPUT WHEN CALLED WITH - c:???>gates3 0 1
The inputs given are: 0 1
The XOR result is: 1
PROGRAM OUTPUT WHEN CALLED WITH - c:???>gates3 0 0
The inputs given are: 0 0
The XOR result is: 0I commented out the cout in the objects to make the output clearer. And you can see
that we are getting the exact results we are after. We can wrap the XOR GATE code and
use it without worrying about how it works. I didn’t mention it before, but there is
a C/C++ bitwise operator that performs XOR operations. It’s the ‘^’ or carat.
We are ready to build our adding machine!
(Page 6 made this document too large! click here to jump to page 6.)
We can cheat a little bit if we want. We could just use the ‘^’ operator instead of the code
we wrote for the XOR GATE. But let’s not. Let’s wrap up the code and place it in the ‘guts’ of
a new class called XOR. Once we have this class, we will continue on and arrange the XOR and the
other GATES into an adding machine and test it. Here is where the generalised command line argument
handling will save us a little bit of work. It can accept any number of inputs and present their
values to us for reference.
I have just decided that instead of ‘hard coding’ our GATEs into some construct within main(), I will
build a new class called “ADDER” that contains the gates as members. ADDER can accept an array as an
argument and work with any number of inputs we like. In actual fact, we present adder with both binary
numbers from the command line. ADDER can split the array in half to find the two operands.
To keep ADDER’s code a little bit cleaner, it will have a more powerful constructor that initialises the
‘machinery’. We want to hide all the mess of constructing the machine so we can test our GATES clearly.
Here is the code to implement the XOR GATE as a seperate class:
#include<iostream>
#include<string>
using namespace std;
typedef unsigned short int USI;
//class declarations
class OR{
public:
OR(){};
OR(string nme); //OR's default constructor
~OR(){}; //Nothing to release - empty destructor
USI Do(USI in1, USI in2);
private:
string m_name;
};
class AND{
public:
AND(){};
AND(string nme); //AND's default constructor
~AND(){}; //Nothing to release - empty destructor
USI Do(USI in1, USI in2);
private:
string m_name;
};
class NOT{
public:
NOT(){};
NOT(string name);
~NOT(){};
USI Do(USI in1){
//cout << endl << this->m_name << " performing NOT on " << in1 << " = ";
return !(in1);
}
private:
string m_name;
};
class XOR{
public:
XOR(){}
XOR(string nme);
~XOR(){};
USI OP(USI in1, USI in2);
private:
AND m_and;
OR m_or;
NOT m_not;
string m_name;
};
//main
int main(int argc, char* argv[]){
int i;
cout << "
The inputs given are: ";
for(i = 0; i < argc -1; i++){
cout << atoi(argv[i+1]) << " ";
}
XOR x1("Nick");
USI res = 0;
res = x1.OP((USI)atoi(argv[1]),(USI)atoi(argv[2])) ;
cout << "
the results of XORing them are " << res << "
";
return 0;
}
//class definitions
OR::OR(string nme){
m_name = nme;
}
USI OR::Do(USI in1, USI in2){
//cout << endl << this->m_name << " performing " << in1 << " OR " << in2 << " = ";
return in1|in2;
}
USI AND::Do(USI in1, USI in2){
//cout << endl << this->m_name << " performing " << in1 << " AND " << in2 << " = ";
return in1 & in2;
}
AND::AND(string nme){
m_name = nme;
}
NOT::NOT(string nme){
m_name = nme;
}
XOR::XOR(string nme){
m_name = nme;
}
USI XOR::OP(USI in1, USI in2){
USI output = 0;
output = this->m_or.Do(this->m_and.Do(in1, this->m_not.Do(in2) ),//first input
this->m_and.Do(in2, this->m_not.Do(in1)));//second input!
return output;
}I have altered the other classes slightly, namely the method names. The XOR class ‘knows’ how to use AND, OR and NOT GATEs because they are used in it’s construction! It’s now easy to perform an XOR operation on any inputs. In main(), to test the new class, I just wrote some simple driver code. The output from some tests was as folows:
PROGRAM OUTPUT:
C:???>adder1 1 0 <ENTER;>
The inputs given are: 1 0
the results of XORing them are 1
C:???>adder1 1 1 <ENTER;>
The inputs given are: 1 1
the results of XORing them are 0
C:???>adder1 0 0 <ENTER;>
The inputs given are: 0 0
the results of XORing them are 0Hey presto! All that’s left now is to decide on how to implement the adder machine in code. My first thought is to build an adder class. The adder objects will accept two inputs and have possible outputs from their XOR section and their AND section. A few points need to be understood before we can start coding. It’s all very well and good to have a machine that can add two binary numbers together, and even carry any overflow to the next column! But, the carrying itself presents a new menace to out machine. Consider what will actually happen during a normal addition of two binary numbers.
10100010
+
11100011
=
10000101 with the MSB discarded.Let’s go through that calculation bit by bit starting, as with any type of number, from the right digits. 1 + 0 in binary is 1= , as it is in decimal also. That’s ok, move on to the next one. 1 + 1 in binary is 10b (a ‘b’ appended to a number signals binary notation) or 2 in decimal. We can’t fit 10b into the first column, so we place a 0 there and we have a carry. 0 + 0 + carry = 1. Next column, 0 + 0 = 0. Same for the next column, 0 + 0 = 0.
Now another 1 + 1 = 0 with a carry. This makes the sum 1 + 0 + carry = 0 with a carry. The
last sum is 1 + 1 + carry = 1 with a carry!
I’m starting to dread coding this one! We will need to employ some clever GATE set ups. Now, we should take a step back and consider what we are trying to achieve and what tools we have at our disposal.
We are trying to build an adding machine that can take two 8 bit binary numbers and give the sum of them both. Earlier, I said that the adding machine simply gives any carries to the next 1bit adder to it’s left. This is ok, but we have to be very careful from here on in! The first bits (bits 0 or LSBs) in our sum are the only ones that can be treated in this simple fashion. All the following bits need more complex circuitry to achieve the correct outputs. Why???
Consider what will happen when we need to add 1 and 1 and a carry. The correct answer is 1 with a carry passed on.
The way to achieve the correct functioning is to handle the input of the carry with more gates!
Each ADDER object in the line of eight has two possible outputs from two operands that are
given to it. The XOR GATE of the ADDER object reflects an addition of the two operands and the AND GATE reflects a carry to be sent to the next most significant bit in the bank of 8. An important fact to realise here is that there can only ever be one carry passed from any addition of single bit values. We will never have the problem of carry bits building up as we move from right to left. It’s actually the same for decimal. The most that is ever passed to the left in an addition operation is a 1 numeral of the next power! 999 + 999 still only makes one unit of carry.
Knowing this, we can start to think about what must happen, gate wise, when carries are encountered. We know that we must add any carries to the current sum. So, to do a binary addition, we use an XOR GATE. We don’t want two carries, so we send the first XOR output that does the initial addition to an OR along with the output from the AND that tests for a carry. This covers us, and the output from that OR becomes the new carry! Also, we need to XOR the carry in with the output of the initial addition XOR. I’ll now run through what needs to be done, then we can code it.
- LSB(No CarryIn) – XOR both operands and place result in output
- AND Both operands and send this to BIT1’s CarryIn.
- BIT1 – XOR both inputs and send output to XOR2 along with the CarryIn. Send result from XOR2 to ouput and to OR1.
- Send the output of AND also to OR1.
- The output of OR1 is the new CarryOut value going to the next bit’s CarryIn.
- BIT2 – XOR both operands send output to XOR2 along with the CarryIn. Send result from XOR2 to ouput and to OR1.
- Send the output of AND also to OR1.
- The output of OR1 is the new CarryOut value going to the next bit’s CarryIn.
etc etc…
Can you see how it will work? Try drawing a picture of it, as I can’t provide drawings here…
Basically, if there is a carry in and results of the main addition produce a carry, we only send one carry out to the next bit. We only XOR the CarryIn with the result of the main addition XOR to arrive at zero if both are 1 or 1 if either is one and the other is 0. Phew. Let’s design some code for this machine…!
You can design yours any way you wish of course, but I have chosen to build mine as a hard coded 8bit adder. This is a simpler way of doing it. Working with logic gates is, really, a waste of time. It’s not a waste of time learning about them and seeing how they work, but we now know these things, and we can move on to the next stage of my tutorial that will focus on computer hardware and how it works. My point is, you would never get anything done if you had to worry about the gates inside the CPU! But it’s nice to know that they are there. Anyway, we should think about the design for the 8bit adder.
I will use a class of adder that works with one bit at a time. Then, I can arrange them to send relative inputs/outputs to the next bit in line. The class should have a method that accepts three inputs(A, B and Carry). There should also be a method for providing output so we can send any carryOuts to the next column/bit. Finally, each one bit adder should be able to display it’s own output value.
The inputs will be provided from the command line and using a helper function, converted into USI (Usigned Short Int. A typedef)arrays. Just to re-cap, I’ll make a class that does the 8 bit adding using eight 1bit adders.
#include<iostream>
#include<string>
using namespace std;
typedef unsigned short int USI;
void Addend_Init(int args, char** theAddend, USI arr[]);
//class declarations
class OR{
public:
OR(){};
OR(string nme); //OR's default constructor
~OR(){}; //Nothing to release - empty destructor
USI Do(USI in1, USI in2);
private:
string m_name;
};
class AND{
public:
AND(){};
AND(string nme); //AND's default constructor
~AND(){}; //Nothing to release - empty destructor
USI Do(USI in1, USI in2);
private:
string m_name;
};
class NOT{
public:
NOT(){};
NOT(string name);
~NOT(){};
USI Do(USI in1){
//cout << endl << this->m_name << " performing NOT on " << in1 << " = ";
return !(in1);
}
private:
string m_name;
};
class XOR{
public:
XOR(){}
XOR(string nme);
~XOR(){};
USI OP(USI in1, USI in2);
private:
AND m_and;
OR m_or;
NOT m_not;
string m_name;
};
class ADDER{
public:
ADDER(){}
ADDER(string nme);
void DoAdder(USI in1, USI in2);
USI GetAnd();
USI GetXor();
private:
USI m_and_output;
USI m_xor_output;
AND m_and;
XOR m_xor;
string m_name;
};
class ADDER8{
public:
void DoBitAdd(USI A, USI B, USI CarryIn = 0); //note the default value to cover the LSB.
void SetOutput(USI a){ m_output = a; }
void SetCarryOut(USI a){ m_carry_out = a; }
USI GetOutput(){ return m_output; }
USI GetCarryOut(){ return m_carry_out; };
private:
USI m_output;
USI m_carry_out;
ADDER m_adder;
OR m_or;
XOR m_xor;
AND m_and;
};
//main
int main(int argc, char* argv[]){
int i;
cout << "
The inputs given are: ";
for(i = 0; i < argc -1; i++){
cout << atoi(argv[i+1]) << " ";
}
int args = argc/2;
USI addend1[8];
USI addend2[8];
Addend_Init(args, argv, addend1);
Addend_Init(args, argv+8, addend2);
cout << "
The two addends are:
Addend1: ";
for(i = 0; i < args; i++){
cout << addend1[i];
}
cout << "
Addend2: ";
for(i = 0; i < args; i++){
cout << addend2[i];
}
//make eight ADDER8 objects and put 'em through their paces!
ADDER8 add0, add1, add2, add3, add4, add5, add6, add7;
//it's now a simple case of presenting each ADDER8 object with
//the two input addends, and the carryin from the last adder8 object
//which is actually that object's m_carry out.
add0.DoBitAdd(addend1[7], addend2[7], 0);
add1.DoBitAdd(addend1[6], addend2[6], add0.GetCarryOut());
add2.DoBitAdd(addend1[5], addend2[5], add1.GetCarryOut());
add3.DoBitAdd(addend1[4], addend2[4], add2.GetCarryOut());
add4.DoBitAdd(addend1[3], addend2[3], add3.GetCarryOut());
add5.DoBitAdd(addend1[2], addend2[2], add4.GetCarryOut());
add6.DoBitAdd(addend1[1], addend2[1], add5.GetCarryOut());
add7.DoBitAdd(addend1[0], addend2[0], add6.GetCarryOut());
cout << "
Output : ";
cout << add7.GetOutput();
cout << add6.GetOutput();
cout << add5.GetOutput();
cout << add4.GetOutput();
cout << add3.GetOutput();
cout << add2.GetOutput();
cout << add1.GetOutput();
cout << add0.GetOutput() << "
";
return 0;
}
void Addend_Init(int args, char* theAddend[], USI addend[]){
int i;
for(i = 0; i < args; i++){
addend[i] = (USI)atoi(theAddend[i+1]);
}
}
//class definitions
OR::OR(string nme){
m_name = nme;
}
USI OR::Do(USI in1, USI in2){
//cout << endl << this->m_name << " performing " << in1 << " OR " << in2 << " = ";
return in1|in2;
}
USI AND::Do(USI in1, USI in2){
//cout << endl << this->m_name << " performing " << in1 << " AND " << in2 << " = ";
return in1 & in2;
}
AND::AND(string nme){
m_name = nme;
}
NOT::NOT(string nme){
m_name = nme;
}
XOR::XOR(string nme){
m_name = nme;
}
USI XOR::OP(USI in1, USI in2){
USI output = 0;
output = this->m_or.Do(this->m_and.Do(in1, this->m_not.Do(in2) ),//first input
this->m_and.Do(in2, this->m_not.Do(in1)));//second input!
return output;
}
ADDER::ADDER(string nme){
m_name = nme;
}
void ADDER::DoAdder(USI in1, USI in2){
this->m_and_output = this->m_and.Do(in1, in2);
this->m_xor_output = this->m_xor.OP(in1, in2);
}
USI ADDER::GetAnd(){
return m_and_output;
}
USI ADDER::GetXor(){
return m_xor_output;
}
void ADDER8::DoBitAdd(USI A, USI B, USI CarryIn){
//after this, the next bit can get it's inputs from this object and from the addends array.
//we have to take care of this bit's output(including the carry in) and the carry out.
USI tmp1 = 0, tmp2 = 0;
this->m_adder.DoAdder(A,B); //set the addends results. m_adder holds this data
this->SetOutput(this->m_xor.OP(this->m_adder.GetXor(),CarryIn)); //catch the overflow from
//adding the carryin to the output
//The carry out is thus...
tmp2 = this->m_or.Do(this->m_adder.GetAnd(), //the carry_out produced by this 'bit'
this->m_and.Do(this->m_adder.GetXor(),CarryIn)); //the carry in, ANDed with
//the output and the CarryIn!
this->SetCarryOut(tmp2);
cout << "
-- Carry out:" << this->GetCarryOut();
cout << "
-- Carry in :" << CarryIn;
cout << "
-- Output :" << this->GetOutput();
}PROGRAM OUTPUT:
The inputs given are: 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1
The two addends are:
Addend1: 11001010
Addend2: 11011101
-- Carry out:0
-- Carry in :0
-- Output :1
-- Carry out:0
-- Carry in :0
-- Output :1
-- Carry out:0
-- Carry in :0
-- Output :1
-- Carry out:1
-- Carry in :0
-- Output :0
-- Carry out:1
-- Carry in :1
-- Output :0
-- Carry out:0
-- Carry in :1
-- Output :1
-- Carry out:1
-- Carry in :0
-- Output :0
-- Carry out:1
-- Carry in :1
-- Output :1
Output : 10100111I have output the comings and goings of all the bits from each column to higlight what’s going on.
This code is very simple. The ADDER8 class builds on what we have built previously. The ADDER8 object has all of the gates we have built as members, plus the ADDER from the last example. The ADDER member is used as a kind of halfway step to providing the full output. Before we can output the XORed result of the two inputs, we need to XOR that result with any Carry In that may be there. This means that this particular column will hold no output if there is a carry in and also a 1 result from adding both addends. That takes care of that, but that’s not the only handling of the initial XOR of the addends. They are also sent to an AND GATE along with any Carry In that came from the previous column. That ouput is then merged, through an OR GATE, with the value of this column’s carry.
The inputs I choose were 202 and 221 in decimal. The addition of these two decimal numbers should produce 423, right? My stupid machine got it wrong!! It came up with 167… Oh dear! Back to the drawing board? Hang on a minute. I reckon my machine works fine. In fact, I reckon, if we examine the ADDER8 object we’ll find where things went wrong. Some of you may have already guessed what went wrong.
The machine is set up to accept 8 bits worth of input. It’s hard coded that way. Have a look at what the last ‘bit’ was doing. Hmm… It has a carry out! Where does that carry out go? It goes into computer hell. It’s burnt up in the cyber wasteland of the never ending for(;;) loop… No, not really. It is discarded. Our machine has no where to hold it, so it is ignored. That’s exactly what could happen in a real CPU, if you’re not careful.
This example shows conclusively that we have built an impatial machine that can add numbers based soley on switches! By the way, the highest number that you can represent with eight bits is 255. That is why we had our little problem!
To wrap up this first installment, I’d just like to make a few points about this exercise. Firstly, you may think this is just a program, and it is rather useless. Well, as a program it is! But let me assure you, if you got out some light switches and wired them up the same way we have in our code here, you would achieve the same results. You would, of course, need to flick each switch manually to input your individual bits! If you wanted to get a little bit more into this side of things, you could go and buy some real logic gates from your local electronics store. They come on a chip called an IC (intergrated circuit) and allow you to play around with what we have been discussing here. You can get these ICs with AND OR XOR and other flavours of switch, with between 4 and 12 switches on each IC. Anyway, that’s for another discussion!
My second point is that what you have seen here is not the way a real, modern computer CPU would do things. That also, is another topic. What we made would work as far as allowing a simple computer to compute the sum of two numbers, but it would be slow if you wanted to process millions on numbers one after the other. And all our machine can do is ADD. A real CPU can subtract, divide and multiply. Don’t worry though. What you have learnt is certainly valid! The same switches are used. They just use more of them and wire them up much more cleverly.
So I hope this was an enjoyable and informative read. I will now start work on the next section, and it will be ready ASAP. The next section will be a look at computer hardware and how to emulate our own computer with software. Yes… It’ll be quite involving, but fun!
