1.一种逻辑电路近似实现方法,其特征在于包括以下步骤:
步骤1:令f表示用于表达待优化的逻辑电路的逻辑功能用的逻辑函数,f采用“与/或”逻辑形式,f的输入变量数为w、输出变量数为v,f中包含有m个乘积项;令fa表示f的近似函数,fa也采用“与/或”逻辑形式,fa的输入变量数也为w、输出变量数也为v,fa中包含有n个乘积项;规定仅属于f或fa的最小项个数不能大于H个;
规定构成f和fa各自中的每一个乘积项中的变量,其排列顺序均一样,并且对于任意一个乘积项中的一个变量,有3种形式出现在乘积项中,即反变量形式、原变量形式和不出现,用“0”表示该变量以反变量形式出现在该乘积项中,用“1”表示该变量以原变量形式出现在该乘积项中,用“2”表示该变量没有出现在该乘积项中,规定变量形式0的取反为1、1的取反为0、2的取反为它本身;规定同一变量不同形式之间的“异或”运算满足0^1=1、0^2=1、1^2=1、0^0=0、1^1=0、2^2=0,且满足交换律;规定同一变量不同形式之间的“相交”运算满足 1∩2=1、0∩2=0、1∩1=1、0∩0=0、2∩2=2,且满足交换律;
将f中包含的所有乘积项构成的集合记为Cf,将Cf中的两个乘积项p'和p”之间的“异或”运算用p'^p”表示,p'^p”等于p'中的各个变量形式与p”中对应变量形式之间的“异或”运算;将Cf中的两个乘积项p'和p”之间的“相交”运算用p'∩p”表示,p'∩p”等于p'中的各个变量形式与p”中对应变量形式之间的“相交”运算;
上述,w≥1,v≥1,m≥2,n≥1,H>0,符号“^”表示“异或”运算,符号“∩”表示“相交”运算, 表示空集;
步骤2:定义两个初始值为空集的集合,分别记为Cer和CE;
步骤3:从Cf中任意取出两个输出相等的乘积项,设定取出的两个乘积项分别为序号为i的乘积项和序号为j的乘积项,对应记为pi和pj;然后执行pi和pj之间的“相交”运算,若pi∩pj=pi,则在Cf中删除pi,再执行步骤10;若pi∩pj=pj,则在Cf中删除pj,再执行步骤10;若pi∩pj≠pi且pi∩pj≠pj,则执行步骤4;其中,0≤i<m,0≤j<m,i≠j;
步骤4:执行pi和pj之间的“异或”运算;然后统计pi^pj的结果中值为“1”的个数,若pi^pj的结果中值为“1”的个数小于或等于2个,则执行步骤5;若pi^pj的结果中值为“1”的个数大于2个,则执行步骤10;
步骤5:若pi^pj的结果中值为“1”的个数为1个,则由pi和pj生成一个新的乘积项,记为Q,Q为通过在pi或pj中去除导致pi^pj的结果中值为“1”的变量后得到的乘积项,然后将乘积项Q存储到Cf中,并在Cf中删除pi和pj,再执行步骤10;若pi^pj的结果中值为“1”的个数为2个,则执行步骤6;
步骤6:分析导致pi^pj的结果中值为“1”的个数为2个的情况,若2个“1”均由0^1=1产生,则执行步骤10;若2个“1”由0^1=1和0^2=1产生或由0^1=1和1^2=1产生,则执行步骤
7;若2个“1”由1^2=1和0^2=1产生,则执行步骤8;
步骤7:确定导致pi^pj的结果中值为“1”的2个变量,设定这2个变量分别为变量x和y;然后由pi和pj生成两个新的乘积项,分别记为Q和E,Q为通过在pi或pj中去除变量x和y后得到的乘积项,E通过以下方法获得:从pi和pj中找出变量x和y均出现的乘积项,设定变量x和y均出现在pj中;然后确定pj中与pi中对应的变量形式之间的“异或”运算为1^2=1或0^2=1的变量,设定pj中的变量x形式与pi中对应的变量x形式之间的“异或”运算为1^2=1或0^2=1,那么将pj中的变量x形式取反后得到的新的乘积项就是E;再执行步骤9;
步骤8:确定导致pi^pj的结果中值为“1”的2个变量,设定这2个变量分别为变量x和y;然后由pi和pj生成两个新的乘积项,分别记为Q和E,Q为通过在pi或pj中去除变量x和y后得到的乘积项,E通过以下方法获得:将在pi和pj中出现的变量x和y形式取反后替换pi或pj中原来的x和y的变量形式后得到的新的乘积项就是E;再执行步骤9;
步骤9:将乘积项E存储到CE中;然后在CE中删除与Cer和Cf中相同的最小项;接着统计Cer中包含的最小项的个数与CE中包含的最小项的个数的和值,若和值小于或等于H,则在Cf中删除pi和pj,将乘积项Q存储到Cf中,将CE并入到Cer中,清空CE,再执行步骤10;若和值大于H,则清空CE,再执行步骤10;
步骤10:返回步骤3继续执行,直至Cf中找不到两个乘积项可以通过步骤3到步骤9进行简化,此时Cf中包含的所有乘积项作为fa中的乘积项。