IEEE International Symposium on Information Theory (ISIT)

Generalized Iterative Decoding for Linear Block Codes on the Binary Erasure Channel

Khaled Abdel-Ghaffar, Jos H. Weber

Published Jun 1, 2007• 6 citations

Abstract

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.

DOI: 10.1109/isit.2007.4557205

Related papers

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

An improvement to GMD-like decoding algorithms

H. Tokushiga, Takuya Koumoto, Tadao Kasami

For binary linear block codes, we introduce a multiple generalized minimum distance (GMD) decoding algorithm, where GMD-like decoding is iterated around a few appropriately selected search centers. Compared with the original GMD decoding by Forney (1966), this decoding algorithm provides better error performance by increasing the number of iterations of erasure and error correction moderately. To reduce the number of iterations, we derive new effective sufficient conditions on the optimality of decoded codewords.

IEEE International Symposium on Information Theory (ISIT)Nov 7, 20022 citations

On Decoding Failure Probabilities for Linear Block Codes on the Binary Erasure Channel

Jos H. Weber, Khaled Abdel-Ghaffar

It has been claimed that the performance of a linear block code under iterative decoding on the binary erasure channel is determined by the stopping distance, i.e., the size of the smallest non-empty stopping set in the associated Tanner graph. Indeed, this is true from the perspective of code word retrieval. However, we show that with respect to the retrieval of just the information bits within the code word, the stopping distance may not be the main performance indicator since the smallest non-empty stopping sets might not hit the information set. We present expressions for decoding failure probabilities for code/information words/bits under optimal or iterative decoding and demonstrate the importance of the choice of the set of bits carrying the information for a fixed code with a fixed decoder

IEEE Information Theory Workshop (ITW)Oct 1, 20063 citations

Erasure-Burst and Error-Burst Decoding of Linear Codes

Shumei Song, Shu Lin, Khaled Abdel-Ghaffar +1 more

Iterative algorithms for decoding over erasure-burst channels have attracted much interest lately due to their simplicity. Although the performance of these techniques is typically good, it may not be optimal if the underlying matrix used for decoding is not properly chosen. In this paper, we construct matrices that lead to optimal performance when used with iterative decoding over erasure-burst channels. We also develop a simple decoding technique that makes use of these same matrices to decode any linear code over error-burst channels. For cyclic codes, this algorithm is optimal.

IEEE Information Theory Workshop (ITW)Sep 1, 20076 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

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

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.

Feb 28, 20150 citations