Intro to CPU design [Part 5: CPU logic] 12-24-2014, 09:45 AM
#1

If you have not already read part 4 you should go ahead and do so before reading this part.

Okay, so we have some basic knowledge here, and we have a rough cut of what we want to implement.

Let's start basic. You know what the operations OR, AND, and NOT are, as well as XOR. So the first thing we will do is draw up our own XOR operation (using the formula xor=AB'+A'B). We will be using a dedicated XOR chip when we build this to save money, but it does the exact same thing.

Once we have that, we will build our first circuit, an adder. It will simply take 2 1-bit numbers, and add them together. This is more specifically known as a half-adder (which we will cover later in this article).

Okay, Figure 1 is our exclusive-or (XOR) circuit. I have labeled each step along the way. Notice that A' and B' happen at the same time, just like A'B and AB' happen at the same time. Since we are dealing with electricity, we can do a nearly infinite number of things at the same time. Also notice the lines drawn. Those are wires (if you did not already know). Also notice how some of the wires have waves in them? This is where a wire crosses over another wire but the two are NOT connected. I won't always draw the little bumps in this tutorial, so if you see two lines cross each other, assume they are NOT connected. They are only connected where there is a dot at the intersection point.

Now, FIG-2: this is where it gets a little complicated. There are actually TWO formulas for half-addition:

Q=A XOR B

C=A AND B

Now, what are Q and C?

Q: the result bit of our addition. This is our final result

C: carry. In the case that we add two 1-bit number, but yield a 2-bit result, C is that extra bit.

Alright, it looks like you are getting it, let's do some more with addition:

Full adder vs Half adder

A half adder takes two 1-bit numbers and adds them together. As simple as that. But what if we wanted to add say two 2-bit numbers together? We would just link up adders together. Well, with a half-adder we can't do that, there isn't a way to handle the second bit.

This is where a full-adder comes in.

A full adder takes three 1-bit numbers and adds them together. You can make a half-adder from a full adder by wiring the third bit directly to ground (logic LOW, binary 0).

Let's take a look at Figure 3:

Now, the formulas for a full-adder and a half-adder are different:

Q=(A XOR B) XOR C[in]

C[out]=((A XOR B) AND C[in]) OR (A AND B)

What is this C[in] and C[out]?

Well, that is what makes a full-adder different from a half-adder. A half-adder only has an output carry bit, while a full-adder has both an in and an out.

Take a look at Figure-4. This is the truth table for our 1-bit full adder. The bits are actually backwards in the table, it should be written like so:

C[out] Q

Just read it like A+B+C[in]=C[out] Q

This might be complicated, but if you look really closely in Figure-3, you will see the half adder, and if you spend some time reviewing your logic, you should be able to understand what is going on with the rest of the circuit.

On to Figure-5:

I don't want to have to draw out Figure-3 every time I use it, so we will make this little square, and call it FADD. every time I use a 1-bit full-adder, I will draw a square and inside it write FADD. We did the same thing with the half-adder and named it ADD.

Now, 1-bit addition is pretty useless for a 4-bit CPU. So let me show you how to use Figure-2 and Figure-3 (more specifically ADD and FADD) to make an adder circuit that adds two 4-bit numbers together.

Figure-4:

Now, here we take two numbers, A and B, add them together, and output S and V. You will notice subscripts on A, B, and S. The subscripts explain which bit of the number we are talking about, in this case from 0-3.

What is this V bit in there?

Well, if you recall, we can add two 1-bit numbers and produce a 4-bit result. The same thing happens here. if you add 1111 (hex f) and 0001 (hex 1) the output should be 10000 (hex 10), but we only have a 4-bit CPU, so our output will actually be 0000 (hex 0). Now, f+1 is not 0, so we have an overflow bit. That bit (V) will be set ONLY if an overflow like that has happened, and we should know that the value is probably wrong.

Notice how the adder works by passing the carry from each adder into the third input of the next? This is how we expand our 1-bit adders to work with more and more bits. Remember this skill, we will be using it a lot later.

Now, I took the time to draw out the full circuit design for our 4-bit adder, which is Figure 7:

This is what you will ultimately be wiring up. The design is a little bit condensed, and won't look the same as FADD or ADD, I did that so I could fit it all on one sheet. Just follow the lines and you should understand it. Notice here, there are no more bumps, but there are dots where wires are connected.

