Binary Decision Diagrams

TLDR

The paper proposes a method to define, analyze, test, and implement large digital functions using binary decision diagrams. The authors detail how to derive binary decision diagrams for basic combinational and sequential devices, analyze them, generate tests, obtain implementations, introduce inversion, and interconnect diagrams to build larger functions. The study shows that binary decision diagrams provide a complete, concise, implementation‑free description of digital functions, are well suited for computer processing, and can represent complex circuits such as a carry‑look‑ahead adder.

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.