This thesis by Robert Gray Gallager, submitted to the Massachusetts Institute of Technology in 1960, focuses on Low Density Parity Check (LDPC) codes, which are a class of error-correcting codes used in digital data transmission. The key contributions of the thesis include: 1. **Distance Properties**: The thesis derives the distance properties of LDPC codes, showing that the typical minimum distance of these codes increases linearly with the block length \( n \) for constant values of \( j \) and \( k \) (where \( j \) is the number of ones in each column of the parity check matrix, and \( k \) is the number of ones in each row). This is significant because it indicates that the error-correcting capability of LDPC codes grows with the block length. 2. **Probability of Decoding Error**: The thesis analyzes the probability of decoding error for LDPC codes on a memoryless symmetric channel with a binary input alphabet and an arbitrary output alphabet. Using maximum likelihood decoding, it is shown that the probability of error decreases exponentially with \( n \), with an exponent close to the theoretical optimum. 3. **Decoding Scheme**: A simple decoding scheme is described that directly uses the channel a posteriori probabilities. This scheme has constant or logarithmically increasing computational complexity per digit and is shown to approach zero error probability on a Binary Symmetric Channel with sufficiently high capacity. 4. **Comparison with Other Schemes**: The thesis compares LDPC codes with other coding schemes such as convolutional codes and Bose-Chaudhuri codes, highlighting their advantages and limitations in terms of error probability, computational complexity, and flexibility in handling different types of channels. 5. **Experimental Results**: The thesis presents experimental results that support the theoretical findings, demonstrating the effectiveness of the proposed decoding scheme on noisy channels. Overall, the thesis provides a comprehensive analysis of LDPC codes, establishing their theoretical foundations and practical applications in error-correcting coding.This thesis by Robert Gray Gallager, submitted to the Massachusetts Institute of Technology in 1960, focuses on Low Density Parity Check (LDPC) codes, which are a class of error-correcting codes used in digital data transmission. The key contributions of the thesis include: 1. **Distance Properties**: The thesis derives the distance properties of LDPC codes, showing that the typical minimum distance of these codes increases linearly with the block length \( n \) for constant values of \( j \) and \( k \) (where \( j \) is the number of ones in each column of the parity check matrix, and \( k \) is the number of ones in each row). This is significant because it indicates that the error-correcting capability of LDPC codes grows with the block length. 2. **Probability of Decoding Error**: The thesis analyzes the probability of decoding error for LDPC codes on a memoryless symmetric channel with a binary input alphabet and an arbitrary output alphabet. Using maximum likelihood decoding, it is shown that the probability of error decreases exponentially with \( n \), with an exponent close to the theoretical optimum. 3. **Decoding Scheme**: A simple decoding scheme is described that directly uses the channel a posteriori probabilities. This scheme has constant or logarithmically increasing computational complexity per digit and is shown to approach zero error probability on a Binary Symmetric Channel with sufficiently high capacity. 4. **Comparison with Other Schemes**: The thesis compares LDPC codes with other coding schemes such as convolutional codes and Bose-Chaudhuri codes, highlighting their advantages and limitations in terms of error probability, computational complexity, and flexibility in handling different types of channels. 5. **Experimental Results**: The thesis presents experimental results that support the theoretical findings, demonstrating the effectiveness of the proposed decoding scheme on noisy channels. Overall, the thesis provides a comprehensive analysis of LDPC codes, establishing their theoretical foundations and practical applications in error-correcting coding.