一种组合逻辑电路等效性检测方法

摘要

本发明公开了一种组合逻辑电路等效性检测方法，通过扩展余子式概念，将逻辑覆盖等效性检测问题分成分解成电路包含检测子问题,逐一求取其中一个电路表达式对另一个电路表达式各乘积项的余子式，然后在建立各乘积项余子式的香农结构图基础上判断其是否重言式，最后根据重言式判别结果确定两电路间是否覆盖等效关系；优点是通过求取乘积项余子式对逻辑函数进行分解和降阶处理,从而加快了覆盖等效性验证速度，可操作性和检测效率均较高，且不会出现内存爆炸问题，实验结构表明，本发明的方法稳定有效的，对EXPRESSO软件集成的三种算法所得电路的测试结果表明,与基于真值表和BDD的两种检测算法相比,具有明显的速度优势。

说明书

技术领域

本发明涉及一种检测方法，尤其是涉及一种组合逻辑电路等效性检测方法。

背景技术

逻辑等效性检测以逻辑层表达式不同的2个组合电路等效性检验为目的，根据给定 的2个组合电路的逻辑表达式，检测它们是否实现相同的逻辑功能。目前组合逻辑电路等效性检测方法主要有代数法、真值表判定法和功能性方法。

代数法是检验组合逻辑电路等效性的一种直观方法，该方法采用逻辑代数的基本公 式处理2个组合电路的逻辑表达式，若能得到相同的结果，则2个组合电路的逻辑表 达式是逻辑等效的。但是，由于逻辑代数的基本公式数量较多，该方法中，基本公式选 择、所选若干个基本公式的应用顺序以及所选的每个基本公式处理对象的选择等环节都 存在多种可选方案，具体方案的选择与电路结构有直接关系，尚没有统一可行的指导路 线可用。因此，采用代数法对组合逻辑电路等效性进行检测具有很大的盲目性，该方法 可操作性差，且计算量和计算时间也随电路规模急剧增长，检测效率很低，在实际中很 少单独采用。

真值表判定法通过利用真值表来判定2个组合电路的逻辑表达式是否存在逻辑等效 关系。该方法中，将2个组合电路的输入变量取值的所有可能组合逐一代入2个组合电路的逻辑表达式，然后根据结果是否都相同即可得出结论。虽然该方法相对于代数法， 可操作性较高，但是很明显，当电路规模增大时，组合电路的输入变量取值也将急剧增 加，该方法的时间开销将急剧增加，检测效率仍然较低。

功能性方法是目前常用的组合逻辑电路等效性检测方法，该方法将2个组合电路表 示成一种规范形式，如二进制决策图(BDD),若2个组合电路的规范形式同构则它们等效。该方法也不存在可操作性的问题，虽然相对于真值表判定法检测效率有所提高，但 是仍不能满足目前超大规模电路的需求，而且该方法在某些输入变量顺序下会面临内存 爆炸的问题。

发明内容

本发明所要解决的技术问题是提供一种可操作性和检测效率均较高，且不会出现内 存爆炸问题的组合逻辑电路等效性检测方法。

本发明解决上述技术问题所采用的技术方案为：一种组合逻辑电路等效性检测方法，包括以下步骤：

(1)将待检测的两个组合电路记为a和b，其中，a的逻辑表达式为：

b的逻辑表达式为：

其中，n为组合电路a和b的变量数，∑为求和运算符号，p为组合电路a的乘积项的数量，q为组合电路b的乘积项的数量，a_i为组合电路a的第i个乘积项，a_i＝x_i'₁x_i'₂…x_i'_k…x_i'_n，>i'_k为乘积项a_i第k位的文字变量，表示对应输入变量>k在乘积项a_i第k位的出现形式，x_i'_k∈{0,1,-}，当x_i'_k＝0时，x_k以其反变量的形式出现 在乘积项a_i第k位，当x_i'_k＝1时，x_k以其原变量x_k的形式出现在乘积项a_i第k位，当x_i'_k＝->k的值恒为1，x_k不出现在乘积项a_i第k位中；b_j为组合电路b的第j个乘积项，>j＝y'_j1y'_j2…y'_jh…y'_jn，h为大于等于1且小于等于n的整数，y'_jh为乘积项b_j第h位的文字>h在乘积项b_j第h位的出现形式，y'_jh∈{0,1,-}，当y'_jh＝0时，y_h以其反变量y_h的形式出现在乘积项b_j第h位，当y'_jh＝1时，y_h以其原变量y_h的形式出现>j第h位，当y'_jh＝-时，表示y_h的值恒为1，y_h不出现在乘积项b_j第h位；

