Automatic test pattern generation-based circuit verification method and apparatus

Patent metadata

Field	Value
Publication number	US-12313680-B2
Application number	US-202318397481-A
Country	US
Kind code	B2
Filing date	Dec 27, 2023
Priority date	Jun 28, 2021
Publication date	May 27, 2025
Grant date	May 27, 2025

Abstract

An automatic test pattern generation-based circuit verification method, comprises determining a to-be-detected first logic cone from a fan-out logic cone corresponding to the target line; determining, based on the first logic cone, a to-be-detected second logic cone from a fan-in logic cone corresponding to the target line; generating a first conjunctive normal form (CNF) based on the first logic cone and the second logic cone, and detecting the target line by using the first CNF to obtain a first detection result; and if the first logic cone is a partial region in the fan-out logic cone, and the first detection result meets a first specified condition corresponding to the first logic cone, determining a first verification result of the target line based on the first detection result.

First claim

What is claimed is:

1. A method comprising:
selecting, a first logic cone from a fan-out logic cone corresponding to a target line in a circuit to be tested, wherein the fan-out logic cone comprises a first gate circuit that extends from the target line to an output end of the circuit;
identifying, based on the first logic cone, a second logic cone in a fan-in logic cone corresponding to the target line, wherein the fan-in logic cone comprises a second gate circuit that extends from an input end of the circuit to the target line, and wherein the second logic cone comprises a third gate circuit that affects a first output value of the first logic cone;
generating a first conjunctive normal form (CNF) based on the first logic cone and the second logic cone;
detecting the target line using the first CNF to obtain a first detection result, wherein the first detection result indicates a fault type of the target line; and
obtaining, when the first logic cone is a partial region in the fan-out logic cone and the first detection result meets a first specified condition corresponding to the first logic cone, a first verification result of the target line based on the first detection result.

2. The method according to claim 1 , wherein the method further comprises further obtaining the first verification result based on the first detection result when the first logic cone is an entire region of the fan-out logic cone.

3. The method according to claim 1 , wherein the method further comprises identifying, when the first logic cone is the partial region in the fan-out logic cone and the first detection result does not meet the first specified condition, a third logic cone from the fan-out logic cone, and wherein the third logic cone and the first logic cone are different.

4. The method according to claim 1 , wherein selecting the first logic cone comprises selecting the first logic cone based on a preset initial depth value and a first step value, and wherein the initial depth value represents a distance between the target line and the first gate circuit.

5. The method according to claim 4 , wherein the first specified condition is that the fault type in the first detection result is a difficult-to-detect fault.

6. The method according to claim 1 , wherein selecting the first logic cone comprises selecting the first logic cone based on a preset quantity of output ends and a first step value.

7. The method according to claim 6 , wherein the first detection result comprises:
the fault type and a test pattern, wherein the test pattern is for performing circuit fault detection on the circuit; and
the first specified condition is that the fault type in the first detection result is a detectable fault.

8. The method according to claim 1 , wherein the method further comprises:
selecting a third logic cone from the fan-out logic cone;
selecting a fourth logic cone from the fan-in logic cone, wherein the third logic cone is different from the first logic cone, and wherein the fourth logic cone is in the fan-in logic cone and comprises a fourth gate circuit that affects a second output value of the third logic cone;
generating a second CNF based on the third logic cone and the fourth logic cone, and
detecting the target line using the second CNF to obtain a second detection result, wherein the second detection result indicates the fault type of the target line;
when the first verification result is not obtained, the third logic cone is a partial region in the fan-out logic cone, and the second detection result meets a second specified condition corresponding to the third logic cone:
obtaining a second verification result corresponding to the target line based on the second detection result; and
stopping detecting the target line by using the first CNF; and

stopping, when the first verification result is obtained, detecting the target line by using the second CNF.

9. The method according to claim 1 , wherein the first CNF comprises at least one clause that is based on a fourth gate circuit in the first logic cone and a fifth gate circuit in the second logic cone.

10. The method according to claim 9 , wherein the detecting the target line comprises:
separately performing, when a quantity of clauses in the first CNF is greater than or equal to a specified threshold, a satisfiability (SAT) solution on the at least one clause;
obtaining an SAT solution result of each of the at least one clause; and
using an intersection of the SAT solution result of each of the at least one clause as the first detection result.

11. The method according to claim 9 , wherein the first CNF comprises at least one target clause corresponding to at least one first target sub-circuit in the first logic cone and at least one target clause corresponding to at least one second target sub-circuit in the second logic cone, wherein the at least one first target sub-circuit is in a one-to-one correspondence with the at least one target clause, and wherein any of the at least one first target sub-circuit and the at least one second target sub-circuit comprises at least one fourth gate circuit.

12. The method according to claim 11 , wherein before selecting the first logic cone, the method further comprises:
identifying, when a quantity of gate circuits in the fan-in logic cone and the fan-out logic cone is greater than a first specified threshold, a first target sub-circuit in the fan-in logic cone based on the second gate circuit in the fan-in logic cone; and
identifying a second target sub-circuit in the fan-out logic cone based on the first gate circuit in the fan-out logic cone.

13. The method according to claim 12 , wherein the first target sub-circuit or the second target sub-circuit is a fan-out free region (FFR).

14. The method according to claim 12 , wherein before selecting the first logic cone, the method further comprises simplifying, when a quantity of gate circuits in the fan-in logic cone and the fan-out logic cone is greater than a second specified threshold, two equivalent gate circuits in the fan-in logic cone and the fan-out logic cone into one fourth gate circuit for generating a CNF clause, wherein the second specified threshold is less than the first specified threshold, and wherein the two equivalent gate circuits are two fifth gate circuits with a same input and a same output.

15. An apparatus comprising:
at least one memory configured to store instructions; and
at least one processor coupled to at least one memory and configured to execute the instructions to cause the apparatus to:
select a first logic cone from a fan-out logic cone corresponding to a target line in a circuit, wherein the fan-out logic cone comprises a first gate circuit that extends from the target line to an output end of the circuit;
identify, based on the first logic cone, a second logic cone in a fan-in logic cone corresponding to the target line, wherein the fan-in logic cone comprises a second gate circuit that extends from an input end of the circuit to the target line, and wherein the second logic cone comprises a third gate circuit that affects a first output value of the first logic cone;
generate a first conjunctive normal form (CNF) based on the first logic cone and the second logic cone;
detect the target line using the first CNF to obtain a first detection result, wherein the first detection result indicates a fault type of the target line; and
obtain, when the first logic cone is a partial region in the fan-out logic cone and the first detection result meets a first specified condition corresponding to the first logic cone, a first verificat

Assignees

• Huawei Tech Co Ltd

Inventors

• Zhen Huiling
• Chen Miaohui
• Yuan Mingxuan
• Wang Naixing
• Luo Wanqian
• Huang Yu

Classifications

• G06F30/33

  Design verification, e.g. functional simulation or model checking · CPC title

• G06F30/3323

  using formal methods, e.g. equivalence checking or property checking · CPC title

• G01R31/318502

  Test of Combinational circuits · CPC title

• G01R31/31835

  Analysis of test coverage or failure detectability · CPC title

• G01R31/31707

  Test strategies (methods for generation of test sequences G01R31/318371) · CPC title