Method and system for efficient testing of digital integrated circuits
One embodiment provides a method and a system for generating test vectors for testing a computational system. During operation, the system obtains a design of the computational system, the design comprising an original system. The system generates a design of a fault-augmented system block by adding a plurality of fault-emulating subsystems to the original system; generates a design of an equivalence-checking system based on the original system and the fault-augmented system block; encodes the design of the equivalence-checking system into a logic formula, with variables within the logic formula comprising inputs and outputs of the original system and inputs and outputs of the fault-augmented system block; and solves the logic formula to obtain a test vector used for testing at least one fault in the computational system.
1. A computer-implemented method for generating test vectors for a computational system, comprising:
obtaining, by a computer, a design of the computational system, the design comprising an original system;
generating a design of a fault-augmented system block by adding a plurality of fault-emulating subsystems to the original system;
generating a design of an equivalence-checking system based on the original system and the fault-augmented system block;
encoding the design of the equivalence-checking system into a logic formula, wherein variables within the logic formula comprise inputs and outputs of the original system and inputs and outputs of the fault-augmented system block; and
solving the logic formula to obtain a test vector used for testing at least one fault in the computational system.
2. The method of claim 1 , wherein the design of the equivalence-checking system comprises the original system and one or more fault-augmented system blocks, and wherein generating the design of the equivalence-checking system comprises:
coupling the inputs of the original system to corresponding inputs of each fault-augmented system block; and
coupling the outputs of the original system and corresponding outputs of each fault-augmented system block to a comparison module.
3. The method of claim 2 , wherein the fault-augmented system block comprises a set of fault-assumable inputs, wherein a respective fault-assumable input corresponds to a fault-emulating subsystem, and wherein generating the design of the equivalence-checking system further comprises coupling the set of fault-assumable inputs to a first constraint system.
4. The method of claim 3 , wherein the first constraint system is configured to apply a constraint on the set of fault-assumable inputs to ensure that the fault-augmented system block simulates one fault.
5. The method of claim 3 , wherein generating the design of the equivalence-checking system further comprises coupling the fault-assumable inputs in the one or more fault-augmented system block to a second constraint system, wherein the second constraint system is configured to apply a constraint to ensure that different fault-augmented system blocks have different sets of fault-assumable inputs.
6. The method of claim 3 , wherein generating the design of the equivalence-checking system comprises adding one fault-augmented system block at a time until there is no satisfying solution to the logic formula.
7. The method of claim 6 , further comprising:
generating an design of an extended system, which includes the equivalence-checking system and at least one copy of the equivalence-checking system; and
solving a logic formula corresponding to the design of the extended system;
wherein generating the design of the extended system comprises coupling corresponding fault-assumable inputs from different fault-augmented system blocks of each of the equivalence-checking systems to a third constraint system configured to apply a constraint to ensure that an arbitrary fault is simulated by at least one fault-augmented system block.
8. The method of claim 7 , wherein generating the design of the extended system comprises:
adding one copy of the equivalence-checking system at a time until a satisfying solution to the logic formula corresponding to the design of the extended system is found.
9. The method of claim 8 , wherein the satisfying solution to the logic formula corresponding to the design of the extended system comprises a plurality of sets of assignments to the inputs of the original systems included in the extended system, wherein a respective set of assignments form a test vector, and wherein test vectors corresponding to the plurality of sets of assignments form a test suite capable of testing any arbitrary fault in the digital system.
10. The method of claim 1 , wherein the computational system comprises one or more of:
a digital circuit;
an analog circuit;
a quantum circuit;
a reversible computing circuit;
an optical circuit;
a quantum optical circuit;
a processor; and
a computer program.
11. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for generating test vectors for a computational system, the method comprising:
obtaining a design of the computational system, the design comprising an original system;
generating a design of a fault-augmented system block by adding a plurality of fault-emulating subsystems to the original system;
generating a design of an equivalence-checking system based on the original system and the fault-augmented system block;
encoding the design of the equivalence-checking system into a logic formula, wherein variables within the logic formula comprise inputs and outputs of the original system and inputs and outputs of the fault-augmented system block; and
solving the logic formula to obtain a test vector used for testing at least one fault in the computational system.
12. The non-transitory computer-readable storage medium of claim 11 , wherein the design of the equivalence-checking system comprises the original system and one or more fault-augmented system blocks, and wherein generating the design of the equivalence-checking system comprises:
coupling the inputs of the original system to corresponding inputs of each fault-augmented system block; and
coupling the outputs of the original system and corresponding outputs of each fault-augmented system block to a comparison module.
13. The non-transitory computer-readable storage medium of claim 12 , wherein the fault-augmented system block comprises a set of fault-assumable inputs, wherein a respective fault-assumable input corresponds to a fault-emulating subsystem, and wherein generating the design of the equivalence-checking system further comprises coupling the set of fault-assumable inputs to a first constraint system.
14. The non-transitory computer-readable storage medium of claim 13 , wherein the first constraint system is configured to apply a constraint on the set of fault-assumable inputs to ensure that the fault-augmented system block simulates one fault.
15. The non-transitory computer-readable storage medium of claim 13 , wherein generating the design of the equivalence-checking system further comprises coupling the fault-assumable inputs in the one or more fault-augmented system block to a second constraint system, wherein the second constraint system is configured to apply a constraint to ensure that different fault-augmented system blocks have different sets of fault-assumable inputs.
16. The non-transitory computer-readable storage medium of claim 13 , wherein generating the design of the equivalence-checking system comprises adding one fault-augmented system block at a time until there is no satisfying solution to the logic formula.
17. The non-transitory computer-readable storage medium of claim 16 , wherein the method further comprises:
generating an design of an extended system, which includes the equivalence-checking system and at least one copy of the equivalence-checking system; and
solving a logic formula corresponding to the design of the extended system;
wherein generating the design of the extended system comprises coupling corresponding fault-assumable inputs from different fault-augmented system blocks of each of the equivalence-checking systems to a third constraint system configured to apply a constraint to ensure that an arbitrary fault is simulated by at least one fault-augmented system block.
18. The non-transitory computer-readable storage medium of claim 17 , wherein generating the design of the extended system comprises:
adding one copy of the equivalence-checking system at a time until a satisfying solution to the logic formula corresponding to the design of the extended system is found.
19. The non-transitory computer-readable storage medium of claim 18 , wherein the satisfying solution to the logic formula corresponding to the design of the extended system comprises a plurality of sets of assignments to the inputs of the original systems included in the extended system, wherein a respective set of assignments form a test vector, and wherein test vectors corresponding to the plurality of sets of assignments form a test suite capable of testing any arbitrary fault in the digital system.
20. The non-transitory computer-readable storage medium of claim 11 , wherein the computational system comprises one or more of:
a digital circuit;
an analog circuit;
a quantum circuit;
a reversible computing circuit;
an optical circuit;
a quantum optical circuit;
a processor; and
a computer program.