## Building a CPU Part I – Implementing logic gates

For a long time now, I was thinking to myself: “I know how to develop softwares, And I also have a little bit of practice with drivers and compiling operation systems (I even tried to write my own code to a boot sector and run it), But I never really understood how CPU works”.

So I’ve decided to take matter into hands and try to build a CPU. At first I thought about creating it all from scratch, But quick enough I discovered that the amount of transistors I will have to solder is enormous (I will soon enough show that even a simple NAND gate requires 4 transistors). So I’ve decided to build it on FPGA which will make life easier, and instead of creating my own architecture, I’ve decided to try and mimic the 6502 microprocessor, which is the CPU used by NES. If everything will go according to plan, I will be able to play Super-Mario on my own CPU.

The first post will have nothing to do with FPGA, as logic gates are provided out-of-the-box when using FPGA, so this part will have nothing to do with my implementation of the 6502 microprocessor. But according to my belief this part is the most important one, because the logic gates are the basic building blocks of any electronic device, in particular a CPU.

### Boolean functions

If you are math geek, you can consider boolean functions as multivariable functions over the field .

If you don’t have any idea what I just said, imagine a function that you’ve seen in math class in high school. A function mapped any number to some number (and we denoted: ). The difference in boolean function, instead of letting be arbitrary number, we are only allowing it to have the values 0 and 1, and the same things goes for .

Moreover, we also allow the function to be multivariable, meaning that instead of providing only one input parameter , we can provide a tuple .

It is crucial to understand that functions doesn’t have to be defined by simple arithmetic, we can simply choose the output value for each input configuration manually and that will be a valid function as well.

### What is a logic gate?

A logic gate is a device that implements a boolean function.

That is, given a boolean function , the logic gate that correspond to is a device that as wires connected to it as input and wires connected to it as output. When we provide a specific input configuration to the device, the output wires will represent the output of the function given the input.

We usually represent a 0 of the boolean function by connecting the pin to the ground of the electronic device (zero voltage, as all voltage levels in an electronic device is measured in reference to the ground level), and we represent 1 by connecting it to a reference voltage different from zero, denoted by .

Confusing? Maybe few examples will help.

### NOT gate (Inverter)

The simplest gate exists is the NOT gate, which is also known as inverter. The not gate has only one input variable, and one output variable . And works as follows:

0 | 1 |

1 | 0 |

Meaning that if we will connect the input pin to the ground, the output of the inverter gate will be , and if we will provide as input we will get zero voltage at the output.

The not gate usually noted by the following symbol:

This gate seems simple, but the way to implement it using electronic devices is a little bit tricky. For once, when we give the input 0 that means that we do not give any energy to the system (the input voltage is the ground) so how can we provide a generate for the output?

As you might guess, the solution is simple, the logic gate must have another pin that will be connected to .

### Transisotrs

But then again, how can we implement the NOT gate? First, we need to familiar ourself with transistors.

I will not go into much details about them or how they exactly work (Maybe one day I will write a post about transistors), But a little bit of introduction is required.

A transistor is a three pin device (The pins are called: “Source”, “Gate” and “Drain”), and in the standard electronic notation it is drawn as:

(“S” for the “Source”, “G” for the “Gate” and “D” for the “Drain”).

The above symbol is actually the symbol for a nMOS transistor, but it is not the only type we will need. We will also use pMOS transistors which symbol is:

(Note the little circle in the Gate pin).

In our case we look at transistors as a switch. In nMOS transistor, If we provide voltage different from the ground to the Gate pin, then the switch is on and the “Source” is connected to the “Drain” allowing current to flow between them and by doing that the voltage of the “Source” will be the same as the “Drain”, if we do not provide voltage then they are disconnected, allowing them to have different voltage.

In pMOS transistor the logic is inverted, Meaning the “Drain” and the “Source” are connected if and only if the voltage at the “Gate” is 0.

### Building NOT gate from transistors

Now, let’s look at the following implementation for the NOT gate:

We want to verify that this is implementation actually implements a NOT gate.

Note that when then the top transistor “switch” is off (because it is pMOS), which means that and are not connected. On the other hand, the bottom transistor “switch” is on (because it is nMOS), which means that is connected to the ground. Therefore we get , which is the NOT gate expected result.

Now, when the top transistor will be on and the bottom will be off, meaning that will be connected to and not to the ground which means that as expected.

Note that it is not possible to connect both of the ground and to , because then we will have short-circuit which will cause unexpected results.

### The NAND gate

The NAND gate (Not AND) is a very important gate because the NAND operator has the special property “functionality complete”. Which means that we can get every other gate as a combination of NAND gates.

The NAND gate has two input pins, and one output and works as follows:

Output | ||
---|---|---|

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

As an exercise, you can check that the following is an implementation of NAND:

I’ve mentioned above that NAND is “functionality complete”, which means that we can get any other gate using only NAND gates. For example, You can easily build a NOT gate from NAND by simply giving A and B the same value. Note that and that . Which means: .

As an exercise you can show that you can also create AND gate (which has two inputs and returns 1 if and only if both of the inputs are 1), OR gate (return 1 if at least one of the inputs are 1 and 0 if both are zero), and XOR (return 1 if ).

### Other gates

As mentioned, NAND is a functionally complete, hence once we’ve implemented it, we can implement any boolean function using only band gates. It won’t be the optimal solution in respect to the amount of transistors (as for example in the NOT gate we only needed 2 transistors, and using NAND we needed 4), so in practice some of the gates are implemented directly in transistors. You can find a list of common logic gates and their implementation on wikipedia.

July 14th, 2014 at 21:19

Hi DiGMi,

I wish to know if your awesome HUJI scheduler is syncronized with the new Shnaton (תשע”ה)?

thanx 🙂

July 15th, 2014 at 19:40

Hi DiGMi,

I wish to know if your awesome HUJI scheduler is syncronized with the new Shnaton (תשע”ה)?

thanx 🙂