Arithmetic Operations

Arithmetic operators

In this section, we will learn how to perform addition and subtraction on binary numbers (unsigned or in two’s complement), using basic logic gates introduced in the #sec:basic-logical-functions[1.2] section.

Addition

Introduction

It is possible to add two binary numbers using the basic algorithm [^11] consisting of adding each digit of the two operands from the least significant bit to the most significant bit and propagating the carry bit.

Example: Unsigned addition of $3_{(10)} = 1 1_{(2)}$ and $2_{(10)} = 1 0_{(2)}$


	$0$	$1$	$1$
$+$	$0_{1}$	$1$	$0$
$=$	$1$	$0$	$1$

Elementary adder

In fact, we are performing several elementary additions taking as inputs a bit of each of the two operands of the calculation ( $a_{i}$ and $b_{i}$ ) and an input carry ( $c_{i}$ ) from the preceding elementary addition, and producing as output a bit of the result ( $s_{i}$ ) and an output carry ( $c_{i + 1}$ ) for the next elementary addition.

This elementary addition can be written arithmetically as the equation[^12]:

$a_{i} + b_{i} + c_{i} = 2 \cdot c_{i + 1} + s_{i}$

The two outputs $c_{i + 1}$ and $s_{i}$ being Boolean variables, it is possible to express their value in the form of Boolean functions of the inputs $a_{i}$ , $b_{i}$ and $c_{i}$ . The truth table of this elementary addition operator is as follows:

$a_{i}$	$b_{i}$	$c_{i}$	$c_{i + 1}$	$s_{i}$	Decimal
$0$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$1$	$1$
$0$	$1$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$	$0$	$2$
$1$	$0$	$0$	$0$	$1$	$1$
$1$	$0$	$1$	$1$	$0$	$2$
$1$	$1$	$0$	$1$	$0$	$2$
$1$	$1$	$1$	$1$	$1$	$3$

From an analytical point of view, we obtain the following equations[^13]:

$s_{i} c_{i + 1} = a_{i} \oplus b_{i} \oplus c_{i} = a_{i} \cdot b_{i} + a_{i} \cdot c_{i} + b_{i} \cdot c_{i}$

The one-bit adder can be represented by the following diagram:

Adding complete numbers

To realize a complete addition over several bits, we just connect together elementary 1-bit operators[^14]:

Dynamics of the addition

We need to pay attention to the fact that the addition of two unsigned binary numbers (two’s complement numbers, respectively) on $n$ bits produces a result that can be represented as an unsigned number (two’s complement number, respectively) on $n + 1$ bits.

In order to be assert a correct result when adding two unsigned numbers represented respectively with $n$ and $m$ bits, we first expand the two operands to $max (n, m) + 1$ bits (using the extension rule seen previously in section #sec:rules-extension[1.4.3]). The result, which is unsigned, will be represented on $max (n, m) + 1$ bits. The possible output carry is to be discarded.

Similarly, in order assert a correct result when adding two numbers represented respectively with $n$ and $m$ bits in two’s complement, we need to extend the two operands to $max (n, m) + 1$ bits (using the sign extension rule seen earlier in section #sec:rules-extension[1.4.3]). The result will be represented as $max (n, m) + 1$ bits in two’s complement form. The outgoing carry of the addition is to be discarded.

Subtraction

We can also perform a subtraction of two numbers using one-bit elementary subtractors.

Basic subtractor

From an arithmetic point of view, we have[^15]:

$a_{i} - b_{i} - c_{i} = - 2 \cdot c_{i + 1} + s_{i}$

The corresponding truth table is:

$a_{i}$	$b_{i}$	$c_{i}$	$c_{i + 1}$	$s_{i}$	Decimal
$0$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$1$	$1$	$- 1$
$0$	$1$	$0$	$1$	$1$	$- 1$
$0$	$1$	$1$	$1$	$0$	$- 2$
$1$	$0$	$0$	$0$	$1$	$1$
$1$	$0$	$1$	$0$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$1$	$1$	$- 1$

From a logical point of view, if we express the outputs ( $c_{i + 1}$ and $s_{i}$ ) depending on inputs and elementary logical functions, we obtain[^16]:

$s_{i} c_{i + 1} = a_{i} \oplus b_{i} \oplus c_{i} = \overline{a_{i}} \cdot b_{i} + \overline{a_{i}} \cdot c_{i} + b_{i} \cdot c_{i}$

This one-bit subtractor can be represented by the following diagram:

circuit diagram of the elementary subtractor

[^11] Algorithm you learned in primary school

[^12] The $+$ and the $\cdot$ here represent the arithmetic operators of addition and multiplication.

[^13] The $+$ and $\cdot$ here represent the operators logic OR and AND.

[^14] This structure is called a carry-ripple adder. There are other adder structures offering trade-offs between the number of logical gates and computation time.

[^15] The $+$ and the $\cdot$ represent the arithmetic operators addition and multiplication here.

[^16] The $+$ and the $\cdot$ represent the logical operators OR and AND.

INF107