Brew Your Own Computer

By David Phillips

July 12, 2009

What is a computer?  How does it work?  Just a bunch of 1’s and 0’s right?  How does a computer know what a 1 or a 0 is?  Is it magic?

No, it is certainly not magic.

Today, I am going to design and build a simple computing device.  We can call this device a “computer” since it is going to perform simple computations and operations. 

To keep, it simple, my computer is going to add and subtract numbers.  For example, we’ll have it compute the result of 7 + 5, but note that I am going to leave hardware specifics like circuitry and implementation of logic gates to the Electrical and Computer Engineering domains.  I am going to treat the hardware as a black box in order to keep the scope of this limited to where the Computer Scientist is interested.  If you want to learn more about the implementation of hardware, check out a book on Computer Architecture.

Ok, here we go!

In order for my computer to operate on numbers, I need a way of representing and number and a means of storing it somewhere.  How does a computer know what a number is?  Sadly to say, a computer is not very smart; it has no idea what a number is.  How can this be?  Well, a computer is really nothing more than an elaborate switching mechanism that can channel electrical signals in an intelligent way.  Humans can then instruct the computer how to channel the signals by supplying it with a series of instructions called a “computer program”.

So let’s start simple.  I need to find a way to represent a number.  I am going to start with a switch that can be turned to either the “ON” or “OFF” position.  This can be modeled in computer hardware as a circuit that either has voltage (on) or has no voltage (off).  We’ll just stay naďve and think of this from the context of a switch that can be turned on and off.

You don’t seem all that impressed with my computer… Ok, well this is my first step.  My computer has a switch which I can turn on and off.  My computer is now capable of storing and representing a number!  You can’t see it?  Sure, if I flip the switch to the “ON” position then we’ll say the value of the number is “1” and if I switch the value of the number to “OFF” then the value of the number is “0”.  This is the simplest piece of information that my computer can store – let’s call it a “binary digit” or “bit” for short.

You still don’t seem all that impressed.  What good is a computer that can only store a 0 or a 1?  Not much.  In order to do some useful computation, we definitely need to be able to represent more numbers than just 0 and 1.  So let’s just add more switches!  Instead of just one switch, let’s install a panel of 8 switches and call it a single “byte register”:

Cool!  So now I have something useful to play around with.  The first question that I have to ask myself is how many different combinations of “ON” “OFF” can I create with my register?  Suppose I only had a 2-bit register, then all possible combinations would be:

            OFF, OFF

            OFF, ON

            ON,  OFF

            ON,  ON

            Or in binary

            0, 0

            0, 1

            1, 0

            1, 1

This problem comes down to calculating the total number of permutations of a bit pattern.  A permutation is just a fancy word for “combination”. 

Skipping the math and keeping this fun, just believe me that the answer is 2 ^ 8 = 256.  If I have a register with 8 switches then there are 256 unique ways for me to flip those switches around.  This means that my 8-bit register can store 256 different numbers!  Wow, now we are getting somewhere.

I want to keep my computer simple so I am going to say that it is only going to use “unsigned” numbers.  We are not going to deal with negative numbers.  Since my computer is only working with unsigned numbers, my 8-bit register can store any number between 0 and 255.

If I want to store a “0” then I will set all of the switches to the off position:

If I want to store a “1” then I will flip the last switch to “ON” and leave the rest “OFF” (00000001):

If I want to store a “255” then I will flip all of the switches to “ON” (11111111):

If I want to store a “97” then I’d flip the following combination (01100001):

Timeout!  What is the logic behind this?

Ok, think of it this way.  It should be intuitive to you that to encode “0”, we set all the switches to the “OFF” position so our binary 8-bit equivalent is 00000000.  Likewise, we expect the last expressible number (255) to be represented by turning all of the switches to the “ON” position so that our binary equivalent is “11111111”.

We can therefore think of each switch as an increasing power of 2 when it is switched to the “ON” position:

So, as you can see, I calculated 97’s binary equivalent as “01100001” because:

(0 x 128) + (1 x 64) + (1 x 32) + (0 x 16) + (0 x 8) + (0 x 4) + (0 x 2) + (1 x 1)

= 0 + 64 + 32 + 0 + 0 + 0 + 0 + 1

= 97

Great! So we now know how to encode numbers into a binary format by flipping the switches inside of our register into various combinations.

So now getting back to building our computer – If I want to add and subtract numbers then my computer will need to be able to operate on multiple numbers at once.  So let’s give our computer three registers.  We will use two of these registers to store the operands and we will use the third register to store the results of our operations:

So my computer now has three registers for storing numbers but it can’t do much else.  We need a piece of hardware that can look at the state of the registers, perform binary arithmetic, and produce an output.  We’ll call this piece of hardware the “Arithmetic and Logic Unit” and connect it to the registers with some circuitry.

Great!  So we now have three registers to store some numbers and we also have an ALU that will take two input numbers and produce a single output number.  Again, we are treating the ALU as a black-box that implements the binary arithmetic in hardware.  If you want to learn how arithmetic is implemented in hardware, check out a computer architecture book.

So then the next question we ask is – How do we make our computer do something useful?  We need a way to drive the thing.  I want to drive it by giving it an instruction such as “Add the values in register 1 and register 2”.  I have to give my computer a way to accept instructions.  But what is an instruction?  The only thing that my computer is able to do is operate on numbers.  It looks like I am going to have to represent my instructions as numbers then.  Suppose we let the number “0” mean “ADD” and let the number “1” mean subtract.  Sure, that would work.  We’ll codify this as our computer’s “Instruction Set”:

