Error-Correcting Codes for Computer Memories

Citation

Blaum, Mario (1985) Error-Correcting Codes for Computer Memories. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/bdd9-pr94. https://resolver.caltech.edu/CaltechTHESIS:12122018-111430579

Abstract

This thesis is divided into four independent chapters and two appendices.

Chapter I deals with the following generalization of the birthday surprise problem: how many people we need to interview on the average until either r birthdays occur k times each or one birthday occurs k + 1 times. If r = 1, we obtain the usual "birthday surprise" number. We verify that our formula generalizes previous known results. We give asymptotic estimates for the birthday surprise number using a theorem proved in appendix I.

In chapter II, we present accurate and easily evaluated estimates for the average lifetime of a semiconductor RAM memory protected by a single error correcting, doubly error detecting (SEC-DED) code. This problem is somehow related to the one in chapter I. As an application, we give an analysis of the benefits of soft error "scrubbing" when both hard and soft errors are present. We also discuss two methods for increasing the lifetime of a computer memory: adding s rows of spare chips and implementing 2-ECC. We close the chapter by comparing the two methods.

In chapter III, we describe a class of burst error correcting array codes. We prove the fundamental properties of these codes.

Patel and Hong have constructed a code that can correct any track error or two track erasures in a 9-track magnetic tape. In chapter IV, we extend the construction to codes that can correct higher numbers of track errors and erasures. The result is a new family of codes, the B(n,m)-codes.

In appendix I, we prove an important theorem used for asymptotic estimates of integrals. This theorem is used in chapters I and II.

Thesis Files