欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2020106124060
申请人: 宁波大学
专利类型:发明专利
专利状态:未下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种单输出组合逻辑电路的近似简化方法,其特征在于包括以下步骤:

步骤1:令f表示用于表达待简化的逻辑电路的逻辑功能用的单输出逻辑函数,f采用“与/或”逻辑形式,f的输入变量的数量为w个,w个输入变量分别为x1,x2,…,xw,f的输出变量的数量为1个,f中包含有m个乘积项;令fa表示f的近似函数,fa采用“与/或/异或”逻辑形式,fa的输入变量和f的输入变量相同,fa的输出变量的数量为1个,fa中包含有n个乘积项;

规定仅属于f或仅属于fa的最小项的数量不能大于H个;

规定构成f和fa各自的每个乘积项中的输入变量,其排列顺序均一样,并且对于任意一个乘积项中的任意一个输入变量,用“0”表示该输入变量以反变量形式出现在该乘积项中,即出现形式为反变量,用“1”表示该输入变量以原变量形式出现在该乘积项中,即出现形式为原变量,用“2”表示该输入变量没有出现在该乘积项中;

将f中的所有乘积项构成的乘积项集合记为Cf,并对Cf中的每个乘积项按序标记序号;

定义符号“∩”表示“相交”运算,定义符号 表示两个不同的集合对应的逻辑覆盖之间的互斥运算,且对于两个不同的乘积项集合 和 它们之间的互斥运算表示为即 的结果等于在 中去除 和 的公共部分,定义符号 表示空集;

定义G[xk0]Q表示输入变量xk以反变量形式在乘积项Q中出现的频次,定义G[xk1]Q表示输入变量xk以原变量形式在乘积项Q中出现的频次,其中,G[xk0]Q的值等于将乘积项Q展开为最小项后,输入变量xk以反变量形式出现在这些最小项中的次数,G[xk1]Q的值等于将乘积项Q展开为最小项后,输入变量xk以原变量形式出现在这些最小项中的次数;

上述,w为正整数,w≥2,x1,x2,…,xw对应表示f和fa的第1个输入变量、第2个输入变量、……、第w个输入变量,m为正整数,m≥2,n为正整数,n≥1,H为正整数,H>0,xk表示f和fa的第k个输入变量,1≤k≤w;

步骤2:定义Ccur、Cdis、Cdis1、CRMD、Ctmp、Cer、CM、Cpnt和Cxor均表示集合,且初始值均为空集;

构建一个包含所有输入变量x1,x2,…,xw的乘积项pz,并将pz中的各个输入变量的表示形式的初始值均设为“2”;

步骤3:在Cf中任取2个乘积项,分别记为pi和pj;然后将乘积项pi存放到Ccur中,将乘积项pj存放到Cdis中,执行 将Ctmp中的所有乘积项存放到Cdis中,在Cf中删除pi和pj,清空Ctmp和Ccur;其中,i∈[1,m],j∈[1,m],i≠j,i为pi的序号,j为pj的序号;

步骤4:检查Cf是否为空集,如果 则执行步骤5,否则,执行步骤6;

步骤5:在Cf中任取1个乘积项,记为pt;然后将pt存放到Ccur中,执行 将Ctmp

中的所有乘积项存放到Cdis中,在Cf中删除pt,清空Ctmp和Ccur,再返回执行步骤4;其中,t∈[1,m],t为pt的序号;

步骤6:统计Cdis中的乘积项的数量,记为M,若M≥2,则执行步骤7;若M<2,则将Cdis中的所有乘积项移除并存放到CM中,然后将CRMD中的所有乘积项移除并存放到Cdis中,再重新统计Cdis中的乘积项的数量,记为M',若M'≥2,则令M=M',并将pz中的各个输入变量的表示形式的取值均设为“2”,再执行步骤7;否则,将Cdis中的所有乘积项移除并存放到CM中,再执行步骤13;其中,M=M'中的“=”为赋值符号;

