The Experts below are selected from a list of 168 Experts worldwide ranked by ideXlab platform
J.c. Madre - One of the best experts on this subject based on the ideXlab platform.
-
MetaPrime: an interactive fault-tree analyzer
IEEE Transactions on Reliability, 1994Co-Authors: O. Coudert, J.c. MadreAbstract:The performances of almost all available fault tree analysis tools are limited by the performance of their Prime Implicant computation procedure. All these procedures manipulate the Prime Implicants of the fault trees in extension, so that the analysis costs are directly related to the number of Prime Implicants to be generated, which in practice makes these tools difficult to apply on fault trees with more than 20 000 Prime Implicants. This paper introduces an analysis method of coherent as well as noncoherent fault trees that overcomes this limitation because its computational cost is related to neither the number of basic events, nor the number of gates, nor the number of Prime Implicants of these trees. The authors present the concepts underlying the prototype tool MetaPrime, and the experimental results obtained with this tool on real fault trees. These results show that these concepts provide complete analysis in seconds on fault trees that no previously available technique could ever even partially analyze, for instance noncoherent fault trees with more than 10/sup 20/ Prime Implicants. These concepts can also be used to analyze event trees because such trees denote Boolean functions on which these concepts can be applied. Prime Implicant computation is also critical in many other domains, in particular in expert system applications such as reasoning maintenance and multiple fault diagnosis. The application of the concepts underlying MetaPrime to the resolution of these problems is under study.
-
Fault tree analysis: 10/sup 20/ Prime Implicants and beyond
Annual Reliability and Maintainability Symposium 1993 Proceedings, 1993Co-Authors: O. Coudert, J.c. MadreAbstract:The performances of almost all available fault tree analysis tools are limited by the performance of the Prime Implicant computation procedure used. All these products manipulate the Prime Implicants of the fault trees explicitly, so that their complexities are directly related to the number of Prime Implicants to be generated. The authors present a novel analysis method of coherent as well as noncoherent fault trees that overcomes this limitation because its computational cost is not related to the number of variables, gates, or Prime Implicants of these trees. The interactive fault tree analyzer MetaPrime based on this new method has been shown by experience to be able to perform in seconds the complete analysis of noncoherent fault trees with more than 10/sup 20/ Prime Implicants.
-
fault tree analysis 1020 Prime Implicants and beyond
1993Co-Authors: Olivier Coudert, J.c. MadreAbstract:The performances of almost all available fault tree analysis tools are limited by the performance of the Prime Implicant computation procedure they use. All these procedures manipulate the Prime Implicants of the fault trees explicitly, so that their complexities are directly related to the number of Prime Implicants to be generated. This paper presents a new analysis method of coherent as well as noncoherent fault trees that overcomes this limitation because its computational cost is not related to either the number of variables or the number of gates or the number of Prime Implicants of these trees. The interactive fault tree analyser METAPrime that is based on this new method has been shown by experience to be able to perform in seconds the complete analysis of noncoherent fault trees with more than 10 Prime Implicants.
Shun-wen Cheng - One of the best experts on this subject based on the ideXlab platform.
-
VLSI Design - Prioritized Prime Implicant Patterns Puzzle for Novel Logic Synthesis and Optimization
Proceedings of ASP-DAC VLSI Design 2002. 7th Asia and South Pacific Design Automation Conference and 15h International Conference on VLSI Design, 2002Co-Authors: Kuo-hsing Cheng, Shun-wen ChengAbstract:Comparing CMOS logic with pass-transistor logic, a question was raised in the minds of the authors: "does any rule exist that contains all good?" This paper reveals novel logic synthesis and optimization procedures for full swing arbitrary logic function. The novel procedures are called prioritized Prime Implicant patterns puzzle (PPIPP). Following the proposed procedures, we can get a new hybrid high performance logic circuit family, which has low power consumption, low power-delay product, area efficiency and is suitable for low supply voltage. It has full swing signal in all nodes and high robustness against transistor downsizing and voltage scaling.
-
Prioritized Prime Implicant patterns puzzle for novel logic synthesis and optimization
Proceedings of ASP-DAC VLSI Design 2002. 7th Asia and South Pacific Design Automation Conference and 15h International Conference on VLSI Design, 2002Co-Authors: Kuo-hsing Cheng, Shun-wen ChengAbstract:Comparing CMOS logic with pass-transistor logic, a question was raised in the minds of the authors: "does any rule exist that contains all good?" This paper reveals novel logic synthesis and optimization procedures for full swing arbitrary logic function. The novel procedures are called prioritized Prime Implicant patterns puzzle (PPIPP). Following the proposed procedures, we can get a new hybrid high performance logic circuit family, which has low power consumption, low power-delay product, area efficiency and is suitable for low supply voltage. It has full swing signal in all nodes and high robustness against transistor downsizing and voltage scaling.
O. Coudert - One of the best experts on this subject based on the ideXlab platform.
-
MetaPrime: an interactive fault-tree analyzer
IEEE Transactions on Reliability, 1994Co-Authors: O. Coudert, J.c. MadreAbstract:The performances of almost all available fault tree analysis tools are limited by the performance of their Prime Implicant computation procedure. All these procedures manipulate the Prime Implicants of the fault trees in extension, so that the analysis costs are directly related to the number of Prime Implicants to be generated, which in practice makes these tools difficult to apply on fault trees with more than 20 000 Prime Implicants. This paper introduces an analysis method of coherent as well as noncoherent fault trees that overcomes this limitation because its computational cost is related to neither the number of basic events, nor the number of gates, nor the number of Prime Implicants of these trees. The authors present the concepts underlying the prototype tool MetaPrime, and the experimental results obtained with this tool on real fault trees. These results show that these concepts provide complete analysis in seconds on fault trees that no previously available technique could ever even partially analyze, for instance noncoherent fault trees with more than 10/sup 20/ Prime Implicants. These concepts can also be used to analyze event trees because such trees denote Boolean functions on which these concepts can be applied. Prime Implicant computation is also critical in many other domains, in particular in expert system applications such as reasoning maintenance and multiple fault diagnosis. The application of the concepts underlying MetaPrime to the resolution of these problems is under study.
-
Fault tree analysis: 10/sup 20/ Prime Implicants and beyond
Annual Reliability and Maintainability Symposium 1993 Proceedings, 1993Co-Authors: O. Coudert, J.c. MadreAbstract:The performances of almost all available fault tree analysis tools are limited by the performance of the Prime Implicant computation procedure used. All these products manipulate the Prime Implicants of the fault trees explicitly, so that their complexities are directly related to the number of Prime Implicants to be generated. The authors present a novel analysis method of coherent as well as noncoherent fault trees that overcomes this limitation because its computational cost is not related to the number of variables, gates, or Prime Implicants of these trees. The interactive fault tree analyzer MetaPrime based on this new method has been shown by experience to be able to perform in seconds the complete analysis of noncoherent fault trees with more than 10/sup 20/ Prime Implicants.
A.r. Newton - One of the best experts on this subject based on the ideXlab platform.
-
Optimum and heuristic algorithms for an approach to finite state machine decomposition
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991Co-Authors: Pranav Ashar, S. Devadas, A.r. NewtonAbstract:Optimum and heuristic algorithms for the general decomposition of finite state machines (FSMs) such that the sum total of the number of product terms in the one-hot-coded and logic-minimized submachines is minimum or minimal are presented. This cost function is much more reflective of the area of an optimally state-assigned and minimized submachine than the number of states/edges in the submachine. The problem of optimum two-way FSM decomposition is formulated as one of symbolic output partitioning, and it is shown that this is an easier problem than optimum state assignment. A procedure of constrained Prime Implicant generation and covering that represents an optimum FSM decomposition algorithm, under the specified cost function, is described. It is shown that by means of this formulation, arbitrary decomposition topologies can be targeted by suitably modifying the constraints on the ability to encode during the covering. A novel iterative optimization strategy of symbolic Implicant expansion and reduction, modified from two-level Boolean minimizers, that represents a heuristic algorithm based on the exact procedure is presented. Reduction and expansion are performed on functions with symbolic rather than binary-valued outputs. Preliminary experimental results that illustrate both the efficacy of the proposed algorithms and the validity of the selected cost function are presented.
-
Exact algorithms for output encoding, state assignment, and four-level Boolean minimization
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991Co-Authors: S. Devadas, A.r. NewtonAbstract:A novel minimization procedure of Prime Implicant generation and covering that operates on symbolic outputs, rather than binary-valued outputs, is proposed for solving the output encoding problem. An exact solution to this minimization problem is also an exact solution to the encoding problem. While this covering problem is more complex than the classic unate covering problem, a single logic minimization step replaces O(N-factorial) minimizations. The input encoding problem can be exactly solved using multiple-valued Boolean minimization. An exact algorithm is presented for state assignment by generalizing the proposed output encoding approach to the multiple-valued input case. Four-level Boolean minimization entails finding a cascaded pair of two-level logic functions that implement another logic function, such that the sum of the product terms in the two cascaded functions or truth tables is minimum. Four-level Boolean minimization can be formulated as an encoding problem and solved exactly using the proposed algorithms. Preliminary experimental results are presented which indicate that this approach is significantly more efficient than exhaustive search. Computationally efficient heuristic approaches based on the exact algorithms are proposed for output encoding, state assignment, and four-level Boolean minimization.
-
Exact algorithms for output encoding, state assignment and four-level Boolean minimization
Twenty-Third Annual Hawaii International Conference on System Sciences, 1990Co-Authors: S. Devadas, A.r. NewtonAbstract:A minimization procedure of Prime-Implicant generation and covering that operates on symbolic outputs rather than binary-valued outputs is proposed for solving the output encoding problem. An exact solution to this minimization problem is also an exact solution to the encoding problem. While this covering problem is more complex than the classic unate covering problem, a single O(N factorial) logic minimization step replaces O(N factorial) minimizations. An exact algorithm is presented for state assignment by generalizing the output encoding approach to the multiple-valued input case. Preliminary experimental results are presented which indicate that medium-sized problems can be solved exactly. Computationally efficient heuristic approaches based on the exact algorithms are proposed for output encoding, state assignment, and four-level Boolean minimization.
S. Devadas - One of the best experts on this subject based on the ideXlab platform.
-
Exact algorithms for output encoding, state assignment, and four-level Boolean minimization
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991Co-Authors: S. Devadas, A.r. NewtonAbstract:A novel minimization procedure of Prime Implicant generation and covering that operates on symbolic outputs, rather than binary-valued outputs, is proposed for solving the output encoding problem. An exact solution to this minimization problem is also an exact solution to the encoding problem. While this covering problem is more complex than the classic unate covering problem, a single logic minimization step replaces O(N-factorial) minimizations. The input encoding problem can be exactly solved using multiple-valued Boolean minimization. An exact algorithm is presented for state assignment by generalizing the proposed output encoding approach to the multiple-valued input case. Four-level Boolean minimization entails finding a cascaded pair of two-level logic functions that implement another logic function, such that the sum of the product terms in the two cascaded functions or truth tables is minimum. Four-level Boolean minimization can be formulated as an encoding problem and solved exactly using the proposed algorithms. Preliminary experimental results are presented which indicate that this approach is significantly more efficient than exhaustive search. Computationally efficient heuristic approaches based on the exact algorithms are proposed for output encoding, state assignment, and four-level Boolean minimization.
-
Optimum and heuristic algorithms for an approach to finite state machine decomposition
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991Co-Authors: Pranav Ashar, S. Devadas, A.r. NewtonAbstract:Optimum and heuristic algorithms for the general decomposition of finite state machines (FSMs) such that the sum total of the number of product terms in the one-hot-coded and logic-minimized submachines is minimum or minimal are presented. This cost function is much more reflective of the area of an optimally state-assigned and minimized submachine than the number of states/edges in the submachine. The problem of optimum two-way FSM decomposition is formulated as one of symbolic output partitioning, and it is shown that this is an easier problem than optimum state assignment. A procedure of constrained Prime Implicant generation and covering that represents an optimum FSM decomposition algorithm, under the specified cost function, is described. It is shown that by means of this formulation, arbitrary decomposition topologies can be targeted by suitably modifying the constraints on the ability to encode during the covering. A novel iterative optimization strategy of symbolic Implicant expansion and reduction, modified from two-level Boolean minimizers, that represents a heuristic algorithm based on the exact procedure is presented. Reduction and expansion are performed on functions with symbolic rather than binary-valued outputs. Preliminary experimental results that illustrate both the efficacy of the proposed algorithms and the validity of the selected cost function are presented.
-
Minimization of functions with multiple-valued outputs: theory and applications
Proceedings of the Twentieth International Symposium on Multiple-Valued Logic, 1990Co-Authors: S. DevadasAbstract:A theoretical framework for the minimization of logic functions with symbolic or multiple-valued outputs is presented. By use of this framework, efficient, exact algorithms for the problems of output encoding and finite-state-machine (FSM) state assignment are developed. All previous automatic approaches to these encoding problems have involved the use of heuristic techniques. A notion of generalized Prime Implicants is presented for functions with multiple-valued outputs, and a novel minimization procedure of Prime Implicant generation and covering for solving the output encoding problem is proposed. An optimum solution to this covering problem is also an optimum solution to the encoding problem. A single logic minimization step thus replaces on the order of n-factorial minimizations required by straightforward exhaustive search. It has been shown previously that the input encoding problem can be exactly solved using Boolean minimization over functions with multiple-valued inputs. An extension of the presented algorithm that handles functions with multiple-valued inputs and outputs can be used to solve the state assignment problem exactly. Experimental results are presented for a set of examples.
-
Exact algorithms for output encoding, state assignment and four-level Boolean minimization
Twenty-Third Annual Hawaii International Conference on System Sciences, 1990Co-Authors: S. Devadas, A.r. NewtonAbstract:A minimization procedure of Prime-Implicant generation and covering that operates on symbolic outputs rather than binary-valued outputs is proposed for solving the output encoding problem. An exact solution to this minimization problem is also an exact solution to the encoding problem. While this covering problem is more complex than the classic unate covering problem, a single O(N factorial) logic minimization step replaces O(N factorial) minimizations. An exact algorithm is presented for state assignment by generalizing the output encoding approach to the multiple-valued input case. Preliminary experimental results are presented which indicate that medium-sized problems can be solved exactly. Computationally efficient heuristic approaches based on the exact algorithms are proposed for output encoding, state assignment, and four-level Boolean minimization.