Figure 8:

This is a bit weird to you now, you will understand it more later, but it is simply a usage chart. It is an attempt to figure out exactly how much it will cost to make a single 4-bit adder. We have 7 XOR operations, 7 AND operations, and 3 OR operations. XOR, AND, and OR chips all have 4 gates per chip, meaning we can use say 4 OR operations, and only use a single chip. So we use 2 XOR chips, 2 AND chips, and 1 OR chip. But we have the problem that we still have 1 extra XOR, AND, and OR operation left on one of each chip. This won't be a problem right now, the waste is low. You can always optimize by moving other parts of the CPU around to fill up the waste and lower cost if you are feeling advanced, but this will get handled in a later part to this tutorial.

Figure 9:

Once again, I don't want to draw that diagram up every time I use it, so we named it 4ADD.

Now we have a way to add numbers, but how do we store them? We will ultimately use a register, but in order to understand registers you must first understand registers. I did not go to the basic level on this, so it might be a little confusing, but we will use flip-flops for our register bits. A flip-flop is just a way to store data, by sending the signal back to the circuit.

A S-R flip flop (actually called an SR Latch) has two input bits: set (S) and reset ®. and two outputs: Q and Q'. The formulas are:

Q=S XOR Q'

Q'=R XOR Q

Yes, this means it's really

