Boolean algebra, Computer algorithms, Quantum computing, Logic circuits
The paper presents a family of new expansions of Boolean functions called Function-driven Linearly Independent (fLI) expansions. On the basis of this expansion a new kind of a canonical representation of Boolean functions is constructed: Function-driven Linearly Independent Binary Decision Diagrams (fLIBDDs). They generalize both Function-driven Shannon Binary Decision Diagrams (fShBDDs) and Linearly Independent Binary Decision Diagram (LIBDDs). The diagrams introduced in the paper, can provide significantly smaller representations of Boolean functions than standard Ordered Binary Decision Diagrams (OBDDs), Ordered Functional Decision Diagrams (OFDDs) and Ordered (Pseudo-) Kronecker Functional Decision Diagrams (OKFDDs) and can be applied to synthesis of reversible circuits.
Kerntopf, Pawel, and Marek A. Perkowski. "Function-driven linearly independent expansions of boolean functions and their application to synthesis of reversible circuits." Proceedings of the 13th International Workshop on Logic and Synthesis. Vol. 30. Dana Point, Laguna Beach, California: ACM SIGDA (special interest group design automation), 2003.