Fast Parallel Integer Multiplier in Binary Representation

摘要

Addition and multiplication of integers in the binary representation are basic operations of any digital processor. For adding two integers of N bits each, the serial adder takes as many clock ticks. In this paper, we describe a fast method for integer addition, which takes 2 clock ticks to perform the addition operation requiring only O(N~2) space. The number of bits N is chosen usually to be a positive integer power of 2. The speedup is achieved by special purpose circuits for increment operations by 2~i , for 0 ≤ i ≤ N — 1, each operation taking only a single clock tick to complete. The usefulness of this adder for multiplication operation is discussed. The standard multiplication method utilizes quantizer and 3-bit to 2-bit consolidation circuits to produce an integer that represents in binary the number of 1s in a column corresponding to a place (weighted coefficient) of nonnegative integer power of 2. The last two consolidated integers are added by an adder in the end.