(2)判断组合电路a是否包含组合电路b，具体过程为：

A.设定变量f，初始化变量f，令变量f＝1；

B.设定变量u，初始化变量u，令u＝1；设定变量t，初始化变量t，令变量t＝1；

C.将组合电路a对组合电路b的第f个乘积项b_f的余子函数表示为a^f(x₁,x₂,…,x_n)，将组合电路a的第t个乘积项a_t对组合电路b的第f个乘积项b_f的余子式记为

D.令x_t”_k为第k位的文字变量，表示对应输入变量x_k在第k位的出现形式，x_t”_k∈{0,1,-,NULL}，当x_t”_k＝0时，x_k以其反变量的形式出现在第k位， 当x_t”_k＝1时，x_k以原变量其x_k的形式出现在第k位，当x_t”_k＝-时，表示x_k的值恒为1，x_k不出现在第k位，当x_t”_k＝NULL时，表示x_k的值恒为0；

按照以下规则依次对的第u位文字变量x_t”_u进行赋值：

若x_t'_u＝y'_fu，则令x_t”_u＝-；

若x_t'_u≠y'_fu，且x_t'_u＝-，y'_fu＝0，则令x_t”_u＝-；

若x_t'_u≠y'_fu，且x_t'_u＝-，y'_fu＝1，则令x_t”_u＝-；

若x_t'_u≠y'_fu，且x_t'_u＝0，y'_fu＝1，则令x_t”_u＝NULL；

若x_t'_u≠y'_fu，且x_t'_u＝1，y'_fu＝0，则令x_t”_u＝NULL；

若x_t'_u≠y'_fu，且x_t'_u＝0，y'_fu＝-，则令x_t”_u＝0；

若x_t'_u≠y'_fu，且x_t'_u＝1，y'_fu＝-，则令x_t”_u＝1；

E.判断x_t”_u的值是否为NULL，如果x_t”_u的值为NULL，则直接令得到组合电路a的第t个乘积项a_t对组合电路b的第f个乘积项b_f的余子式的表达式，然后进入步骤F；否则，判断u的当前值是否等于n，如果u的当前值等于n，则表明的第1位～第n位 文字变量全部赋值完成，将第1位～第n位文字变量全部赋值完成的的表达式作为组合电路a的第t个乘积项a_t对组合电路b的第f个乘积项b_f的余>的表达式，然后进入步骤F，如果u的当前值不等于n，则采用u的当前值加1后的 值去更新u，然后重复步骤D和步骤E；

F.判断的第1位文字变量～第n位文字变量的值是否都为-，如果是，表明的值恒为1，则直接令a^f(x₁,x₂,…,x_k,…,x_n)＝1，得到组合电路a对组合电路b的第f个乘积项b_f的余子函数a^f(x₁,x₂,…,x_n)的表达式，然后进入步骤G，如果否，则判断t的当前值是否>得到组合电路a对组合电 路b的第f个乘积项b_f的余子函数a^f(x₁,x₂,…,x_n)的表达式，然后进入步骤G，如果不等>

G.判定组合电路a对组合电路b的第f个乘积项b_f的余子函数a^f(x₁,x₂,…,x_n)的表达>

G-1.首先判断余子函数a^f(x₁,x₂,…,x_n)的表达式的值是否为0，如果余子函数>f(x₁,x₂,…,x_n)的表达式的值为0，则余子函数a^f(x₁,x₂,…,x_n)的表达式不是重言式，组>f(x₁,x₂,…,x_n)的表达式的值不为0，则进入步骤G-2，对余子函数>f(x₁,x₂,…,x_n)的表达式的值是否为1进行判断；

G-2.如果余子函数a^f(x₁,x₂,…,x_n)的表达式的值是1，则余子函数a^f(x₁,x₂,…,x_n)的>f(x₁,x₂,…,x_n)的表达式的值不是1，则进入步骤G-3；

G-3.从余子式中随机选取一个未被选取过的不等于0的余子式，将其记为v为整数且1≤v≤p，从的表达式中随机选取一个不等于-的文字变量，将其记为 x'_v'_s，s为大于等于1且小于等于n的整数，将x'_v'_s对应的变量x_s作为拆分变量，根据香农展开定理计算余子函数a^f(x₁,x₂,…,x_n)的表达式对x_s的原变量x_s的余子式，将得到的余子>根据香农展开定理计算余子函数a^f(x₁,x₂,…,x_n)的表达式对x_s的反变量的 余子式，将得到的余子式记为然后进入步骤G-4，判断是否是重言式；

