Synthesis and Complexity of Asymptotically Optimal Circuits with Unreliable Gates

Issue title: Hardest Boolean Functions and O.B. Lupanov

Article type: Research Article

Authors: Alekhina, Marina An.

Affiliations: Penza State University, Krasnaya st., 40, Penza, Russia. ama@sura.ru

Note: [] Address for correspondence: Penza State University, Krasnaya st., 40, Penza, Russia

Abstract: 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.

Keywords: Boolean function, synthesis, complexity, reliability of combinatorial circuits

DOI: 10.3233/FI-2010-345

Journal: Fundamenta Informaticae, vol. 104, no. 3, pp. 219-225, 2010