The Number of Elements in Minimum Test Set for Locally Exhaustive Testing of Combinational Circuits with Five Outputs

Tokumi YOKOHIRA; Toshimi SHIMIZU; Hiroyuki MICHINISHI; Yuji SUGIYAMA; Takuji OKAMOTO

The Number of Elements in Minimum Test Set for Locally Exhaustive Testing of Combinational Circuits with Five Outputs

Tokumi YOKOHIRA, Toshimi SHIMIZU, Hiroyuki MICHINISHI, Yuji SUGIYAMA, Takuji OKAMOTO

Full Text Views

0

Cite this

Summary :

Any minimum test set (MLTS) for locally exhaustive testing of multiple output combinational circuits (CUTs) has at least 2^w test patterns, where w is the maximum number of inputs on which any output depends. In the previous researches, it is clarified that every CUT with up to four outputs has an MLTS with 2^w elements. On the other hand, it can be easily shown that every CUT with more than five outputs does not have such an MLTS. It has not been however known whether every CUT with five outputs has such an MLTS or not. In this paper, it is clarified that every CUT with five outputs has such an MLTS. First, some terminologies are introduced as preliminaries. Second, features of 5(w1) dependence matrices of CUTs with five outputs and (w1) inputs are discussed. Third, an equivalence relation between dependence matrices of two CUTs is introduced. The relation means that if it holds and one of the CUTs has an MLTS with 2^w elements, then the other CUT also has such an MLTS. Based on the features described above, a theorem is established that there exists a 5w dependence matrix which is equivalent to each of the above 5(w1) matrices. Finally, it is proved by the use of the theorem that every CUT with five outputs has an MLTS with 2 ^w elements.

Publication: IEICE TRANSACTIONS on Information Vol.E78-D No.7 pp.874-881

Publication Date: 1995/07/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Verification, Test and Diagnosis of VLSI Systems)

Category

Cite this

Copy

Tokumi YOKOHIRA, Toshimi SHIMIZU, Hiroyuki MICHINISHI, Yuji SUGIYAMA, Takuji OKAMOTO, "The Number of Elements in Minimum Test Set for Locally Exhaustive Testing of Combinational Circuits with Five Outputs" in IEICE TRANSACTIONS on Information, vol. E78-D, no. 7, pp. 874-881, July 1995, doi: .
Abstract: Any minimum test set (MLTS) for locally exhaustive testing of multiple output combinational circuits (CUTs) has at least 2^w test patterns, where w is the maximum number of inputs on which any output depends. In the previous researches, it is clarified that every CUT with up to four outputs has an MLTS with 2^w elements. On the other hand, it can be easily shown that every CUT with more than five outputs does not have such an MLTS. It has not been however known whether every CUT with five outputs has such an MLTS or not. In this paper, it is clarified that every CUT with five outputs has such an MLTS. First, some terminologies are introduced as preliminaries. Second, features of 5(w1) dependence matrices of CUTs with five outputs and (w1) inputs are discussed. Third, an equivalence relation between dependence matrices of two CUTs is introduced. The relation means that if it holds and one of the CUTs has an MLTS with 2^w elements, then the other CUT also has such an MLTS. Based on the features described above, a theorem is established that there exists a 5w dependence matrix which is equivalent to each of the above 5(w1) matrices. Finally, it is proved by the use of the theorem that every CUT with five outputs has an MLTS with 2 ^w elements.
URL: https://global.ieice.org/en_transactions/information/10.1587/e78-d_7_874/_p

Copy

@ARTICLE{e78-d_7_874,
author={Tokumi YOKOHIRA, Toshimi SHIMIZU, Hiroyuki MICHINISHI, Yuji SUGIYAMA, Takuji OKAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={The Number of Elements in Minimum Test Set for Locally Exhaustive Testing of Combinational Circuits with Five Outputs},
year={1995},
volume={E78-D},
number={7},
pages={874-881},
abstract={Any minimum test set (MLTS) for locally exhaustive testing of multiple output combinational circuits (CUTs) has at least 2^w test patterns, where w is the maximum number of inputs on which any output depends. In the previous researches, it is clarified that every CUT with up to four outputs has an MLTS with 2^w elements. On the other hand, it can be easily shown that every CUT with more than five outputs does not have such an MLTS. It has not been however known whether every CUT with five outputs has such an MLTS or not. In this paper, it is clarified that every CUT with five outputs has such an MLTS. First, some terminologies are introduced as preliminaries. Second, features of 5(w1) dependence matrices of CUTs with five outputs and (w1) inputs are discussed. Third, an equivalence relation between dependence matrices of two CUTs is introduced. The relation means that if it holds and one of the CUTs has an MLTS with 2^w elements, then the other CUT also has such an MLTS. Based on the features described above, a theorem is established that there exists a 5w dependence matrix which is equivalent to each of the above 5(w1) matrices. Finally, it is proved by the use of the theorem that every CUT with five outputs has an MLTS with 2 ^w elements.},
keywords={},
doi={},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - The Number of Elements in Minimum Test Set for Locally Exhaustive Testing of Combinational Circuits with Five Outputs
T2 - IEICE TRANSACTIONS on Information
SP - 874
EP - 881
AU - Tokumi YOKOHIRA
AU - Toshimi SHIMIZU
AU - Hiroyuki MICHINISHI
AU - Yuji SUGIYAMA
AU - Takuji OKAMOTO
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 1995
AB - Any minimum test set (MLTS) for locally exhaustive testing of multiple output combinational circuits (CUTs) has at least 2^w test patterns, where w is the maximum number of inputs on which any output depends. In the previous researches, it is clarified that every CUT with up to four outputs has an MLTS with 2^w elements. On the other hand, it can be easily shown that every CUT with more than five outputs does not have such an MLTS. It has not been however known whether every CUT with five outputs has such an MLTS or not. In this paper, it is clarified that every CUT with five outputs has such an MLTS. First, some terminologies are introduced as preliminaries. Second, features of 5(w1) dependence matrices of CUTs with five outputs and (w1) inputs are discussed. Third, an equivalence relation between dependence matrices of two CUTs is introduced. The relation means that if it holds and one of the CUTs has an MLTS with 2^w elements, then the other CUT also has such an MLTS. Based on the features described above, a theorem is established that there exists a 5w dependence matrix which is equivalent to each of the above 5(w1) matrices. Finally, it is proved by the use of the theorem that every CUT with five outputs has an MLTS with 2 ^w elements.
ER -