一种逻辑函数的ESOP最小化方法

摘要

本发明公开了一种逻辑函数的ESOP最小化方法，通过将n变量逻辑函数的ESOP最小化过程中存在3n全局空间的最优覆盖搜索问题转换为多个立方体分块中的最简连通问题以减少搜索空间，从而摆脱了变量规模的约束；另外，直接操作立方体集合而无需转换成最小项集合，从而避免了乘积项数量的限制；为了实现快速ESOP的精确最小化，采用立方体EXOR转换图的最小化转换算法以提高运行效率，有效降低了计算复杂度及内存占用量，且计算时间对输入变量的数量不敏感而仅与逻辑函数包含的乘积项数量以及相交性有关的特性，能有效地实现任意n变量完全规定逻辑函数的ESOP最小化；优点是不受逻辑函数中乘积项数量和变量数量的限制，能对任意逻辑函数的ESOP进行最小化处理。

说明书

技术领域

本发明涉及一种逻辑函数的最小化方法，尤其是涉及一种逻辑函数的ESOP最小化方法。

背景技术

以往超大规模集成电路(VLSI)低功耗设计主要针对与/或电路展开，而数字逻辑电路既可表示为与/或形式的布尔逻辑，也可以表示为与/异或形式的Reed-Muller逻辑。经研究表明，与/异或构成的异或和之积式(exclusive-orsumofproducts,ESOP)比与/或构成的传统和之积式(sumofproducts,SOP)具有更精简的形式；其次，采用ESOP实现的部分功能电路(如算术电路、通信电路、奇偶校验电路等)能够获得面积、功耗、速度和可测性等方面的显著优势，特别是在奇偶校验电路中，ESOP乘积项数与输入变量数成线性关系，而SOP二者成指数关系；此外，EXOR门是可逆逻辑中的基本构造单元，利用ESOP可直接映射成可逆逻辑，其最小化有利于量子可逆电路的高效低成本综合。因此，研究与/异或电路低功耗逻辑综合技术对发展和完善集成电路低功耗设计方法有重要意义。

针对与/异或电路的低功耗逻辑综合，国内学者的研究热点集中在固定极性Reed-Muller(Fixed-PolarityReed-Muller,FPRM)电路和混合极性Reed-Muller(Mixed-PolarityReed-Muller,MPRM)电路的优化上，其中MPRM包含所有的FPRM，MPRM比FPRM更可能获得功耗较小的与/异或电路，但还没有涉及ESOP电路的研究，各种与/异或表达式的关系为ESOP是与/异或电路所有子类中最一般的AND-EXOR形式，能包含最少数量的乘积项。

针对完全规定逻辑函数的ESOP最小化，国外学者提出了许多化简算法和系统方法，如Helliwell等提出利用Helliwell函数来确定一种最佳覆盖的化简方法，该方法采用穷尽搜索策略，实现精确ESOP最小化，但的穷举空间无法处理3变量以上函数；其次，基于乘积项转换规则提出几种启发式化简软件，如EXMIN2、MINT和EXORCISM-2,3,4，其中以EXORCISM-4性能最优，可处理较大规模的多输出函数，但不能确保取得最小ESOP，且当乘积项数达到1000个以上时化简效率快速下降；另外，Mishchenko等、Sasao和Stergiou等分别提出三种非常有效的化简算法，主要适用于部分测试基准电路的ESOP最小化。另一方面，由于ESOP的最小化求解相当困难还未能提出真正有效的ESOP最小化算法，在实际应用中，如文献Gaidukov提出了一种基于最小化定理的ESOP最小化方法，但因其计算复杂度，只能处理6变量以下的Boolean函数；尽管还有一些算法能处理20变量以上函数的ESOP最小化，但在乘积项(乘积项也称为立方体)数量上却有相应限制。

发明内容

本发明所要解决的技术问题是提供一种逻辑函数的ESOP最小化方法，该最小化方法不受逻辑函数中乘积项数量和变量数量的限制，能对任意逻辑函数的ESOP进行最小化处理。

