In this article, we will build logic circuits that implement math functions. It is part of a quest to answer the question “How do computers do math?”. This will section bring us the long awaited grail!\(\)
In combinational logic, the output is a function of the input values. There are a wide variety of logic gates our disposal to build these functions. Ever since the 80s, the leading logic families are the TTL-based 7400 and the CMOS-based 4000 series.
The figure below shows an example of a package with four two-input NAND gates.
Following sections discuss implementations of a multiplexer and some basic math operations.
Multiplexer (mx)
Albeit technically not a math function, we will cover the multiplexer because we will be needing it to build operations.
A multiplexer uses a binary value (address) to select between several inputs. The output then assumes the value of that input.
The table below gives the truth table for a 2-to-1 multiplexer. From this follows the boolean equation that expresses the output z as a function of the inputs. The illustration also shows the corresponding circuit, where the circle at the input of the top NAND-gate represents an inverter.
| os | a | b | z |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
We have now reached the the heart of the question “How do computers do Math?”. The first math operation that we will tackle using these gates is: addition.
Addition (fa)
The full adder forms the building block for all n-bit adders. This full adder adds the 1-bit values a and b to the incoming carry (ci), and outputs a 1-bit sum (s) and a 1-bit outgoing carry (co). The carry is similar as when adding decimal numbers — if you have a carry from one column to the next, then that next column has to include that carry.
The truth table, shown below, gives the relation between these inputs and outputs. The Boolean equations and circuit are derived from this table.
| a | b | ci | co | s |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Now that we can add 1-bit values, we can move on to n-bit values. The basic carry-propagate adder starts by adding the least significant bit and passing the carry on to each following bit. The s outputs are combined to form the sum S.
Expanding
The circuit shown below gives an example of a 4-bit carry-propagate adder. The carry has to propagate from the lowest to the highest bit position. This so-called “ripple carry” limits the speed of the circuit.
The accompanying article “Building Math Circuits” describes Verilog HDL implementations of this along with a faster algorithms, and a demonstration setup.
Subtraction (fs)
Before we can look at subtraction, we need to be able to represent negative numbers. Referring back to the section on digital systems, the positive decimal value would be represented by the binary value 111 as shown below.
$$
\require{color}
7 \equiv
\color{red}{1}\color{black}{\times 2^2}\ +\
\color{red}{1}\color{black}{\times 2^1}\ +\
\color{red}{1}\color{black}{\times 2^0} = \mathrm{b}\color{red}{111}
\nonumber
$$
The most common digital representation for negative numbers is called “two’s complement”. It assigns the most significant bit (msb) a negative weight. The other bits have their usual binary weights. The advantage of this system is that the circuits can treat positive and negative numbers the same when doing arithmetic. The 4-bit two’s complement for decimal value -7 is 1001 is shown below.
$$
\require{color}
-7 \equiv
\color{red}{1}\color{black}{\times (-2^3)}\ +\
\color{red}{0}\color{black}{\times 2^2}\ +\
\color{red}{0}\color{black}{\times 2^1}\ +\
\color{red}{1}\color{black}{\times 2^0} = \mathrm{b}\color{red}{1001}
\nonumber
$$
Inverting the bits of a binary number and adding 1 makes the number negative. This implies that positive numbers have the value 0 as their most significant bit, and negative numbers have the value 1 as their most-significant bit.
$$
\require{color}
\color{red}-\color{black}7 \equiv
\,^{\color{red}\sim}\mathrm{b}0111\color{red}\color{red}{+\mathrm{b}1}\color{black} =\mathrm{b}1000 + \mathrm{b}0001 = \mathrm{b}1001
\nonumber
$$
This implies that using 8-bits, we can encode the decimal values -128 to 127.
Similar to addition, the simplest subtraction method is borrow propagation. Again, we will start by building a 1-bit subtractor. The inputs a and b represent the 1-bit binary numbers being added. Output d, the difference. bi and bo are the incoming and outgoing borrow signals.
The truth table shown below gives the relation between the inputs and outputs. The outputs d and bo can both be expressed as a function of the inputs. The result d is an exclusive-or (XOR) function, just as the sum was for addition.
| a | b | li | lo | d |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
To build a 4-bit subtractor we combine four of these building blocks.
For a faster approach or a Verilog implementation of the subtractor shown above, refer to Building Math Circuits.
Multiplication (ma)
Multiplication is another important operation in digital signal processing (e.g. fast Fourier Transfers). It is an excellent example of combining simple logic functions to make a much more complex function. The two methods that allow us to do this called “array multipliers”.
The array multiplier is a simple technique for implementing multiplication. It resembles the process how you would probably perform a multiplication yourself, aside from the fact that it sums up the partial products as it goes.
Each partial product bit position can be generated by a simple AND gate between corresponding positions of the multiplicand A and multiplier B bits. Adding the partial products forms the product.
The multiplier adder (ma) shown below, is the basic building block for the multiplier. It uses an AND gate to form the partial product of two binary digits. To calculate the partial sum and carry out signals, it reuses the 1-bit full adders described earlier. The boolean equations describe the multiplier adder (ma) as a function of its ports:
| x | y | si | ci | b | co | so |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 |
The carry propagation array multiplier works similarly to the way humans multiply. The maij building blocks connect in a grid, where ij identifies the row and column. The figure below gives an example of a 4-bit multiplier.
You might notice some redundancy in the top row, where ma0x merely function as AND gates.
This method will provide the expected result, but it will take a relatively long time to do so because of the long carry chain. A more optimized method is the carry-save array multiplier described below.
Implementations of this and faster multipliers in Verilog HDL can be found in the accompanying articles Building Math Circuits.
Division (csm)
Division is another example of combining simple logic function to make a more complex circuit. Note that the method shown below ignores the divide-by-0 condition. (See also Multipliers and dividers.)
Next we’ll introduce the most basic division method called attempt subtraction divider. In calculating x/y, it repeatedly subtracts the divisor y⋅os* from the digits of the dividend x. Initially the value of os equals logic 0, so that it subtracts the value y. If the difference is negative, the subtraction is cancelled by making os logic 1. Together, all the successive OS‘s together makes the division result, while the remainder is the difference of last subtraction step.
To implement this algorithm, we need subtractors that can cancel the subtraction. Each subtractor calculates the difference between two input numbers, but if the result is negative, the operation is canceled and replaced with a subtraction of zero.
Such a Controlled Subtract-Multiplex (CSM) contains a 1-bit subtractor a-b with the usual inputs a, b, and bi and outputs d and bo. The output select (os) signal selects between bit x and d=a-b. The signal is connected to the borrow output of the most significant 1-bit subtractor.
- 0, means subtraction result was positive ⇒ D’ = D.
- 1, means subtraction result was negative ⇒ D’ = X.
Inside each divider cell the os controls a multiplexer that selects between the result of the addition d and the original remainder x. The boolean expressions express the output as a function of the inputs. (Click image to animate)
| os | x | y | bi | bo | d |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
The circuit shown below implements a complete 8:4-bit divider matrix using CSM modules. Each row performs one “attempt subtraction” cycle. Note that the most significant bit is used to drive the os inputs. (For details see “Combinational arithmetic“.)
For a faster approach or a Verilog implementation of above divider, refer to Building Math Circuits.
Square root
The square root operation is an interesting algorithm to implement in hardware. Its implementation is another example of combining simple logic functions, reusing previous designs.
Samavi and Sutikno improved the classical non-restoring digit recurrence square root algorithm. This example uses their algorithm but without the optimizations. The algorithm of this Simplified-Samovi Square root is:
- Add the next bit from the input number to the right of the current remainder. This becomes the new current remainder (A)
-
Take the square root obtained so far, append
01to it and subtracts this, properly shifted, from the current remainder. (The0in01corresponds to multiplying by 2; the1is a new guess bit.) -
If the result is
- Positive, then the new root bit is 1, and the result becomes the new remainder.
- Negative, then the current remainder (A) will become the new remainder (as if the subtraction never happened).
The circuit shown below implements a complete 8-bit square root circuit. Each row performs one “attempt subtraction” cycle. Like in the division circuit, the most significant bit is used to drive the os inputs.
For a Verilog implementation of above square root algorithm, refer to Building Math Circuits.
I hope the this answered the question “How do computers do math?“. The easy answer would be “because the physics make it”, just like a ball rolling down a hill. I hope you enjoyed our much longer journey into this exciting field!