Page 515 - Introduction to Information Optics

500 9. Computing with Optics

the residue of X divided by m ;:

(i = 0, 1,. , ., N - 1). (9.20)
x t = X modulo m,- = \a\m it
The range of the numbers to be represented is determined by the product of
the moduli:

It can be directly utilized for carry-free addition, subtraction, and multiplica-
tion, because the operations on different moduli can be performed in parallel:

Pi — |P|m ; = \a * h m, = \a f * frjm,-, (9,22)

where * represents an addition or a multiplication, and P is the sum or
product. Subtraction can be transformed to addition by complementing the
subtrahend with respect to the moduli. However, this technique also suffers
from several disadvantages. For example, since different moduli operations are
performed for different digits, it is not suitable for SIMD space-invariant global
optical operations and the processing complexity is asymmetrically distributed.
Moreover, decoding of the final result from residue to binary or decimal is
rather complicated, and the increased time delay may offset almost all of the
time saved in eliminating carries.
The signed-digit number system allows us to implement parallel arithmetic
by using redundancy. The modified signed-digit (MSD) number system [70, 71,
72, 74, 121-145] has been widely studied. It confines the carry propagation to
two adjacent digit positions and thus permits parallel carry-free addition and
borrow-free subtraction of two arbitrary length numbers in constant time.
Higher radix signed-digit number systems [73, 146-160] permit higher infor-
mation storage density, less complexity, fewer components, and fewer cascaded
gates and operations. Consequently, various parallel algorithms involving
single as well as multiple computational steps have been proposed for MSD,
trinary signed-digit (TSD) [146-154], and quaternary signed-digit (QSD) [73,
155 160] number systems. Among these algorithms, a two-step receding
technique [138, 139, 140, 149, 152, 153, 154, 156, 157, 160] has been recently
introduced in which the operands are first receded so that the second step
operation is carry free. Moreover, negabinary number system [55, 94, 95, 108,
109, 160, 161], using —2 as the base, possess the particular superiority of
uniquely representing both positive and negative numbers without a sign bit.
Recently, a two-step parallel negabinary signed-digit (NSD) arithmetic has
been proposed [160]. The negabinary numbers can be directly input for
operation since negabinary is a subset of NSD.