本发明解决上述技术问题所采用的技术方案为：一种逻辑函数的ESOP最小化方法，包括以下步骤：

①读入逻辑函数的ESOP式n为逻辑函数f的变量数且n>3，k为整数且1≤k≤n，(x_n,x_n-1,…,x_k,…,x₁)为ESOP式f的n个输入变量，i为整数且0≤i≤3ⁿ-1；π_i为ESOP式f的第i个立方体，π_i用输入变量序列表示为其中表示第k个输入变量x_k在立方体π_i中的出现形式，将称为变量文字，简称文字，当时，第k个输入变量x_k在立方体π_i中以原变量x_k出现，当时，第k个输入变量x_k在立方体π_i中以反变量出现，当时，第k个输入变量x_k在立方体π_i中不出现；b_i为立方体π_i的系数，b_i为常数且b_i∈{0,1}，当b_i＝0时，立方体π_i在ESOP式f中不存在，当b_i＝1时，立方体π_i在ESOP式f中存在，为“异或和”运算符；若在ESOP式f的两个立方体中呈现不同文字，则称两立方体在处文字相异，即两立方体在处具有不同文字部分，若在两个立方体中呈现相同文字，则称两立方体在处文字相同，即两立方体在处具有相同文字部分；

②统计逻辑函数的ESOP式f中存在的所有立方体，将其数量记为m，m为正整数且1≤m≤3ⁿ-1；将m个立方体记为π'₁,π'₂,…,π'_m，m个立方体构成的立方体集合记为Π，Π＝{π'₁,π'₂,…,π'_m}；

③将两个立方体具有不同文字部分的文字相异处的数量定义为两个立方体之间的距离，将两个立方体之间的距离记为d_l，计算立方体集合∏中每两个立方体π'_a和π'_b之间的距离d_l(π'_a,π'_b)，其中，a,b∈{1,2,…,m}且a≠b；

④根据具有相同文字部分且任意两立方体之间的距离d_l小于等于3的规则来划分立方体集合Π，将立方体集合Π中满足上述规则的立方体组成的集合称为立方体分块Π'，立方体分块Π'最多具有3个文字相异处；

⑤判断立方体集合Π中是否成功划分得到立方体分块Π'：如果不存在立方体分块Π'，则对立方体集合Π的划分为无效划分，ESOP最小化结束；如果存在立方体分块Π'，则对立方体集合Π的划分为有效划分，进入步骤⑥操作；

⑥计算步骤④划分得到的各个立方体分块Π'的势|Π'|，将具有最大的势的立方体分块Π'记为Π'_max，对Π'_max进行变量移位操作后再进行变量分组操作，得到立方体分块Π”_max，其中变量移位操作和变量分组操作的具体过程为：

⑥-1将立方体分块Π'_max中包含的立方体分别进行变量移位操作：立方体分块Π'_max中包含的立方体或者在三个变量文字和处文字相异，或者在两个变量文字和处文字相异，或者在一个变量文字处文字相异，其中t₁、t₂和t₃均为正整数且1≤t₁<t₂<t₃≤m；

如果立方体分块Π'_max中包含的立方体在和三个变量文字处文字相异，则将每个立方体的移到输入变量序列的第1位，移到输入变量序列的第2位，移到输入变量序列的第3位，其他变量保持不变，得到新的立方体，该立方体的输入变量序列为

如果立方体分块Π'_max中包含的立方体在和两个变量文字处文字相异，则将每个立方体的移到输入变量序列的第1位，移到输入变量序列的第2位，其他保持不变，得到新的立方体，该立方体的输入变量序列为如果立方体分块Π'_max中包含的立方体在一个变量文字处文字相异，则将每个立方体的移到输入变量序列的第1位，其他变量保持不变，得到新的立方体，该立方体的输入变量序列为

⑥-2对步骤⑥-1得到的每个新的立方体分别进行分组：将每个新的立方体的输入变量序列从低位到高位每3位分为一组位串，最后一组不够3位时也作为一组位串，从低位到高位依次记为第一组位串，第二组位串，以此类推；

