On parity check collections for iterative erasure decoding that correct all correctable erasure patterns of a given size

Abstract

Recently there has been interest in the construction of small parity check sets for iterative decoding of the Hamming code with the property that each uncorrectable (or stopping) set of size three is the support of a codeword and hence uncorrectable anyway. Here we reformulate and generalise the problem, and improve on this construction. First we show that a parity check collection that corrects all correctable erasure patterns of size m for the r-th order Hamming code (i.e, the Hamming code with codimension r) provides for all codes of codimension $r$ a corresponding ``generic'' parity check collection with this property. This leads naturally to a necessary and sufficient condition on such generic parity check collections. We use this condition to construct a generic parity check collection for codes of codimension r correcting all correctable erasure patterns of size at most m, for all r and m <= r, thus generalising the known construction for m=3. Then we discussoptimality of our construction and show that it can be improved for m>=3 and r large enough. Finally we discuss some directions for further research.

13 pages, no figures. Submitted to IEEE Transactions on Information Theory, July 28, 2005

Cited by in corpus (6)

• Multiple-Bases Belief-Propagation Decoding of High-Density Cyclic Codes
• Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes
• The Trapping Redundancy of Linear Block Codes
• Bounds on Separating Redundancy of Linear Codes and Rates of X-Codes
• Single-Exclusion Number and the Stopping Redundancy of MDS Codes
• Refined Upper Bounds on Stopping Redundancy of Binary Linear Codes