You are encouraged to post any questions about the reading on the course discussion board!
We've learned some of the basics about boolean logic and circuit gates! Now we are going to learn how we can use this system that has two values (true and false) to support a wide range of integer numbers and operations. This reading will focus on binary, a system that we will make use of to represent numbers in hardware.
A base n number system is a system of that uses n symbols to represent numbers. For example, we are super familiar with a base 10 number system that uses the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. In number systems, we count by moving to the next greatest symbol, adding digit places when we need to. For example, after counting 9 in our base 10 system, we then move to 10, adding a tens digit place and restarting the ones digit place.
Binary is a base 2 number system that just uses the symbols 0 and 1. The rules for counting in binary are the same as they are for decimal numbers, but we have less symbols we can use in each digit place (so we tend to need more digits to represent a number in binary than we would in decimal). Here are some examples of binary numbers and their decimal equivalents:
binary decimal
0 0
1 1
10 2
11 3
100 4
101 5
... ...
Notice how there are two symbols in binary (1 and 0) just like there are two values in boolean logic and our circuit abstraction! We can use a single hardware wire to represent a binary digit, and we can use groups of wires (or buses) to represent groups of binary digits, or in other words, a binary number. This is why we are learning about binary - it becomes a powerful and necessary tool for reasoning about numbers in hardware.
Since we are so used to the decimal system, it's often useful for us to be able to translate from decimal to binary (and vice versa) when thinking about numbers in hardware.
In decimal systems, we calculate the value of a number by summing the value of each digit multiplied by the power of 10 that digit represents. For example, 423 = (4 * 10^2) + (2 * 10^1) + (3 * 10^0). Notice how the index of the digit corresponds to the power of 10 for that digit slot (starting at index 0). We call the rightmost digit the least significant digit because it has the least weight (in decimal this is a weight of 10^0). We call the leftmost digit the most significant digit because it has the most weight (in decimal this is a weight of 10^(N - 1) where N is the number of digits in our number).
All of this translates to a binary system, except now we are using 2 as our base instead of 10. So to calculate the decimal value of a binary number, we simply multiply the value of each digit by the power of 2 that digit represents. For example, 101 = (1 * 2^2) + (0 * 2^1) + (1 * 2^1) = 5 (in decimal). Notice that since we only have two possible values for each digit, 0 and 1, then this is the same as simply adding up the powers of 2 that have a 1 in the corresponding digit.
Check your understanding: What is the decimal value of the binary number 11101? (See the “Exercise Solutions” section to check your answer).
Going from decimal to binary has a slightly different and more involved process, though it's equally mechanical. The process we will use has the following steps: 1. List out powers of 2 from right to left starting at 20 (1) and increasing until we reach a power of 2 that is greater than the number we are converting. These will correspond to the digits of our resulting number. 2. Keep track of an amount we have left to convert. To start, this will be the value we want to convert. 3. For each power of 2, starting with the largest and ending with the smallest: * If the power of 2 is greater than the amount we have left to convert, then put a 0 for that digit and move to the next smallest power of 2. * Otherwise, if the power of 2 is less than or equal to the amount we have left to convert, then put a 1 in that digit. Subtract the power of 2 from the amount we have left to convert and use this new value going forward. * Continue this process until the amount we have left to convert is 0.
To make this process more clear, let's walk through an example where we are trying to convert the number 13. First we will list out the powers of 2 until we have reached one that is larger than 13. We also set our “amount left to convert” to 13.
Amount left to convert: 13
Digits:
16(2^4) 8(2^3) 4(2^2) 2(2^1) 1(2^0)
_ _ _ _ _
Next, we begin checking each of the digits starting with our largest power of 2. Our first power of 2 (16) is larger than 13, so we place a 0 in that digit and move to the next power of 2.
Amount left to convert: 13
Digits:
16(2^4) 8(2^3) 4(2^2) 2(2^1) 1(2^0)
0 _ _ _ _
Our next power of 2 (8) is smaller than 13, so we place a 1 in that digit, update our value left to convert to 13 - 8 = 5 and move to the next power of 2.
Amount left to convert: 5
Digits:
16(2^4) 8(2^3) 4(2^2) 2(2^1) 1(2^0)
0 1 _ _ _
This process continues, resulting in:
Amount left to convert: 0
Digits:
16(2^4) 8(2^3) 4(2^2) 2(2^1) 1(2^0)
0 1 1 0 1
We can drop the leading zero and report 1101 as the binary representation of 13.
Check your understanding: What is the binary representation of 23? (See the “Exercise Solutions” section to check your answer).
While binary numbers in theory can have any number of digits (just like decimal numbers), in reality, our hardware will not be able to add an arbitrary number of wires depending on the numbers that programs use. Most of our values will have a fixed width of wires allocated to represent them. For example, in our computer, we will typically use binary values with a width of 16 wires/digits/bits. When we limit the number of bits that can be used with our values, we also impose limits on what numbers we can represent in our system.
With N bits, we can only represent 2^N unique values (there are 2 choices for each of the N digit spots). For example, if N = 3, then we can represent 2^3 = 8 different numbers, namely 000, 001, 010, 011, 100, 101, 110, and 110.
Ignoring any representation of negative values (we'll discuss negative numbers later this week) then what is the highest value that we can represent? You may have already figured out that this is the number equivalent to N ones, but calculating the decimal value of this gets really tedious as we increase N (for our system where N = 16 we'd have to add up 16 powers of 2…).
There's actually a quick trick we can use to calculate our maximum value. Let's say we have a system where N = 5. Our maximum value in binary is 11111. Rather than add up 5 powers of two though, we can also note that 11111 + 1 = 100000. We can't actually represent 100000 because it requires 6 digits/wires, but we know what value it would have - since it just has one 1 in the 5th index (remember that our indexing starts from 0!) then we know it's value is equal to 2^5. Updating our equation from before, we now have 11111 + 1 = 2^5, which we can rearrange to 11111 = 2^5 - 1 = 32 - 1 = 31. Now instead of having to calculate 5 powers of 2, we only have to calculate 1! This trick works more generally, such that for a system that uses N bits, then the maximum value for that system is 2^N - 1. For our computer, where N = 16, it's now a breeze to calculate our max value which is 65535, giving us a range of numbers from 0-65535 inclusive (again, we'll deal with negative numbers later).
For the purposes of our computer, we'd like to support the following operations: * Addition (we will implement this in hardware) * Subtraction (based on our addition hardware) * Comparison (based on our addition hardware) * Multiplication (implement in software later) * Division (implement in software later)
Notice how just by implementing addition in hardware, we can actually support a wide range of operations. This reading will just focus on how binary addition works, and during class we will get into the specifics of how to build circuits that implement this logic.
To add two decimal numbers, we add each of the corresponding digits of the numbers together starting at the least significant digit and we carry a 1 to the next column if our result is more than one digit (greater than or equal to 10). For example, let's say we wanted to calculate 536 + 345:
carry: 0 0 1 0
_______________
5 3 6
+ 3 4 5
_________
8 8 1
Binary works exactly the same, we add each of the corresponding digits of the numbers together starting at the least significant digit and we carry a 1 to the next column if our result is more than one digit in binary (greater than or equal to 2 which is 10 in binary!). For example, here is 3 + 2 = 5 in binary:
carry: 0 1 0 0
_______________
0 1 1 (3)
+ 0 1 0 (2)
_________
1 0 1 (5)
Sometimes addition will result in a carry that extends the width of our number:
carry: 1 1 1 0
_______________
0 1 1 (3)
+ 1 0 1 (5)
_________
1 0 0 0 (8)
What if we were in a system that only had values with a width of 3 digits though? For our purposes, if an addition results in a carry beyond the width of our representation, we will ignore the carry bit. So our above example becomes:
carry: 1 1 1 0
_______________
0 1 1 (3)
+ 1 0 1 (5)
_________
0 0 0 (0)
^ ignore the carry bit since it's outside our width of 3
Check your understanding: What is the decimal value you get when adding the binary numbers 1001 and 0011 together? Assume our system uses a width of 4 digits for numbers. (See the “Exercise Solutions” section to check your answer).
Now that we've explored some of the mechanics of binary and addition at a high level, in lecture we will dive into the details of implementing addition of binary numbers in hardware. This will set us up to build the first major component of our computer - the Arithmetic Logic Unit.
number: 11101
digit index: 43210
11101 = 2^4 + 2^3 + 2^2 + 2^0 = 16 + 8 + 4 + 1 = 29
Here's the setup for the problem:
Amount left to convert: 23
Digits:
32(2^5) 16(2^4) 8(2^3) 4(2^2) 2(2^1) 1(2^0)
_ _ _ _ _ _
Omitting the intermediate steps, here is the picture we are left with at the end:
Amount left to convert: 0
Digits:
32(2^5) 16(2^4) 8(2^3) 4(2^2) 2(2^1) 1(2^0)
0 1 0 1 1 1
Which gives us a binary representation of 10111.
1001 and 0011 together? Assume our system uses a width of 4 digits for numbers.carry: 0 0 1 1 0
_________________
1 0 0 1 (9)
+ 0 0 1 1 (3)
___________
1 1 0 0 (12)