Binary Decision Diagrams and MUX Networks
April 26, 2021

A binary decision diagram can be read as a structured network of conditional choices. In circuit terms, that is close to a MUX network. In programming terms, it is close to an if-then-else tree.

The useful connection is between EDA representation and programming conditionals: a Boolean decision structure can be both a data structure and a physical implementation path.

Boolean-representation noteOriginally posted 2021-04-26; expanded here around BDDs and MUX networks.

Related: Boolean Algebra Is All That Is Required

Article focus: binary decision diagrams, MUX networks, if-then-else trees, and EDA representation.

The Representation

The original note compared binary decision diagrams with MIG, AIG, DNF, and CNF representations. The BDD path is interesting because it can be understood as a network of multiplexers.

That makes the representation readable from two directions: EDA can see a Boolean structure, and a programmer can see nested conditionals.

https://lnkd.in/gihhg7i

Why MUXes Matter

A MUX makes a conditional physical. It selects one of two inputs based on a control bit. A tree or graph of those choices becomes a compact way to express Boolean behavior, and it connects directly to the larger Boolean-fabric work.

Links From the Original Post