Page 560 - Introduction to Information Optics

9.5. Conversion between Different Number Systems 545

Let us define a binary variable C t corresponding to the j'th digit position. At
the current MSD digit position i, if there is at least one, I to the right of this
position and no 1 between the Ts and the current position, then C (— I;
otherwise, C ;- = 0. Note that C 0 = 0. Furthermore, each digit .x ; is represented
by two binary bits (S^Z),-); i.e., 0 = (0, 0), 1 = (0, 1), and I = (1, 1). For each
position i, if the input MSD digits S t and D t, and C t are known, we can obtain
the binary output B { and the output variable C i+ ] according to the following
binary logic expressions:

BI = /),- © C, (9.75)
CH^^ + D.-CI, C 0 = 0. (9.76)

Therefore, at a given stage, a carry is generated if S (. is true, and a stage
propagates an input carry to the higher-level position if D t is false. On this
basis, we can derive a fast-conversion algorithm in carry-lookahead format. If
we replace D { with P, and extend it to a four-digit block, we can write the
following equations:

(9.77)
(9.78)
C 2 = S, + PjC, = S t + P^o + PiP 0C 0
(9.79)
C 3 = S 2 + P 2C 2 = S 2 + P 2S, + P.F^o + P 2P 1P 0C 0
C 4 = S 3 + P 3C 3 = S3 + P 35 2 + P3P 2S 1+P 3P 2P 15 0 + P 3P 2P 1P 0C 0. (9.80)

Equation (9.80) can be rewritten as
C 4 = S' 0 + P^C 0, (9.81)

where

SQ = S 3 + P 3S 2 + P 3P 2S l + P 3P 2PiS 0
P^P 3P 2P 1P 0.

In genera],
c . = s;. + p;c ., (9.82)
4i +4
4i
where

V — ^ -i-P V 4- P P ^ -I-P P r P C
I
1
,j (- — >J 4i- + 3 T i 4i+3°4i + 2 "T" -* 4/ + 2 4i + 2°4t+ l "^ •* 4J+3- 4i+2 4i+ l°4i
p' _ p p p p
J r J r r
i ~~ 4i+3 4i + 2 4i+ l 4r