基于否证蕴含的极小一阶不可满足子式求解算法

解释公式不可满足的原因在软件分析与验证等众多领域都具有非常重要的理论与应用价值,而极小不可满足子公式能够为公式不可满足的原因提供精炼的解释,帮助应用领域的自动化工具迅速定位错误,准确地诊断问题失败的本质缘由.文中针对极小一阶不可满足子式的求解问题,引入了否证蕴含图及其正向与逆向可达结点的概念,并证明了不可满足子式与否证蕴含图之间的关系.基于二者的关系,提出了基于冲突分析与否证蕴含的极小一阶不可满足子式求解算法,并融合了蕴含图剪枝技术,以提高算法效率.通过实验与当前最优的深度优先搜索算法进行了比较,结果表明:文中的算法显著优于深度优先搜索算法,并且随着公式复杂度的增加,性能优势更加明显.     

Novel way to research nonlinear feedback shift register

In this paper,we regard the nonlinear feedback shift register（NLFSR） as a special Boolean network,and use semi-tensor product of matrices and matrix expression of logic to convert the dynamic equations of NLFSR into an equivalent algebraic equation. Based on them,we propose some novel and generalized techniques to study NLFSR. First,a general method is presented to solve an open problem of how to obtain the properties（the number of fixed points and the cycles with different lengths） of the state sequences produced by a given NLFSR,i.e.,the analysis of a given NLFSR. We then show how to construct all 2^2^n-（l-n）/2^2^n-lshortest n-stage feedback shift registers（nFSR） and at least 2^2^n-（l-n）-1/2^2^n-l-1shortest n-stage nonlinear feedback shift registers（nNLFSR） which can output a given nonperiodic/periodic sequence with length l. Besides,we propose two novel cycles joining algorithms for the construction of full-length nNLFSR. Finally,two algorithms are presented to construct 2^2^n-2-1different full-length nNLFSRs,respectively.     

线性关联规则研究

首先讨论了布尔型关联规则的不足,然后提出了线性关联规则的概念,详细讨论了线性关联规则的挖掘方法,具体给出了线性关联规则的挖掘过程,分析了线性关联规则的作用。还给出了实验结果,并将线性关联规则和布尔型关联规则及定量关联规则进行了比较。     

最大代数免疫度的偶变元对称函数的性质

代数免疫度达到最大的偶变元对称布尔函数的特征仍然是个公开问题。结合组合数学和数论的相关结论研究这类函数的性质,得到了此类函数值向量的几个特征。最后,对于变元个数为两类特殊偶数的情况,得到了代数免疫度达到最大的对称函数的一个特征。     

基于配用电数据关联的中压配电网断线故障诊断方法

基于配用电信息系统数据和关联规则算法,提出一种诊断中压配电网分支线断线不接地故障的方法。通过分析相互关联的配用电信息系统数据,提出基于数据特征选择的关联规则挖掘方法,并通过卡方分裂算法将连续型特征量转换为布尔型特征量,同时采用MSApriori算法解决故障信息中的稀有项问题,然后在此基础上应用kulc准则消除冗余规则以形成约简的代表规则家族。以华东某地区配用电信息系统中的历史数据为依据进行实际算例分析,结果说明所提出的方法能够大量减少无效挖掘,显著提高效率和准确度,适用于中压配电网断线故障的在线诊断。     

素数元旋转对称弹性布尔函数的构造与计数

通过对素数元旋转对称弹性布尔函数特征矩阵的研究,给出了其特征矩阵的若干性质,得到了素数元旋转对称布尔函数为弹性函数的一个充要条件,由此完全决定了旋转对称弹性函数的构造以及这类函数的精确计数公式,最后还给出了所有的三元、五元、七元旋转对称弹性布尔函数的构造方案与精确计数。     

一种新的SAT问题预处理算法

提出了一项新的正向推理技术:对称扩展的一元子句推导(Symmetric Extended Unit Propagation)。与传统的一元子句推导技术相比,文中的方法通过在一元子句推导过程中添加对称的蕴涵关系从而能够推导出更多的一元子句。基于这项新技术实现了一个可满足性问题(SAT)预处理器Snowball。实验结果验证了该项技术的有效性,表明该预处理器Snowball能够有效地化简SAT问题的规模并减少解决SAT问题的时间。     

16 位改进型条件进位加法器电路设计

为提升数字信号处理电路的性能,对16 位传统条件进位加法器(conditional carry select adder,CCS)的逻 辑层布尔函数提出一种改进方案。使用Verilog 语言和Synopsys 对16 位改进型和传统型条件进位加法器进行仿真分 析。结果表明：该方案能在加法器功耗下降的同时实现关键路径延迟的明显降低,性能明显优于传统加法器。     

多文字可满足SAT问题的相变点上界

可满足(SAT)问题是指：是否存在一组布尔变元赋值,使得随机合取范式(CNF)公式中每个子句至少有1个文字为真。多文字可满足SAT问题是指：是否存在一组布尔变元赋值,使得随机CNF公式中每个子句至少有2个文字为真。此问题仍然是一个NP难问题。定义约束密度α为CNF公式子句数与变元数之比,对该问题的相变点上界α^*进行了研究。如果α>α^*,则多文字可满足SAT问题高概率不可满足。通过一阶矩一个简单的推断,可以证明α^*=-ln 2/ln(1-(k+1)/2^k),当k=3时,α^*=1。利用Kirousis等人的局部最大值技术,提升了多文字可满足3-SAT问题的相变点上界α^*=0.7193。最后,选择了大量数据进行实验验证,结果表明,理论结果与实验结果相吻合。