The present studies are developed to propose the automatic test pattern generation (ATG) algorithms for combinational circuits. These ATG algorithms are realized in two ATG programs: One is the ATG program for stuck-at fault and the other one for delay faults. In order to accelerate the ATG process, these two ATG programs have a common feature (the search method based on the concept of the degree of freedom), whereas only ATG program for the delay fault utilizes the 19-valued logic, a type of composite valued logic. This difference between two ATG programs results from the difference of the target fault.
Accelerating the ATG process is indispensable for improving the ATG algorithms. This acceleration is mainly achieved by reducing the number of the unnecessary backtrackings, making the earlier detection of the conflicts, and shortening the computation time between the implication. Because of this purpose, the developed ATG programs include the new search method based on the concept of the degree of freedom (DF). The DF concept, computed directly and easily from the system descriptions such as types of gates and their interconnections, is the criterion to decide which, among several alternate lines' logic values required along each path, promises to be the most effective in order to accelerate and improve the ATG process. This DF concept is utilized to develop and improve both of ATG programs for stuck-at and delay faults in combinational circuits.
In addition to improving the ATG process, reducing number of test pattern is indispensable for testing the delay faults because the size of the delay faults grows rapidly as increasing the size of the circuit. In order to improve the compactness of the test set, 19-valued logic are derived. Unlike other TG logic systems, 19-valued logic is utilized to generate the robustly hazard-free test pattern. This is achieved by using the basic 5-valued logic, proposed in this work, where the transition with no hazard is defined as the rising/falling transition. The existence of hazard leads to the invalidation of a nonrobust delay test. This 19-valued logic can avoid the conflict and unnecessary implications in generating the test set that it detects as many delay faults as possible by a single test. The calculation of the 19-valued algebra has a forward procedure, whereas that of the DF concept has a backward procedure.
The proposed ATG program for stuck-at faults is applied to generate the test for stuck-at fault in a 3-input and a 4 input circuits of a universal card (UV Card). In addition, the proposed ATG program for delay faults is applied to generate the test for stuck-at fault in a 3-input and a 4 input circuits of a universal card (UV Card), and ISCAS85 benchmark circuits. The UV Card is a NPP digital input/output solid state protection system card [KEPCRC 88], and the ISCAS85 circuits are the combinational benchmark circuits [Brglez 85]. The experiment results on ISCAS85 benchmark circuits show the compactness of using DF concept and 19-valued algebra in increasing the average number of faults that are covered by single test.
조합논리회로 내부에서 발생하는 정적 고장 (stack-at fault) 및 동적 고장 (delay fault) 검출을 위한 검사 입력단 자동 생성 알고리즘을 개발하였다. 알고리즘은 고장진단대상에 따라 두 개의 프로그램으로 구현되었다. 하나는 정적 고장에 대한 검사 입력단 자동생성프로그램 (ATG 프로그램) 이고, 다른 하나는 동적 고장에 대한 최적화 검사 입력단 자동생성 프로그램 (CTG 프로그램) 이다. 보다 빠른 자동생성 알고리즘 구현을 위하여 가속기법을 두개의 프로그램에 개발하여 적용하였다. 개발된 가속기법은 검색방법으로 degree of freedom (DF) 개념을, composite valued logic 형태로 19-valued logic을 각각 개발 및 적용하였다. DF 개념을 이용한 가속기법은 두개의 프로그램 모두에서 이용되었고, 반면 composite valued logic을 이용한 가속기법은 CTG 프로그램에서만 이용하였다. 그 이유는 고장진단대상인 fault의 종류가 따르기 때문이다.
검사 입력단 자동생성과정을 가속화하는 것은 검사 입력단 자동생성 알고리즘을 개선함에 있어서 반드시 필요하다. 가속화는 주로 불필요한 backtracking의 수를 줄이고, conflict를 조기에 발견하고, implication 사이의 계산 시간을 단축함으로써 달성된다. 이러한 목적을 위하여 DF 개념이 개발되었다. 이 DF 값은 backtracking을 수행할 때, 진단대상회로내의 특정한 장소에 원하는 값을 정의하기 어려운 정도인데, Gate의 종류와 연결 구조만으로 쉽게 계산된다. 얻어진 DF값은 하나의 장소에 여러 가지의 논리값(logic value)이 요구될 때, 이중에 가장 효과적인 값을 찾기 위해 이용된다.
동적 고장의 수는 전자회로의 크기가 커지면서 급속하게 늘어난다. 이와 같은 이유로 검사 입력단 생성 알고리즘의 가속화와 더불어 검사 입력단의 수를 줄이는 연구도 필요하다. 하나의 검사입력으로 보다 많은 동적 고장을 검출할 수 있는 검사 입력단을 생성하는 프로그램을 CTG 프로그램이라한다. 19-valued logic은 이와 같은 목적을 위해서 개발되었다. 다른 동적 고장 검사 입력단 생성 프로그램과는 달리, 19-valued logic은 robustly hazard-free test를 생성한다. 19-valued logic은 basic 5-valued logic에서 유도되는데, 6-valued logic과는 달리 이 basic 5-valued logic은 hazard 현상을 고려하여 정의되었다. 결론적으로 동적 고장에 대한 검사 입력단 자동생성 알고리즘의 가속기법은 DF 개념과 19-valued logic으로 구성되었다. DF 값은 뒤에서 앞으로 계산하는 backtracking을 수행할 때 이용되고, 19-valued logic은 앞에서 뒤로 계산하는 forward implication을 수행할 때 이용한다.
개발된 정적 고장 검출을 위한 검사 입력단 자동생성 프로그램을 원자력발전소 Solid state protection system에서 현재 이용되고 있는 디지털 입출력 카드인 Universial Card (UV Card)에 적용하여, 정적 고장을 검출을 위한 검사 입력단을 생성하였다. 아울러 동적 고장 검출을 위한 검사 입력단 자동생성 프로그램은 UV Card 및 ISCAS85 조합논리회로에 적용하여, 동적 고장 검출을 위한 검사 입력단을 생성하였다. 얻어진 결과로부터 DF 개념과 19-valued logic을 이용한 동적 고장 검사 입력단 생성 프로그램이 다른 동적 고장 검사 입력단 생성 프로그램보다 하나의 검사입력으로 검출되는 동적 고장의 수가 많음을 보였다. 이와 같은 결과로부터 CTG 프로그램을 이용하면 검사 입력단을 효과적으로 압축하여, 동적 고장 검사시 소요되는 시간을 줄여 고장진단 시간을 단축할 수 있음을 알았다.
