Search

The use of non-binary (multiple-valued) logic in the synthesis of digital systems can lead to savings in chip area. Advances in very large scale integration (VLSI) technology have enabled the successful implementation of multiple-valued logic (MVL) circuits. A number of heuristic algorithms for the synthesis of (near) minimal sum-of products (two-level) realisation of MVL functions have been reported in the literature. The direct cover (DC) technique is one such algorithm. The ant colony optimisation (ACO) algorithm is a meta-heuristic that uses constructive greediness to explore a large solution space in finding (near) optimal solutions. The ACO algorithm mimics the ant's behaviour in the real world in using the shortest path to reach food sources. We have previously introduced an ACO-based heuristic for the synthesis of two-level MVL functions. In this article, we introduce the ACO–DC hybrid technique for the synthesis of multi-level MVL functions. The basic idea is to use an ant to decompose a given MV...

Statistical analysis of multiple intermittent faults (SAMIFs) is proposed as a method for estimating the detection probabilities and fault coverage of multiple intermittent faults in combinational circuits. SAMIFs involves the concurrent simulation of multiple intermittent faults and an estimation of the controllability and observability values for each node of the faulty circuit for a given set of input vectors. The controllabilities and observabilities are then used to derive estimates of the fault-detection probabilities and the overall fault coverage. An algorithm for estimating the fault coverage of a pseudo-random test vector set over a set of multiple intermittent faults in a combinational circuit is also proposed. Experimental results obtained from applying the algorithm to a number of benchmark circuits are also presented.

Testability should be considered as early as possible in VLSI synthesis and optimization. In most CAD tools, testability preservation is achieved as a by-product of finding a less redundant implementation. Unfortunately, this approach is not supported by theory. It is essential to have an optimization scheme that systematically preserves testability. A complete theory covering testability-preserving optimization of combinational circuits is yet to be developed.In this paper, a new testability-preserving theory is established. This theory covers most optimization cases in the synthesis of irredundant circuits. Optimization of redundant circuits is also considered. Algorithms based on this theory are proposed. Experiments to verify the theory and algorithms are reported. The developed theory and algorithms are more general than previous results.

In this brief, a divide-and-conquer based RNS (residue number system) decoding algorithm is proposed. The basic idea of this algorithm is to decompose a set of moduli into groups each of size two moduli and to decode a given number in a two moduli representation. The time complexity of the algorithm used is O(log n), where n is the size of the moduli set. There is no assumption made on the elements of the module set. In addition, the algorithm requires less ROM size and smaller size module adders compared to those required by existing approaches.

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 fault simulation method, deductive critical path tracing (D-CPT), for very large combinational circuits is proposed. The simulator uses both the deductive fault propagation technique (used in deductive fault simulation (DFS)) and the critical path tracing (CPT) method in forming the D-CPT. Deductive fault propagation is not performed on the whole fault set of a circuit as in DFS but instead only on a partial fault set, i.e., those faults on fanout stems. The capture lines of each fanout fault are determined, and used to resolve the difficulty in determining the criticality of a fanout stem during the CPT process. Furthermore, the huge storage requirement of DFS is sharply reduced to an acceptable level when handling very large circuits. Experiments on ISCAS benchmark circuits show that the proposed method is both efficient and complete.

Hierarchical interconnection networks (HINs) provide a framework for designing networks with reduced link cost by taking advantage of the locality of communication that exists in parallel applications. HINs employ multiple levels. Lower-level networks provide local communication while higher-level networks facilitate remote communication. HINs provide fault tolerance in the presence of some faulty nodes and/or links. Existing HINs can be broadly classified into two classes. those that use nodes and/or links replication and those that use standby interface nodes. The first class includes Hierarchical Cubic Networks, Hierarchical Completely Connected Networks, and Triple-based Hierarchical Interconnection Networks. The second HINs class includes Modular Fault-Tolerant Hypercube Networks and Hierarchical Fault-Tolerant Interconnection Network. This paper presents a review and comparison of the topological properties of both classes of HINs. The topological properties considered are network degree, diameter, cost and packing density. The outcome of this study show among all HINs two networks that is, the Root-Folded Heawood (RFH) and the Flooded Heawood (FloH), belonging to the first HIN class provide the best network cost, defined as the product of network diameter and degree. The study also shows that HFCube(n,n)provide the best packing density, that is, the smallest chip area required for VLSI implementation.

Optimizing the number of transistors in a complex MOS gate, which is important for minimizing chip area and delay in VLSI designs, is an NP-complete problem. The worst-case computational complexity of graph-oriented algorithms used in existing approaches is exponential in the number of transistors. This problem is addressed through the use of bridging switches. A theory and an algorithm for optimization of MOS switch networks using an edge-merging technique are proposed. The worst-case computational complexity of the heuristic algorithm proposed is O(n/sup 5/e/sup 2/), where n is the number of nodes and e is the number of edges in the switch network. >

A checker/corrector system has stronger fault-tolerant ability than a checker system. The design of a totally self-checking checker/corrector (TSC3) circuit is considered. The TSC property for checker/corrector systems is defined. One of the critical issues in designing a TSC3 is that the test vectors for detecting the faults in the corrector may not occur in normal operation. A self-exercising method to solve this problem is proposed. A design of self-exercising TSC3 for a two-dimensional error-correcting code is given as an example.

A 2-bit decoder programmable logic array (PLA) is an array of transistors that realizes the sum of products (realized by rows of transistors) of inputs taken from the outputs of 2-input 4-output decoders. Functions of several variables, which are assigned to the decoder inputs using Tomczuk and Miller's heuristic algorithm to pair closely related variables using the autocorrelation of the functions, are realized using reduced area PLAs. The number of product rows (representing product terms) used in such PLAs, which is a function of the assignment of pairs of variables to the decoders, is reduced using simulated annealing techniques which are applied to permuting the assignment of input variables to the decoder inputs.

