Carry-free addition of recoded binary signed-digit numbers

Signed-digital number representation systems have been defined for any radix r⩾3 with digit values ranging over the set {-α,···,-1,0,1,···, α}, where α is an arbitrary integer in the range r/2<α<r. Such number representation systems possess sufficient redundancy to allow for the annihilation of carry or borrow chains and hence result in fast, propagation-free addition and subtraction. The original definition of signed-digit arithmetic precludes the case of r=2 for which α cannot be selected in the proper range. Binary signed-digit numbers are known to allow limited-carry propagation with a somewhat more complex addition process. The author shows that a special `recorded´ representation of binary signed-digit numbers not only allows for carry-free addition and borrow-free subtraction but also offers other important advantages for the practical implementation of arithmetic functions. The recoding itself is totally parallel and can be performed in constant time, independent of operand lengths. It is also shown that binary signed-digit numbers compare favorably to other redundant schemes such as stored-carry and higher radix signed-digit representations