G-4.判断是否是重言式，具体为：如果的值为0，则不是重言式，组合电 路a不包含组合电路b，组合电路a和组合电路b不是逻辑等效关系，检测完成；如果的值不为0，则继续判断的值是否为1，如果的值不是1，则重复步骤G-3和步骤G-4；如果的值是1，则是重言式，进入步骤G-5；

G-5.采用判定是否为重言式的方法来判断是否是重言式，若不是重言式，则组合电路a不包含组合电路b，组合电路a和组合电路b不是逻辑等效关系，检测完成； 若是重言式，则表明a^f(x₁,x₂,…,x_n)是重言式，进入步骤G-6；

G-6.判断f的当前值是否为q，如果f的当前值不为q，则采用f的当前值加1后的值去更新f，然后重复步骤(2)的步骤B～步骤G，如果f的当前值为q，则表明组合电路a 包含组合电路b，进入步骤(3)；

(3)采用判定组合电路a是否包含组合电路b相同的方法来判定组合电路b是否包含 组合电路a，如果组合电路b包含组合电路a，则表明组合电路a和组合电路b是逻辑等效关系，如果组合电路b不包含组合电路a，则组合电路a和组合电路b不是逻辑等效关系， 检测完成。

与现有技术相比，本发明的优点在于通过扩展余子式概念，将逻辑覆盖等效性检测 问题分成分解成电路包含检测子问题,逐一求取其中一个电路表达式对另一个电路表达 式各乘积项的余子式，然后在建立各乘积项余子式的香农结构图基础上判断其是否重言 式，最后根据重言式判别结果确定两电路间是否覆盖等效关系，本发明的方法通过求取乘积项余子式对逻辑函数进行分解和降阶处理,从而加快了覆盖等效性验证速度，可 操作性和检测效率均较高，且不会出现内存爆炸问题，实验结构表明，本发明的方法稳 定有效的，对EXPRESSO软件集成的三种算法所得电路的测试结果表明,与基于真值表 和BDD的两种检测算法相比,具有明显的速度优势。

具体实施方式

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

实施例：一种组合逻辑电路等效性检测方法，包括以下步骤：

(1)将待检测的两个组合电路记为a和b，其中，a的逻辑表达式为：

b的逻辑表达式为：

其中，n为组合电路a和b的变量数，∑为求和运算符号，p为组合电路a的乘积项的数量，q为组合电路b的乘积项的数量，a_i为组合电路a的第i个乘积项，a_i＝x_i'₁x_i'₂…x_i'_k…x_i'_n，>i'_k为乘积项a_i第k位的文字变量，表示对应输入变量>k在乘积项a_i第k位的出现形式，x_i'_k∈{0,1,-}，当x_i'_k＝0时，x_k以其反变量的形式出现 在乘积项a_i第k位，当x_i'_k＝1时，x_k以其原变量x_k的形式出现在乘积项a_i第k位，当x_i'_k＝->k的值恒为1，x_k不出现在乘积项a_i第k位中；b_j为组合电路b的第j个乘积项，>j＝y'_j1y'_j2…y'_jh…y'_jn，h为大于等于1且小于等于n的整数，y'_jh为乘积项b_j第h位的文字>h在乘积项b_j第h位的出现形式，y'_jh∈{0,1,-}，当y'_jh＝0时，y_h以其反变量的形式出现在乘积项b_j第h位，当y'_jh＝1时，y_h以其原变量y_h的形式出现>j第h位，当y'_jh＝-时，表示y_h的值恒为1，y_h不出现在乘积项b_j第h位；

(2)判断组合电路a是否包含组合电路b，具体过程为：

A.设定变量f，初始化变量f，令变量f＝1；

B.设定变量u，初始化变量u，令u＝1；设定变量t，初始化变量t，令变量t＝1；

C.将组合电路a对组合电路b的第f个乘积项b_f的余子函数表示为a^f(x₁,x₂,…,x_n)，将组合电路a的第t个乘积项a_t对组合电路b的第f个乘积项b_f的余子式记为

D.令x_t”_k为第k位的文字变量，表示对应输入变量x_k在第k位的出现形式，x_t”_k∈{0,1,-,NULL}，当x_t”_k＝0时，x_k以其反变量的形式出现在第k位， 当x_t”_k＝1时，x_k以原变量其x_k的形式出现在第k位，当x_t”_k＝-时，表示x_k的值恒为1，x_k不出现在第k位，当x_t”_k＝NULL时，表示x_k的值恒为0；

