A branch-and-bound algorithm to obtain an optimal evaluation tree for monotonic Boolean functions

Summary For monotonic Boolean functions, a branch-and-bound algorithm is given for constructing an optimal decision tree (sequential evaluation procedure). The tree is optimal in minimizing the average number of variables which need to be examined.Presently at Computer Science Dept. SUNY at Albany, Albany, N.Y., USA.     

Refinement algebra with dual operator

Algebras of imperative programming languages have been successful in reasoning about programs. In general an algebra of programs is an algebraic structure with programs as elements and with program compositions (sequential composition, choice, skip) as algebra operations. Various versions of these algebras were introduced to model partial correctness, total correctness, refinement, demonic choice, and other aspects. We introduce here an algebra which can be used to model total correctness, refinement, demonic and angelic choice. The basic model of our algebra are monotonic Boolean transformers (monotonic functions from a Boolean algebra to itself).     

最优代数免疫布尔函数的完全构造

任意的布尔函数可以唯一地表示成有限域上的单变元多项式函数,利用布尔函数的单变元多项式表示和代数编码理论,讨论了布尔函数的代数免疫达到最优的判别条件,得到了布尔函数的变元个数为奇数时,布尔函数具有最优代数免疫(MAI)的等价判别条件。利用该等价判别条件,给出3元布尔函数满足MAI的等价判别条件,进而构造出所有3元的MAI布尔函数。     

Algorithms for fast evaluation of Boolean expressions

Summary For Boolean functions whose variables appear in secondary storage, algorithms which minimize the expected cost of evaluation are considered. An easyto-implement algorithm which gives nearly optimal results is proposed for the case of monotonic functions without a priori probabilities. Optimality proofs are given for a simple special cases.     

Generation of sign Walsh spectra from disjoint cubes of Boolean functions

A new algorithm is given that converts a reduced representation of Boolean functions in the form of disjoint cubes to sign Walsh spectra. Since the known algorithms that generate sign Walsh spectra always start from the truth table of Boolean functions, the method presented computes faster with a smaller computer memory. The method is especially efficient for such Boolean functions that are described by only few disjoint cubes.     

满足k次强扩散准则的布尔函数谱特征分析

利用概率方法和频谱理论,给出布尔函数满足强扩散准则的一个新的等价判别条件,并根据强扩散准则与扩散准则之间的关系,得到满足k次强扩散准则的布尔函数的2种构造方法。结合具有平衡性和相关免疫性的布尔函数的谱特征,给出缸欺骗免疫秘密共享定义函数的谱判别条件。     

Creep in Thin Magnetic Films†

In this paper a method of testing and realization of two-realizable threshold functions have been suggested. It is shown that the two–realizable functions may be factored into three different forms, (i) sum of or (ii) product of or (iii) ‘ sum–of–product ’ of threshold functions. Since threshold functions are unate functions, a method of decomposition of Boolean functions into unate functions in the above three forms is suggested. The concept of minimal unate function and the cover table of the given Boolean function und its complement is utilized to obtain the above three factored forms.     

基于性能驱动的工艺映射算法

用多级逻辑实现控制器的逻辑综合,工艺映射是其中的一个重要步骤。本文叙述的工艺映射算法TTMAP,是在映射过程中考虑了电路的时延与芯片面积等性能因素,在多级逻辑综合中将因子化的逻辑函数映射为CMOS的串并赶电路单元,产生可布图的网表文件。本算法在比利时HMEC研究中心开发,为多级逻辑综合系统MLL中的一个模块。经实例运行,与美国加州大学柏克莱分校的MISⅡ软件相比,本算法的结果较优。     

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.     

布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。     

The symbolic OBDD scheme for generating mechanical assembly sequences

Assembly sequence planning is one of typical combinatorial optimization problems, where the size of parts involved is a significant and often prohibitive difficulty. The compact storage and efficient evaluation of 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, assembly knowledge models of liaison graph and translation function are formulated by OBDDs, and OBDD-based representation of assembly sequences is proposed. A novel OBDD-based procedure was presented to generate all geometrically feasible assembly sequences from the OBDDs of liaison graph and translation relation. This procedure can be used conveniently on the computer and all the feasible sequences can be derived. The great advantage of OBDD-based scheme is that the storage space of OBDD-based representation of feasible assembly sequences does not increase with the part count of assembly dramatically so quickly as that of AND/OR graph does. We developed the prototype tool for generating assembly sequence using Visual C++ and CUDD package, and undertake some experimental tests. It was shown that the OBDD scheme generated feasible assembly sequences correctly and completely.     

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.     

