Building a Discrete Computer

Build a transistor level computer with me!

Arithmetic Logic Unit: Understanding Binary Addition

by · Published · Updated

12/12/2022

What is an Arithmetic Logic Unit (ALU)

The arithmetic Logic unit is the part of the computer that will handle the arithmetic operations of the computer including binary addition, subtraction, multiplication, and division. Additionally some ALUs can perform logical operations such as AND, OR, NOT, and bit shifts.

Binary Addition

The easiest way to understand binary addition is to look at the similarities between binary addition and decimal addition:

When performing basic decimal addition, there are a few key rules that must be followed. The first step is to add the two rightmost digits, then move one place to the left and repeat the process until all digits have been added. It is important to note that an overflow may occur when adding each line of digits, which means that the resulting sum cannot be represented using the digits 0-9. In this case, a carry value of 1 is added to the next place over, as shown in the following example: 8+9=17, since 17 cannot be represented using a single decimal digit, the result of that column’s addition is 7 and a carry of 10 is added to the next place over (since 10+7=17, this is allowed). This process is demonstrated by adding 14 to 28:

Decimal addition of 14+28

Here, the rightmost digits are added to produce a result of 2. Since this sum can be represented using a single decimal digit, no carry is needed. The next step is to move one place to the left and add the next two digits, which produces a result of 10. Since this sum cannot be represented using a single decimal digit, a carry of 1 is added to the next place over. The final step is to add the carry value of 1 to the leftmost digit, which produces a result of 42. This final result can be represented using a single decimal digit, so no additional carry is needed.

Binary addition is a straightforward concept that is based on the same principles as decimal addition. The only difference is that it uses only the binary digits 0 and 1. The process of binary addition can be understood using a truth table, which shows all possible bitwise results of the addition of three bits. It is important to note that the addition of three bits may produce a carry, which must be taken into account when performing binary addition.

The table is derived from the following basic bitwise addition operations:

  • 0+0=00 (0+0=0)
  • 1+0=01 (1+0=1)
  • 1+1=10 (1+1=2)
  • 1+1+1=11 (1+1+1=3)

In the case where the result of the sum of a line of binary digits can be represented using a single bit (i.e., when the CARRY_OUT value is 0), the value of C is simply placed in the result and the next line is summed without a carry. However, in the case where the value cannot be represented using a single bit (i.e., when the CARRY_OUT value is 1), the value of C is still placed in the result, but the carry value is added to the next row. This process is illustrated by the following example:

Bitwise addition of 14+28
  1. The rightmost digits are added to produce a result of 0. Since this sum can be represented using a single bit, the value of C is placed in the result and the next line is summed without a carry.
  2. Move one place to the left (second digit from right) and add the next two bits, which produces a result of 1. Again, this sum can be represented using a single bit, so the value of C is still placed in the result without a carry.
  3. Move one place to the left (third digit from right) and add the next two bits, which produces a result of 10. Since this sum cannot be represented using a single bit, the value of C (0) is placed in the result, but the carry value of 1 is added to the next row.
  4. Move one place to the left (fourth digit from right) and add the next two bits, which produces a result of 11. Since this value cannot be expressed in one bit, the C (1) is placed below, and a carry of one goes to the final bit addition.
  5. The final addition results in 10 so a 0 is placed below and a carry out of 1 is generated.

Methods of Bitwise Subtraction

Obtaining Negative Binary Numbers

It is important for an arithmetic logic unit (ALU) to be able to perform subtraction as well as addition. Subtraction is similar to addition, just with a few steps added. One way to approach binary subtraction is to derive it from the principle that A-B=A+(-B), which means that if we can convert the second number to a negative value, we can simply add the two values and the resulting value will be the result of the subtraction. There are three accepted ways to represent negative numbers in binary: two’s complement, one’s complement, and sign-magnitude. Each of these methods has its own advantages and disadvantages, and the choice of which method to use depends on the specific application:

Sign-Magnitude method: One of the ways to represent negative numbers in binary is sign-magnitude representation, which is the simplest method. In this method, the most significant bit (MSB; leftmost bit) indicates the sign of the number, and the rest of the bits represents the value. For example, the binary number 1101 would represent -6, since the leftmost 1 indicates that the number is negative, giving -(101)=-6. When using this method, it is important to know how many bits are used to represent the number in order to determine which bit is the MSB. However, this method is not well-suited for subtraction, as can be seen in the example of 1-1 (which is the same as 1+(-1)). In binary, this can be represented by 001+101, which when summed yields 110 (-2), instead of the expected 000.

Sign-Magnitude of 3-bit numbers

