Title :
Computations over finite monoids and their test complexity
Author :
Becker, B. ; Sparmann, U.
Author_Institution :
Univ. of Saarland, Saarbruecken, West Germany
Abstract :
The authors consider the test pattern generation problem for circuits than compute expressions over some algebraic structure. The relation between the algebraic properties of this structure and its test complexity is analyzed. This relation is looked at in detail for the family of all finite monoids. The test complexity of a monoid with respect to a problem is measured by the number of tests needed to check the best testable circuit (in a certain computational model) that will solve the problem. Two important computations over finite monoids, namely, expression evaluation and parallel prefix computation, are considered. In both cases it can be shown that the set of all finite monoids partitions into exactly three classes with constant, logarithmic, and linear test complexity, respectively. These classes are characterized using algebraic properties. For each class, circuits are provided with optimal test sets and efficient methods, which decide the membership problem for a given finite monoid M.<>
Keywords :
VLSI; computational complexity; integrated circuit testing; logic testing; VLSI; algebraic structure; computational model; constant test complexity; expression evaluation; finite monoids; linear test complexity; logarithmic test complexity; logic testing; membership problem; parallel prefix computation; test pattern generation problem; testable circuit; Adders; Circuit testing; Combinational circuits; Computational modeling; Concurrent computing; Logic arrays; Marine vehicles; Programmable logic arrays; Test pattern generators; Very large scale integration;
Conference_Titel :
Fault-Tolerant Computing, 1989. FTCS-19. Digest of Papers., Nineteenth International Symposium on
Conference_Location :
Chicago, IL, USA
Print_ISBN :
0-8186-1959-7
DOI :
10.1109/FTCS.1989.105583
