包含无关项的MPRM展开式最小化算法

通过对包含无关项布尔逻辑函数SOP(Sum-of-Products)展开式和MPRM(Mixed Polarity Reed-Muller)展开式的研究,结合基于系数矩阵的FPRM(Fixed Polarity Reed-Muller)展开式极性转换算法,提出了一种包含无关项逻辑函数MPRM展开式最小化算法.首先将包含无关项逻辑函数SOP展开式转换为MPRM展开式,并用系数矩阵的形式表示;然后删除函数中的冗余变量,归纳出一种包含无关项MPRM展开式最小化算法,得到与项数较少的MPRM展开式;最后随机选取15个MCNC基准电路进行测试,结果表明该算法能有效地优化电路面积.     

基于混合遗传算法的MPRM最小化

MPRM(Mixed-Polarity Reed-Muller)最小化是RM(Reed-Muller)电路逻辑综合过程中一个非常重要的阶段,对于输入数较多的布尔函数,传统遗传算法(Genetic Algorithm,GA)在解决MPRM最小化问题时收敛过早.提出了一种基于混合遗传算法(Hybrid Genetic Algorithm,HGA)的MPRM最小化算法,该算法将基于相异度的局部改善策略结合到GA算法的迭代过程中.局部改善策略对种群中最佳个体和与之相异度最大的个体实施交叉操作生成新个体,并将新个体与最佳或最差个体进行竞争.将所提算法应用于一组具有较多输入数的MCNC基准电路,并与其他智能MPRM最小化算法进行比较.结果表明,局部改善策略能够避免算法陷入局部极小,增强了全局收敛能力.与模拟退火遗传算法(Simulated Annealing Genetic Algorithm,SAGA)相比,HGA算法在获得类似结果的前提下提高了时间效率;与Hybrid multi-valued DPSO算法相比,HGA在得到基本相同的算法结果时,时间效率亦基本相同.     

基于K图的函数RM展开式在固定极性下的最小化

分析了K图的性质，发现在K图中过某格的所有聚合圈相应的各乘积项所含变量与该格对应的最小项均有相同的极性，在此基础上提出了得到基于K图函数RM展开式在固定极性下的最小化的图形方法，该方法可以从K图直接得到函数的最小化的RM展开式，从而省略了传统的把K图转变为bj图再求最小化的步骤，它具有直观、简单、易于掌握等特点。此外，文中还提出了该方法的改进算法。     

基于模糊遗传算法的XNOR/OR展开式最小化研究

提出一种改进的模糊遗传算法用于求解XNOR/OR展开式最小化问题. 在算法进化过程中,采用模糊规则对交叉率和变异率进行修正, 以提高算法的收敛速度, 并在一定程度上抑制了局部收敛现象的发生. 并采用8个MCNC Benchmark电路对该算法进行测试, 结果表明: 所提算法具有较好的优化效果和较高的收敛速度.     

逻辑函数最大项展开式和CRM展开式的转换

在逻辑函数的CRM展开式和两种新运算基础上，对函数量大项展开系数和CRM展开系统(dj系数)之间的关系作了较详细的讨论，并提出了两者的矩阵转换法，快速转换法和直接代入转换法，具备较好的实用性．     

函数CRM展开式在固定极性下最小化的图形方法

分析了dj图、K图的性质,在此基础上提出了基于dj图、K图的函数CRM展开式在固定极性下最小化的图形方法.它具有直观、简单、易于掌握等特点.     

检测含无关项旋转对称逻辑函数的快速算法

旋转对称逻辑函数在密码学函数构造领域有广泛应用。针对含无关项旋转对称逻辑函数检测中存在的不足,从含无关项逻辑函数的定义和旋转对称函数的性质出发,提出了检测含无关项旋转对称逻辑函数的快速算法。该算法通过判断逻辑函数1值最小项二进制编码周期旋转后产生的新编码同1值最小项及无关项二进制编码的重复性实现快速检测。结果表明,快速算法在适用的逻辑函数变量数、含无关项旋转对称逻辑函数检测的适用性和检测过程的复杂度方面均优于现有的表格方法与谱系数方法。     

检测含无关项旋转对称逻辑函数的快速算法

旋转对称逻辑函数在密码学函数构造领域有广泛应用。针对含无关项旋转对称逻辑函数检测中存在的不足,从含无关项逻辑函数的定义和旋转对称函数的性质出发,提出了检测含无关项旋转对称逻辑函数的快速算法。该算法通过判断逻辑函数1值最小项二进制编码周期旋转后产生的新编码同1值最小项及无关项二进制编码的重复性实现快速检测。结果表明,快速算法在适用的逻辑函数变量数、含无关项旋转对称逻辑函数检测的适用性和检测过程的复杂度方面均优于现有的表格方法与谱系数方法。     

计算含无关项布尔c-导数的K图方法

