Page 539 - Introduction to Information Optics

524 9. Computing with Optics

(1)
procedure consists of two steps: generate the partial products P and add them
[123, 126]. The product is formed as

N - 1
(i)
p = AB = £ P = X Ab^. (9.55)
(=0

(l)
Each partial product P is formulated by multiplying the multiplicand A by
the ith digit b t of the multiplier B and shifting by i digit positions, which
corresponds to the weight 2'. The partial product is a shifted version of A, or
0, or A, depending on whether the value of b t is T, or 0, or 1. The traditional
multiplication algorithm checks each digit of the multiplier B from the least
significant digit b 0 to the most significant digit b v -i- To speed up the
multiplication, the following two measures must be pursued.
• Generate all partial products in parallel. This can be accomplished via
symbolic substitution, truth-table look-up, and outer-product, crossbar,
and perfect-shuffle interconnection networks.
• Add all partial products pairwise by means of an adder tree. With a total
of N partial products at the leaves of the tree, the summation process
j
takes log 27V steps. At each step /, we perform N/2 MSD additions in
parallel:
P.j = P 2i- 2iJ- 1 + P 2i- ltj-,, for i = 1, 2,..., N/2{ j = 1,2,..., Iog 2A'.
(9.56)

The final product is produced at the root of the binary tree. The partial
products are generated in constant time while the addition of partial products
using the tree structure requires log 2JV iterations. Therefore, the multiplication
of two N-digit MSD numbers can be carried out in 0(log 2iV) time. The
following numerical example illustrates the multiplication process between the
numbers A = 10TT = 5 ]0 and B - lOll = 7 10.

Step 1: Generation of the partial products

(0)
p : Ab 0 x 2° = 00010TT
(l} 1
p : Ab, x 2 =0010110
<2)
2
p : Ab 2 x 2 = 0000000
(3)
3
p : Ab 3 x 2 = lOlIOOO