Structurally Synthesized BDDs

In this Chapter, we present the theoretical basics of structural BDDs considering, first, the model of Structurally Synthesized BDDs (SSBDDs) and then the more concise model of Shared SSBDDs (S3BDDs). We present the definitions of the models and the methods of synthesis of the models from the descriptions of the given gate-level circuits. We discuss the main properties of the graphs, describe their relationships to Boolean algebra and compare them with traditional BDDs. We also consider the issues of optimization of the models by introducing the theory of equivalent transformation of SSBDDs and developing the lower bounds of the sizes of S3BDDs created from a given gate-level circuit.