按照以下规则依次对的第u位文字变量x_t”_u进行赋值：

若x_t'_u＝y'_fu，则令x_t”_u＝-；

若x_t'_u≠y'_fu，且x_t'_u＝-，y'_fu＝0，则令x_t”_u＝-；

若x_t'_u≠y'_fu，且x_t'_u＝-，y'_fu＝1，则令x_t”_u＝-；

若x_t'_u≠y'_fu，且x_t'_u＝0，y'_fu＝1，则令x_t”_u＝NULL；

若x_t'_u≠y'_fu，且x_t'_u＝1，y'_fu＝0，则令x_t”_u＝NULL；

若x_t'_u≠y'_fu，且x_t'_u＝0，y'_fu＝-，则令x_t”_u＝0；

若x_t'_u≠y'_fu，且x_t'_u＝1，y'_fu＝-，则令x_t”_u＝1；

E.判断x_t”_u的值是否为NULL，如果x_t”_u的值为NULL，则直接令得到组合电路a的第t个乘积项a_t对组合电路b的第f个乘积项b_f的余子式的表达式，然后进入步骤 F；否则，判断u的当前值是否等于n，如果u的当前值等于n，则表明的第1位～第n位 文字变量全部赋值完成，将第1位～第n位文字变量全部赋值完成的的表达式作为组合电路a的第t个乘积项a_t对组合电路b的第f个乘积项b_f的余>的表达式，然后进入步骤F，如果u的当前值不等于n，则采用u的当前值加1后的 值去更新u，然后重复步骤D和步骤E；

F.判断的第1位文字变量～第n位文字变量的值是否都为-，如果是，表明的值恒为1，则直接令a^f(x₁,x₂,…,x_k,…,x_n)＝1，得到组合电路a对组合电路b的第f个乘积项b_f的余子函数a^f(x₁,x₂,…,x_n)的表达式，然后进入步骤G，如果否，则判断t的当前值是否>得到组合电路a对组合电 路b的第f个乘积项b_f的余子函数a^f(x₁,x₂,…,x_n)的表达式，然后进入步骤G，如果不等>

G.判定组合电路a对组合电路b的第f个乘积项b_f的余子函数a^f(x₁,x₂,…,x_n)的表达>

G-1.首先判断余子函数a^f(x₁,x₂,…,x_n)的表达式的值是否为0，如果余子函数>f(x₁,x₂,…,x_n)的表达式的值为0，则余子函数a^f(x₁,x₂,…,x_n)的表达式不是重言式，组>f(x₁,x₂,…,x_n)的表达式的值不为0，则进入步骤G-2，对余子函数>f(x₁,x₂,…,x_n)的表达式的值是否为1进行判断；

G-2.如果余子函数a^f(x₁,x₂,…,x_n)的表达式的值是1，则余子函数a^f(x₁,x₂,…,x_n)的>f(x₁,x₂,…,x_n)的表达式的值不是1，则进入步骤G-3；

G-3.从余子式中随机选取一个未被选取过的不等于0的余子式，将其记为v为整数且1≤v≤p，从的表达式中随机选取一个不等于-的文字变量，将其记为 x'_v'_s，s为大于等于1且小于等于n的整数，将x'_v'_s对应的变量x_s作为拆分变量，根据香农展开定理计算余子函数a^f(x₁,x₂,…,x_n)的表达式对x_s的原变量x_s的余子式，将得到的余子>根据香农展开定理计算余子函数a^f(x₁,x₂,…,x_n)的表达式对x_s的反变量的 余子式，将得到的余子式记为然后进入步骤G-4，判断是否是重言式；

G-4.判断是否是重言式，具体为：如果的值为0，则不是重言式，组合电 路a不包含组合电路b，组合电路a和组合电路b不是逻辑等效关系，检测完成；如果的值不为0，则继续判断的值是否为1，如果的值不是1，则重复步骤G-3和步骤 G-4；如果的值是1，则是重言式，进入步骤G-5；

G-5.采用判定是否为重言式的方法来判断是否是重言式，若不是重言式，则组合电路a不包含组合电路b，组合电路a和组合电路b不是逻辑等效关系，检测完成； 若是重言式，则表明a^f(x₁,x₂,…,x_n)是重言式，进入步骤G-6；

G-6.判断f的当前值是否为q，如果f的当前值不为q，则采用f的当前值加1后的值去更新f，然后重复步骤(2)的步骤B～步骤G，如果f的当前值为q，则表明组合电路a 包含组合电路b，进入步骤(3)；