Ones-Complement Method: Another way to represent negative numbers in binary is one’s complement representation. In this method, the positive number is taken (with the MSB equal to 0) and each bit is inverted to obtain the negative version of that number. As in the sign-magnitude method, the MSB indicates whether the number is negative or positive. For example, to obtain a value of -6 using one’s complement representation, the binary value of +6 (0110) is inverted to produce 1001. While this method is somewhat better suited for subtraction than the sign-magnitude method, it is still not ideal. The results of subtraction using this method always yield a number that is one less than the expected value. For example, in the case of 1-1 (which is the same as 1+(-1)), the binary representation using one’s complement would be 001+101, which when summed yields 1000 (-1) instead of the expected 0000 (0).

  • 3-3 = 3+(-3) = 011 + 100 = 111 (-0)
  • 3-2 = 3 + (-2) = 011 + 101 = 000(+0)
  • 3-1 = 3 + (-1) = 011 + 110 = 001 (+1)
Ones-Complement Method of 3-bit numbers

Twos-Complement Method: To address the shortcomings of one’s complement representation for negative numbers in binary, the two’s complement method is often used. In this method, the one’s complement of a number is obtained as described above, and then 1 is added to the result. For example, to represent -12 in two’s complement, the one’s complement is first obtained (10011), then 1 is added to produce 10100. There is a shortcut for this method, which involves finding the first 1 going from right to left, leaving the 1 and everything to the right as is, then inverting all the bits to the left. Using this shortcut to obtain the two’s complement representation of -12, the positive value of 12 (01100) is used, then everything to the left of the first 1 from the right is inverted, and everything to the right (including the 1) is kept the same. This produces the same result of 10100 as the previous method.

  • 3-2 = 3 + (-2) = 011 + 110 = 001 (1)
  • 2-3 = 2 + (-3) = 010 + 101 = 111 (-1)
  • 3-3 = 3 + (-3) = 011 + 101 = 000 (0)
Twos-Complement Method of 3-bit numbers

After considering the various methods for representing negative numbers in binary, it is clear that two’s complement is the best choice for an ALU design that includes subtraction functionality. The hardware implementation of subtraction is much easier using the Twos-Complement method, as it involved inverting each bit, then adding 1 to the resulting number. This is all easy to do in hardware, and the exact mechanism will be explained in more detail in the next post.

The Hardware of Boolean Addition

The Half Adder

The first piece of hardware to understand is something known as a half adder. A half adder is a simple digital logic circuit that performs the addition of two binary digits. It has two inputs (A and B) and two outputs (C and CARRY). The output value (C) is the sum of the two input values (A and B), while the carry output (CARRY) indicates whether an overflow has occurred (i.e., whether the sum of A and B cannot be represented using a single bit). The half adder is a fundamental building block of digital logic circuits, as it allows for the basic addition of two binary digits.

Truth Table for Half Adder

To derive the logic gates the CARRY and C output can be taken separately. The CARRY bit is simply and AND operation of A and B, and the C bit is an XOR operation of A and B (Exclusive OR; 1 when only one of the inputs is 1, otherwise outputs 0):

Circuit Architecture for Half Adder

The Full Adder

The half adder circuit is useful in operations that involve the addition of two binary digits, such as an incrementor, but it is not well-suited for more complex operations that involve the addition or subtraction of multiple digits. This is because the half adder does not have the ability to take into account a carry value from a previous addition, which is necessary for handling overflows in multi-digit calculations. To address this limitation, a full adder circuit can be used. A full adder circuit takes three inputs (A, B, and CARRY_IN) and produces two outputs (C and CARRY_OUT). The output values (C and CARRY_OUT) represent the sum of the three input values (A, B, and CARRY_IN), and the carry value indicates whether an overflow has occurred. The truth table for a full adder circuit is as follows:

Full Adder Truth Table

The design of a full adder circuit is straightforward, as it involves the cascading of two half adder circuits in series. The first half adder circuit performs the addition of the two input values A and B, while the second half adder circuit takes the result of this addition and adds the CARRY_IN input value to it. The two carry values (one from each half adder) are then ORed together to produce the final CARRY_OUT output value. This is illustrated by the following diagram:

Circuit Architecture for Full Adder

4-Bit Adder

To create a higher-level adder that can handle the addition or subtraction of multiple digits, multiple full adder circuits can be cascaded in series. In this configuration, the output bit (C) of each full adder circuit becomes the input bit (CARRY_IN) of the next full adder circuit. This allows for the efficient and accurate addition or subtraction of an arbitrary number of bits. Additionally, the subtraction of two numbers can be performed by inverting the bits of one of the inputs and setting the initial CARRY_IN value to 1, which effectively uses two’s complement representation to perform the subtraction. This allows the full adder cascade to perform both addition and subtraction operations.

Circuit Architecture of 4-Bit adder

The next post will include the design, breadboarding, and building of the ALU, which will use many of the concepts outlined in this post.

You may also like...