Binary Decision Diagrams: From Abstract Representations to Physical Implementations

The Binary Decision Diagram ( BDD ) has established its place as a modelling technique for digital systems. The paper shows that further significant benefits can be realized by implementing BDDs as custom or semi-custom integrated circuits. Benefits include efficient use of silicon area and improved simulation. A well-known example is given of a traffic light controller previously implemented by a PLA. The BDD layout is regular, compact and lends itself to automatic generation. A sample worst-case circuit simulation is included.