Signed-Digit Numbe Representations for Fast Parallel Arithmetic

TLDR

Signed‑digit representations reduce carry‑propagation to a single adjacent position by using redundant operand representations, eliminating long carry chains in addition and subtraction. The paper introduces signed‑digit representations and discusses logical design issues for signed‑digit adders. By employing redundant digits, each sum or difference digit depends only on two adjacent operand digits, enabling fast addition, subtraction, multiplication, division, and rounding. Addition of signed‑digit numbers of any length takes the same time as adding two digits.

Abstract

This paper describes a class of number representations which are called signed-digit representations. Signed-digit representations limit carry-propagation to one position to the left during the operations of addition and subtraction in digital computers. Carry-propagation chains are eliminated by the use of redundant representations for the operands. Redundancy in the number representation allows a method of fast addition and subtraction in which each sum (or difference) digit is the function only of the digits in two adjacent digital positions of the operands. The addition time for signed-digit numbers of any length is equal to the addition time for two digits. The paper discusses the properties of signed-digit representations and arithmetic operations with signed-digit numbers: addition, subtraction, multiplication, division and roundoff. A brief discussion of logical design problems for a signed-digit adder concludes the presentation.