Method and apparatus for generating test sequence

Claim 1

A method for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising: a first step of counting a number of fault propagation processes executed for every target fault, for which a test sequence is generated; and a second step of judging whether the number counted is beyond a predetermined number and then terminating the test sequence generation if the number counted is beyond the predetermined number wherein the first step comprises: a first substep of selecting one target fault from either target faults for which the fault propagation processes have not been executed yet or other target faults for which the fault propagation processes are regarded to have not been executed yet, and for which test sequences have not been generated yet; a second substep of, when a D-frontier indicating an input of a path to be sensitized is already registered as an illegal frontier, selecting a D-frontier other than the illegal frontier in a time frame where a target fault is propagated to an external output pin in order to execute a fault propagation process; a third substep of judging whether the target fault propagation in the second substep is successful or not; a fourth substep of, when the target fault propagation is judged to be unsuccessful, registering the D-frontier selected in a time frame where the effects of the target fault is propagated to an external output pin as an illegal D-frontier of the target fault; and a fifth substep of, when the first through third substeps have been executed for all the target faults, regarding target faults for which the fault propagation processes have been unsuccessfully executed as target faults for which fault propagation processes have not been executed yet.

Claim 2

A method for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising: a first step of counting a number of fault propagation processes executed for every target fault, for which a test sequence is generated; and a second step of judging whether the number counted is beyond a predetermined number and then terminating the test sequence generation if the number counted is beyond the predetermined number wherein the first step comprises: a first substep of selecting one target fault from either target faults for which the fault propagation processes have not been executed yet or other target faults for which the fault propagation processes are regarded to have not been executed yet, and for which test sequences have not been generated yet; a second substep of, when a D-frontier indicating an input of a path to be sensitized is already registered as an illegal frontier, selecting a D-frontier other than the illegal frontier in a time frame where a target fault is propagated to an external output pin in order to execute a fault propagation process; a third substep of judging whether the target fault propagation in the second substep is successful or not; a fourth substep of, when the target fault propagation is judged to be unsuccessful, registering the D-frontier selected in a time frame where the effects of the target fault is propagated to an external output pin as an illegal D-frontier of the target fault; and a fifth substep of, when the first through third substeps have been executed for all the target faults, regarding target faults for which the fault propagation processes have been unsuccessfully executed as target faults for which fault propagation processes have not been executed yet.

Claim 3

A method for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising: a first step of providing a fault propagation process to a target fault in one time frame; a second step of storing a propagation path selected in a time frame immediately before a time frame being processed in the first step as a set of a signal line indicating the output of the propagation path (target pseudo-primary output) and a D-frontier indicating the input of the propagation path; a third step of judging whether the fault propagation process in the first step is successful or not and executing the first step for the next time frame if it is successful, or otherwise registering a set of the target pseudo-primary output and the D-frontier stored in the second step as an illegal path; a fourth step of, when the fault propagation process in the first step is unsuccessful, clearing from the test sequence at least a segment already generated on and after one frame ahead of the time frame where the fault propagation process is unsuccessful; and a fifth step of restarting the first step from the time frame corresponding to a segment cleared without selecting a set of the D-frontier and the target pseudo-primary output registered as an illegal path.

Claim 4

A method for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising: a first step of providing a fault propagation process to a target fault in one time frame; a second step of storing a propagation path selected in a time frame immediately before a time frame being processed in the first step as a set of a signal line indicating the output of the propagation path (target pseudo-primary output) and a D-frontier indicating the input of the propagation path; a third step of judging whether the fault propagation process in the first step is successful or not and executing the first step for the next time frame if it is successful, or otherwise registering a set of the target pseudo-primary output and the D-frontier stored in the second step as an illegal path; a fourth step of, when the fault propagation process in the first step is unsuccessful, clearing from the test sequence at least a segment already generated on and after one frame ahead of the time frame where the fault propagation process is unsuccessful; and a fifth step of restarting the first step from the time frame corresponding to a segment cleared without selecting a set of the D-frontier and the target pseudo-primary output registered as an illegal path.

Claim 5

An apparatus for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising: backtrace means for tracing backward in the series of time frames to propagate a fault signal of the stuck-at fault along a path selected in a time frame, wherein an input value in the time frame is assigned in order to sensitize the path and a backtrace operation, performed by the backtrace mean starts from a first time frame, which contains an output pin to be a goal of the stuck-at fault up to a time frame containing a fault site; defining means for, when a given path unsuccessfully sensitized in a time frame is detected, defining at least a segment of the giver path as illegal information, the given path extending between the first time frame and the time frame where the given path is detected to have been unsuccessfully sensitized; memory means for storing the illegal information correspondingly with the fault signal; and prohibiting means for prohibiting selection of a path defined as illegal information when the backtrace means is driven for another fault.