A new structure is proposed for the realization of multiple-valued logic (MVL) functions. Multiple-valued logic levels are represented in terms of current values, which represent the inputs and the outputs of the MVL circuits. Binary voltage signals are generated inside the structure by using a circuit element called threshold. Using these voltage signals and binary operators, such as AND, OR, XOR and inverter, binary voltage signals are obtained and used as control signals for generating the output current levels for the desired MVL function. The realizations of some example MVL circuits using the proposed structure are included along with HSPICE transient analysis simulation results to verify the functionality of the designed circuits.

A CMOS circuit implementation of a functionally complete multiple-valued logic (MVL) set of operators is proposed. The set consists of literal, cycle, complement of literal, complement of cycle, min, and tsum operators. In all of the circuits, multiple-valued logic levels are represented in terms of current values. Binary voltage signals are generated inside the circuits using a threshold circuit element. These binary voltage signals are used to generate control signals for switches to realize appropriate current levels for the desired multiple-valued logic levels. Transient analysis simulations (using HSPICE) to verify the functionality of the designed circuits and the effect of variation in process parameters are also reported. >

For pt. I see ibid vol. 40, no. 8 p 503-14 (1993). The performance of the set of operators proposed in pt. I is compared with existing sets of operators for the realization of multiple-valued logic (MVL) functions. In pt. I, a set of operators was proposed consisting of literal, cycle, complement of literal, complement of cycle, min, and tsum operators (Set 1). This set of operators is compared to two existing sets of operators consisting of literal, complement of literal, min, and tsum operators (Set 2) and literal, min, and tsum operators (Set 3). For 3-valued 2-variable MVL functions, it is shown that the maximum number of product terms (PTs) required to realize all functions can be reduced to three PTs (using the Set 1 operators) from five PTs (using the Set 2 operators) and six PTs (using the Set 3 operators). In addition, it is shown that the average number of PTs required to realize all the functions reduces to 2.61 (using the Set 1 operators) from 3.19 (using the Set 2 operators) and 3.61 (using the Set 3 operators). It is anticipated that similar improvements are possible for higher valued logic. Realizations of a 4-valued 2-variable function based on different sets of operators are included to support such a claim. >

The use of programmable logic array structures for the implementation of multi-valued multi-threshold (MVMT) functions using charge-coupled device technology is considered. Two new such structures for the implementation of MVMT functions are introduced. The number of functions realized using these structures is shown to be larger than those realized using previously proposed structures. The new structures are dynamically reprogrammable at the user level by controlling the thresholds of the gates used. One of the proposed structures is superior to the other in terms of the number of functions realized per one column. However, this increase in functionality is achieved at the expense of increasing the number of gates per column by 50%.

A binary-to-quaternary encoder and quaternary-to-binary decoder circuit pair is proposed. Two non-zero voltage levels and two pulse durations are used to define a 4-valued logic scheme. We have simulated the encoder and decoder circuits using model parameters for standard CMOS technology and minimum geometry devices. An average amplitude decoder delay of 10 ns has been recorded using Hspice simulator transient analysis. Width decoder delays of respectively 50 and 75 ns for the rising and the trailing transitions of the encoded signal have been recorded. Since only two voltage levels have to be distinguished, the noise immunity and logic level tolerances are improved, compared to the case where four different voltage levels have to be distinguished using existing approaches. This improvement is achieved at the expense of the greater bandwidth needed for transmission of signals using the proposed scheme.

Programmable logic array (PLA) structures are investigated for the implementation of multi-valued multi-threshold functions using charge-coupled device technology. A new PLA structure is introduced for this purpose. It is shown that the number of functions realized using this structure is larger than those realized using an existing PLA structure. The new structure exhibits the desirable feature of being dynamically reprogrammable at the user level by controlling the thresholds of the gates used.

In the above titled paper (ibid., vol 54, no. 12, pp. 2683-2695), the first paragraph of Section I (p. 2683), was incomplete. The correct paragraph is presented here.

A number of decomposition based mapping techniques are proposed. In these techniques, the synthesis problem is formulated as a mapping from an input matrix to an output matrix. The minimisation is obtained by constructing a 'matching-count matrix'. The entries of the matching-count matrix MC ij represent the number of entry matches between the input variable number i in the input matrix (X) and the output function number j in the output matrix (Y). It then selects those input-output pairings that give the maximum matching count, thus maximising the number of switching operations which can be eliminated in the realisation of multiple-valued logic (MVL) functions. The proposed techniques are classified as: output-phase with complement, input-phase with and without complement. Numerical results are presented to show that the proposed techniques result in significant reduction in the number of switching operators required for the implementation of 5000 randomly generated r-valued functions (for r = 3, 4 and 5). It is also shown that the input-phase assignment techniques do not require any additional hardware circuitry at the output to restore the original function. This may give this technique an edge over other techniques.

Several approaches have been developed for the synthesis of one-variable 4-valued functions using CCDs. In all these approaches an attempt has been made to reduce the cost of implementing a given function. In this paper, we propose a new approach for the synthesis of such functions. Starting at zero cost, a search is conducted for the possible functions that can be realized using basic CCD gate structures. These functions are recorded in a list. At a given cost C, each of the four possibilities of using addition, overflow, inhibit, and multiplication as an output gate is considered. For each possibility, the set of possible inputs to the gate are determined and used. Only those outputs which are not covered at lower costs are added to the list. The cost is then incremented by one and the search is repeated for new functions. The process terminates when all possible 256 functions are in the list. Using this approach, it is shown that in 195 functions (76% of the total) there is a cost improvement compared ...