A statistical decoding algorithm for linear block codes

Includes bibliographical references (p. 39)Linear block codes are used in modern communication and digital storage systems to combat random errors that are introduced by communication channels (e.g., telephone lines, atmosphere, and compact discs). The idea is that the redundant bits contained in each codeword of a code can be used by the receiver to recover the actual transmitted codeword or message. The process of recovering the original codeword from a corrupted version of it is called decoding. It is implemented by an algorithm located at the receiver's end. Informally speaking, a good code is one that has a high rate, that is, it does not use much redundancy to allow error correction, but it also has an efficient decoding algorithm. Therefore, finding good codes is a relevant problem in the design of communication systems. Decoding a general linear code is an NP-hard problem: The best known general decoding algorithm for linear codes, a.k.a. syndrome decoding, increases exponentially in complexity with the length of the code. The objective of the present work is to implement/analyze a statistical decoding algorithm in a robust manner that is efficient with regards to both the amount of storage space needed and computation complexity. At least for codes of lengths less than 100, it has proven to work much faster than syndrome decoding and even some well-established decoding algorithms. The application of the algorithm is mainly illustrated with quadratic residue codes. The choice was due to the fact that QR codes have a high rate, but finding efficient decoding algorithms for them is still a challenging problem