Calculation of the paired Haar transform through shared binary decision diagrams

A concept of paired Haar transform (PHT) for representation and efficient optimization of systems of incompletely Boolean functions has recently been introduced. In this article, a method to calculate PHT for incompletely specified switching functions through shared binary decision diagrams (SBDDs) is presented. The algorithm converts switching functions in the form of SBDDs into their paired Haar spectra and can operate on functions with many variables.     

Dynamic processor allocation in scalable multiprocessors using boolean algebra *

In this paper, we study a new model for dynamic processor allocation in k-ary n-dimensional mesh or torus multiprocessors. The model uses Boolean functions to represent free processors and allocates processors by applying Boolean operations on the functions. The processor allocation algorithms based on the Boolean model can be implemented easily using binary decision diagrams(BDDs)and related software packages. To enhance the efficiency of the allocation algorithms, a reordering procedure will be introduced to change the ordering of Boolean variables in the BDD representation and thereby change the free subcube composition. Such a change leads to an improved free processor recognition capability. Complexities of the proposed allocation algorithms will be analyzed. Performance of the algorithms will be evaluated using simulation and compared with other approaches.     

多输出布尔函数的k阶严格雪崩准则

首次将k阶严格雪崩准则的概念扩展到多输出布尔函数上,首先研究了多输出函数的严格雪崩准则、扩散准则,给出了多输出函数满足k阶严格雪崩准则的两个充分必要条件,证明了多输出布尔函数满足高阶严格雪崩准则时一定满足低阶严格雪崩准则。然后根据对称函数的特性,应用数论的知识,研究了多输出对称布尔函数的严格雪崩准则、扩散准则和k阶严格雪崩性质,给出了相应准则的充分必要条件,特别给出了两个k阶严格雪崩准则的组合判别公式。     

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC⁰. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.     

Exploiting Functional Properties of Boolean Functions for Optimal Multi-Level Design by Bi-Decomposition

This paper introduces the theory of bi-decomposition of Boolean functions. This approach optimally exploits functional properties of a Boolean function in order to find an associated multilevel circuit representation having a very short delay by using simple two input gates. The machine learning process is based on the Boolean Differential Calculus and is focused on the aim of detecting the profitable functional properties availablefor the Boolean function. For clear understanding the bi-decomposition of completely specifiedBoolean functions is introduced first. Significantly better chance of successare given for bi-decomposition of incompletely specifiedBoolean functions, discussed secondly. The inclusion of the weak bi-decomposition allows to prove the the completeness of the suggested decomposition method. The basic task for machine learning consists of determining the decomposition type and dedicated sets of variables. Lean on this knowledge a complete recursive design algorithm is suggested. Experimental results over MCNC benchmarks show that the bi-decomposition outperforms SIS and other BDD-based decomposition methods interms of area and delay of the resulting circuits with comparableCPU time. By switching from the ON-set/OFF-set model of Boolean function lattices to their upper- and lower-bound model a new view to the bi-decomposition arises. This new form of the bi-decomposition theorymakes a comprehensible generalization of the bi-decomposition to multivalued function possible.     

The autocorrelation distribution of balanced Boolean function

The global avalanche characteristics (the sum-of-squares indicator and the absolute indicator) measure the overall avalanche characteristics of a cryptographic Boolean function. Sung et al. (1999) gave the lower bound on the sum-of-squares indicator for a balanced Boolean function satisfying the propagation criterion with respect to some vectors. In this paper, if balanced Boolean functions satisfy the propagation criterion with respect to some vectors, we give three necessary and sufficient conditions on the auto-correlation distribution of these functions reaching the minimum the bound on the sum-of-squares indicator. And we also find all Boolean functions with 3-variable, 4-variable, and 5-variable reaching the minimum the bound on the sum-of-squares indicator.     

异步时序电路反馈稳定性判据

本文提出了"含相开关代数"的概念,证明了它与布尔代数是同构的,从而使布尔代数可 用于设计时序电路.文中利用含相开关代数这一概念推导出异步时序电路反馈稳定性判据, 从而能方便地找出全部不稳定转换.