Redundancy and complexity of logical elements

Abstract

This paper deals with the problem of increasing the reliability of gate-type logical circuits through the use of redundancy. We will derive a lower bound on the amount of redundancy necessary to achieve a certain error correcting ability and show how this bound varies with the complexity of the elements used in the design of the redundant circuit, measured by the number of inputs. The complexity of encoders of block codes for transmission of information is defined. A bound similar to the one mentioned above on the error correcting ability of codes is derived which depends on the codes' rate of transmission and on the complexity of their encoders. Finally, we establish a connection between the bound on the error correcting ability of a redundant circuit and the bound on the error correcting ability of a block code. © 1963 Academic Press Inc.