1993年10月
BEM-II - AN ARITHMETIC BOOLEAN EXPRESSION MANIPULATOR USING BDDS
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
- 巻
- E76A
- 号
- 10
- 開始ページ
- 1721
- 終了ページ
- 1729
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
Recently, there has been a lot of research on solving combinatorial problems using Binary Decision Diagrams (BDDs), which are very efficient representations of Boolean functions. We have already developed a Boolean Expression Manipulator, which calculates and reduces Boolean expressions quickly based on BDD techniques. This greatly aids our works on developing VLSI CAD systems and solving combinatorial problems. Any combinatorial problem can be described in Boolean expressions; however, arithmetic operations, such as addition, subtraction, multiplication, equality and inequality, are also used for describing many practical problems. Arithmetic operations provide simple descriptions of problems in many cases. In this paper, we present an arithmetic Boolean expression manipulator (BEM-II), based on BDD techniques. BEM-II calculates Boolean expressions containing arithmetic operations and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with using 0-1 linear programming. We show the efficient data structure based on BDD representation, algorithms for manipulating Boolean expressions with arithmetic operations, and good formats for displaying the results. Finally we present the specification of BEM-II and an example of application to the 8-Queens problem. BEM-II is customizable to various applications. It has good computation performance in terms of the total time for programming and execution. We expect BEM-II to be a helpful tool in research and development on digital systems.
- リンク情報
- ID情報
-
- ISSN : 0916-8508
- eISSN : 1745-1337
- CiNii Articles ID : 110003215400
- Web of Science ID : WOS:A1993MD78200021