Reliable Information Storage in Memories Designed from Unreliable Components

The problem of designing systems which operate reliably even though their components are unreliable has been formulated in many different ways. In a typical formulation, one considers some particular * This work, which is based on part of a doctoral thesis submitted to the D e p a r t m e n t of Electrical Engineering, M.IT., September 1966, was supported by the National Aeronautics and Space Administration ( G r a n t NsG-334), 2299 2306 T H E BELL SYSTEM T E C H N I C A L J O U R N A L , DECEMBER 19(58 system which performs a computation with a nonzero probability of error. The problem is to design some other "reliable" system which performs the same computation using the same types of components but with a smaller probability of error. In fact, the ultimate objective is to show that it is possible to design systems, using only unreliable components, which perform computations with an arbitrarily small probability of error. Unfortunately, there is no standard terminology for describing these systems; therefore, the following section introduces the terminology to be used throughout this paper. l.l Definitions The computations performed by the computing systems are described in terms of elementary operations where an elementary operation is any Boolean function of two binary operands. There are sixteen different elementary operations, each one of which can be represented by a binary matrix of the type shown in Fig. 1. Typical elementary operations are AND, OR, and modulo-2 addition.