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

通过对包含无关项布尔逻辑函数SOP（Sum—of-Products）展开式和MPRM（MixedPolarityReed—Muller）展开式的研究,结合基于系数矩阵的FPRM（FixedPolarityReed—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在得到基本相同的算法结果时,时间效率亦基本相同.     

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

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

基于近似计算技术的FPRM逻辑功耗优化

提出了一种基于近似计算技术的FPRM逻辑功耗优化的算法, 该算法包括基于信号概率和跳变密度的固定极性Reed-Muller(Fixed Polarity Reed-Muller, FPRM)函数动态功耗模型, 基于遗传算法的以功耗优化为导向的RM逻辑极性搜索方法, 以及利用双锐积运算的RM逻辑错误率计算方法. 在错误率的约束下, 通过有选择性地删减部分乘积项, 实现功耗优化. 提出的算法用C语言实现, 并用MCNC Benchmark电路测试. 结果表明: 与原始FPRM电路功耗相比, 在平均错误率为3.21％时, 电路动态功耗平均减少了22.77％.     

基于近似逻辑的不完全指定FPRM函数的功耗优化

基于精确逻辑的逻辑综合和优化方法已有广泛的研究. 但有时并非需要精确逻辑, 从而可利用这种特性进行关键指标的综合和优化. 本文提出了基于近似逻辑的不完全指定固定极性Reed-Muller (Incompletely Specified Fixed Polarity RM, ISFPRM)逻辑函数的逻辑优化方法. 首先建立基于二级逻辑的功耗估算模型和近似电路的设计效能评估模型, 然后提出基于近似逻辑的ISFPRM函数的优化算法, 并用遗传算法加以实现. 所提算法应用于MCNC标准电路进行测试, 结果表明在一定的面积约束下, 电路每增加1%的误差率获得12%~18%的功耗优化     

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

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

基于矩形覆盖的FPRM电路多级面积优化

Reed-Muller(RM)逻辑因其优越的性能而广泛应用于数字电路,本文提出一种固定极性RM(FixedPolarityRM,FPRM)逻辑函数的多级优化方法.首先将电路表示成XOR/AND形式的FPRM逻辑函数,再计算函数的kernels和co-kernels,并由其生成矩阵,然后从矩阵中搜索尽可能多的矩形覆盖,利用矩阵分块和贪心策略逐步提取公共变量,最后生成多级逻辑表达式.MCNC Benchmarks测试后的结果表明,本方法得到的表达式比原RM逻辑表达式减少66%的文字(literals)数目,比onset表方法的优化结果减少19%.     

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

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

基于SMPSO算法的三值FPRM电路延时优化

n输入变量的三值FPRM电路存在3n个不同极性及其对应的函数展开式. 通过对三值列表转换技术以及三值FPRM逻辑表达式的研究, 并结合自适应变异粒子群算法提出一种三值FPRM电路延时优化解决方案. 首先根据三值FPRM逻辑表达式的特征建立延时估计模型; 然后结合三值列表转换技术和SMPSO算法, 对三值FPRM电路延时进行优化; 最后采用PLA格式的MCNC Benchmark电路进行算法测试. 结果表明: SMPSO算法相比于穷尽算法的优化效果更佳, 电路的延时和面积平均节省11.6%和18.6%.     

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

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