RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2017 Issue 10, Pages 126–128 (Mi pdma310)

Mathematical Foundations of Reliability of Computing and Control Systems

On the reliability of circuits in some full bases (in $P_3$) with inverse faults at the gate outputs

M. A. Alekhinaa, O. Yu. Barsukovab

a Penza State Technological University, Penza
b Penza State University, Penza

Abstract: We consider the realization of ternary logic functions by circuits from unreliable functional elements in full finite bases $B_1$ and $B_2$, the first of which is the dual one to Rosser–Turkett basis, and the second one is the dual basis to the basis consisting of Webb's function. We assume that the circuit elements are exposed to inverse faults with probability $p$ at element outputs independently. We have obtained the following results: in the basis $B_1$, 1) any function from $P_3$ can be realized by a circuit with unreliability that is asymptotically (for small $p$) not more than $6p$; 2) for almost any function, such a circuit is asymptotically optimal to reliability and operates with the unreliability asymptotically equalled $6p$ for small $p$; in the basis $B_2$, almost any function can be realized by a reliable circuit that operates with the unreliability that is asymptotically not more than $8p$ and asymptotically not less than $6p$ for small $p$.

Keywords: ternary logic functions, unreliable functional gates, the reliability and unreliability of a circuit, inverse failures on outputs of gates.

UDC: 519.718

DOI: 10.17223/2226308X/10/49



© Steklov Math. Inst. of RAS, 2024