步骤7:统计各个输入变量x1,x2,…,xw在Cdis中的所有乘积项中的表示形式的取值为“0”、取值为“1”和取值为“2”的数量;然后将各输入变量x1,x2,…,xw在Cdis中的M个乘积项中的表示形式取值为“0”的统计结果组成的第一数组记为[[x10],[x20],…,[xk0],…,[xw0]],将各输入变量x1,x2,…,xw在Cdis中的M个乘积项中的表示形式取值为“1”的统计结果组成的第二数组记为[[x11],[x21],…,[xk1],…,[xw1]],将各输入变量x1,x2,…,xw在Cdis中的M个乘积项中的表示形式取值为“2”的统计结果组成的第三数组记为[[x12],[x22],…,[xk2],…,[xw2]];其中,[x10]表示输入变量x1在Cdis中的M个乘积项中的表示形式的取值为“0”的数量,[x20]表示输入变量x2在Cdis中的M个乘积项中的表示形式的取值为“0”的数量,[xk0]表示输入变量xk在Cdis中的M个乘积项中的表示形式的取值为“0”的数量,[xw0]表示输入变量xw在Cdis中的M个乘积项中的表示形式的取值为“0”的数量,[x11]表示输入变量x1在Cdis中的M个乘积项中的表示形式的取值为“1”的数量,[x21]表示输入变量x2在Cdis中的M个乘积项中的表示形式的取值为“1”的数量,[xk1]表示输入变量xk在Cdis中的M个乘积项中的表示形式的取值为“1”的数量,[xw1]表示输入变量xw在Cdis中的M个乘积项中的表示形式的取值为“1”的数量,[x12]表示输入变量x1在Cdis中的M个乘积项中的表示形式的取值为“2”的数量,[x22]表示输入变量x2在Cdis中的M个乘积项中的表示形式的取值为“2”的数量,[xk2]表示输入变量xk在Cdis中的M个乘积项中的表示形式的取值为“2”的数量,[xw2]表示输入变量xw在Cdis中的M个乘积项中的表示形式的取值为“2”的数量;

步骤8:计算每个输入变量以反变量形式在Cdis中的各个乘积项中出现的频次的总和,将输入变量xk以反变量形式在Cdis中的各个乘积项中出现的频次的总和记为[xk02],同样,计算每个输入变量以原变量形式在Cdis中的各个乘积项中出现的频次的总和,将输入变量xk以原变量形式在Cdis中的各个乘积项中出现的频次的总和记为[xk12], 然后获取第四数组和第五数组,对应记为[[x102],[x202],…,[xk02],…,[xw02]]和[[x112],[x212],…,[xk12],…,[xw12]];其中,1≤α≤M, 表示输入变量xk以反变量形式在乘积项pα中出现的频次,pα∈Cdis,pα表示Cdis中的第α个乘积项,表示输入变量xk以原变量形式在乘积项pα中出现的频次,[x102]表示输入变量x1以反变量形式在Cdis中的各个乘积项中出现的频次的总和,[x202]表示输入变量x2以反变量形式在Cdis中的各个乘积项中出现的频次的总和,[xw02]表示输入变量xw以反变量形式在Cdis中的各个乘积项中出现的频次的总和,[x112]表示输入变量x1以原变量形式在Cdis中的各个乘积项中出现的频次的总和,[x212]表示输入变量x2以原变量形式在Cdis中的各个乘积项中出现的频次的总和,[xw12]表示输入变量xw以原变量形式在Cdis中的各个乘积项中出现的频次的总和;

步骤9:如果第一数组中有若干个元素的值等于M,则将这些元素各自对应的输入变量在pz中的表示形式的取值改为“0”;如果第二数组中有若干个元素的值等于M,则将这些元素各自对应的输入变量在pz中的表示形式的取值改为“1”;如果第三数组中有若干个元素的值等于M,则将这些元素各自对应的输入变量在pz中的表示形式的取值改为“2”;