⑦构造三输入变量逻辑函数的立方体EXOR转换图G(V，E)，其中V表示立方体EXOR转换图G的顶点集合，E表示立方体EXOR转换图G的边集合，V包括27个顶点，每个顶点用一个长度为3的位串表示，V＝{000、010、100、110、001、011、101、111、0-0、-00、-10、1-0、00-、01-、10-、11-、0-1、-01、-11、1-1、--0、0--、-0-、-1-、1--、--1、---}，E＝{e(v_c,v_d)|d_l(v_c,v_d)＝1,v_c,v_d∈V且c≠d}，其中e(v_c,v_d)|d_l(v_c,v_d)＝1表示当顶点v_c和顶点v_d之间的距离等于1时，顶点v_c和顶点v_d之间存在边；构造的立方体EXOR转换图G为一个6-正则图，立方体EXOR转换图G中任意顶点可对应3个圈长为3的圈；

⑧采用立方体EXOR转换图对立方体分块Π”_max进行转换，具体步骤如下所述：

⑧-1提取立方体分块Π”_max中每个立方体的第一组位串构成一个位串集合；

⑧-2选择立方体EXOR转换图中与位串集合中的位串相同的顶点，这些顶点构成待转换顶点集合；

⑧-3计算待转换顶点集合的权和1≤s≤|Π”_max|，w_s为待转换顶点集合中第s个待转换顶点的权，|Π”_max|为Π”_max的势，∑为求和符号；位串中不含“-”的顶点的权为3，位串中含1个“-”的顶点的权为2，位串中含2个“-”的顶点的权为1，位串中含3个“-”的顶点的权为0；

⑧-4根据以下规则确定待转换顶点集合中各顶点之间的连通关系：

a.如果待转换的两个顶点能包含在同一个圈长为3的圈上，那么待转换的两个顶点在该圈上连通；该圈为待转换顶点的一个连通圈，

b.如果待转换的两个顶点能分别包含具有相同顶点的两个圈长为3的圈上，那么待转换的两个顶点通过该两圈连通，该两圈为待转换顶点的两个连通圈；

c.如果待转换的两个顶点不能分别包含在有相交的两个圈上，那么两个顶点不能连通；

d.任意待转换顶点只能包含在一个圈长为3的圈上；

e.除待转换的顶点以外的其他顶点最多可被两个圈长为3的圈包含；

⑧-5在步骤⑧-4中确定的连通关系基础上，选取以下两种顶点构成保留顶点集合Π_min：

a.不被任何一个连通圈包含的待转换顶点；

b.除待转换的顶点以外的其他顶点中仅被一个连通圈包含的顶点；

⑨计算保留顶点集合的权和w'_s'为保留顶点集合Π_min中第s'个保留顶点的权，|Π_min|为Π_min的势，1≤s'≤|Π_min|；

⑩比较W'和W的大小，如果W'<W，则采用保留顶点集合Π_min中包含的|∏_min|个顶点对应的长度为3的位串取代Π”_max中任意|Π_min|个立方体的第一组位串，删除Π”_max中未被取代的其他立方体，得到新的立方体分块Π'_min，如果W'≥W，则直接将Π”_max作为新的立方体分块Π'_min；

将新的立方体分块Π'_min中包含的立方体分别进行与步骤⑥-1中变量移位操作相反的变量复位操作，即将新的立方体分块Π'_min中立方体的处于步骤⑥-1中立方体分块Π'_max中包含的立方体移位后的位置处的变量移动到该立方体中处于步骤⑥-1中立方体分块Π'_max中包含的立方体移位前的位置处，得到立方体分块Π”_min；将立方体分块Π”_min取代前一次得到的立方体集合Π中的Π'_max，得到更新后的立方体集合Π；

采用步骤④的方法重新划分新更新后的立方体集合Π得到立方体分块Π'，如果划分得到的立方体分块Π'中包含已经进行过变量移位操作的立方体分块Π'，则将这些已经进行过变量移位操作的立方体分块Π'视为无效的立方体分块不进入后续步骤处理，其他未进行过变量移位操作的立方体分块Π'视为有效的立方体分块进入后续步骤处理；

