数字组合逻辑电路输出发生线“或”短接故障的检测方法

摘要

本发明公开了一种数字组合逻辑电路输出发生线“或”短接故障的检测方法，其先获取两个数字组合逻辑电路各自的乘积项构成的集合；然后对全集与第一个集合进行乘积项集合之间的不相交锐积运算，对得到的结果与第二个集合进行乘积项集合之间的不相交锐积运算，对第二次得到的结果与第二个集合进行乘积项集合之间的不相交锐积运算，第三次得到的结果中的乘积项作为测试输入组合；再将测试输入组合加到两个数字组合逻辑电路的输入端，判定两个数字组合逻辑电路是否发生线“或”短接故障；优点是适用于计算机快速计算实现，适合两个大的数字组合逻辑电路输出发生线“或”短接故障的检测。

权利要求

1.一种数字组合逻辑电路输出发生线“或”短接故障的检测方法，其特征在于包括以下步骤：①将待检测的两个数字组合逻辑电路分别记为f(X)和g(X)；并设定f(X)展开有p个乘积项，f(X)表示为其p个乘积项的逻辑“或”形式，g(X)展开有q个乘积项，g(X)表示为其q个乘积项的逻辑“或”形式；其中，X表示f(X)和g(X)的输入变量集合，X中至少包含有1个输入变量，p≥1，q≥1；

②将f(X)的p个乘积项构成的集合记为Cf(X)，将g(X)的q个乘积项构成的集合记为Cg(X)；

③令U表示全集；然后对U与Cf(X)进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合 中， 其中， 的初始值为空集，符号 为两个布尔逻辑函数乘积项集合之间的不相交锐积运算符号，该运算符号 的作用是去掉两个布尔逻辑函数乘积项集合对应的逻辑覆盖中的公共部分，如就是等于在Cf(X)中去除与Cg(X)相交的部分，即 也即符号“∪”为集合间“并”运算符号，

符号“Θ”为公知的乘积项之间的不相交锐积运算符号， 表示Cg(X)中的第1个乘积项，表示Cg(X)中的第2个乘积项， 表示Cg(X)中的第3个乘积项， 表示Cg(X)中的第q个乘积项；

④对Cg(X)与 进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合Cg(X)_d中， 其中，Cg(X)_d的初始值为空集；

⑤对Cg(X)与Cg(X)_d进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合CT中， CT中的乘积项为用于两个数字组合逻辑电路输出发生线“或”短接故障检测的测试输入组合；其中，CT的初始值为空集；

⑥将步骤⑤得到的测试输入组合加到f(X)和g(X)的输入端，若f(X)的输出值与预期值不一致，则判定f(X)和g(X)输出发生线“或”短接故障。

说明书

数字组合逻辑电路输出发生线“或”短接故障的检测方法

技术领域

[0001] 本发明涉及一种数字组合逻辑电路短接故障的检测方法，尤其是涉及一种数字组合逻辑电路输出发生线“或”短接故障的检测方法。

背景技术

[0002] 随着集成电路集成度的不断提高和集成电路功能的不断增加，集成电路内部的连接变得越来越复杂，使得集成电路生产过程中的连接错误变得不可避免，从而导致集成电路逻辑功能错误。因而电路故障测试已成为集成电路设计与生成过程中一个非常重要的内容。由于现有的集成电路的结构非常复杂，因此人工手动完成一个电路故障测试已经变得越来越不可能，而更多的是借助计算机来完成电路故障测试工作，并已经成为电子设计自动化(EDA，Electronics Design Automation)中的一个重要内容。在电路故障测试中，可以借助计算机生成相应的测试输入，这些测试输入作用在待测集成电路的输入端，然后通过比对实际输出与预想中的设计结果的差别来判断集成电路是否存在逻辑功能错误。

[0003] 以两个数字组合逻辑电路输出发生短接，且短接结果为线“或”的短接故障检测为例。图1给出了两个数字组合逻辑电路输出发生线“或”短接的示意图，图1中的两个方块表示两个数字组合逻辑电路，这两个数字组合逻辑电路的逻辑功能分别用f(X)和g(X)表示，f(X)的输出用f表示，g(X)的输出用g表示，这两个数字组合逻辑电路的n(n≥1)个输入变量集合用X表示，图1中的虚框表示因封装等原因使得虚框内电路不可见。从图1中可以看出，显然，当f和g没有发生短接时，f和f'的输出应该是一致的，但是考虑到电路在制造过程中，因为某种原因可能会使f被g短接，短接点为a，并且f与g短接后形成线“或”关系，即f变成了f'＝f+g。为了判别是否存在这类的短接，导致电路逻辑功能错误，需要选择一些适当的测试输入组合T，当输入的n个输入变量集合为XT时，XT属于T，那么满足f(XT)的原来的输出f为0而g(XT)的输出g为1，这样只要存在电路f(X)和g(X)的输出为线“或”型短接时，就可以通过观察f'的值与预想中的f值是否一致，进而判断电路是否存在故障。

