Article

Free access

Shared binary decision diagram with attributed edges for efficient Boolean function manipulation

Authors:

Shin-ichi Minato,

Nagisa Ishiura,

Shuzo YajimaAuthors Info & Claims

DAC '90: Proceedings of the 27th ACM/IEEE Design Automation Conference

Pages 52 - 57

https://doi.org/10.1145/123186.123225

Published: 03 January 1991 Publication History

PDF eReader

Abstract

The efficiency of Boolean function manipulation depends on the form of representation of Boolean functions. Binary Decision Diagrams (BDD's) are graph representations proposed by Akers and Bryant. BDD's have some properties which can be used to enable efficient Boolean function manipulation.

In this paper, we describe a technique of more efficient Boolean function manipulation that uses Shared Binary Decision Diagrams (SBDD's) with attributed edges. Our implements include an ordering algorithm of input variables and a method of handling don't care. We show experimental results produced by the implementation of the Boolean function manipulator.

References

[1]

S. B. Akers: "Binary Decision Diagram", IEEE Trans. on Computers, Vol. C-27, No. 6, pp. 509- 516, (June, 1978).

Google Scholar

[2]

R. E. Bryant: "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Trans. on Computers, Vol. C-35, No. 8, pp. 677-691, (August, 1985).

Digital Library

Google Scholar

[3]

J. C. Madre and J. P. Billon: "Proving Circuit Correctness using Formal Comparison Between Expected and Extracted Behaviour", Proc. 25th A CM/IEEE DAC, pp. 205-210, (June, 1988).

Digital Library

Google Scholar

[4]

K. Cho and R. E. Bryant: "Test Pattern Generation for Sequential M OS Circuits by Symbolic Fault Simulation", Proc. ~6th A CM/IEEE DA C, pp. 418- 423, (june, 1989).

Digital Library

Google Scholar

[5]

F. Brglez, H. Fujiwara: "A neutral netlist of 10 combinational circuits", Special Session on A TPG and Fault Simulation, Proc. 1985 IEEE International Symposium Circuit and Systems, Kyoto, Jap an, (June, 1985).

Google Scholar

[6]

M. Fujita, H. Fujisawa and N. Kawato: "Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams", IEEE ICCAD-88 Tech. Papers, pp. 2-5, (November, 1988).

Google Scholar

[7]

S. Malik, A. R. Wang, R. K. Brayton and A. S. Vimcentelli: "Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment" IEEE ICCAD-88 Tech. Papers, pp. 6-9, (November, 1988).

Google Scholar

Cited By

View all

Thijssen SRashed MJha SEwetz R(2024)PATH: Evaluation of Boolean Logic Using Path-Based In-Memory Computing SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334452343:5(1387-1400)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3344523
Lu PDeng TZhang HJin YLiu FMao TLiu L(2024)Ontology-Mediated Query Answering Using Graph Patterns with Conditions2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00036(382-395)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00036
Gunnarsdóttir EIngólfsdóttir A(2024)The EM-BDD Algorithm For Learning Hidden Markov ModelsLeveraging Applications of Formal Methods, Verification and Validation. Rigorous Engineering of Collective Adaptive Systems10.1007/978-3-031-75107-3_8(121-138)Online publication date: 27-Oct-2024
https://doi.org/10.1007/978-3-031-75107-3_8
Show More Cited By

Index Terms

Shared binary decision diagram with attributed edges for efficient Boolean function manipulation

Recommendations

An Efficient Method of Computing Generalized Reed-Muller Expansions from Binary Decision Diagram

An efficient method for the generation of all the 2/sup n/ sets of generalized Reed-Muller (GRM) coefficients for a Boolean function f(X) of n variables using the binary decision diagram (BDD) is presented. The author describes the generation of RM ...
A construction of binary linear codes from Boolean functions

Boolean functions have important applications in cryptography and coding theory. Two famous classes of binary codes derived from Boolean functions are the Reed-Muller codes and Kerdock codes. In the past two decades, a lot of progress on the study of ...
Decomposition of a system of incompletely specified Boolean functions defined with a binary decision diagram

We propose a decomposition method for systems of incompletely specified Boolean functions represented as binary decision diagrams. Minimizing the number of intermediate functions in such a decomposition is intended to improve the performance of Boolean ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '90: Proceedings of the 27th ACM/IEEE Design Automation Conference

January 1991

742 pages

ISBN:0897913639

DOI:10.1145/123186

Chairman:
Richard C. Smith

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC90

Sponsor:

SIGDA
IEEE-CS

DAC90: The 27th ACM/IEEE-CS Design Automation Conference

June 24 - 27, 1990

Florida, Orlando, USA

Acceptance Rates

DAC '90 Paper Acceptance Rate 125 of 427 submissions, 29%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

170
Total Citations
View Citations
975
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)39

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Thijssen SRashed MJha SEwetz R(2024)PATH: Evaluation of Boolean Logic Using Path-Based In-Memory Computing SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334452343:5(1387-1400)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3344523
Lu PDeng TZhang HJin YLiu FMao TLiu L(2024)Ontology-Mediated Query Answering Using Graph Patterns with Conditions2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00036(382-395)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00036
Gunnarsdóttir EIngólfsdóttir A(2024)The EM-BDD Algorithm For Learning Hidden Markov ModelsLeveraging Applications of Formal Methods, Verification and Validation. Rigorous Engineering of Collective Adaptive Systems10.1007/978-3-031-75107-3_8(121-138)Online publication date: 27-Oct-2024
https://doi.org/10.1007/978-3-031-75107-3_8
Sølvsten SRysgaard CVan de Pol J(2024)Random Access on Narrow Decision Diagrams in External MemoryModel Checking Software10.1007/978-3-031-66149-5_7(137-145)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-66149-5_7
Kwashie SKang WSanthosh Kumar SJarrad GCamtepe SNepal S(2024)Acumen: Analysing the Impact of Organisational Change on Users’ Access EntitlementsComputer Security – ESORICS 202310.1007/978-3-031-51482-1_21(410-430)Online publication date: 11-Jan-2024
https://doi.org/10.1007/978-3-031-51482-1_21
Bryant RHeule M(2023)Generating Extended Resolution Proofs with a BDD-Based SAT SolverACM Transactions on Computational Logic10.1145/359529524:4(1-28)Online publication date: 25-Jul-2023
https://dl.acm.org/doi/10.1145/3595295
Sølvsten Svan de Pol J(2023)Predicting Memory Demands of BDD Operations Using Maximum Graph CutsAutomated Technology for Verification and Analysis10.1007/978-3-031-45332-8_4(72-92)Online publication date: 19-Oct-2023
https://doi.org/10.1007/978-3-031-45332-8_4
Kumar AWagatsuma H(2022)A Kamm’s Circle-Based Potential Risk Estimation Scheme in the Local Dynamic Map Computation Enhanced by Binary Decision DiagramsSensors10.3390/s2219725322:19(7253)Online publication date: 24-Sep-2022
https://doi.org/10.3390/s22197253
Bai ZCassé HDe Michiel MCarle TRochange C(2022)A Framework for Calculating WCET Based on Execution Decision DiagramsACM Transactions on Embedded Computing Systems10.1145/347687921:3(1-26)Online publication date: 28-May-2022
https://dl.acm.org/doi/10.1145/3476879
Sølvsten Sde Pol JJakobsen AThomasen M(2022)Adiar Binary Decision Diagrams in External MemoryTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-030-99527-0_16(295-313)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-030-99527-0_16
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An Efficient Method of Computing Generalized Reed-Muller Expansions from Binary Decision Diagram

A construction of binary linear codes from Boolean functions

Decomposition of a system of incompletely specified Boolean functions defined with a binary decision diagram