Mod-2-OBDDs—A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams

We present a data structure for Boolean manipulation-the Mod-2-OBDDs-that considerably extends ESOPs (EXOR-sum-of-products) as well as OBDDs (ordered binary decision diagrams). There are Boolean functions of practical interest which have exponential size optimal ESOPs (even multilevel EXOR-expressions) and/or OBDDs that can be represented by (low degree) polynomial size Mod-2-OBDDs. We show that Boolean manipulation tasks such as apply operation, quantification, composition can be performed with Mod-2-OBDDs at least as efficient as with OBDDs. Indeed, since the size of a minimal Mod-2-OBDD-representation of a Boolean function is, in general, smaller (sometimes even exponentially smaller) than the size of an optimal OBDD-representation, the increase in efficiency is considerable. Moreover, EXOR-operations as well as complementations can be performed in constant timeO (1). However, the price of constant time EXOR-apply operations is the canonicity of the Mod-2-OBDD-representation. In order to allow in spite of this fact efficient analysis of Mod-2-OBDDs we present a fast probabilistic equivalence test with one-sided error probability for Mod-2-OBDDs (and, hence, for ESOPs) which performs only linear many arithmetic operations.     

A Unifying Theoretical Background for Some Bdd-based Data Structures

In the paper, we propose a general concept (denoted by TBDD) for Boolean functions manipulation that is based on cube transformations. The basic idea is to manipulate a Boolean function by converting it by means of a cube transformation into a function that can be efficiently represented and manipulated in terms of ordered binary decision diagrams (OBDDs). We show that the new concept unifies several BDD–based data structures considerably, and simplifies their manipulation to work with the simple and well–understood data struture of OBDDs. This is especially important for practical applications.Further, to give an example of how TBDDs open new ways in the search for efficient data structures for Boolean functions, we discuss the data structure of typed kFBDDs.     

一种基于熵的OBDD变量排序算法

有序二叉决策图（OBDD）是一种有效表示布尔函数的数据结构，其大小依赖于所采用的变量序。熵是定量描述布尔函数中变量重要性的一种方法。基于变量的熵值分析了高质量变量序的特征，给出了一种基于熵的OBDD变量排序算法。实验结果表明：该算法与模拟退火算法和遗传算法结果相当。时间仅为相应算法的80．84％和29．79％。     

A simpler counterexample to a long-standing conjecture on the complexity of Bryantʼs apply algorithm

In 1986 in his seminal paper Bryant has introduced Ordered Binary Decision Diagrams (OBDDs) as a dynamic data structure for the representation and manipulation of Boolean functions which allow efficient algorithms for important operations like synthesis, the combination of two Boolean functions by a Boolean operator, and equivalence checking. Based on his empirical evaluation he has conjectured that his apply algorithm for the synthesis works in linear time with respect to the input and output size. Recently in 2012, Yoshinaka et al. have presented a counterexample which contradicts this conjecture but their example has the drawback that the chosen variable ordering for the OBDD representation of the input and output is bad. Therefore, they have raised the question whether Bryant?s conjecture may still stand for reasonable variable orderings. Here, a negative answer is given by presenting a simple counterexample which works for such kind of variable orderings.     

Larger lower bounds on the OBDD complexity of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Recently, the question whether the OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. In this paper a larger general lower bound is presented using a simpler proof. Furthermore, we prove a larger lower bound for the variable order assumed to be one of the best ones for the most significant bit. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.     

A note on the size of OBDDs for the graph of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are the most common dynamic data structure for Boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. Analyzing the limits of symbolic graph algorithms for the all-pairs-shortest paths problem which work on OBDD-represented graph instances the so-called graph of integer multiplication has been investigated by Sawitzki [D. Sawitzki, Lower bounds on the OBDD size of graphs of some popular functions, in: Proc. of SOFSEM, LNCS, vol. 3381, 2005, pp. 298-309]. Using simple arguments his lower bound of ²n/768−1 on the size of OBDDs representing the graph of integer multiplication is improved up to ²n/24.     

Symbolic OBDD representations for mechanical assembly sequences

Assembly sequence planning is one typical combinatorial optimization problem, where the size of parts involved is a significant and often prohibitive difficulty. The compact storage and efficient evaluation of all the feasible assembly sequences is one crucial concern. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate the Boolean functions efficiently, and appears to give improved results for large-scale combinatorial optimization problems. In this paper, subassemblies, assembly states and assembly tasks are represented as Boolean characteristic functions, and the symbolic OBDD representation of assembly sequences is proposed. In this framework, the procedures to transform directed graph and AND/OR graph into OBDDs are presented. The great advantage of OBDD-based scheme is that the storage space of OBDD-based representation of all the feasible assembly sequences does not increase with the part count of assembly dramatically so quickly as that of both directed graph and AND/OR graph do. We undertake many experimental tests using Visual C++ and CUDD package. It was shown that the OBDD scheme represented all the feasible assembly sequences correctly and completely, and outperforms either directed graph or AND/OR graph in storage efficiency.     

Arithmetic Boolean Expression Manipulator Using BDDs

Recently, there has been a lot of works on LSI design systems using Binary Decision Diagrams (BDDs), which are efficient representations of Boolean functions. We previously developed a Boolean expression manipulator, that can quickly calculate Boolean expressions by using BDD techniques. It has greatly assisted us in developing VLSI design systems and solving combinatorial problems.In this paper, we present an Arithmetic Boolean Expression Manipulator (BEM-II), that is also based on BDD techniques. BEM-II calculates Boolean expressions that contain arithmetic operations, such as addition, subtraction, multiplication and comparison, and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with in 0-1 linear programming. We discuss the algorithm and data structure used for manipulating arithmetic Boolean expressions and show the formats used for displaying the results.The specifications for BEM-II are described and several application examples are presented. Arithmetic Boolean expressions will be useful for various applications. They perform well in terms of the total time for programming and execution. We expect BEM-II to facilitate research and development of digital systems.     

Counterexamples to the long-standing conjecture on the complexity of BDD binary operations

In this article, we disprove the long-standing conjecture, proposed by R.E. Bryant in 1986, that his binary decision diagram (BDD) algorithm computes any binary operation on two Boolean functions in linear time in the input–output sizes. We present Boolean functions for which the time required by Bryant?s algorithm is a quadratic of the input–output sizes for all nontrivial binary operations, such as ∧, ∨, and ⊕. For the operations ∧ and ∨, we show an even stronger counterexample where the output BDD size is constant, but the computation time is still a quadratic of the input BDD size. In addition, we present experimental results to support our theoretical observations.     

OBDD-Based Cryptanalysis of Oblivious Keystream Generators

Many keystream generators of practical use consist of a certain number of linear feedback shift registers (LFSRs) combined with a nonlinear output automaton. For this type of generator, we present an algorithm computing the secret initial state x ∈ {0,1}ⁿ from a short piece of corresponding keystream by performing 2^{(1 - α)/(1 + α)n} polynomial-time operations, where α denotes the rate of information which the output keystream reveals about the internal bitstream produced by the LFSRs. The algorithm uses Ordered Binary Decision Diagrams (OBDDs), a data structure for minimizing and manipulating Boolean functions. We demonstrate the potential of our method by applying it to the self-shrinking generator and to the E₀-generator used in the Bluetooth wireless system and obtain the best known short-keystream attacks for these generators.