找出第四数组和第五数组中值最大的元素,若仅存在一个值最大的元素,则将该元素作为待处理元素;若存在多个值相同且最大的元素,则从这些元素中任取1个元素作为待处理元素;当待处理元素属于第四数组时,将Cdis中与待处理元素对应的输入变量的表示形式的取值为“1”的乘积项移除并存放到CRMD中,并将待处理元素对应的输入变量在pz中的表示形式的取值改为“0”;当待处理元素属于第五数组时,将Cdis中与待处理元素对应的输入变量的表示形式的取值为“0”的乘积项移除并存放到CRMD中,并将待处理元素对应的输入变量在pz中的表示形式的取值改为“1”;

步骤10:清空Ccur、Cer和Cpnt,将pz存放到Ccur中,执行 然后将

Cpnt中的所有乘积项移除并存放到Cer中,再统计更新后的Cer中包含的乘积项的数量,并与Cdis中包含的乘积项的数量进行比较,如果Cer中包含的乘积项的数量不大于Cdis中包含的乘积项的数量,则执行步骤11;否则,返回执行步骤6;

步骤11:计算Cer中的所有乘积项中包含的最小项的数量,记为N_Cer,N_Cer的计算过程为:逐个统计Cer中的每个乘积项中表示形式的取值为“2”的输入变量的数量,若存在一个乘积项中表示形式的取值为“2”的输入变量的数量为v个,那么该乘积项中包含的最小项的数v量为2个;然后计算Cer中的所有乘积项中包含的最小项数量的总和,记为N_Cer;同样,计算pz中包含的最小项的数量,记为N_pz,若pz中表示形式的取值为“2”的输入变量的数量为v'v' v'个,那么pz中包含的最小项的数量为2 个,即N_pz等于2 ;其中,v和v'均为整数,0<v≤w,0<v'≤w;

步骤12:引入中间变量λ,令 若 则将pz存放到CM中,将Cer中的所有乘积项

存放到Cxor中,清空Cer和Cdis,并判断CRMD是否为空集,若 则将CRMD中的所有乘积项存放到Cdis中,清空CRMD,将pz中的各个输入变量的表示形式的取值均置为“2”,返回执行步骤

6;若 则执行步骤13;

若 则统计Cdis中包含的乘积项的数量,如果Cdis中包含的乘积项的数量大于或等于2个,则返回执行步骤6;如果Cdis中包含的乘积项的数量小于2个,则将Cdis中的所有乘积项移除并存放到CM中,并判断CRMD是否为空集,若 则将CRMD中的所有乘积项存放到Cdis中,清空CRMD,将pz中的各个输入变量的表示形式的取值均置为“2”,返回执行步骤6,若执行步骤13;

步骤13:统计Cxor中的乘积项的数量,如果Cxor中的乘积项的数量大于或等于2个,则执行步骤14;否则,执行步骤16;

步骤14:在Cxor中任取2个乘积项,分别为pxor1和pxor2,如果pxor1和pxor2不相交,则执行步骤15;如果pxor1和pxor2相交,则将pxor1存放到事先清空的Ccur中,将pxor2存放到事先清空的Ctmp中,令 将Cdis1中的所有乘积项全部移除并存放到Cxor中,然后令再将Cdis1中的所有乘积项全部移除并存放到Cxor中;

步骤15:不断重复步骤14,直到Cxor中的任意2个乘积项均不相交,再执行步骤16;

步骤16:将Cxor和CM中的乘积项,按照每个乘积项中表示形式的取值为“2”的输入变量的数量从小到大的次序,逐个删除,并统计被删除的乘积项中包含的最小项的数量,直到所有被删除的乘积项中包含的最小项的数量最接近但不大于约定的值H为止,Cxor和CM中剩余的乘积项就构成近似函数fa;其中,Cxor中的乘积项之间为逻辑“或”关系,CM中内部存在相交关系的乘积项之间是逻辑“异或”关系,而内部存在不相交关系的乘积项之间是逻辑“或”关系,Cxor与CM之间是逻辑“异或”关系。