1.一种异或‑多数逻辑图中的反相器数量优化方法,其特征在于包括以下步骤:
步骤①:计算出XMG中反相器初始总数C1;
步骤②:对于XMG中任一结点q,根据该结点的输入连接线的条数M判断该结点的类型,如果M=3,则判断该结点为多数逻辑结点;如果M=2,则判断该结点为异或逻辑结点;
步骤③:判断结点q执行反相器传输规则前后所引起的反相器数量的改进值,记为savings;
对于多数逻辑结点,满足如下反相器传输规则(1)或(2)或(3):
对于异或逻辑结点,满足如下反相器传输规则(4)或(5):
式(1)~(3)中,“<>”表示多数逻辑运算,x、y、z表示任一多数逻辑结点的三个输入,x、y、z上的横线表示该多数逻辑结点的输入连接线上有反相器,“=”表示等式左右两个多数逻辑结点的逻辑功能一致;式(4)~(5)中, 表示异或逻辑运算,m、n表任一异或逻辑结点的两个输入,m、n上的横线表示该异或逻辑结点的输入连接线上有反相器;
针对任一多数逻辑结点,记A1为该多数逻辑结点的输入连接线和输出连接线上的所有反相器的数量,B1为该多数逻辑结点的输入连接线和输出连接线上没有反相器的连接线的数量,记S1为该多数逻辑结点的savings值:S1=A1‑B1 (6)
针对任一异或逻辑结点,记A2为该异或逻辑结点的输入连接线和输出连接线上的所有反相器的数量,B2为该异或逻辑结点的输入连接线和输出连接线上没有反相器的连接线的数量,C为修正参数,记S2为该异或逻辑结点的savings值:S2=A2‑B2+C (7)
S2的计算分三种情况:
1)当该异或逻辑结点的输入连接线上没有反相器时,C=‑1,则S2=A2‑B2‑1;
2)当该异或逻辑结点的输入连接线上只有一个反相器时,C=1,则S2=A2‑B2+1;
3)当该异或逻辑结点的输入连接线上有两个反相器时,对于该异或逻辑结点的所有输出连接线,若存在反相器的输出连接线数量小于或等于没有反相器的输出连接线数量,则直接令S2=2;否则按照公式(7)计算,此时令C=1,则S2=A2‑B2+1;
计算出savings值S1或者S2后,如果S1为正数,则在XMG中执行反相器传输规则(1)或(2)或(3),转至步骤⑤;如果S2为正数,则在XMG中执行反相器传输规则(4)或(5),转至步骤⑤;
如果S1或者S2为负数,则执行步骤④;
步骤④:定义结点集合Q由结点q及与q的输出连接线相连接的所有结点组成,判断集合Q中所有结点执行反相器传输规则前后所引起的反相器数量的改进值,记为savings_two_level;针对集合Q中的每个结点,分别按照步骤②判断结点的类型,并分别按照结点的类型调用式(6)或式(7)计算savings值,则savings_two_level为集合Q中所有结点的savings值之总和;如果savings_two_level为正数,则分别对集合Q中所有结点在XMG中按照结点的类型执行相应的反相器传输规则,否则执行步骤⑤;
步骤⑤:遍历XMG中下一个结点,重复步骤②~④,直到将XMG中所有结点遍历一遍为止,完成对XMG中反相器数量的第一遍优化;
步骤⑥:完成对XMG中反相器数量的第一遍优化后,计算当前XMG中反相器总数C2,比较当前XMG中反相器总数C2与执行步骤②~⑤之前的XMG中反相器初始总数C1,如果C2=C1,则说明第一遍优化已得到XMG中反相器数量的最优结果,优化结束;如果C2﹤C1,则以该当前XMG中反相器总数C2作为第二遍优化前XMG中反相器初始总数,再次执行步骤②~⑤进行第二遍优化,如此循环进行第i遍优化,i为等于或大于2的正整数,直至第i遍优化后XMG中反相器总数与第i遍优化前XMG中反相器初始总数相等,则说明已得到XMG中反相器数量的最优结果,优化结束。