Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

4

ARITHMETIC OPERATIONS: ADDITION AND SUBTRACTION

Addition is used as a primitive operation for computing most arithmetic functions, so that it deserves particular attention. The classical pencil and paper algorithm implies the sequential computation of a set of carries, each of them depending on the preceding one. As a consequence, the execution time of any program, or circuit, based on the classical algorithm is proportional to the number n of digits of the operands. In order to minimize the computation time, several general ideas have been proposed. One of them consists of modifying the classical algorithm in such a way that the computation time of each carry is minimal; the time complexity is still proportional to n, but the proportionality constant is smaller. Another approach rests on the use of a different numeration system; instead of adding two base-B n-digit numbers, two base-B^s (n/s)-digit numbers are considered. Several algorithms, different from the classical one and generally based on some kind of tree structure, have been proposed. If their implicit parallelism can be exploited, execution times proportional to log n are reached.