Weights Binary Decision Diagram (WBDD) and its application to Matrix Multiplication

Binary decision diagrams (BDDs) are the most frequently used data structure for handling Boolean functions because of their excellent efficiency in terms of time and space. Algebraic decision diagrams (ADDs) have been used to solve general purpose problems such as matrix multiplication, logic synthesis and formal verification. We propose a new type of BDD called weights binary decision diagram (WBDD). We apply the proposed BDD for matrix multiplication. We express weights as binary values and the matrix can be represented by a collection of matrices taken for each weight bit. Since the Boolean expressions are for weight values, the computations are easier and faster compared to ADDs.