design is equally important. Major errors can often be detected by testing the design with a small set of input values that provide results that are known independently. For the actual system this can be done by running it on the selected inputs; for earlier (paper) stages of the design this can be done by hand simulating the operation.

The most important property of these test cases (besides the fact that the results must be independently known so a true check is possible) is that they exercise all the logical paths in the program. It is not sufficient that each K(branch) have each output taken at some time, though that is surely necessary. Each combinatorial possibility for tracing a path through the program must occur. In addition, an attempt must be made to include both special values and general values of inputs, in terms of the operations known to occur. For arithmetic 0 and 1 are always special, as well as the. numbers at the maximum and minimum of the range. With all these conditions, the number of test cases can be quite large, especially with systems that have any degree of cascaded branching.

Hand simulation is an untrustworthy process, especially when what is desired is an assurance of correctness. It can often be replaced by using a computer to do the simulation. Figure 6 gives a FORTRAN program for checking the RTM flowchart stage of our multiplier design. The program is directly mapped from the RTM structure of Figure 4, and it is not taken from the flowchart describing the algorithm (though that could be checked too, if desired). In our case the two flowcharts are essentially identical, but that will not be the case most of the time. Consequently, care must be taken in the simulation program to reflect each of the RTM actions correctly.

The program of Figure 6 actually proves the correctness of the RTM flowchart of Figure 4 (assuming the translation to the simulator was made correctly), for it exhaustively checks all possible inputs. All 2^8 values of N1 are tested against all 2^8 values of N2, for a total of 2^16 test cases. This requires only about 30 seconds of time on a large computer (IBM 360/65 or DEC PDP-1O), well worthwhile to attain completeness. However, this is a very special case, as consideration of the time required to exhaustively check a full 16-bit multiplier will show. The point of our example is that the notion of exhaustive testing should not be excluded automatically, just because it usually takes too long; sometimes it can be done.

The final step in a design, even after checking out the system, is documentation. The notation of Figure 4 serves this purpose well -- one of the side benefits from a systematic scheme of RT-level design. The wiring pin numbers and module locations can be conveniently entered on the same diagram, as was done in Figure 7 of Chapter 2 for the sum-of-integers problem. It is desirable to have as few separate documents as possible, since changes and corrections then have to be entered in several places. However, if handwiring is to be done in implementing a design, it is usually convenient to prepare a separate wiring list.

VARIATIONS IN THE USE OF MULTIPLICATION

We have now designed a scheme for multiplying. Let us resist for the moment casting it into concrete hardware. Some of the recurrent issues in RT-level design occur when one considers doing some multiplication within a larger computation. To consider multiplication as analogous to another basic module (e.g., a DM(multiply)) is certainly possible and often useful. But it can pre-empt some other options.

116