Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes

Published Feb 28, 2015• 0 citations

Abstract

Abstract — We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the trade-off between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovász’s Local Lemma and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed prop-erties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum likelihood decoding.

Related papers

Thorsten Hehn, Olgica Milenković, Stefan Laendner +1 more

We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovasz's local lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.

arXiv:0708.0905IEEE Transactions on Information TheoryDec 1, 200833 citations

The stopping redundancy hierarchy of cyclic codes

Thorsten Hehn, Stefan Laendner, Olgica Milenković +1 more

We extend the framework for studying the stopping redundancy of a linear block code by introducing and analyzing the stopping redundancy hierarchy.The stopping redundancy hierarchy of a code represents a measure of the trade-off between performance and complexity of iteratively decoding a code used over the binary erasure channel.It is defined as an ordered list of positive integers in which the ith entry, termed the i-th stopping redundancy, corresponds to the minimum number of rows in any parity-check matrix of the code that has stopping distance at least i.In particular, we derive lower and upper bounds for the i-th stopping redundancy of a code by using probabilistic methods and Bonferroni-type inequalities.Furthermore, we specialize the findings for cyclic codes, and show that parity-check matrices in cyclic form have some desirable redundancy properties.We also propose to investigate the influence of the generator codeword of the cyclic parity-check matrix on its stopping distance properties.

Allerton Conference on Communication, Control, and ComputingJan 1, 200610 citations

Permutation Decoding and the Stopping Redundancy Hierarchy of Linear Block Codes

Thorsten Hehn, Olgica Milenković, Stefan Laendner +1 more

We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of up to a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.

arXiv:cs/0702050IEEE International Symposium on Information Theory (ISIT)Jun 1, 20073 citations

Stopping Redundancy Hierarchy Beyond the Minimum Distance

Yauhen Yakimenka, Vitaly Skachek, Irina E. Bocharova +1 more

Stopping sets play a crucial role in failure events of iterative decoders over a binary erasure channel (BEC). The ℓth stopping redundancy is the minimum number of rows in the parity-check matrix of a code, which contains no stopping sets of size up to ℓ. In this paper, a notion of coverable stopping sets is defined. In order to achieve maximum-likelihood performance under iterative decoding over the BEC, the parity-check matrix should contain no coverable stopping sets of size ℓ, for 1 ≤ ℓ ≤ n-k, where n is the code length, k is the code dimension. By estimating the number of coverable stopping sets, we obtain upper bounds on the ℓth stopping redundancy, 1 ≤ ℓ ≤ n-k. The bounds are derived for both specific codes and code ensembles. In the range 1 ≤ ℓ ≤ d-1, for specific codes, the new bounds improve on the results in the literature. Numerical calculations are also presented.

arXiv:1804.06770IEEE Transactions on Information TheoryOct 1, 20185 citations

Generalized Stopping Sets and Stopping Redundancy

Khaled Abdel-Ghaffar, Jos H. Weber

Iterative decoding for linear block codes over erasure channels may be much simpler than optimal decoding but its performance is usually not as good. Here, we present a general iterative decoding technique that gives a more refined trade-off between complexity and performance. In each iteration, a system of equations is solved. In case the maximum number of equations to be solved is just one, the general iterative decoder reduces to the well-known iterative decoder. On the other hand, if the maximum number is set to the redundancy of the codes, the general iterative decoder gives the same performance as the optimal decoder. Varying the maximum number of equations to be solved in each iteration between these two extremes allows for a better match, in terms of performance and complexity, to the system specifications. Stopping sets and stopping redundancy are important concepts in the analysis of the performance and complexity of iterative decoders on the erasure channel. In consequence of the new generalized decoding procedure, the notions of stopping sets and stopping redundancy are generalized as well. Basic properties and examples of both generalized stopping sets and generalized stopping redundancy are presented in this paper.

Information Theory and Applications Workshop (ITA)Jan 1, 20073 citations

On the stopping distance and the stopping redundancy of codes

M. Schwartz, Alexander Vardy

It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s = d. We thus introduce a new parameter, termed the stopping redundancy of Copf, defined as the minimum number of rows in a parity-check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely s(H) = d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes

IEEE International Symposium on Information Theory (ISIT)Jan 1, 200527 citations