Binary Decision Diagrams

1978/06/01 by Akers · 1,831 citations
Computer Science · Engineering · Mathematics · #Adder #Algorithm #Arithmetic #Binary decision diagram #Binary number #Computer science #Data mining #Decision tree #Diagram #Digital electronics #Embedded Systems and FPGA Applications #Formal Methods in Verification #Implementation #Influence diagram #Latency (audio) #Mathematics #Programming language #Theoretical computer science #VLSI and Analog Circuit Testing

paper · doi:10.1109/tc.1978.1675141

published in IEEE Transactions on Computers C-27(6), 509-516 (Institute of Electrical and Electronics Engineers)

openalex publication_date 1978/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/10

Abstract

This paper describes a method for defining, analyzing, testing, and implementing large digital functions by means of a binary decision diagram. This diagram provides a complete, concise, "implementation-free" description of the digital functions involved. Methods are described for deriving these diagrams and examples are given for a number of basic combinational and sequential devices. Techniques are then outlined for using the diagrams to analyze the functions involved, for test generation, and for obtaining various implementations. It is shown that the diagrams are especially suited for processing by a computer. Finally, methods are described for introducing inversion and for directly "interconnecting" diagrams to define still larger functions. An example of the carry look-ahead adder is included.

Cited by

• Toward robust integrated circuits: The embryonics approach
• Graph-Based Algorithms for Boolean Function Manipulation
• Skolem Functions for Factored Formulas
• Integrated Task and Motion Planning for Safe Legged Navigation in Partially Observable Environments
• SNAP: Stateful Network-Wide Abstractions for Packet Processing
• pForest: In-Network Inference with Random Forests
• Symmetric Logic Synthesis with Phase Assignment
• A Canonical Partition of the Primes of Logic Functions
• Social Influence as a Voting System: a Complexity Analysis of Parameters and Properties
• Proceedings of the Fifth International Workshop on Automated Debugging (AADEBUG 2003)
• Event-Flow Graphs for Efficient Path-Sensitive Analyses
• Building Very Small Test Suites (with Snap)
• Resolution Simulates Ordered Binary Decision Diagrams for Formulas in Conjunctive Normal Form
• Ackermann Encoding, Bisimulations, and OBDDs
• Large Random Forests: Optimisation for Rapid Evaluation
• An algorithm to compute the Hoffman constant of a system of linear constraints
• Model Checking in The COSMA Environment as a Support for The Design of Pipelined Processing
• BDDs Naturally Represent Boolean Functions, and ZDDs Naturally Represent Sets of Sets
• Technical Report: Directed Controller Synthesis of Discrete Event\n Systems
• First-Order vs. Second-Order Encodings for LTLf-to-Automata Translation
• Interventions and Counterfactuals in Tractable Probabilistic Models: Limitations of Contemporary Transformations
• A Brief Tour of Logic and Optimization
• Modified Fredkin gates in logic design
• The Beginning of Model Checking: A Personal Perspective
• Computing the Tutte polynomial of a graph of moderate size
• Advanced Many-Valued Logics
• Towards Parallel Boolean Functional Synthesis
• A Unifying Framework for Reinforcement Learning and Planning. [europepmc]
• A Kamm's Circle-Based Potential Risk Estimation Scheme in the Local Dynamic Map Computation Enhanced by Binary Decision Diagrams. [europepmc]
• Detection of Physical Activity Using Machine Learning Methods Based on Continuous Blood Glucose Monitoring and Heart Rate Signals. [europepmc]
• Developmental transcriptomics in Pristionchus reveals the environmental responsiveness of a plasticity gene-regulatory network. [europepmc]
• Availability of drone mission with binary decision diagram based on uncertain data. [europepmc]

Related

• Compressing Binary Decision Diagrams
• Synthesis of Low-Power Digital Circuits Derived from Binary Decision Diagrams
• Chain Reduction for Binary and Zero-Suppressed Decision Diagrams
• HermesBDD: A Multi-Core and Multi-Platform Binary Decision Diagram Package
• On the Relative Succinctness of Sentential Decision Diagrams