Adders:Addition in the Binary Number System

Introduction

Adders are the most common arithmetic circuits in digital systems. Adders are used to do subtraction and also are key components of multipliers and dividers, as described in Chapters 42 and 43. There are various types of adders with different speeds, areas, and configurations. We can select an appropriate one which satisfies given requirements. For the details of adders and addition methods, see Refs. 2, 4–6, 12, 15, 17, and 20.

Addition in the Binary Number System

Before considering adders, let us take a look at addition in the binary number system.

In digital systems, numbers are usually represented in the binary number representation, although the most familiar number representation to us is the decimal number representation. The binary number representation is with the radix (base) 2 and the digit set {0, 1}, while the decimal number representation is with the radix 10 and the digit set {0, 1, 2,…, 9}. For example, a binary number (i.e., a number in the binary number representation) [1101] represents 1·23 + 1·22 + 0·21 + 1·20 = 13, whereas a decimal number (i.e., a number in the decimal number representation) [8093] for example, represents 8·103 + 0·102 + 9·101 + 3·100 = 8093.

In the binary number representation, an integer is represented as [xn–1xn–2 …x0] where each binary digit, called a bit, xi, is one of the elements of the digit set {0, 1}. The binary representation [xn –1xn– epresents the integer ∑i =0 xi ⋅ 2 .

By the binary number representation, we can represent not only an integer, but also a number that has a fractional part as well as an integral part, as by the decimal number representation. The binary

representation [xn–1xn–2 …x0.x–1x–2 …x–m] represents the number For example, [1101.101] represents 13.625. By a binary representation with n-bit integral part and m-bit fractional part, we can represent 2n+m numbers in the range from 0 to 2n – 2–m.

[10010.010] + [0.001]. By a two’s complement representation with n-bit integral part (including a sign bit) and m-bit fractional part, we can represent 2n+m numbers in the range from –2n to 2n – 2–m.

Each of all the binary number representations described so far (i.e., the positive number representation, sign and magnitude representation, and two’s complement representation) can express essentially the same numbers, that is, 2n+m numbers, although the second case expresses 2n+m – 1 numbers (i.e., one number less) when a number is expressed with n + m bits. Thus, these representations essentially do not lose the precision, no matter whether or not one of the n + m-bits is used as a sign bit, although the range of the numbers is different in each case.

When we add two numbers represented in the sign and magnitude representation, we calculate the sign and the magnitude separately. When the operands (the augend and the addend) are with the same sign, the sign of the sum is the same as that of the operands, and the magnitude of the sum is the sum of those of the operands. A carry, 1, from the most significant position of the magnitude part indicates overflow. On the other hand, when the signs of the operands are different, the sign of the sum is the same as that of the operand with larger magnitude, and the magnitude of the sum is the difference of those of the operands.

1. The sign bits are added in the same manner as the two bits, xi and yi, in any other bit position, that is, according to Table 41.1. As illustrated in Figure 41.1(a), the sign bits, xn –1 and yn –1, and the carry, cn –1, from the (n – 2)-th position are added, producing the sum bit sn –1 (in the sign bit position) and the carry cn. Always, cn is ignored, no matter whether it is 1 or 0.

2. When xn –1 = yn –1 (i.e., X and Y have the same sign bit), an overflow occurs if sn –1 is different from xn –1 and yn –1 (i.e., cn ⊕ cn –1 = 1 means an overflow, as can be seen from Table 41.1). This case is illustrated in Figure 41.1(b) because we have sn–1 = 0 while xn–1 = yn–1 = 1 and hence sn–1 is not equal to xn –1 or yn –1.

Next let us consider the subtraction of two numbers represented in the two’s complement representation, X – Y, that is, subtraction of Y from X, where each of X and Y is a positive or negative number. This can be done as addition as explained in the previous paragraph after taking the two’s complement of Y (i.e., deriving 2n – Y), no matter whether Y is a negative or positive number. Actually, the subtraction, X – Y, can be realized by the addition of X and the bitwise complement of Y with a carry input of 1 to the least significant position. This is convenient for realizing a subtracter circuit, whether it is a serial or parallel adder (to be described later).

Henceforth, let us consider addition of n-bit positive binary integers (without the sign bit) for the sake of simplicity. Let the augend, addend, and sum be X = [xn –1xn –2 …x0], Y = [yn –1yn –2 …y0], and S = [snsn –1sn –2 …s0] with sn = cn, respectively, where each of xi , yi, and si assumes a value of 0 or 1.