Belief Revision and Small Loops in Gallager-Type Error-Correcting Codes

Abstract

Gallager-type error-correcting codes are low density parity check codes (LDPC) which may in specific case nearly saturate Shannon’s bound. They are based on the construction of two very sparse matrices, various structures of which have been studied in recent years. We will mainly focus here on constructions that have recently been studied by Kanter and Saad. The aim of this project is to examine the performance of two different decoding LDPC algorithms, belief propagation and belief revision within this framework, as well as that of different coding methods (MN vs. Gallager codes).We will also look at the effect of removing small loops in the matrices on the code’s performance.