RUS  ENG
Full version
JOURNALS // University proceedings. Volga region. Physical and mathematical sciences // Archive

University proceedings. Volga region. Physical and mathematical sciences, 2009 Issue 2, Pages 2–13 (Mi ivpnz680)

Mathematics

About one set of functions

V. V. Chugunova

Penza State University, Penza

Abstract: The realization of Boolean functions with circuits of unreliable functional elements in bases, contained the function $h(x_1,...,x_{2k+1})$ from set $H_{2k+1}$ is considered. The basis elements are supposed to be prone to inverse faults on element inputs independently from each other with the probability ($\epsilon \in (0; 1/2)$). I this work there are demonstrated: 1) in arbitrary finite full basis B, contained function $h(x_1,...,x_{2k+1})$ from set $H_{2k+1}$, all Boolean functions are possible to realize with circuits with reliability at most $a\epsilon^{k+1}+\epsilon^{k+2}$ at $\epsilon \leq \frac{1}{48am^2(2k+1)}$, where $a=C_{2k+1}^{k+1}$, $m$ is the greatest number of element inputs in finite full basis B; 2) in basis $\tilde{B}$, contained all functions, depended at most on two variables, and the function $h(x_1,...,x_{2k+1}) \in H_{2k+1}$, functions are possible to realize with asymptotically optimal on reliability circuits, worked with unreliability, asymptotically equal to $a\epsilon^{k+1}$ (at $\epsilon \to 0$), where $a=C_{2k+1}^{k+1}$.

Keywords: boolean functions, asymptotically optimal reliable circuits.

UDC: 519.718



© Steklov Math. Inst. of RAS, 2024