Page 528 - Introduction to Information Optics

9.4. Parallel Signed-Digit Arithmetic 51 3

9.4.2.1.4. One-Step MSD Addition/Subtraction
As seen in the three-step arithmetic, the iih output sum digit depends on
three adjacent digit pairs; i.e., a (, b t, fl £_i, t> i_ 1, a, :_ 2, and h^ 2- Mirsalehi and
Gay lord [141] developed a truth table with the above variables as the inputs
and s ( as the output. Since each variable has three possible values (T, 0, and 1),
6
the table contains 3 = 729 entries. There are 183 input patterns that produce
an output 1, and 183 patterns that produce an output T. By logical minimiz-
ation, the number of patterns for each case is reduced from 183 to 28. Thus,
the output digit can be obtained by comparing the input patterns with a total
of 56 reduced minterms. Note that a reference pattern that produces a T output
is a digit-by-digit complement of the corresponding minterm producing a 1.
The reduced minterms for generating the output 1 are shown in Table 9.14.
Recently, redundant bit representation was used as a mathematical descrip-
tion of the possible digit combinations [142]. Based on this representation and
the two-step arithmetic, a single-step algorithm was derived which requires 14
and 20 minterms for generating the 1 and 1 outputs, respectively. Furthermore,
by classifying the three neighboring digit pairs into 10 groups, another one-step
algorithm was proposed where it is critical to determine the appropriate group
to which the digit pairs belong. Another one-step addition algorithm [143] was
investigated in which the operands are in binary while the result is obtained in
MSD. In this case, 16 terms are necessary which can be reduced to 12
minterms. This special case [143] is of limited use since MSD-to-binary
conversion is needed for addition of multiple numbers.

9.4.2.2. Digit-Set-Restricted MSD Addition/Subtraction
To derive a parallel MSD algorithm, it must be guaranteed that at each
digit position, the two digit combinations of (1,1) and (I, I) never occur. This
can be also realized by limiting the intermediate carry and sum digits to the
sets {1,0} and {0, 1), respectively [144]. However, according to Eq. (9.25), in
this case the sum x { + y t can contain the values from the set {— 2, — 1, 0, 1, 2}
while the result of operation 2c i _ 1 + s t can contain the values from the set

Table 9.14
Reduced Minterms that Produce a 1 in the Output Digit of the MSD Adder [141]
d Tl ldd T ild, OldOld, d Tl d 01 ld T ild, Od 01d 0,01d 01, TT dOld, Od 01101d
di,ldd T id 01 l d Tl Id 0 i001 TOdOOd OldOdl Old 01 0d 01 d 01 d Tl TlOOd 01
TldOld 0110d 01d OTd 01dj,01 d T) Od 01 Oll Oldlld Od 01d011
01!d TlOd 01 d Tl010td 01 OldlTd djjldjjd^d OOd 01d TJJ
dTidoAidTildo, OOdlOd d Tl d 01 dd Tl ll 001d nld 01 d Tl ld 01 d Tl d 01 d 0 ,