Minimum One-Shot State Assignment for Asynchronous Sequential Machines Using BDD
スポンサーリンク
概要
- 論文の詳細を見る
We propose a new method of the one-shot state assignment for asynchronous sequential circuits, in which propositional calculus, or Boolean algebra is adopted. Exact minimum solutions of the one-shot state assignment are obtained by our method for the first time. In order to handle huge propositional formulas, the shared binary decision diagrams (SBDD's) are used as an internal representation of the formulas. Several solving methods are also proposed to reduce the size of SBDD's : applying of coded Boolean variables, 2SAT and filtering functions. Although we succeeded now only in the one-shot state assignment for small problems, having new machines capable of handling larger SBDD's, much bigger problems could be solved with this approach. moreover, we propose a heuristic algorithm for solving big and practical problems which are regarded as being beyond the ability of the current SBDD package. Experimental results show that our methods are effective to obtain minimum solutions at significantly reduced computation cost.
- 一般社団法人情報処理学会の論文
- 1994-09-15
著者
-
Kwon Y‐j
Department Of Information Science Faculty Of Engineering Kyoto University
-
Yajima Shuzo
Department Of Information Science Kyoto University
-
Kwon Yong-jin
Department of Information Science, Faculty of Engineering, Kyoto University
-
Kwon Yong-jin
Department Of Information Science Faculty Of Engineering Kyoto University
-
Yajima Shuzo
Department Of Information Science Facu1ty Of Engineering Kyoto University
関連論文
- A Computer Communication Control Technique for Virtualization of Network Memory Resources and Its Implementation
- Regular Temporal Logic Expressively Equivalent to Finite Automata and Its Application to Logic Design Verification
- Locally Exhaustive Testing of Combinational Circuits Using Linear Logic Circuits
- Minimum One-Shot State Assignment for Asynchronous Sequential Machines Using BDD
- The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
- A Raster-scan Computer Graphic Display Device Having Random-scan Functions with Color Specifying Light Pen Facility
- Combinatorial Algorithms Using Boolean Processing
- Minimum Single Transition-Time Assignments for Asynchronous Sequential Circuits Using BDD