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.
The generalized iterative decoding concept offers attractive performance versus complexity trade-off opportunities in the spectrum between traditional iterative decoding and optimal decoding for linear block codes over the binary erasure channel. In each iteration, a system of equations is solved. The maximum number of equations to be solved in one iteration is called the order of the decoder. In case the order is just one, the generalized iterative decoder reduces to the traditional iterative decoder. On the other hand, if the order is set to the redundancy of the codes, the generalized iterative decoder gives the same performance as the optimal decoder. Varying the order between these two extremes allows for a better match to the system specifications. In this paper, we consider aspects regarding the implementation of generalized iterative decoding and we determine the minimum order (as a function of the girth) that can potentially lead to improvement over traditional iterative decoding.
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 Lová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.
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.
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.
It is now well known that the performance of a linear code
C 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
C. Several recent papers refer to this parameter as the \emph{stopping distance}
s of
C. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for
C depends on the corresponding choice of a parity-check matrix. It is easy to see that
s≤d, where
d is the minimum Hamming distance of
C, and we show that it is always possible to choose a parity-check matrix for
C (with sufficiently many dependent rows) such that
s=d. We thus introduce a new parameter, termed the \emph{stopping redundancy} of
C, defined as the minimum number of rows in a parity-check matrix
H for
C 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 35 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes.
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.