Analyzing and Designing Error-Correcting Codes
A fundamental problem in information theory is the analysis and design of optimal and efficiently decodable error-correcting codes of a given block-length and rate. The discovery of turbo codes in 1993 and the re-discovery of Gallager codes soon thereafter stimulated considerable research into iterative decoding of codes on graphs. One can now argue that in the infinite block-length limit, we understand how to approach the Shannon limit. For practical applications, however, one must work with codes of finite block-length, for which existing theory is far from sufficient. We have developed new techniques to analyze and design finite-blocklength codes which can be decoded using iterative message-passing algorithms.
Background & Objective: The best-known technique to analyze the performance of iterative belief propagation decoding is the "density evolution" method. However, this method presumes that the "messages" passed in the decoding algorithm are statistically independent, and is therefore only valid for the infinite block-length limit of certain codes such as irregular Gallager codes and their relatives. Our objective is to devise an efficient technique for computing the entire performance curve for an arbitrary parity check code of finite block-length. This performance curve can then be used to estimate the performance of a code at very low error-rates where simulation is impossible, or as an objective function in a search over codes.
Technical Discussion: We have so far developed two new techniques. The first is based on the "renormalization-group" approach from physics: the idea is to continually replace an error-correcting code with a simpler error-correcting code that has nearly identical performance, until the code is reduced to a small enough size that its performance can be computed exactly. The second technique, which we call "projective algebra," is a generalization of density evolution that exactly accounts for the statistical dependencies between messages in the same loop.
Publications:
Technology Area: Digital Communications
Modification Date: September 12, 2007