Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Synthesis and Complexity of Asymptotically Optimal Circuits with Unreliable Gates

Alekhina M.Z.

Fundamenta Informaticae

2010

Vol. 104, nr 3

219-225

We consider the realization of Boolean functions by combinatorial circuits with unreliable gates computing the functions from a complete final basis B. We assume that all gates of the basis can have inverse faults on the outputs independently with probability ε(ε∈(0,1/2). We describe a set Mk (k≥3) of Boolean functions, presence even by one of which in basis B guarantees the computing of almost all Boolean functions by asymptotically optimal circuits with unreliability ε at ε→0. We prove that, for almost all functions, the complexity of asymptotically circuits with unreliable gates exceeds the complexity of the minimal circuits constructed from absolutely reliable gates by a multiplicative factor of 3(1 + b) for any b > 0.