This paper identifies a new class of Boolean functions called single-faced functions. Single-faced functions are extensions of the related double-faced core functions which have fewer supporting variables. It is proven that single-faced functions can be simplified to their core functions with respect to Sum of Product minimization, general factored forms minimization and Ordered Binary Decision Diagram (OBDD) minimization. Even if a function $f$ is not single-faced, it must contain single-faced function restrictions if $f$ is not the odd–even parity function. Experimental results show that single-faced functions are common in benchmark circuits. The structure of OBDDs of single-faced functions is studied in detail giving insights which can lead to efficient OBDD minimization algorithms. Moreover it is proven that for symmetric functions and the newly identified complete single-faced functions, any variable ordering will lead to identical OBDDs, which implies that traditional OBDD minimization algorithms will search exhaustively for those functions. Therefore for OBDD minimization, symmetry detection is mandatory in order to avoid unnecessary permutation of variables.

The hypercube is an interesting and useful topology for parallel computation. While hypercubes have been analyzed in graph theory, this analysis has done little to determine the minimum area required for realizations of the hypercube topology on two-dimensional chips. In a common VLSI layout of the hypercube, the hypercube nodes are placed in a single-row in numeric order. This paper derives an easily computed formula for the minimum number of tracks used by this configuration. For an n-node hypercube, the number of tracks required is roughly two-thirds of n. This result is also a useful upper bound on the number of tracks required under optimal ordering. In general, the number of tracks required is a function of the ordering, but finding the optimal order (optimal in the sense of requiring the minimum number of tracks over all orderings) is NP-hard. Finally, the formula is applied to more area-efficient and practical two-dimensional hypercube layouts. In general, it allows estimation of and control over implementation parameters such as area and chip aspect ratios.

The necessary and sufficient conditions for detecting transistor stuck-open faults in arbitrary multilevel CMOS circuits are shown. A method for representing a two-pattern test for detecting a single stuck-open fault using only one cube is presented. The relationship between the D-algorithm and the conditions for detecting transistor stuck-open faults in CMOS circuits is provided. The application of the proposed approach in robust test generation for transistor stuck-open faults in a number of benchmark circuits is demonstrated. The fault coverage achieved is as good as or better than those reported using existing techniques.

Data traffic in modern telecommunications systems is loss-sensitive, delay-insensitive, and highly bursty. Most data applications cannot predict their own traffic parameters, but require low cell loss rates. These features make traffic management for data traffic complex. In ATM networks, where multiple types of applications co-exist, it becomes even more difficult. Many models have been proposed for the flow control of data traffic over ATM networks. Among them the explicit rate (ER) mechanism proposed for the available bit rate (ABR) service is the principal method. The ER and other proposed mechanisms are found to suffer in some regard. These mechanisms also need many buffers in the intermediate switches and thus increase the hardware costs. Flow control based on bandwidth contracting (BCA), can achieve higher bandwidth throughputs at lower hardware costs. In this paper, we evaluate ER and BCA mechanisms in LAN and WAN environments for bursty data traffic. This study focuses on the use of short-term bandwidth contracts for the reliable transport of bursty data.

Boolean equations are important tools in digital logic. Previous algorithms for solving Boolean equations are based on the Boolean algebra of disjoint SOP forms. In this paper, we develop a new Boolean algebra with more efficient Boolean operation algorithms, called the reduced ordered SOP (ROSOP) forms, which are canonical representations. ROSOPs are closely related to the well-known OBDD data structure. The results here also show the algebraic structure of OBDDs.

The ATM Forum has defined a new service category, called the available bit rate service (ABR), which is intended for applications requiring tightly constrained cell loss but no bound on the delay or delay variation. Appropriate traffic control schemes are necessary for ABR service to achieve very low cell loss and maximize the network resource utilization by taking advantage of the available bandwidth remaining after CBR/VBR services have been supported. This paper compares the performance of a burst-level traffic control scheme and a rate-based feedback control scheme, through simulation in an ATM LAN environment. Our results indicate that the burst-level control scheme is more suitable for loss-sensitive but delay-insensitive applications such as ABR service, because it requires nearly zero buffers to achieve zero cell loss and potentially high network resource utilization, at the cost of an acceptable burst transfer delay.

This paper presents an elegant and efficient algorithm for detection of symmetry in Boolean functions represented by ordered binary decision diagrams (OBDDs).

Boolean function complementation is a basic operation of Boolean algebra. For functions given in SOP form, the complementation methods include the DeMorgan's Law, sharp, disjoint sharp, unate complementation, recursive, and Sasao's method. This paper accomplishes three purposes: (1) It exposes an underlying unification of the existing complementation algorithms. It is proven that (a) unate-complementation and sharp are the same as the DeMorgan Law algorithm; (b) Sasao's algorithm is the same as disjoint sharp; (c) disjoint sharp is a special case of the recursive method. (2) It proposes negation trees for the representation of functions and their complements. (3) It gives faster algorithms for finding complements of functions in SOP form based on negation trees.

A graph-based approach to finding near-optimal output phase assignments for PLA minimization is presented. A distinctive feature of the approach is that it exploits the necessary and sufficient conditions to reduce the number of product terms needed for PLA implementation and permits the use of existing graph algorithms to solve the PLA output phase optimization problem. The work is based on the transformation of a PLA into a graph whose vertices are the set of conditions required to reduce each product term of the PLA, and whose edges represent the relations between these conditions. Cliques (completely connected subgraphs) in the graph correspond to the output phase assignments required to reduce the product terms represented by the vertices in the cliques. The optimal PLA output phase assignment problem is then formulated as the well-studied problem in graph theory: finding maximum cliques in graphs. Using an existing algorithm for locating cliques in graphs, a modified greedy algorithm is proposed to compute output phase assignments for logic functions in polynomial time. Experimental results using a number of benchmark functions show that the graph-based approach can achieve optimal or near-optimal output phase assignment for PLA minimization and can lead to PLA's with fewer product terms than achieved using existing approaches.>

A new source of computational saving for test pattern generation, i.e., information reusing, is presented. The proposed technique can make full use of the pattern generation information from the last pattern to derive a set of new tests by means of critical path transitions. By so doing, fault propagation procedure is no longer required in the next pattern generation process and the line justification procedure is simplified. Experiments using the ISCAS-85 benchmark circuits show that when the technique is used with a deterministic test pattern generation algorithm (DTPG), computational cost is greatly reduced without a substantial increase in test length.>