Math inside circuits

There’s this circuit known as the ALU (Arithmetic Logic Unit), it does math and logical operations all through logic gates. Let me just say that everything done here is about addition. Subtraction is adding negative numbers, multiplication is repetitive adding, and division is just repetitive adding of negative numbers.

So in order to add, you basically use the AND and the XOR logic gates. (If you’re not familiar with Logic Gates, see [url=http://www.lingubender.com/forum/viewtopic.php?f=24&t=118&start=0]My post on Logic Gates[/url].)

                     +-----+
Input A --------+----|     |
                |    | XOR |----Output S
Input B ----+---|----|     |
            |   |    +-----+
            |   |
            |   |    +-----+
            |   +----|     |
            |        | AND |----Output C
            +--------|     |
                     +-----+

What you just saw is called the half-adder. It performs the addition of two one-bit binary numbers. The two one-bit inputs are A and B, and the result is output to S and C. I’m not quite sure what S and C stand for but I believe they stand for Sum and Carry. The math is done in a way that S contains the XOR result of the two bits, and C contains the AND result of the two bits. This simulates adding, check it out:

+-------+     +-------+
| Input |     |  Out  |    C = A AND B
+---+---+     +---+---+    S = A XOR B
| A | B |     | C | S |
+---+---+     +---+---+
| 0 | 0 | --> | 0 | 0 |
+---+---+     +---+---+
| 0 | 1 | --> | 0 | 1 |
+---+---+     +---+---+
| 1 | 0 | --> | 0 | 1 |
+---+---+     +---+---+
| 1 | 1 | --> | 1 | 0 |
+---+---+     +---+---+

So it is obvious that S represents the first digit (right digit) and C represents the second digit (left digit) when A and B are added.

There’s also this circuit known as the full-adder, which can add 3 bits. The output can range from 0b to 11b, or 4 different values (that’s one more possible value than the half-adder with room for one more input).

                     +-----+
Input A --------+----|     |
                |    | XOR |---+
Input B ----+---|----|     |   |        +-----+
            |   |    +-----+   +---+----|     |
            |   |                  |    | XOR |----------------Output S
Input Cin --|---|--------------+---|----|     |
            |   |              |   |    +-----+
            |   |              |   |
            |   |              |   |    +-----+
            |   |              |   +----|     |
            |   |              |        | AND |---+
            |   |              +--------|     |   |   +----+
            |   |                       +-----+   +---|    |
            |   |                                     | OR |---Output Cout
            |   |                       +-----+   +---|    |
            |   +-----------------------|     |   |   +----+    
            |                           | AND |---+
            +---------------------------|     |
                                        +-----+

Here’s the truth table for the full-adder:

+-------------+     +----------+
|    Input    |     |  Output  |
+---+---+-----+     +------+---+
| A | B | Cin |     | Cout | S |
+---+---+-----+     +------+---+
| 0 | 0 |  0  | --> |  0   | 0 |
+---+---+-----+     +------+---+
| 1 | 0 |  0  | --> |  0   | 1 |
+---+---+-----+     +------+---+
| 0 | 1 |  0  | --> |  0   | 1 |
+---+---+-----+     +------+---+
| 1 | 1 |  0  | --> |  1   | 0 |
+---+---+-----+     +------+---+
| 0 | 0 |  1  | --> |  0   | 1 |
+---+---+-----+     +------+---+
| 1 | 0 |  1  | --> |  1   | 0 |
+---+---+-----+     +------+---+
| 0 | 1 |  1  | --> |  1   | 0 |
+---+---+-----+     +------+---+
| 1 | 1 |  1  | --> |  1   | 1 |
+---+---+-----+     +------+---+

So that’s nice and all, but how do you subtract? Well like I said, subtracting is adding negative numbers. In order to represent negative numbers in binary, they came up with this thing known as the two’s complement. It is a way to represent negative binary numbers by inverting all the bits so that the 1’s become 0’s and vice-versa, after that you add one to the number.
Here’s a chart of 3-bit numbers showing their positive and their two’s-complement negate values:

+-----+-----+-----+
| Bin |  +  |  -  |
+-----+-----+-----+
| 000 |  0  | -0  |
+-----+-----+-----+
| 001 |  1  | -7  |
+-----+-----+-----+
| 010 |  2  | -6  |
+-----+-----+-----+
| 011 |  3  | -5  |
+-----+-----+-----+
| 100 |  4  | -4  |
+-----+-----+-----+
| 101 |  5  | -3  |
+-----+-----+-----+
| 110 |  6  | -2  |
+-----+-----+-----+
| 111 |  7  | -1  |
+-----+-----+-----+

The above 3-bit number system goes from -7 to 7. Let’s test this out by adding -3 to 2.
First we need to find what -3 is: 3 = 011 (Invert)> 100 (Add 1)> 101. So -3 is 101b. Since we have the negative value of 3, we can now add it to 2: 010b + 101b = 111b. The result is 111b, to tell whether this is a 7 or a -1, just see which number has the greatest absolute value. So the result is -1 or 111b.

So that’s how math is done in ALU circuits. It’s done bit by bit.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: