伪布尔约束的一种模型计数方法

伪布尔约束问题是一类与布尔约束问题相似的组合优化难题。解决这类问题的核心在于以不同的数学形式对伪布尔约束进行编码,例如线性规划、整数规划以及其他形式的组合优化。当前流行的解决方法是将问题转化为布尔公式,然后运用冲突导向的子句学习(CDCL)类SAT求解器对这些布尔公式进行求解。提出了一种新的方法来解决伪布尔约束问题中的模型计数问题。首先,介绍了知识编译和扩展规则的相关概念,随后详细阐述了如何利用知识编译将伪布尔约束问题转化为二元决策图(BDD),并着重探讨了BDD结构的特性,最后采用基于扩展规则的模型计数方法来处理伪布尔约束问题中的模型计数问题。实验结果表明,该方法在处理互补因子较高的子句集时表现出更为优越的性能。

基于汉明重的LED代数旁路攻击研究

对CHES 2011会议提出的LED轻型分组密码抗代数旁路攻击能力进行了评估。给出了密码算法代数旁路攻击模型及LED密码代数方程表示方法;利用示波器采集微控制器ATMEGA324P上的LED实现功耗泄露,选取功耗特征较为明显的部分泄露点,基于Pearson相关系数方法推断加密中间状态汉明重;分别基于可满足性问题、伪布尔优化问题、线性编程问题给出了LED密码和汉明重泄露的3种代数方程表示方法;使用CryptoMinisat和SCIP 2种解析器对建立的代数方程求解恢复密钥,在已知明文、未知明密文、容错等场景下进行了大量的攻击实验。结果表明,LED易遭受代数旁路攻击,一条功耗曲线的1轮汉明重泄露分析即可恢复64 bit完整密钥。

基于代数决策图的路由查找算法

为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。

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

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

剩余格中基于核映射的滤子

在剩余格中,基于核映射引入了对合滤子、扩展对合滤子、Glivenko滤子的概念,讨论了它们的性质且给出了它们的特征定理。分析了滤子的一种带有核映射的扩张形式的代数性质,得到了扩展对合滤子的应用。进一步,在MTL代数中引入了相对伪布尔滤子的概念,得到了相对伪布尔滤子的特征定理。

基于伪布尔模型和启发式算法求解无容量设施选址问题

采用伪布尔模型和启发式算法来求解无容量设施选址问题。首先给出了问题的伪布尔(pseudo-Boolean)表示,然后基于Khumawala规则对问题进行预处理,最后提出两种启发式分支准则来求解问题。实验结果表明所提算法简单有效。

逻辑电路的神经网络

Ｍ．Ｌ．Ｂｕｓｈｎｅｌ教授和作者给出了ＮＯＴ，ＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲ，ＸＯＲ和ＸＮＯＲ门的神经网络．以这些门的神经网络为基础，可构成任何逻辑电路的神经网络．由此，将电路的相容信号转换为平方伪布尔函数的全局极小．从而。

H-GRASP:一种基于GRASP改进的混合SAT解法器

为了改善GRASP的局限性,提出了一种能解决含有伪布尔(PB)和合取范式(CNF)混合约束问题的新的混合算法(H-GRASP)。该新算法采用了切削平面技术来提取PB约束条件之间的推论,并把它结合到普通的蕴涵图中,分析引起冲突的学习。与解决混合约束问题的其他两种方法——整数线性规划和纯基于SAT方法进行了彻底的比较。实验结果证明,H-GRASP方法从整体上大大减少了运行时间,加快了速度,同时还保证了加入这种方法的低耗费。

一种改进的子集可满足性算法用于FPGA布线

介绍了用布尔可满足性(SAT)和子集可满足性(sub-SAT)算法解决FPGA的详细布线问题。在布线资源固定的FPGA布线环境中,布尔公式可以证明所给电路的不可布通性,这一点要优于典型的one-net-at-a-time方法。子集可满足性方法把一个有N个约束的"严格的"SAT问题转换成一个新的"松弛的"SAT问题,仅当在原始问题中变量的不可满足个数不超过阈值k(kN)时,这一问题是可满足的。它改进了布尔可满足性,但是却产生了很多额外的变量和子句。针对这一问题,提出了用伪布尔可满足性(PBS)来消除子集可满足性公式带来的缺点。初步的实验结果表明,把这个方法加入子集可满足性方法中可以减少变量和子句数量,并显著减少运行时间。

区间值模糊概率集及其在模式识别中的应用

首次提出区间值模糊概率集(IvFPS)的概念.区间值模糊概率集的矩和其他一些重要性质,以及区间值模糊概率集间的相关性也将得到研究和探讨.最后通过一个实际数例来阐述区间值模糊概率集的相关系数在模式识别中的应用.

一类可优化的平方伪布尔函数

该文给出一类平方伪布尔函数ｆ（ｘ）＝ｘＱｘ￣Ｔ＋ｃｘ￣Ｔ＋ｄ，它的最小点与最小值可在线性时间内找到。其基本思想在于将Ｑ和Ｃ所关联的图转换为由ＮＯＴ，ＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲ，ＸＯＲ和ＸＮｏＲ门组成的逻辑电路，后者的相容信号值对应伪布尔平方函数的最小点。这种方法建立了平方伪布尔函数与逻辑电路之间的结构关系。

Lovász延拓权值下的伪泊松混合分布的风险期望模型

本文在风险损失量为自然数且服从泊松分布的条件下,将泊松分布进行截断和均化的处理生成伪泊松分布,然后根据有限可数混合分布的表达式,利用从集函数转换而来的多线性形式的Pseudo-Boolean函数的Lovász延拓得到新的权值并构建伪泊松混合分布,最后根据期望的定义和性质得到相应的伪泊松混合分布的风险期望模型.该模型为今后研究混合分布在风险分析中的应用提供了依据.

基于伪布尔可满足性的纳米CMOS电路单元配置

针对传统布尔可满足性(SAT)法在处理纳米CMOS电路(CMOL)单元配置时,存在合取范式(CNF)表示的约束子句个数过多、中间处理文件过大的问题,该文提出了利用伪布尔可满足性(PBS)来解决CMOL电路的单元配置问题。实验结果显示,相对于传统的SAT法,PBS法在不增加额外的布尔变量集个数的条件下,通过降低编码过程中的约束个数,能有效减少中间处理文件大小,达到提高算法效率和提高处理大电路的能力。

判别一个序列是m－序列的一个充要条件

本文借助于布尔置换和ｍ－序列之间的关系给出了判别一个序列是ｍ－序列的一个充要条件．

伪BL-代数的犹豫模糊滤子

提出了伪BL-代数的犹豫模糊滤子的概念,给出它的几个等价刻画,并研究了它的一些性质。进一步,引入了伪BL-代数的几种犹豫模糊滤子,如犹豫模糊Boolean滤子、犹豫模糊正规滤子、犹豫模糊超滤子和犹豫模糊固执滤子,讨论了它们的一些刻画,给出了其间的一些关系。通过研究伪BL-代数中犹豫模糊Boolean滤子与犹豫模糊正规滤子的关系,解决了伪BL-代数中是否每个Boolean滤子都是正规滤子这样一个开问题。

一种基于伪布尔可满足性FPGA布线算法

为了克服布尔可满足性算法在现场可编程门阵列布线中存在的不足,引进了一种在标准对称阵列(隔离岛状)现场可编程门阵列结构下的新型有效布线方法——伪布尔可满足性算法,并结合实例详细地阐述了将其应用于布线的原理及方法,同时采用实际工业电路将布尔可满足性算法与伪布尔可满足性算法作出比较。实验结果显示,伪布尔可满足性算法比布尔可满足性算法在布线时间上减少了10.5%,在稳定性上提高了3.3%。

Neural Networks for Logic Circuits

Bushnell and the author proposed the neural networks for NOT, AND, OR, NAND, NOR, XOR and XNOR gates. Using these neural networks, the neural networks of any logic circuits can be constructd. From this, the consistent signals in the logic circuits will be transformed into the global minimal points of a quadratic pseudo Boolean function. Thus the neural network application in the field of circuit modeling and automatic test pattern generation can be widened.

psBCK-代数的Boolean滤子与psMV-滤子

在psBCK-代数中引入Boolean滤子和psMV-滤子的概念,研究了这2种滤子的性质及其相互关系.同时,借助psMV-滤子概念,给出psBCK-代数成为psMV-代数的若干充要条件.

线性伪布尔方程的计算机求解

伪布尔方程的求解在逻辑综合、故障诊断、网络理论和优化设计等领域是一个极需解决的问题．作者用Ｖｉｓｕａｌｃ＋＋和ＭｉｃｒｏｓｏｆｔＷｉｎｄｏｗｓ采用分枝算法编制了一个求解伪布尔方程的程序，通过读入伪布尔方程的参数，给出相应的求解结果．

基于影响网络的混合约束作战方案优化方法

在复杂不确定的战场环境中,军事决策人员面临的首要问题是确定满足一定约束条件、优化的作战方案。研究考虑资源和协同约束,利用影响网络度量作战方案的优劣程度,建立基于影响网络的混合约束作战方案优化问题。优化问题是一个伪布尔约束和布尔约束混合、优化目标非解析表达的0-1整数优化问题。同时,提出遗传算法结合伪布尔约束求解的方法对优化问题求解,通过测试案例对该优化方法的有效性进行验证。