A GENERALIZED MULTIBIT RECODING OF TWOS COMPLEMENT BINARY-NUMBERS AND ITS PROOF WITH APPLICATION IN MULTIPLIER IMPLEMENTATIONS

A multibit recoding algorithm for signed two’s complement binary numbers is presented and proved. In general, a k + 1 -bit recoding will result in a signed-digit (SD) representation of the binary number in radix 2k, using digits −2k−1 to +2k−1 including 0. It is shown that by scanning k + 1-tuples (k ≥ 1) with one bit overlapping between adjacent groups, a correct SD representation of the original number is obtained. Recoding of binary numbers has been used in computer arithmetic with 3-bit recoding being the dominant scheme. With the emergence of very high speed adders, hardware parallel multipliers using multibit recoding with k > 2 (i.e., more-than-3-bit recoding) are feasible with potentials of improving both the performance and the hardware requirements. A parallel hardware multiplier based on the specific case of 5-bit recoding is proposed. Such an implementation would use three fast adders to produce the odd multiples of the multiplicand while reducing the size of the carry-save-adder array by 50% compared to the classic case of 3-bit recoding. Extensions beyond 5-bit recoding for multiplier design are studied for their performance and hardware requirements. Other issues relating to multiplier design such as multiplication by a fixed or controlled coefficient are also discussed in the light of multibit recoding. © 1990 IEEE