So I have now found a way to drive the computer by giving it instructions that can be distinguished via the instruction’s operation code.  Let’s be lazy and refer to “operation code” as “opcode” from now on.

My computer is going to need another register to store these instructions that I give it, as well as some decode and execution circuitry to parse the opcodes, flip the switches in the registers, feed the inputs to the ALU, and write the output from the ALU to the result register:

Now we are starting to get somewhere.  Our computer is all set to start doing some useful work, but the instruction set is not completely defined yet.  If I want to do some addition, simply sending opcode “0” to the execution unit does not tell the computer which numbers are supposed to be added.  What if I want to add the value in register 1 to the value in register 1?  What if I want to add the value in register 1 to the value in register 2?

I need a way to specify this information to the execution unit.  I can easily do this by partitioning the bits in the instruction.  My instruction register has 8 switches (bits).  I certainly do not need all 8 bits to encode the opcode.  So I will design my instruction set to only use the first two bits to encode the instruction’s opcode.  The remaining bits can then be used to encode the operation parameters.

Perfect, so we’ll design our instruction set to specify that all instructions will use bits 1 and 2 to specify the opcode and the remaining bits can be used to specify the parameters in whatever way each individual instruction requires. 

Let’s update our instruction set:

ADD Instruction

            Opcode                  : Bits 1 through 2

            Operand Register 1 : Bits 3 through 5

            Operand Register 2 : Bits 6 through 8

Assume the result is always stored in register 3 so that we don’t have to encode a result register in the instruction.

Subtract Instruction

            Opcode                  : Bits 1 through 2

            Operand Register 1 : Bits 3 through 5

            Operand Register 2 : Bits 6 through 8

Assume the result is always stored in register 3 so that we don’t have to encode a result register in the instruction.

Load Immediate Instruction

            Opcode                     : Bits 1 through 2

            Destination Register   : Bits 3 through 5

            Value                        : Bits 6 through 8

Since we only get 3 bits to encode our value, we can only use it to load numbers between 0 and 7.  In order to load larger numbers, we would need to change our instruction set to use multiple bytes for a single instruction.  For example purposes and to keep the instruction set simple, I am limiting all of the instruction lengths to a single byte.

Our instruction set is now updated.  We can now encode the source registers into our instructions.

If we want to load the value “5” into register 1, we just create the instruction as:

            Opcode                   : 11          (Load Immediate Opcode)

            Destination Register  :  001 (Register 1)

            Value                       :  101 (5 in binary)

Concatenate the pieces; we get a final encoded machine instruction: 11001101

If we want to add the value in register 1 to the value in register 1, we just create the instruction as:

            Opcode     : 00    (Addition opcode)

            Operand 1 : 001   (Register 1)

            Operand 2 : 001   (Register 1)

            Concatenate the pieces; we get a final encoded machine instruction: 00001001

If we want to add the value in register 1 to the value in register 2, we just create the instruction as:

            Opcode     : 00    (Addition opcode)

            Operand 1 : 001   (Register 1)

            Operand 2 : 010   (Register 2)

            Concatenate the pieces; we get a final encoded machine instruction: 00001010

If we want to subtract the value in register 1 from the value in register 1, we just create the instruction as:

            Opcode      : 01    (Subtraction opcode)

            Operand 1 : 001   (Register 1)

            Operand 2 : 001   (Register 1)

            Concatenate the pieces; we get a final encoded machine instruction: 01001001

If we want to subtract the value in register 1 from the value in register 2, we just create the instruction as:

            Opcode      : 01    (Subtraction opcode)

            Operand 1 : 001   (Register 1)

            Operand 2 : 010   (Register 2)

            Concatenate the pieces; we get a final encoded machine instruction: 01001010

As you can probably tell, programming in machine instructions is a real pain.  It’s much easier to program in a language that uses syntactical constructs of the English language that can then be translated into machine code automatically.

Let’s create a programming language for our computer called “Assembly”.  It will be considered to be a relatively low level of programming because it provides only simple instructions that correspond to machine level instructions.

We will map our ADD and SUBTRACT operations to assembly level constructs as follows:

ADD     <Operand Register>      <Operand Register>

SUB      <Operand Register>      <Operand Register>

LOADI <Destination Register> <immediate value between 0 and 7>

Great, so now it will be a lot easier to create instructions for my computer.  If I want to add the value of register 1 to the value in register 2, I can just say:

ADD $1, $2

My computer will have a program called an “Assembler” that will analyze the above instruction and translate it into the machine instruction “00001010” that we had to create by hand up above (see above).  Having this assembler makes creating the machine instructions much easier.

Now we just need a place to store our instructions that our computer can fetch them from.  We’ll add in some random access memory (R.A.M) that we’ll use to store our instructions which we call “programs”.

We now have what we need to drive our computer.  Let’s construct a program to have our computer calculate the result of “7 + 5”.

We’ll use our assembly language to generate the program:

LOADI     $1, 7     #Load the value 7 into register 1

LOADI     $2, 5     #Load the value 5 into register 2

ADD         $1, $2   #Add the values in register 1 and register 2 and store the result in register 3

Our assembler translates our program into the following 3 machine instructions:

11001111

11010101

00001010

We load our program into the computer’s memory and tell it to fetch the instructions one by one.

Our computer loads 7 and 5 into the input registers.  Our add instruction causes the ALU to read the two input registers and compute the result of 7 and 5 = 12 decimal = 00001100 binary which is then written to the result register:

Not so magic, now, is it?