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

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes,10.1109/TIT.2008.2006456,IEEE Transactions on Informati

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes   (Citations: 7)
BibTex | RIS | RefWorks Download
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.
Journal: IEEE Transactions on Information Theory - TIT , vol. 54, no. 12, pp. 5308-5331, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Another closely related approach was described in [11], where a simple simulation-based study was performed using randomly chosen parity-check matrices of the [24, 12, 8] extended Golay code...
    • ...The approach followed in this paper draws upon the prior work of the authors on BEC decoding [12] and introduces a novel decoding method that operates in parallel and iterative fashion on a collection of parity-check matrices...
    • ...For cyclic algebraic codes, we proved in a companion paper [12] that parity-check matrices that consist of cyclic shifts of carefully chosen cogs offer excellent stopping set properties...
    • ...illustrate our findings only on the [24, 12, 8] extended Golay...
    • ...We use �� to denote the number of parallel BP decoders in the MBBP architecture. A. The [24, 12, 8] Extended Golay Code...
    • ...The [24, 12, 8]extended Golay code is self dual and contains 759 codewords of minimum weight 8. This set of codewords can be partitioned into 33 cyclic orbits...
    • ...For the 24-th row of the parity-check matrix, we use the all-one codeword: this codeword preserves the stopping set distribution of the 23 × 24 matrix, and is the only reasonable parity check of the [24, 12, 8] extended Golay code invariant under all affine permutations...
    • ...Fig. 2. Performance comparison for the [24, 12, 8] extended Golay code using �� ℓ, ℓ ∈ℱ 1, ℱ2, ℱ3...
    • ...NUMBER OF STOPPING SETS FOR THE [24, 12, 8] EXTENDED GOLAY CODE, �� ℓ, cog ℓ ∈ℱ �� , �� =1 ,..., 3...

    Thorsten Hehnet al. Multiple-bases belief-propagation decoding of high-density cyclic code...

    • ...In order to mitigate this problem, one may resort to the use of redundant parity-check matrices, i.e., matrices that contain more than n − k rows, although they have row-rank equal to n − k. Examples of the use of redundant parity-check matrices for signaling over the binary erasure channel can be found in [6], [4], [17], [18]...

    Stefan Laendneret al. The Trapping Redundancy of Linear Block Codes

    • ...Several authors [2], [3], [4], [5], [6] presen ted pioneering work on the binary erasure channel (BEC) and provided results on the number of redundant parity-check equations required to prevent certain decoder failures...

    Thorsten Hehnet al. MBBP for improved iterative channel decoding in 802.16e WiMAX systems

Sort by: