Low Density Parity Check Codes By Robert Gray Gallager B.S., University of Pennsylvania (1953) M.S., Massachusetts Institute of Technology (1957) Submitted in partial fulfillment of the requirements for the degree of Doctor of Science at the Massachusetts Institute of Technology September, 1960 Signature of Author Department of Electrical Engineering, August 26, 1960 Certified by ___ Thesis Supervisor Accepted by ___ Chairman, Departmental Committee on Graduate Students Low Density Parity Check Codes by Robert Gray Gallager Submitted to the Department of Electrical Engineering on August 26, 1960 in partial fulfillment of the requirements for the degree of Doctor of Science. Abstract An ensemble of parity check codes of arbitrary block length, n, is considered in which each digit of each code is checked by a small fixed number, j, of parity check equations, and each parity check set contains a small, fixed number, k, of digits. The typical minimum distance of codes in such an ensemble increases linearly with n for constant j and k if j ≥ 3. The probability of decoding error for this ensemble of codes on a memoryless symmetric channel with a binary input alphabet and an arbitrary output alphabet is analyzed. Using maximum likelihood decoding on a sufficiently quiet channel, the probability of error is shown to be exponentially decreasing with n; this exponent is relatively close to the theoretical optimum exponent. A simple decoding scheme that directly uses the channel a posteriori probabilities is described in which the decoding computation per digit appears to be constant, or at most, logarithmically increasing with the code length. The probability of decoding error is shown by a weak bound to approach zero with increasing block length when this non-optimum decoding scheme is used on a Binary Symmetric Channel of sufficiently high capacity. Although no tight bounds have been found for the probability of decoding error using this simple decoding scheme, both some experimental results and the form of the weak bound indicate the potentiality of the decoding scheme. Thesis Supervisor: Peter Elias Title: Professor of Electrical Engineering Acknowledgment The author gratefully acknowledges both the Research Laboratory of Electronics and the M. I. T. Computation Center for the facilities used in this research. He is also indebted to his associates in R. L. E. for their patience in listening to many half-formed ideas and proofs. He also wishes to publicly thank his wife, Ruth, for her aid in editing and the typing of this paper. The author is especially grateful to Professor Robert M. Fano, not only for assistance in this work, but also for his consistent encouragement and excellent advice over the past four years. Finally, the author particularly wishes to thank Professor Peter Elias for the time, quickness, and insight that aided this work in immeasurable ways. Table of Contents Page Abstract.....2 AcknowledgmentLow Density Parity Check Codes By Robert Gray Gallager B.S., University of Pennsylvania (1953) M.S., Massachusetts Institute of Technology (1957) Submitted in partial fulfillment of the requirements for the degree of Doctor of Science at the Massachusetts Institute of Technology September, 1960 Signature of Author Department of Electrical Engineering, August 26, 1960 Certified by ___ Thesis Supervisor Accepted by ___ Chairman, Departmental Committee on Graduate Students Low Density Parity Check Codes by Robert Gray Gallager Submitted to the Department of Electrical Engineering on August 26, 1960 in partial fulfillment of the requirements for the degree of Doctor of Science. Abstract An ensemble of parity check codes of arbitrary block length, n, is considered in which each digit of each code is checked by a small fixed number, j, of parity check equations, and each parity check set contains a small, fixed number, k, of digits. The typical minimum distance of codes in such an ensemble increases linearly with n for constant j and k if j ≥ 3. The probability of decoding error for this ensemble of codes on a memoryless symmetric channel with a binary input alphabet and an arbitrary output alphabet is analyzed. Using maximum likelihood decoding on a sufficiently quiet channel, the probability of error is shown to be exponentially decreasing with n; this exponent is relatively close to the theoretical optimum exponent. A simple decoding scheme that directly uses the channel a posteriori probabilities is described in which the decoding computation per digit appears to be constant, or at most, logarithmically increasing with the code length. The probability of decoding error is shown by a weak bound to approach zero with increasing block length when this non-optimum decoding scheme is used on a Binary Symmetric Channel of sufficiently high capacity. Although no tight bounds have been found for the probability of decoding error using this simple decoding scheme, both some experimental results and the form of the weak bound indicate the potentiality of the decoding scheme. Thesis Supervisor: Peter Elias Title: Professor of Electrical Engineering Acknowledgment The author gratefully acknowledges both the Research Laboratory of Electronics and the M. I. T. Computation Center for the facilities used in this research. He is also indebted to his associates in R. L. E. for their patience in listening to many half-formed ideas and proofs. He also wishes to publicly thank his wife, Ruth, for her aid in editing and the typing of this paper. The author is especially grateful to Professor Robert M. Fano, not only for assistance in this work, but also for his consistent encouragement and excellent advice over the past four years. Finally, the author particularly wishes to thank Professor Peter Elias for the time, quickness, and insight that aided this work in immeasurable ways. Table of Contents Page Abstract.....2 Acknowledgment