A new symbolic substitution based addition algorithm
Symbolic substitution, a parallel processing technique, has been proposed in computing literature to perform fast, carry-free addition of numbers. Several algorithms and corresponding symbolic substitution tables have been developed for addition of two numbers represented in binary, modified signed digit (MSD), and canonical modified signed digit (CMSD) number systems. In this paper, however, we present a new symbolic substitution based algorithm and corresponding substitution table for the addition of two numbers represented in canonical modified signed digit (CMSD) notation. In contrast with the existing algorithm in this regard, that derives the addition result in MSD system, our algorithm derives the result in CMSD notation and thus it could be employed to perform symbolic substitution based associative addition of a set of CMSD numbers. (c) 2005 Elsevier Ltd. All rights reserved.
symbolic substitution parallel processing canonical modified signed digit associative addition substitution step