按照步骤⑤-步骤对有效的立方体分块进行迭代操作，直到步骤⑤中满足ESOP最小化结束条件，最后一次更新后的立方体集合∏即为逻辑函数f的ESOP最小化对应的立方体集合。

与现有技术相比，本发明的优点在于通过将n变量逻辑函数的ESOP最小化过程中存在3ⁿ全局空间的最优覆盖搜索问题转换为多个立方体分块中的最简连通问题以减少搜索空间，从而摆脱了变量规模的约束；另外，直接操作立方体集合而无需转换成最小项集合，从而避免了乘积项数量的限制；为了实现快速ESOP的精确最小化，采用立方体EXOR转换图的最小化转换算法以提高运行效率，由此，本发明有效降低了计算复杂度及内存占用量，且计算时间对输入变量的数量不敏感而仅与逻辑函数包含的乘积项数量以及相交性有关的特性，能有效地实现任意n变量完全规定逻辑函数的ESOP最小化，不受逻辑函数中乘积项数量和变量数量的限制，能对任意逻辑函数的ESOP进行最小化处理。

具体实施方式

以下结合实施例对本发明作进一步详细描述。

实施例：一种逻辑函数的ESOP最小化方法，包括以下步骤：

①读入逻辑函数的ESOP式n为逻辑函数f的变量数且n>3，k为整数且1≤k≤n，(x_n,x_n-1,…,x_k,…,x₁)为ESOP式f的n个输入变量，i为整数且0≤i≤3ⁿ-1；π_i为ESOP式f的第i个立方体，π_i用输入变量序列表示为其中表示第k个输入变量x_k在立方体π_i中的出现形式，将称为变量文字，简称文字，当时，第k个输入变量x_k在立方体π_i中以原变量x_k出现，当时，第k个输入变量x_k在立方体π_i中以反变量出现，当时，第k个输入变量x_k在立方体π_i中不出现；b_i为立方体π_i的系数，b_i为常数且b_i∈{0,1}，当b_i＝0时，立方体π_i在ESOP式f中不存在，当b_i＝1时，立方体π_i在ESOP式f中存在，为“异或和”运算符；若在ESOP式f的两个立方体中呈现不同文字，则称两立方体在处文字相异，即两立方体在处具有不同文字部分，若在两个立方体中呈现相同文字，则称两立方体在处文字相同，即两立方体在处具有相同文字部分；

②统计逻辑函数的ESOP式f中存在的所有立方体，将其数量记为m，m为正整数且1≤m≤3ⁿ-1；将m个立方体记为π'₁,π'₂,…,π'_m，m个立方体构成的立方体集合记为Π，Π＝{π'₁,π'₂,…,π'_m}；

③将两个立方体具有不同文字部分的文字相异处的数量定义为两个立方体之间的距离，将两个立方体之间的距离记为d_l，计算立方体集合∏中每两个立方体π'_a和π'_b之间的距离d_l(π'_a,π'_b)，其中，a,b∈{1,2,…,m}且a≠b；

④根据具有相同文字部分且任意两立方体之间的距离d_l小于等于3的规则来划分立方体集合Π，将立方体集合Π中满足上述规则的立方体组成的集合称为立方体分块Π'，立方体分块Π'最多具有3个文字相异处；

⑤判断立方体集合Π中是否成功划分得到立方体分块Π'：如果不存在立方体分块Π'，则对立方体集合Π的划分为无效划分，ESOP最小化结束；如果存在立方体分块Π'，则对立方体集合Π的划分为有效划分，进入步骤⑥操作；

⑥计算步骤④划分得到的各个立方体分块Π'的势|Π'|，将具有最大的势的立方体分块Π'记为Π'_max，对Π'_max进行变量移位操作后再进行变量分组操作，得到立方体分块Π”_max，其中变量移位操作和变量分组操作的具体过程为：

