Symbolic substitution based approach for the design of carry-free binary arithmatic unit

Abstract

Symbolic Substitution has been proposed in optical computing literature as a parallel processing technique to perform arithmetic computation. Employing a conversion table as a reference, the process iteratively substitutes a set of input patterns by pre-defined output patterns. Along with the development of this parallel processing technique, researchers have also come up with a number of non-bil)ary representations that allow fast carryfree addition. Modified Signed Digit(MSD) and Canonical Modified Signed Digit(CMSD) number systems have been extremely popular in this regard. In contrast with the binary system, these number systems use three types of symbols: 0, 1 and -1. Redundancy due to the extra digit make these systems suitable for symbolic substitution based parallel addition process. However, traditional computing is based on binary system and corresponding binary logic. But generation of carry in binary arithmetic is the main hindrance to employing the symbolic substitution process and making the computation fast. The focus of this study has, therefore, been the development of a symbolic substitution based process for fast arithmetic computation of binary numbers. The idea has been the design of a fast addition unit that accepts at its interface numbers represented in binary form, then converts these numbers to some intermediate non-binary representation for processing, and then converts the result back to the binary form. The focus has been the development of symbolic substitution processes for all the intermediate phases involved like the conversion of binary to the non-binary representation, processing of the numbers and finally the conversion of the non-binary representation to binary representation. Due to its capability of unique representation of numbers and sparseness of the non-zero digits in the representation, Canonical Modified Signed Digit (CMSD) representation has been chosen as the non-intermediate representation for the arithmetic unit proposed in the study. An important factor in the context of symbolic substitution is the required number of ii substitution steps. The thesis presents a set of symbolic substitution tables and algorithms that require much less substitution steps to complete the conversion and addition operations than any other corresponding earlier schemes. Also, the addition algorithm presented in the study derives the addition result in CMSD notation and thus it could be employed to perform symbolic substitution based associative addition of a set of CMSD numbers. An important contribution of this thesis is the development of a symbolic substitution based unit that can perform the associative addition of a set of binary numbers in computationally more efficient way than using any of the earlier proposed schemes. Such an algorithm can lead to the way of employing symbolic substitution in other arithmetic operations, like multiplication, where associative addition of a set of numbers is an integral process.