Q = S XOR (R XOR (S XOR (R XOR ...

This is just about the only time you can have recursive electricity (I won't explain why that works, it just does, know that for now).

Well, we need to do read and write operations to these, so we need to keep track of time. That will be done using a clock signal. But if we want to write a bit when the clock is logic HIGH, and we just make an enable circuit for that (google those if you really care that much), we will end up writing that bit so quickly and often we may actually flip the bit and it won't write correctly. So we don't want to write when the clock is HIGH, we want to write when the clock goes from LOW to HIGH. That only happens once.

We will use a form of a schmidt trigger for that. The formula is:

Q=A AND (NOT A)

Yes, it is confusing. It actually works because things don't happen instantly, so by the time that the NOT is processed, A may have already changed, and therefore the values will be different. I don't want to go into depth on how that works, that may be a later topic if it needs to be explained.

Alright, now I can show you the figures:

Take a good look at figure-10, just for amusement.

The real magic is Figure-11, which we also make one of those boxes for and named it DFF. The first part is our enable circuit, basically a schmidt trigger and a data input, and the second part is the SR latch. Both of these combined make what is known as a D-flip-flop. These will make up our 4-bit registers.

Figure-12:

We take in 4 bits (D[0]-D[3]), a clock (CLK) signal, and put those into 4 different DFF's. Notice that CLK is shared between the 4 DFF's. Why do we do this? We want a synchronized write cycle. It will write all 4 bits at THE SAME TIME. Obviously there is also Q[0]-Q[3] coming out. These are ALWAYS outputting the value from the DFF. There is no output for Q' on the DFF because we simply won't use it, we will have an instruction later for that.

I named the 4-bit register 4REG for use later.

See, you are getting the hang of this, I know it is a lot of stuff to throw at you all at once, but if you need to take as long as required until you understand each figure.

I also don't want to write so many lines when we do our memory block, so I made a block called D4R, which is identical to the 4REG, except it takes a dark line and a light line. The dark line actually means there are 4 wires there. It outputs a single dark line, which means 4 lines in this case. Here is the diagram: firgure-14

The block D4R is Figure-15.

Nothing new in this figure, I simply created our 8-byte memory block. Remember there will be two of these. There isn't any point making one of those squares for it just yet, so I won't. Use this as a reference. For fun, the first person who draws out the ENTIRE circuit diagram for the memory block might win something.

EDIT: If you do the extra credit, you are ONLY allowed to use AND, OR, and NOT gates.

I used DS[0]-DS[f], meaning Data Set 0 through Data Set f. These symbolize the dark lines on the D4R. I also used QS[0]-QS[f] meaning Q Set 0 through Q Set f.

Figure-16:

Now, just for that one guy who asked "what about subtraction", here are the figures (with annotations) for subtracting.

So, there you have it, our basic logic elements of the CPU. We still have yet to learn about multiplexers so that we can make the instruction fetcher, decoder, and the memory IO system. Those will probably be covered in part 6.

Okay, so we have some basic knowledge here, and we have a rough cut of what we want to implement.

Let's start basic. You know what the operations OR, AND, and NOT are, as well as XOR. So the first thing we will do is draw up our own XOR operation (using the formula xor=AB'+A'B). We will be using a dedicated XOR chip when we build this to save money, but it does the exact same thing.

Once we have that, we will build our first circuit, an adder. It will simply take 2 1-bit numbers, and add them together. This is more specifically known as a half-adder (which we will cover later in this article).

Okay, Figure 1 is our exclusive-or (XOR) circuit. I have labeled each step along the way. Notice that A' and B' happen at the same time, just like A'B and AB' happen at the same time. Since we are dealing with electricity, we can do a nearly infinite number of things at the same time. Also notice the lines drawn. Those are wires (if you did not already know). Also notice how some of the wires have waves in them? This is where a wire crosses over another wire but the two are NOT connected. I won't always draw the little bumps in this tutorial, so if you see two lines cross each other, assume they are NOT connected. They are only connected where there is a dot at the intersection point.

Now, FIG-2: this is where it gets a little complicated. There are actually TWO formulas for half-addition:

Q=A XOR B

C=A AND B

Now, what are Q and C?

Q: the result bit of our addition. This is our final result

C: carry. In the case that we add two 1-bit number, but yield a 2-bit result, C is that extra bit.

Alright, it looks like you are getting it, let's do some more with addition:

Full adder vs Half adder

A half adder takes two 1-bit numbers and adds them together. As simple as that. But what if we wanted to add say two 2-bit numbers together? We would just link up adders together. Well, with a half-adder we can't do that, there isn't a way to handle the second bit.

This is where a full-adder comes in.

A full adder takes three 1-bit numbers and adds them together. You can make a half-adder from a full adder by wiring the third bit directly to ground (logic LOW, binary 0).

Let's take a look at Figure 3:

Now, the formulas for a full-adder and a half-adder are different:

Q=(A XOR B) XOR C[in]

C[out]=((A XOR B) AND C[in]) OR (A AND B)

What is this C[in] and C[out]?

Well, that is what makes a full-adder different from a half-adder. A half-adder only has an output carry bit, while a full-adder has both an in and an out.

Take a look at Figure-4. This is the truth table for our 1-bit full adder. The bits are actually backwards in the table, it should be written like so:

C[out] Q

Just read it like A+B+C[in]=C[out] Q

This might be complicated, but if you look really closely in Figure-3, you will see the half adder, and if you spend some time reviewing your logic, you should be able to understand what is going on with the rest of the circuit.

On to Figure-5:

I don't want to have to draw out Figure-3 every time I use it, so we will make this little square, and call it FADD. every time I use a 1-bit full-adder, I will draw a square and inside it write FADD. We did the same thing with the half-adder and named it ADD.

Now, 1-bit addition is pretty useless for a 4-bit CPU. So let me show you how to use Figure-2 and Figure-3 (more specifically ADD and FADD) to make an adder circuit that adds two 4-bit numbers together.

Figure-4:

Now, here we take two numbers, A and B, add them together, and output S and V. You will notice subscripts on A, B, and S. The subscripts explain which bit of the number we are talking about, in this case from 0-3.

What is this V bit in there?

Well, if you recall, we can add two 1-bit numbers and produce a 4-bit result. The same thing happens here. if you add 1111 (hex f) and 0001 (hex 1) the output should be 10000 (hex 10), but we only have a 4-bit CPU, so our output will actually be 0000 (hex 0). Now, f+1 is not 0, so we have an overflow bit. That bit (V) will be set ONLY if an overflow like that has happened, and we should know that the value is probably wrong.

Notice how the adder works by passing the carry from each adder into the third input of the next? This is how we expand our 1-bit adders to work with more and more bits. Remember this skill, we will be using it a lot later.

Now, I took the time to draw out the full circuit design for our 4-bit adder, which is Figure 7:

This is what you will ultimately be wiring up. The design is a little bit condensed, and won't look the same as FADD or ADD, I did that so I could fit it all on one sheet. Just follow the lines and you should understand it. Notice here, there are no more bumps, but there are dots where wires are connected.

Figure 8:

This is a bit weird to you now, you will understand it more later, but it is simply a usage chart. It is an attempt to figure out exactly how much it will cost to make a single 4-bit adder. We have 7 XOR operations, 7 AND operations, and 3 OR operations. XOR, AND, and OR chips all have 4 gates per chip, meaning we can use say 4 OR operations, and only use a single chip. So we use 2 XOR chips, 2 AND chips, and 1 OR chip. But we have the problem that we still have 1 extra XOR, AND, and OR operation left on one of each chip. This won't be a problem right now, the waste is low. You can always optimize by moving other parts of the CPU around to fill up the waste and lower cost if you are feeling advanced, but this will get handled in a later part to this tutorial.

Figure 9:

Once again, I don't want to draw that diagram up every time I use it, so we named it 4ADD.

Now we have a way to add numbers, but how do we store them? We will ultimately use a register, but in order to understand registers you must first understand registers. I did not go to the basic level on this, so it might be a little confusing, but we will use flip-flops for our register bits. A flip-flop is just a way to store data, by sending the signal back to the circuit.

A S-R flip flop (actually called an SR Latch) has two input bits: set (S) and reset ®. and two outputs: Q and Q'. The formulas are:

Q=S XOR Q'

Q'=R XOR Q

Yes, this means it's really

Q = S XOR (R XOR (S XOR (R XOR ...

This is just about the only time you can have recursive electricity (I won't explain why that works, it just does, know that for now).

Well, we need to do read and write operations to these, so we need to keep track of time. That will be done using a clock signal. But if we want to write a bit when the clock is logic HIGH, and we just make an enable circuit for that (google those if you really care that much), we will end up writing that bit so quickly and often we may actually flip the bit and it won't write correctly. So we don't want to write when the clock is HIGH, we want to write when the clock goes from LOW to HIGH. That only happens once.

We will use a form of a schmidt trigger for that. The formula is:

Q=A AND (NOT A)

Yes, it is confusing. It actually works because things don't happen instantly, so by the time that the NOT is processed, A may have already changed, and therefore the values will be different. I don't want to go into depth on how that works, that may be a later topic if it needs to be explained.

Alright, now I can show you the figures:

Take a good look at figure-10, just for amusement.

The real magic is Figure-11, which we also make one of those boxes for and named it DFF. The first part is our enable circuit, basically a schmidt trigger and a data input, and the second part is the SR latch. Both of these combined make what is known as a D-flip-flop. These will make up our 4-bit registers.

Figure-12:

We take in 4 bits (D[0]-D[3]), a clock (CLK) signal, and put those into 4 different DFF's. Notice that CLK is shared between the 4 DFF's. Why do we do this? We want a synchronized write cycle. It will write all 4 bits at THE SAME TIME. Obviously there is also Q[0]-Q[3] coming out. These are ALWAYS outputting the value from the DFF. There is no output for Q' on the DFF because we simply won't use it, we will have an instruction later for that.

I named the 4-bit register 4REG for use later.

See, you are getting the hang of this, I know it is a lot of stuff to throw at you all at once, but if you need to take as long as required until you understand each figure.

I also don't want to write so many lines when we do our memory block, so I made a block called D4R, which is identical to the 4REG, except it takes a dark line and a light line. The dark line actually means there are 4 wires there. It outputs a single dark line, which means 4 lines in this case. Here is the diagram: firgure-14

The block D4R is Figure-15.

Nothing new in this figure, I simply created our 8-byte memory block. Remember there will be two of these. There isn't any point making one of those squares for it just yet, so I won't. Use this as a reference. For fun, the first person who draws out the ENTIRE circuit diagram for the memory block might win something.

EDIT: If you do the extra credit, you are ONLY allowed to use AND, OR, and NOT gates.

I used DS[0]-DS[f], meaning Data Set 0 through Data Set f. These symbolize the dark lines on the D4R. I also used QS[0]-QS[f] meaning Q Set 0 through Q Set f.

Figure-16:

Now, just for that one guy who asked "what about subtraction", here are the figures (with annotations) for subtracting.

**Spoiler:**

So, there you have it, our basic logic elements of the CPU. We still have yet to learn about multiplexers so that we can make the instruction fetcher, decoder, and the memory IO system. Those will probably be covered in part 6.