previous | contents | next


You have now been introduced to the set of basic RT modules and have designed a number of simple devices and systems, no doubt relying mostly on native intelligence. As we commented in the first chapter, in any sufficiently complex domain there is no systematic way of doing design. The design specifications and objective functions are too varied and the combinatorial possibilities for composing new structures are too immense. Still, much more can be said than just asserting 'that each design problem is an isolated puzzle. Candidate designs can be evaluated quantitatively to reveal explicitly the extent to which the objective functions are satisfied. The space of possible designs can be explored systematically (even if not exhaustively) to obtain a clear impression of the properties of the accepted design in contrast to the ones rejected. Furthermore, recurrent patterns arise in the space of possible designs that help in understanding whether further possibilities exist to be investigated.

This chapter is devoted to indicating the systematic characteristics of RT-level design. Consonant with the rest of the book we will proceed primarily by example, rather than by detailed theoretical description. The entire chapter will be devoted to the design of a-single device -- the multiplier. We will endeavor to carry this through in a way that exhibits good design as well as revealing many of the basic patterns of design alternatives.


We take as given the desired goal of multiplying any two 8-bit positive integers to form a 16-bit product. We will consider that such a system for multiplication is to be used in many other systems that will be constructed later. Thus, the data is to be represented in standard form. as 8 and 16 bit vectors in a word, and the fixed character of the PDP-16 data organization with the Bus determines almost completely the way input and output will occur to our system.

The first design decision is the algorithm for doing multiplication. Starting with what we all know about multiplication, Figure 1a shows by example (on 4- bit numbers) the standard method of multiplication, using the multiplicand 11 and multiplier 6. For machine implementation, the algorithm consists of forming a series of partial products for each digit of the multiplier, shifting each one, to the left one place, and then adding them all up to obtain the final product as shown in Figure lb. Since the hardware adds all the bits of a word in parallel, but does not add up a column of digits (all corresponding digits of the partial products) all at once, the algorithm has been reformed to accumulate the partial result at each stage. Furthermore, multiplication by a 0-bit does not add anything and. multiplication by a 1-bit is equivalent to simply adding the multiplicand. Thus, the algorithm reduces fundamentally to adding the multiplicand whenever the multiplier bit is 1 and then shifting the multiplier and multiplicand one place, until all the bits of the multiplier have been processed, as shown in Figure 1c.

Additional insight into adapting this standard manual multiplication algorithm to a binary machine with parallel addition can be obtained by considering the right shift scheme of Figure 2. Here we shift the partial result and the multiplier to the right at each stage. But since the partial result grows by 1 bit each step and the multiplier shrinks by 1 bit each step, their total bit, size remains constant (at 8 in the example of the figure). Thus, if the multiplier and product can be coupled together it may be possible to shift them in the same operation.



previous | contents | next