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

Prikl. Diskr. Mat. Suppl., 2015 Issue 8, Pages 108–110 (Mi pdma240)

Mathematical Foundations of Reliability of Computing and Control Systems

On length, height and reliability of circuits realizing selection function

A. V. Rybakov

Penza State University, Penza

Abstract: We consider planar (flat) circuits realizing the selection function $v_n=\bigvee_\sigma x_1^{\sigma_1}x_2^{\sigma_2}\dots x_n^{\sigma_n}y_{|\widetilde\sigma|}$, where $n$ is an even integer; $\sigma_i\in\{0,1\}$, $x_i^{\sigma_i}=x_i$ if $\sigma_i=1$ and $x_i^{\sigma_i}=\bar{x_i}$ if $\sigma_i=0$, $i=1,2,\dots,n$; $|\widetilde\sigma|\in\{0,1,\dots,2^n-1\}$ and $|\widetilde\sigma|=\sum_{i=1}^n\sigma_i2^{n-i}$. It is assumed that the switching elements are absolutely reliable, functional elements are subject to inversion failures on its outputs and independently pass into defective states. Some relations for the length and height, as well as an estimate of the unreliability of such circuits are found.

Keywords: Boolean functions, planar circuits, inversion failures, unreliability of circuit, function of selection.

UDC: 519.718

DOI: 10.17223/2226308X/8/41



© Steklov Math. Inst. of RAS, 2024