On length, height and reliability of circuits realizing selection function

A. V. Rybakov

Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 108-110

Résumé

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.

Détail

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