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.