⑥-1将立方体分块Π'_max中包含的立方体分别进行变量移位操作：立方体分块Π'_max中包含的立方体或者在三个变量文字和处文字相异，或者在两个变量文字和处文字相异，或者在一个变量文字处文字相异，其中t₁、t₂和t₃均为正整数且1≤t₁<t₂<t₃≤m；

如果立方体分块Π'_max中包含的立方体在和三个变量文字处文字相异，则将每个立方体的移到输入变量序列的第1位，移到输入变量序列的第2位，移到输入变量序列的第3位，其他变量保持不变，得到新的立方体，该立方体的输入变量序列为

如果立方体分块Π'_max中包含的立方体在和两个变量文字处文字相异，则将每个立方体的移到输入变量序列的第1位，移到输入变量序列的第2位，其他保持不变，得到新的立方体，该立方体的输入变量序列为如果立方体分块Π'_max中包含的立方体在一个变量文字处文字相异，则将每个立方体的移到输入变量序列的第1位，其他变量保持不变，得到新的立方体，该立方体的输入变量序列为

⑥-2对步骤⑥-1得到的每个新的立方体分别进行分组：将每个新的立方体的输入变量序列从低位到高位每3位分为一组位串，最后一组不够3位时也作为一组位串，从低位到高位依次记为第一组位串，第二组位串，以此类推；

⑦构造三输入变量逻辑函数的立方体EXOR转换图G(V，E)，其中V表示立方体EXOR转换图G的顶点集合，E表示立方体EXOR转换图G的边集合，V包括27个顶点，每个顶点用一个长度为3的位串表示，V＝{000、010、100、110、001、011、101、111、0-0、-00、-10、1-0、00-、01-、10-、11-、0-1、-01、-11、1-1、--0、0--、-0-、-1-、1--、--1、---}，E＝{e(v_c,v_d)|d_l(v_c,v_d)＝1,v_c,v_d∈V且c≠d}，其中e(v_c,v_d)|d_l(v_c,v_d)＝1表示当顶点v_c和顶点v_d之间的距离等于1时，顶点v_c和顶点v_d之间存在边；构造的立方体EXOR转换图G为一个6-正则图，立方体EXOR转换图G中任意顶点可对应3个圈长为3的圈；

⑧采用立方体EXOR转换图对立方体分块Π”_max进行转换，具体步骤如下所述：

⑧-1提取立方体分块Π”_max中每个立方体的第一组位串构成一个位串集合；

⑧-2选择立方体EXOR转换图中与位串集合中的位串相同的顶点，这些顶点构成待转换顶点集合；

⑧-3计算待转换顶点集合的权和1≤s≤|Π”_max|，w_s为待转换顶点集合中第s个待转换顶点的权，|Π”_max|为Π”_max的势，∑为求和符号；位串中不含“-”的顶点的权为3，位串中含1个“-”的顶点的权为2，位串中含2个“-”的顶点的权为1，位串中含3个“-”的顶点的权为0；

⑧-4根据以下规则确定待转换顶点集合中各顶点之间的连通关系：

a.如果待转换的两个顶点能包含在同一个圈长为3的圈上，那么待转换的两个顶点在该圈上连通；该圈为待转换顶点的一个连通圈，

b.如果待转换的两个顶点能分别包含具有相同顶点的两个圈长为3的圈上，那么待转换的两个顶点通过该两圈连通，该两圈为待转换顶点的两个连通圈；

c.如果待转换的两个顶点不能分别包含在有相交的两个圈上，那么两个顶点不能连通；

d.任意待转换顶点只能包含在一个圈长为3的圈上；

e.除待转换的顶点以外的其他顶点最多可被两个圈长为3的圈包含；

⑧-5在步骤⑧-4中确定的连通关系基础上，选取以下两种顶点构成保留顶点集合Π_min：

a.不被任何一个连通圈包含的待转换顶点；

b.除待转换的顶点以外的其他顶点中仅被一个连通圈包含的顶点；

⑨计算保留顶点集合的权和w'_s'为保留顶点集合Π_min中第s'个保留顶点的权，|Π_min|为Π_min的势，1≤s'≤|Π_min|；