[0004] 假设f(X)的电路如图2a所示，f(X)对应的逻辑表达式为g(X)的电路如图2b所示，g(X)对应的逻辑表达式为
其中，x1,x2,x3,x4为四个输入
变量， 为x3的反， 为x1的反， 为x2的反， 为x1⊕x2⊕x3的反，符号 为异或运算符号。现假设图2a所示的电路的输出f与图2b所示的电路的输出g发生了短接，如图
2c所示，且短接点a具有线“或”特点。为了检测这类故障，在理论上可以借助来得到测试输入组合T，其中， 为 的反， 表示f(X)
对g(X)的c导数。考虑到 可将 转化为
其中， 为f(X)的反。

[0005] 对于小电路，符合 的测试输入组合T比较容易得到。如为了检测图2a所示的电路的输出f与图2b所示的电路的输出g是否发生线“或”短接，可以用卡诺图来求得满足 的测试输入组合T。先得到如图3a所示的f(X)的反 的
卡诺图，再得到如图3b所示的g(X)的卡诺图。取图3a所示的f(X)的反 的卡诺图和图3b所示的g(X)的卡诺图中取值都为“1”的公共部分，即对图3a所示的f(X)的反 的卡诺图和图3b所示的g(X)的卡诺图进行逻辑“与”，结果如图3c所示。由图3c可得，其中， 为x4的反，“-”表示该变量
在乘积项中没有出现。显然当输入为{0000,101-}时，f为0，g为1，而实际得到的输出f'＝f+g＝0+1＝1，与预测的f为0不符，进而可以判别出电路发生故障。

[0006] 虽然 在理论上给出了检测两个数字组合逻辑电路输出发生线“或”的测试输入组合T的产生方法，但是在实际应用时，如何产生符合
的测试输入组合T，则面临着很多困难，尤其是f(X)和g(X)对应的电路的输入变量比较多的情况下，可能根本无法在有限的时间内得到测试输入组合T，即对于大电路，利用求解测试输入组合T实际不可行。其原因在于， 的实
质是在求解一个逻辑函数的补集和两个逻辑函数的交集，如采用图3a至图3c的图形方法来处理，对于输入变量数小于5的逻辑函数很有效，但对于输入变量数大于5的逻辑函数则不适合；又如采用常用的方法，就是将f(X)和g(X)展开为最小项的形式，这种方法对于输入变量数小于20个的电路来说，会比较方便，但是对于输入变量数大于30个以上的电路，可能无法处理或者处理的效率很低下，这是因为：当f(X)和g(X)的输入变量有n个时，它们包含的n
最小项的个数与2成正相关，而当n>30或更大时，最小项的个数以亿计了，庞大的最小项的数量，使得计算机无法有效进行运算，即无法产生测试输入组合T，进而无法判断相应的短接故障。

发明内容

[0007] 本发明所要解决的技术问题是提供一种数字组合逻辑电路输出发生线“或”短接故障的检测方法，其通过利用数字组合逻辑电路对应的逻辑函数之间的不相交锐积操作，实现逻辑函数的逻辑“反”操作和逻辑函数之间的逻辑“与”操作，获得用于故障检测的测试输入组合，进而能够有效判断相应的短接故障，且适合两个大的数字组合逻辑电路输出发生线“或”短接故障的检测。

[0008] 本发明解决上述技术问题所采用的技术方案为：一种数字组合逻辑电路输出发生线“或”短接故障的检测方法，其特征在于包括以下步骤：

[0009] ①将待检测的两个数字组合逻辑电路分别记为f(X)和g(X)；并设定f(X)展开有p个乘积项，f(X)表示为其p个乘积项的逻辑“或”形式，g(X)展开有q个乘积项，g(X)表示为其q个乘积项的逻辑“或”形式；其中，X表示f(X)和g(X)的输入变量集合，X中至少包含有1个输入变量，p≥1，q≥1；

[0010] ②将f(X)的p个乘积项构成的集合记为Cf(X)，将g(X)的q个乘积项构成的集合记为Cg(X)；

[0011] ③令U表示全集；然后对U与Cf(X)进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合 中， 其中， 的初始值为空集，符号 为两个布尔逻辑函数乘积项集合之间的不相交锐积运算符号；

[0012] ④对Cg(X)与 进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合Cg(X)_d中， 其中，Cg(X)_d的初始值为空集；

[0013] ⑤对Cg(X)与Cg(X)_d进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合CT中， CT中的乘积项为用于两个数字组合逻辑电路输出发生线“或”短接故障检测的测试输入组合；其中，CT的初始值为空集；

[0014] ⑥将步骤⑤得到的测试输入组合加到f(X)和g(X)的输入端，若f(X)的输出值与预期值不一致，则判定f(X)和g(X)输出发生线“或”短接故障。

