Capacity and coding for computer memory with defects
Chris Heegard · 1981
This thesis is concerned with the problem of reliable message storage in an imperfect computer memory. We examine the type of imperfections that affect individual cells of the memory. For example, some of the cells of a binary memory may be stuck at 0 and unable to store information. A second type of imperfect memory cell is a noisy cell that is occasionally in error. The distinction between these two sources of error is that stuck-at defects are permanent while errors caused by noise are random. By testing the memory it is possible to determine the locations of the stuck-at cells. In this thesis we examine how the information that describes the state of the defects can be used to aid the encoding or decoding of messages. First, a probabilistic model for computer memory with defects and noise is introduced. The capacity of a computer memory is defined as the largest rate at which messages can be reliably stored. We present a lower bound to the capacity when complete or partial knowledge of the location and nature of the defects is available to the encoder or to the decoder. This bound yields the capacity for several special cases including every case that involves complete knowledge of the defects. Algorithms are presented that can be used to compute the capacity of these memories. These algorithms are used to examine several examples. Next, computer memory with stuck-at defects and additive errors are examined from an algebraic viewpoint. We examine the problem of efficiently incorporating defect information in the encoding or decoding of linear block codes. When the locations of the stuck-at cells is given to the decoder, these cells act as erasures. Thus techniques for decoding linear block codes with erasures and errors can be employed. A class of modified linear block codes is introduced to correct defects and errors when the location and nature of the stuck-at cells is given to the encoder. The defect and error correction capability of linear block codes is characterized in terms of the minimum distances of the code. It is shown that every linear block code can assume a systematic form without affecting the defect and error correction capability. The capacity of a class of q -ary symmetric memory cells is derived using the information theoretic model. Two theorems are stated that are used to prove that the class of modified linear block codes achieve capacity for these memories. Finally, the class of modified cyclic block codes is introduced. The BCH bound for these cyclic codes can be employed to construct MLBC's with specified bounds on the minimum distances. Parameters of binary codes for several block lengths are tabulated.