⑩比较W'和W的大小，如果W'<W，则采用保留顶点集合Π_min中包含的|∏_min|个顶点对应的长度为3的位串取代Π”_max中任意|Π_min|个立方体的第一组位串，删除Π”_max中未被取代的其他立方体，得到新的立方体分块Π'_min，如果W'≥W，则直接将Π”_max作为新的立方体分块Π'_min；

将新的立方体分块Π'_min中包含的立方体分别进行与步骤⑥-1中变量移位操作相反的变量复位操作，即将新的立方体分块Π'_min中立方体的处于步骤⑥-1中立方体分块Π'_max中包含的立方体移位后的位置处的变量移动到该立方体中处于步骤⑥-1中立方体分块Π'_max中包含的立方体移位前的位置处，得到立方体分块Π”_min；将立方体分块Π”_min取代前一次得到的立方体集合Π中的Π'_max，得到更新后的立方体集合Π；

采用步骤④的方法重新划分新更新后的立方体集合Π得到立方体分块Π'，如果划分得到的立方体分块Π'中包含已经进行过变量移位操作的立方体分块Π'，则将这些已经进行过变量移位操作的立方体分块Π'视为无效的立方体分块不进入后续步骤处理，其他未进行过变量移位操作的立方体分块Π'视为有效的立方体分块进入后续步骤处理；

按照步骤⑤-步骤对有效的立方体分块进行迭代操作，直到步骤⑤中满足ESOP最小化结束条件，最后一次更新后的立方体集合∏即为逻辑函数f的ESOP最小化对应的立方体集合。

本实施例的方法采用C语言编程加以实现，在硬件环境为PentiumDualE22002.20GHzCPU、3GBRAM的PC机和软件环境为WindowsXPProfessional操作系统下用VisualStudio2008编译并调试，并用MCNC基准电路进行测试。

为了验证本发明的ESOP最小化方法的有效性和效率，分别采用本发明的ESOP最小化方法和目前公认的方法(EXORCISM-4和Min-tau2)对21个不同规模的两类MCNC基准电路进行ESOP最小化性能测试，为了公平比较，现有两种方法均采用C语言编程实现并在相同硬件和软软环境下运行。在11个小规模的MCNC基准电路测试下的ESOP最小化比较结果如表1所示。

表1小规模MCNC基准电路下的ESOP最小化的比较结果

表1中，从左至右依次为基准电路、所有输出逻辑函数的ESOP式包含的立方体数总和、所有输出逻辑函数的ESOP式包含的文字数总和以及算法的CPU运行时间(单位为s)。分析表1可以看出，本发明的ESOP最小化方法在小规模MCNC基准电路测试中获得与Min-tau2相同的精确ESOP最小化结果，在基准电路sqrt8和t481上获得了更低文字数，同时本发明的ESOP最小化方法只需花费极少计算时间，运算效率明显优于EXORCISM-4，表明本发明的ESOP最小化方法能在多项式时间内获得最小乘积项数的同时并降低文字数。

采用本发明的ESOP最小化方法对10个大规模的MCNC基准电路进行最小化操作，其ESOP最小化结果如表2所示。

表2大规模MCNC基准电路下的测试结果

由于获得的ESOP立方体数相对较大且没有可比较的方法数据，表2中因而没有统计文字数。对于表2中除带*的基准电路外，EXORCISM-4和Min-tau2两种方法均效率低下无法运算，当运行基准电路apex1与apex5时，EXORCISM-4的运行时间达到了8分钟，而Min-tau2则超过了3小时。分析表2可以看出，本发明的ESOP最小化方法可以实现对大变量逻辑函数的ESOP最小化，表2中反映本发明的ESOP最小化方法的CPU运行时间对输入变量的数量不敏感，而与逻辑函数包含的立方体数量以及相交性有关。如基准电路exmaple2、i5和i7等，虽然变量数达到199而立方体数却小于369，CPU运行时间不多于20ms；但是对于立方体数大的基准电路，如dalu、frg2和i8等，立方体数最高达到4377，CPU运行时间则几十倍增加。