Claim 6

An apparatus for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising: backtrace means for tracing backward in the series of time frames to propagate a fault signal of the stuck-at fault along a path selected in a time frame, wherein an input value in the time frame is assigned in order to sensitize the path and a backtrace operation, performed by the backtrace mean starts from a first time frame, which contains an output pin to be a goal of the stuck-at fault up to a time frame containing a fault site; defining means for, when a given path unsuccessfully sensitized in a time frame is detected, defining at least a segment of the giver path as illegal information, the given path extending between the first time frame and the time frame where the given path is detected to have been unsuccessfully sensitized; memory means for storing the illegal information correspondingly with the fault signal; and prohibiting means for prohibiting selection of a path defined as illegal information when the backtrace means is driven for another fault.

Claim 11

An apparatus for generating a test sequence through a state initialization wherein input signal values to be inputted to external input pins of a sequential circuit to be tested are found in order to transfer a state of the circuit from its initial state to a state that appeared when a fault propagation process for a stuck-at fault has been just completed, comprising: assigning means for, in order to justify a current state of the sequential circuit, assigning outputs of memory elements and input signal values to be given to the external input pins, the assignment being processed to obtain an initial state starting from a state that appeared when the fault propagation process has been just completed; judging means for judging whether the justified state corresponding to the assignment coincides with either a state that appeared when the fault propagation process has been just completed or a state corresponding to an assignment made before the justified state is assigned; and restarting means for, when the two states are judged to be coincident with each other, restarting an assignment operation while cancelling at least the latest state of those states corresponding to assignments already made.

Claim 12

An apparatus for generating a test sequence through a state initialization wherein input signal values to be inputted to external input pins of a sequential circuit to be tested are found in order to transfer a state of the circuit from its initial state to a state that appeared when a fault propagation process for a stuck-at fault has been just completed, comprising: assigning means for, in order to justify a current state of the sequential circuit, assigning outputs of memory elements and input signal values to be given to the external input pins, the assignment being processed to obtain an initial state starting from a state that appeared when the fault propagation process has been just completed; judging means for judging whether the justified state corresponding to the assignment coincides with either a state that appeared when the fault propagation process has been just completed or a state corresponding to an assignment made before the justified state is assigned; and restarting means for, when the two states are judged to be coincident with each other, restarting an assignment operation while cancelling at least the latest state of those states corresponding to assignments already made.

Claim 15

A method for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising the steps of: tracing backward in the series of time frames to propagate a fault signal of the stuck-at fault, the tracing occurring in each time frame along a path selected in each time frame and assigning an input value in each time frame in order to sensitize the path, at least one of the paths comprising a dominator-frontier (D-frontier) having a target fault site and a flip-flop that can propagate an effect of the target fault site to a target pseudo-primary output (PPO) located in an earlier time frame, the target PPO being an input of a flip-flop that is a D-frontier of the earlier time frame, the tracing-backward step starting from a first earlier time frame, which corresponds to an output pin to be a goal of the stuck-at fault up to a time frame corresponds to a target fault site; defining, when a given path unsuccessfully sensitized in a time frame is detected, at least a segment of the given path including a D-frontier as illegal information, the given path extending between the first earlier time frame and the time frame where the given path is detected to have been unsuccessfully sensitized; and restarting another propagation of a fault signal from a D-frontier to a target PPO without selecting the segment of the given path defined as illegal information.

Claim 16

A method for generating a test sequence to test an assumed stuck-at fault in a sequential circuit expanded as a series of time frames, comprising the steps of: tracing backward in the series of time frames to propagate a fault signal of the stuck-at fault, the tracing occurring in each time frame along a path selected in each time frame and assigning an input value in each time frame in order to sensitize the path, at least one of the paths comprising a dominator-frontier (D-frontier) having a target fault site and a flip-flop that can propagate an effect of the target fault site to a target pseudo-primary output (PPO) located in an earlier time frame, the target PPO being an input of a flip-flop that is a D-frontier of the earlier time frame, the tracing-backward step starting from a first earlier time frame, which corresponds to an output pin to be a goal of the stuck-at fault up to a time frame corresponds to a target fault site; defining, when a given path unsuccessfully sensitized in a time frame is detected, at least a segment of the given path including a D-frontier as illegal information, the given path extending between the first earlier time frame and the time frame where the given path is detected to have been unsuccessfully sensitized; and restarting another propagation of a fault signal from a D-frontier to a target PPO without selecting the segment of the given path defined as illegal information.