Abstract

Among the various nonbinary number systems introduced for solving the bottleneck of carry propagation, modified signed-digit (MSD) arithmetic¹ appears to be the most promising because it provides parallel, carry-free addition and borrow-free subtraction with storage complexity proportional to the length of the bit string. In MSD carry-free addition schemes, the pair of numbers to be added is first converted into an intermediate pair such that the addition of the latter pair will not generate any carry. In this paper, we extend the higher-order symbolic substitution (SS) technique to incorporate the MSD numbers. The propos d method ensures that both addition and sub traction operations can be implemened in only two steps, irrespective of the number of bits to be processed, thus saving a tremendous amount of computation time. Further, a new set of carry-free SS rules that are based upon checking a pair of reference bits from the next-lower-order bit position is derived. Finally, a content-addressable memory based optical implementation for the proposed scheme is also suggested.

© 1992 Optical Society of America