Lower bounds for lengths of single tests for Boolean circuits

被引：5
作者：
Popkov, Kirill A. [1 ]
机构：
[1] Keldysh Inst Appl Math, Moscow, Russia
来源：
DISCRETE MATHEMATICS AND APPLICATIONS | 2019年 / 29卷 / 01期
基金：
俄罗斯基础研究基金会;
关键词：
Boolean circuit; stuck-at fault; single fault detection test; single diagnostic test; EASILY TESTABLE CIRCUITS; CONSTANT FAULTS; OUTPUTS;
D O I：
10.1515/dma-2019-0004
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We obtain nontrivial lower bounds for lengths of minimal single fault detection and diagnostic tests for Boolean circuits in wide classes of bases in presence of stuck-at faults at outputs of circuit gates.
引用
收藏
页码：23 / 33
页数：11
相关论文
共 19 条
[1]   Synthesis of easily testable circuits over the Zhegalkin basis in the case of constant faults of type 0 at outputs of elements [J].
Borodina, Yu V. ;
Borodin, P. A. .
DISCRETE MATHEMATICS AND APPLICATIONS, 2010, 20 (04) :441-449
[2]   Circuits Admitting Single-Fault Tests of Length 1 under Constant Faults at Outputs of Elements [J].
Borodina, Yu. V. .
MOSCOW UNIVERSITY MATHEMATICS BULLETIN, 2008, 63 (05) :202-204
[3]   Synthesis of easily-tested circuits in the case of single-type constant malfunctions at the element outputs [J].
Borodina Y.V. .
Moscow University Computational Mathematics and Cybernetics, 2008, 32 (1) :42-46
[4]  
Chegis I. A., 1958, Tr. Mat. Inst. Steklova, V51, P270
[5]  
Kolyada S. S, 2013, THESIS
[6]  
Popkov K. A, 2015, PREPRINTY IPM MV KEL
[7]  
Popkov K. A., 2016, PREPRINTY IPM MV KEL
[8]  
Red'kin N. P, 1986, MOSCOW U MATH B 1, V1, P72
[9]  
Red'kin N. P, 1992, MOSCOW U MATH B 1, V1, P43
[10]  
Reddy S. M., 1972, IEEE T COMPUT, V21, P124
12