Implementation of Linear Boolean Functions by Self-Correcting Circuits of Unreliable Logic Gates
摘要
Abstract
We prove that if a Boolean function essentially depends on at least two variables, then it cannot be implemented by a circuit that consists of unreliable gates with at most two inputs each and is self-correcting with respect to at least some faults of an arbitrary number of gates. In view of the previous results, it suffices to establish this fact for linear functions.