Although there were some wonderfully usefull skills that they taught you as a child, the mathematics you learned does not hold true here. Most people starting in Microelectronic engineering (or Semiconductor Design) stumble with these concepts. The very start of boolean algebra is actually quite simple--in fact, it only involves 0's and 1's. Boolean algebra is a mathematical way to solve and optimise logic problems, involving only true (1) and false (0).
Why only 0's and 1's? Because the electronic equipment that we will be using can not read complex voltages, or values--to a computer there is only on and off. On is symbolically true. In the actual computer this is usually any voltage that is greater than the threshold value (typically 2.2V) up to the max voltage (typically 5V). This range in voltages to represent true is necessary to allow for small powerlosses caused by resistance in the circuit, and other flucuations. Any value that is below the threshold value is considered to be false (0). By using voltages to determine true and false algorithms, we are making it possible to feed electricity through a circuit, and activate different stages. But we will touch more on this later.
The very first thing that we need to learn to do using boolean algebra is count. The number system of 0's and 1's in boolean algebra is known as binary. Binary is very simple to learn. As you begin, you just keep carrying over the numbers... Here is an example--
000 001 010 011 100 101 110 111For our purposes, however many numbers (bits) you start with, that is as high as you can count.
Now that we are used to only using 0's and 1's, we need to learn some very simple techniques--like addition and subtraction. Don't be fooled it is not as simple as you might think. The first step is addition, this should be very familiar. In fact, it is the same as the decimal math that you are used to. Here are a few examples.
0001 0100 1000 + 0010 + 0110 + 1000 ---- ---- ---- 0011 1010 1 0000Pay close attention to the final case, where there is a "carry." This last floating 1 is to high to be included in the sequence, so our answer is "0000" with a carry, not "10000." This distinction is very important in boolean algebra, since in hardware each digit will be represented as a bit, and you can not increase the number of "bits" your processor can handle at a time. Ie-- if you have an 8-bit processor and you have a carry, you must have a way to handle that 9th digit, because only 8 can fit on the bus at one time. You don't need to worry about a bus yet, however. For now, just know that you can not have more bits than the number that you started with. This leads us into subtraction. This once simple action is not necessarily so easy anymore. Our processors really only do addition. In order to subtract, we need to add a negative. This is simple in concept, but here is where it gets tricky--there are no negatives in boolean algebra. This is why the 2's compliment number system was devised. Two's compliment is a way that lets us represent the entire numeric range in binary. This is done by taking the first significant bit and converting it for use similar to a +/- sign. A "1" proceeding a number means that number is negative, while a "0" means it is postive. Here are some examples:
Decimal Binary 3 = 011 2 = 010 1 = 001 0 = 000 -1 = 111 -2 = 110 -3 = 101 -4 = 100Keep in mind that when we are dealing with two's compliment numbers for subtraction, 111 does not represent the decimal "8", but rather a "-3." However, when we are adding, or not dealing with two's compliment, it does. Are you still with me? I hope so, because I'm sure by now you see the problem with two's compliment. If your processor can only handle 8 bits, in order to handle negative values, it can really only compute 7 numeric bits, and one signed bit! This limits the maximum word length that a CPU can handle. However, for now, we won't worry about that. What is more important is a way to have the processor compute the two's compliment number for itself. Luckily, this is very simple. There is one simple process that converts normal binary to two's compliment, and vice versa. All that you need to do is take your number, lets say 101, invert every number and add 1, like this:
0101 (Number in unsigned binary)
1010 (Bits inverted)
+ 0001 (Add a 1)
-----
1011 Your finished two's compliment number.
You can see from here that this number is now a negative 101. Notice how I added a bit to the front to hold the sign. This gives us a 4 bit number. For our first processor, we will leave it as a 4-bit design, although adding more would be quite simple. The main advantage to this conversion scheme, is that it works both ways. Say we are complete with two's complement processing, and would like to return to normal-- just apply the method again--
1011 (Number as two's compliment)
0100 (Bits inverted)
+ 0001 (Add a 1)
-----
0101 Your finished Unsigned Binary number
Simple! Now that we understand how two's compliment works, we can move on to subtraction... see I told you it was not what you were used to! Okay, lets start with an example.
0100 Convert this 0100 Now represent 0100 Then complete 0100 -0011 to an addition +-0011 our negative + 1101 the addition! + 1101 ---- problem first ---- as 2's comp. ---- ---- = -> -> -> 1 0001The decimal equivalent to what we just did was take 4-3=1. Only, you can see that we actually ran out of significant bits, causing a carry situation. If you were watching closely you would realize that this 2's complement scheme has a hole in it--overflows. This is a situation where an you actually run out of significant bits and the number rolls over. This is best shown with another example
5 Our decimal 0101 However in binary 5 +3 problem looks + 0011 the numbers end up +3 --- like this ------ like this, meaning --- 8 1000 -8This common overflow problem can only be encountered when you are adding 2 numbers of the same sign (ie negative plus negative, or positive plus a positive.) What happens is, that the 2's compliment system is really a number "wheel" and the number follwing +7 is -8. If you were counting up in binary, the 2's compliment equivalent would look like this
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 +0 +1 +2 +3 +4 +5 +6 +7 -8 -7 -6 -5 -4 -3 -2 -1Alrighty... By now I hope you have a light grasp on 2's compliment. As you use it more it gets much easier.
Now that we understand the most basic of the boolean/binary functions, it is time to move onto logic. Logic is perhaps the single most straightforward topic you'll ever use. Digital circuit logic is something you have been practicing since you learned to talk, you just didn't know it. There are two key operators that you must learn first--'And' and 'Or'. The first operator, And, is represented by the multiplication symbol (*) in Boolean algebra, while Or is represented by the addition symbol (+). A few good examples of + and * will clarify their usage
1 and 1 = 1 1 or 1 = 1 1 and 0 = 0 1 or 0 = 1 0 and 1 = 0 0 or 0 = 0 0 and 0 = 0 0 or 0 = 1As you can see, for an And statement to be true, all of the statements must be true. For an Or statement, only one of the statements must be true. Now let's look at that very same problem represented in true Boolean algebra style.
1 * 1 = 1 1 + 1 = 1 1 * 0 = 0 1 + 0 = 1 0 * 1 = 0 0 + 0 = 0 0 * 0 = 0 0 + 0 = 1There we have it! Boolean algebra! Now that we know that, there is really only a few small additional rules to hammer out. Instead of deriving all of the rules we will use, I am just going to give them to you. If you are ambitious enough, all of these rules can be proved using the boolean algebra techniques that you've already learned.
The set B contains at least two elements a, b such that a does not equal b.
Closure: For every a, b in B
a + b is in B
a * b is in B
Commutative Laws For every a, b in B.
a + b = b + a
a * b = b * a
Associative Laws: For every a, b, c in B
(a + b) + c = a + (b + c) = a + b + c
(a * b) * c = a * (b * c) = a * b * c
Distributive Laws--These are different than you are used to!
a + (b * c) = (a + b) * (a + c)
a * (b + c) = (a * b) + (a * c)
Compliment Where a' is the compliment of a
a + a' = 1
a * a' = 0
Lemma 1:
X + X = X
And through Duality X * X = X
Lemma 2:
X + 1 = 1
And through Duality X * 0 = 0
This wraps up your basic starter course in Boolean Algebra. These basic skills will let you rapidly progress into the field of processor design! So why wait, join in on the next installment of The Math Behind the Magic where we begin to build logic circuits that will add, perform functions, and more!
Jump Back to the Processor Design Home Page