[0015] 与现有技术相比，本发明的优点在于：本发明方法利用数字组合逻辑电路对应的逻辑函数之间的不相交锐积操作，实现逻辑函数的逻辑“反”操作和逻辑函数之间的逻辑“与”操作，本发明方法在生成测试输入组合时，不涉及待处理电路的卡诺图展开或最小项展开，因此本发明方法的处理速度与待处理电路的输入变量的数量没有直接关系，更适合两个大的数字组合逻辑电路输出发生线“或”短接故障的检测；另外，电路故障检测是现代电子设计自动化(EDA)技术中一个重要内容，本发明方法适合在计算机上编程实现，使得本发明方法很容易与其他电子设计自动化技术实现整合。

附图说明

[0016] 图1为两个数字组合逻辑电路输出发生线“或”短接的示意图；

[0017] 图2a为两个数字组合逻辑电路中的其中一个数字组合逻辑电路f(X)的示例示意图；

[0018] 图2b为两个数字组合逻辑电路中的另一个数字组合逻辑电路g(X)的示例示意图；

[0019] 图2c为图2a所示的电路的输出f与图2b所示的电路的输出g发生线“或”短接的示意图；

[0020] 图3a为图2a所示的电路的互补卡诺图；

[0021] 图3b为图2b所示的电路的卡诺图；

[0022] 图3c为图3a所示的卡诺图和图3b所示的卡诺图进行逻辑“与”的结果示意图；

[0023] 图4为本发明方法的总体实现框图。

具体实施方式

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

[0025] 本发明提出的一种数字组合逻辑电路输出发生线“或”短接故障的检测方法，其总体实现框图如图4所示，其包括以下步骤：

[0026] ①将待检测的两个数字组合逻辑电路分别记为f(X)和g(X)；并设定f(X)展开有p个乘积项，f(X)表示为其p个乘积项的逻辑“或”形式，g(X)展开有q个乘积项，g(X)表示为其q个乘积项的逻辑“或”形式；其中，X表示f(X)和g(X)的输入变量集合，X中至少包含有1个输入变量，p≥1，q≥1。

[0027] ②将f(X)的p个乘积项构成的集合记为Cf(X)，将Cf(X)中的第i个乘积项记为 将g(X)的q个乘积项构成的集合记为Cg(X)，将Cg(X)中的第j个乘积项记为 其中，1≤i≤p，1≤j≤q。

[0028] ③令U表示全集；然后对U与Cf(X)进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合 中， 其中， 的初始值为空集，符号 为两个布尔逻辑函数乘积项集合之间的不相交锐积运算符号，该运算符号的作用是去掉两个布尔逻辑函数乘积项集合对应的逻辑覆盖中的公共部分，如就是等于在Cf(X)中去除与Cg(X)相交的部分，即
也即
符号“∪”为集合间“并”运算符号，符号“Θ”为公知的乘积项之间的不相交锐积运算符号，表示Cg(X)中的第1个乘积项， 表示Cg(X)中的第2个乘积项， 表示Cg(X)中的第3个乘积项， 表示Cg(X)中的第q个乘积项。

[0029] ④对Cg(X)与 进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合Cg(X)_d中， 其中，Cg(X)_d的初始值为空集。

[0030] ⑤对Cg(X)与Cg(X)_d进行两个布尔逻辑函数乘积项集合之间的不相交锐积运算，再将运算结果保存于集合CT中， CT中的乘积项为用于两个数字组合逻辑电路输出发生线“或”短接故障检测的测试输入组合；其中，CT的初始值为空集。

[0031] ⑥将步骤⑤得到的测试输入组合加到f(X)和g(X)的输入端，若f(X)的输出值与预期值不一致，则判定f(X)和g(X)输出发生线“或”短接故障。

[0032] 以下为对本发明方法进行试验，以验证本发明方法的可行性与有效性。

[0033] 假设X＝{x1,x2,x3,x4}，x1,x2,x3,x4为X中的四个输入变量，并假设p＝2,q＝4。假设用数字“1”表示原变量，用数字“0”表示反变量，用“-”表示该变量在乘积项中没有出现，则有：Cf(X)＝{-1--,--01}，Cg(X)＝{000-,011-,110-,101-}，全集U＝{----}。通过计算得到 与图3a所示
的卡诺图一致，
CT与图3c
所示的卡诺图一致。当 和
的输出发生图2c所示的线“或”
短接故障时，可以将CT中的测试输入组合加到图2c所示的电路的输入端进行线“或”短接判断。如假设将{0000}加到图2c所示的电路的输入端，则有： 的值为
“0”， 的值为“1”，如果没有发生
输出线“或”短接，那么f'的预期值应该与 的值一致，即为“0”，但f'
的实际输出为f'＝f+g＝0+1＝1，显然与预期值不一样，因此可以判别出电路发生故障。

[0034] 表1给出了利用本发明方法用于两个数字组合逻辑电路输出发生线“或”短接故障的测试输入组合的生成。表1中的电路f(X)取自MCNC标准测试电路；电路g(X)为截取电路f(X)的展开表达式的前10项，然后随意修改部分乘积项得到；t/ms表示利用本发明方法生成CT的时间，单位为毫秒，“<1”表示生成CT的时间小于1毫秒。从表1中可以看出，本发明方法可以完成输入变量数为66的电路处理，而且处理速度均比较快。

[0035] 表1本发明用于实验测试的结果

[0036]