(3)采用判定组合电路a是否包含组合电路b相同的方法来判定组合电路b是否包含 组合电路a，如果组合电路b包含组合电路a，则表明组合电路a和组合电路b是逻辑等效关系，如果组合电路b不包含组合电路a，则组合电路a和组合电路b不是逻辑等效关系， 检测完成。

本发明的方法在PentiumⅣ1.60GHz,1.00GB内存的Windows XP环境下,采用C 语言编程实现，并通过VC6.0进行编译和调试。测试包括有效性测试和效率测试：1)采 用输入变量数不大于4的多个单输出电路测试算法有效性，利用卡诺图优化原电路表达 式，将优化前后的表达式均写成标准的BLIF文件作为算法的测试电路对；测试结果表 明：每对测试电路均为覆盖等效的；2)测试前通过以下一种或多种方式修改测试电 路:随机改变若干乘积项的若干位变量取值、删除或添加若干行ONSET项或无关项， 测试结果与预期结果均相符合；3)采用ESPRESSO软件集成的本发明的方法和现有 的两种优化算法优化不同规模的MCNC Benchmark电路，由原电路分别与不同优化算 法所得电路组成测试电路对,继续测试本发明的有效性，同时观察算法的效率。表1所 示为12个测试电路的简要信息,包括电路名称、输入/输出数量、原始电路乘积项数量 以及三种算法优化结果电路的乘积项数量；Esp1代表最优化算法优化结果电路、Esp2 代表ESPRESSO算法优化结果电路，Esp3代表快速ESPRESSO算法优化结果电路。

表1ESPRESSO优化前后

12个MCNC Benchmark电路的乘积项数

为便于比较本发明的方法与现有的方法的有效性和效率；采用以上测试电路对分别 测试基于真值表的等效性检测算法(简称真值表法)、基于BDD的等效性检测算法(简称BDD法)和本发明的方法。其中，真值表法在相同环境下采用C语言编程,在实现基于 真值表的重言式判定算法基础上进一步实现；BDD法采用文献(Somenzi F.CUDD:CU decisiondiagram package release 3.0.0[OL].[2015-12-31]. http://vlsi.colorado.edu/～fabio/CUDD/cudd.pdf)公开的CUDD中的组合电路等价性检验 算法，该算法将测试电路对分别构建最优输入变量顺序下的OBDD，然后对每个输出的 等效节点逐一比较。当所有的输出节点都确认等效时，判定测试电路对等效。三种等 效性检测算法结果均表明：以上测试电路对都满足覆盖等效关系。该一致性结论也同时 表明本发明的方法的有效性。表2所示为相应检测过程的运行时间及比较情况,均为5 次运行时间的平均值.其中；t_Tr、t_BDD和t_Our分别为真值表法、BDD法和本发明方法测>1为本发明相比真值表法的时间节省百分比，S₂为本发明相>

表2 12个MCNC Benchmark电路优化前后用3种算法进行等效性测试所需时间

从表2可以看出：1)显然，随着输入变量数量增长，真值表法所需时间显著增长，本发明方法和BDD法运行时间与输入变量数量没有明显的关系；2)乘积项数量对本发 明方法和真值表法速度影响明显，对BDD法影响相对较小，例如电路cordic和duke2 输入变量数仅相差1，前者乘积项数是后者的10倍以上，真值表法对前者不同测试对的 运行时间均是后者的10倍以上，本发明方法对cordic电路对的测试时间则是duke2的 50倍以上，而BDD法对cordic电路的测试时间反而减少为duke2的近十分之一，另外 seq,cordic和alu4电路的乘积项数相对最多,本发明方法对这3个电路的测试时间相比 其他电路更多,也说明乘积项数是本文算法效率的最重要影响因素；3)电路输出数量对 BDD法测试时间影响最大,对真值表法和本发明方法影响相对较小，这个结论通过比较 cps,seq,duke2等电路的测试时间容易得到；4)就三种方法法的整体运行效率而言，真 值表法效率最低，但当输入变量和乘积项数量较少时仍具有相对较高的运行效率，当电 路具有输出量少、输入量和乘积项较多时,如seq和cordic电路，BDD法速度最快，对 于输入和输出量较多、乘积项数量相对较少的电路，适合采用本发明方法进行测试.就 所涉及测试电路而言,本发明方法平均效率最高,相比真值表法和BDD法的时间平均 节省率均超过60％。