The random logic portion of an MOS LSI chip intended mainly for a calculator is constructed of an array of MOS complex gates, each composed of an MOS ratioless circuit with a multiphase clocking system, and occupies ordinarily a considerable part of chip area. In this paper a layout system for this portion of an LSI chip is described, which is constructed on the basis of heuristics for a set of interrelated optimization problems. Implementation results of the layout system are also shown to reveal that the random logic portion can be realized in such an areas as comparable to one done by manual layout.

The random logic portion of an MOS LSI chip intended mainly for a calculator is constructed of an array of MOS complex gates, each composed of an MOS ratioless circuit with a multi-phase clocking system, and occupies ordinarily a considerable part of chip area. In this paper, a layout system for this portion of an LSI is described, which is constructed on the basis of a set of optimization heuristics. Experimental results of the layout system are also shown so as to reveal that the random logic portion can be realized in much the same area as can be done by manual layout.

Thts paper deals wRh the problem of enumerating all the cutsets or all the s-t cutsets separatmg two spectfied verttces s and t m an undirected graph A vanety of approaches have been proposed for this problem, among which one based on the partmon era set of veruces rote two sets is the most effi¢ienL It is first shown that an algorithm of this type has time complexity O((n + m)(n -log2#)#), and two new algorithms with ume complexity O((n + m)O + I)) are then proposed One of these new algorithms has space complexity O(nZ), and the other has space complexity O(n + m), where n and m are the numbers of veraces and edges, respectively, and ta ts the number ofs-t cutsets m a given graph The results of some computatmnal experiments are also described.An mvest~gaUon ~s made of the extent to whtch the new algorithms are better, and how good the performance of the old algorithm is, especmlly when a given graph is "dense," t e, 2m/(n(n -1)) _> 0.4.

High-density packaging is one of the most urgent requirements in the design of digital systems. In the assembly of such systems, printed wiring boards (PWB's) are used very often to provide the necessary interconnection among circuit modules. Thus, methods to raise wirability of routers are continually under investigation.

By a checking sequence for a sequential machine, we mean an input-output sequence with a special property such that, when the input sequence is applied to the machine, the decision whether or not the machine operates correctly can be made by comparing the output sequence with the output of the machine.