为简化与-或-非代数系统中含无关项逻辑函数布尔c-导数的计算过程,从逻辑函数布尔c-导数的定义出发,提出了计算含无关项一阶布尔c-导数和二阶布尔c-导数的K图方法.该方法通过折叠映射K图中的填入格值,并对相应格值进行"或"运算以计算含无关项布尔c-导数.应用实例表明,该方法直观有效,且能直接得到布尔c-导数的最简与/或式.     

含无关项布尔函数的对称变量检测算法

为简化布尔函数中12类对称变量的检测过程,提出了含无关项布尔函数基于最小项展开系数的对称变量检测算法.该算法通过判别布尔函数有序特征值矩阵的约束条件以实现对称变量的快速检测.应用结果表明,与现有方法相比,算法在适用的布尔函数变量数、检测类型、检测含无关项布尔函数和检测过程的复杂度方面表现较优.     

含任意项逻辑函数布尔差分的图形化算法研究

针对包含任意项的逻辑函数,提出了一种利用该类逻辑函数K图和bj图的图形转换来实现一阶布尔差分和二阶布尔差分计算的方法．实例表明,该图形方法具有简单、直接、方便的特点．     

一种改进的混合极性列表技术

针对基于多输出混合极性Reed-Muller逻辑表达式极性转换问题, 提出了基于不相交项的列表极性转换方法, 并通过极性搜索实现函数的最小化. 结果表明: 与传统列表极性转换法相比, 提出的新方法能有效降低时间复杂度.     

基于三角形结构计算GRM展开系数的新算法

分析了单变量、两变量和n变量逻辑函数GRM展开系数的递推三角形结构,相应的三角形的左边或右边表示某固定极性下的GRM展开系数.进一步分析表明极性为q的GRM展开系数即为自上向下由各行脚标中含q的项.在此基础上提出了基于三角形结构计算GRM展开系数的新算法.与已有算法相比,本文提出的算法在速度上优于其他算法.     

逻辑函数RM展开式和CRM展开式的转换

讨论了逻辑函数在与-异或和或-符合代数系统中的RM展开式和CRM展开式.根据异或和符合运算的性质详细讨论了逻辑函数bj系数和dj系数间的关系,并提出了两者的矩阵转换法,举例说明了转换过程.该方法揭示了bj系数和dj系数的内在联系,具有较好的实用性.     

逻辑函数的布尔减-异或、布尔除-符合展开式在固定极性下的最小化方法

在混合极性下的减-异或、除-符合展开式的最小化方法基础上,讨论了在固定极性下减-异或、除-符合展开式的代数化简法和图形化简法,并给出了化简实例．实例验证了上述方法有效性．该法有助于进一步完善减-异或、除-符合代数系统的理论并促进新的数字元件及新一代数字电路的研发．     

三值FPRM电路极性间转换算法及其在面积优化中的应用

通过对三值FPRM(Fixed-polarity Reed-Muller)展开式和四值列表技术的研究,提出了一种三值FPRM电路极性间转换算法,并将其应用于电路面积优化.首先根据四值RM(Reed Muller)逻辑多项式系数的计算方法,推导出三值FPRM展开式极性间系数转换算法;然后利用该算法,结合三值模代数特点以及电路面积估计模型,沿非循环格雷码极性遍历路径进行三值FPRM电路面积最佳极性搜索,得到面积最优的FPRM电路.最后对8个MCNC基准电路进行测试,结果表明：与0极性Reed-Muller电路相比,三值FPRM电路的面积平均减少56.2%.     

加权最小化问题中限制等距性的研究

本文针对加权最小化问题, 首先给出了测量矩阵的加权限制等距性(RIP)与加权鲁棒零空间特性(rNSP)的定义, 证明了加权RIP蕴含着加权rNSP. 最后以加权RIP作为充分条件, 给出了解重构的误差估计.     

基于K图的逻辑函数OC展开式在固定极性下的化简

分析了K图在表示逻辑函数最大项展开式的特点和性质,发现在K图中作含某格的所有聚合圈相应的和项中所含变量的极性与该格对应的最大项具有相同的极性.在此基础上提出了基于K图的逻辑函数OC展开式在固定极性下化简的新方法.该方法可以利用K图直接得到逻辑函数的最小化的OC展开式,从而省略了传统方法把K图转换为dj图的步骤,具有直观、方便等特点.     

逻辑函数的减-非和除-非展开式的最小化方法

讨论了布尔减和布尔除的定义以及逻辑函数在布尔减及非运算、布尔除及非运算完备集中的展开,给出了减-非和除-非逻辑函数的化简公式.在此基础上提出了减-非和除-非逻辑函数的代数化简法以及图形化简法,并给出了化简实例.实例验证了上述化简方法的有效性.     

基于XOR门的静态逻辑电路功耗优化技术

提出了一种新的基于XOR门的静态逻辑电路功耗优化技术.通过极性转换,可迅速得到基于XOR门的静态逻辑电路的最优结构,达到优化功耗的目的.实验结果表明,本文提出的算法在功耗节省方面比其他同类算法更有效.