Conditional Testing for Cardot Circuits
- PDF / 471,651 Bytes
- 2 Pages / 612 x 792 pts (letter) Page_size
- 4 Downloads / 208 Views
T COMMUNICATIONS
Conditional Testing for Cardot Circuits A. A. Voronenko* Department of Computational Mathematics and Cybernetics, Moscow State University, Moscow, 119991 Russia Received April 2, 2020; in final form, May 7, 2020; accepted May 12, 2020
Abstract—Absolute lower bound 2n is established for the length of a full conditional diagnostic test for a Cardot circuit that implements the sum of n variables. Keywords: contact circuit, test, chain. DOI: 10.3103/S0278641920030061
All the basic definitions not interpolated here can be found in [1, pp. 59–80]. In [2], the properties of the Cardo circuit implementing the sum of n variables modulo 2 were described. The principal result was obtained in [3], where it was proved that with a certain number of faults, given any contact circuit that implements the sum modulo 2 of variables x1 , . . . , xn , we can obtain any one of the functions xσ1 1 & . . . &xσnn , where σ1 ⊕ . . . ⊕ σn = 1, and functions xσ1 1 ∨ . . . ∨ xσnn , where σ1 ⊕ . . . ⊕ σn = 0, along with both constants. This result implies a lower bound 2n for the length of the unconditional full diagnostic test for an arbitrary contact circuit that implements the sum of n variables modulo 2 and a lower bound 2n−1 for the conditional test for this problem. Upper and lower logarithmic (in the number of variables) bounds for the length of diagnostic tests for Cardot circuits can be found in [4–6]. In [7, 8], the set of fault functions was described for a Cardot circuit that implements the sum of four variables. However, a mistake was made in these works: the so-called inverse conductivity was not considered, making the resulting set of functions have a conditional test of depth 14. This error was corrected in [9]. The set obtained in [9] had several hundred fewer functions than in [7, 8], but it allowed only a trivial test of depth 24 = 16. In this work, we establish that in a problem of the full diagnostic testing procedure of the Cardot circuit, the possibility of using conditional tests does not reduce the test depth, which takes trivial maximum value 2n . For clarity, we consider a Cardot circuit in the same form as in [1, p. 75]: the blocks of contacts are in ascending order of the indices of variables from the pole at the lower left to the pole at the upper right. To confirm this, we prove the main statement below: Lemma 1. For any Boolean function of n 3 variables that takes the value 1 at most at a single point, there exists a faulty Cardot circuit that implements this function. Proof. If we open all contacts in the Cardot circuit, we obtain the one that implements the zero constant. Let σ1 ⊕ . . . ⊕ σn = 1. There then exists a chain of n contacts in the Cardot circuit that conducts only on set (σ1 , . . . , σn ). Opening all other contacts, we get a circuit that implements function xσ1 1 & . . . &xσnn . Ssituation σ1 ⊕ . . . ⊕ σn = 0 can be divided into two cases: 1. There exists a position i, 2 i n − 1 such that σi = 1. 2. σ2 = . . . = σn−1 = 0. 1. Let C be a conductive chain corresponding to set (σ1
Data Loading...
