Automating the verification of Boolean functions in digital computer logic modules
Reese, Oran Thomas
Master of Science
When digital computer logic modules contain a large number of gates and have many input and output terminals, the problem of testing the modules is a formidable one. This thesis is a study of one aspect of the problem, that being the verification of Boolean functions implemented by irredundant combinational logic. The assumption is made that even when an automatic testing system is employed it will not be feasible to provide all possible combinations of binary input signals as a test pattern sequence. The manner in which a module should be tested is influenced by a number of considerations. Several schemes are suggested for classifying modules according to the type of electronic hardware involved. For several circuit types, it is shown that the input bit patterns required for testing individual gates are independent of the type of circuitry. It is also shown, however, that when gates are interconnected on a module the type of circuitry as well as the interconnections must be considered. An algorithm is developed which produces a set of module input bit patterns that will detect any single gate failure and at least some double failures. The characteristics of an automatic testing system are considered, first by means of an abstract model and then with regard to actual equipment that can be adapted to the problem. Techniques for generating and manipulating bit patterns in the testing system are investigated. Finally, a number of suggestions are given for further investigation.