Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronics and Communications in Japan (Part III Fundamental Electronic Science)

Decoding algorithm for iterated codes correcting compound errors

Masazumi Kurihara

Published Jan 1, 2005• 0 citations
Publisher

Abstract

This paper discusses codes, and a decoding method, that can correct compound errors containing a mix of random and burst errors. Specifically, the paper provides a minimum compound distance that represents a compound error correcting capacity for iterated codes, proposes a compound error correcting decoding algorithm for the code, and demonstrates that the decoding algorithm is capable of correcting compound errors up to half the minimum compound distance of the code. The proposed decoding algorithm is a generalized decoding method in which the decoding method for iterated codes indicated by Reddy and Robinson is a particular case. By this generalization, the proposed decoding algorithm can correct compound errors that cannot be corrected by conventional decoding methods. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 89(1): 60–72, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20035

DOI
10.1002/ecjc.20035

Related papers

Generalized minimum distance iterative decoding of Tanner codes

Saejoon Kim

In this letter, we present a linear-time decoding algorithm for Tanner codes that can correct errors up to close to half the minimum distance of the code. The algorithm is a simple generalization to the iterative decoding algorithm of expander codes proposed by Skachek and Roth (2003).

IEEE Communications Letters•Aug 1, 2005•1 citation

Generalized minimum distance iterative decoding of expander codes

Vitaly Skachek, Ron M. Roth

Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.

IEEE Information Theory Workshop (ITW)•Mar 1, 2004•27 citations

On decoding iterated codes

Sudhakar M. Reddy

Algorithms to decode iterated codes when at least one of the "component codes" is majority decodable are given. The decoding algorithms allow the use of the decoders of the component codes and still make it possible to correct all error patterns guaranteed to be correctable by the minimum distance of the iterated code.

IEEE Transactions on Information Theory•Sep 1, 1970•33 citations

Decoding of linear codes for single error bursts correction based on the determination of certain events

Andrei A. Ovchinnikov, Вересова Алина Максимовна, Anna A. Fominykh

Introduction: In modern systems for communication, data storage and processing the error-correction capability of codes are estimated for memoryless channels. In real channels the noise is correlated, which leads to grouping error in bursts. A traditional method to fight this phenomenon is channel decorrelation, which does not allow developing of coding schemes, mostly utilizing the channel capacity. Thus the development of bursts decoding algorithms for arbitrary linear codes is the actual task. Purpose: To develop a single error burst decoding algorithm for linear codes, to estimate the decoding error probability and computational complexity. Results: Two approaches are proposed to burst error correction. The first one is based on combining the window sliding modification of well-known bit-flipping algorithm with preliminary analysis of the structure of parity check matrix. The second one is based on the recursive procedure of constructing the sequence of certain events which, in the worst case, performs the exhaustive search of error bursts, but in many cases the search may be significantly decreased by using the proposed heuristics. The proposed recursive decoding algorithm allows a guaranteed correction of any single error bursts within burst-correction capability of the code, and in many cases beyond the burst-correction capability. The complexity of this algorithm is significantly lower than that of a bit flipping algorithm if the parity-check matrix of the code is sparse enough. An alternative hybrid decoding algorithm is proposed utilizing the bit-flipping approach and showing the error probability and completion time comparable to the recursive algorithm, however, in this case the possibility of a guaranteed burst correction hardly can be proved. Practical relevance: The proposed decoding methods may be used in modern and perspective communication systems, allowing energy saving and increasing reliability of data transmission by better error performance and computational complexity.

Информационно-управляющие системы•Dec 27, 2022•10 citations

Reduced GMD decoding of concatenated codes

Jos H. Weber, Khaled Abdel-Ghaffar

We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.

Globecom•Nov 13, 2002•0 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, 2002•2 citations
This paper discusses codes, and a decoding method, that can correct compound errors containing a mix of random and burst errors. Specifically, the paper provides a minimum compound distance that represents a compound error correcting capacity for iterated codes, proposes a compound error correcting decoding algorithm for the code, and demonstrates that the decoding algorithm is capable of correcting compound errors up to half the minimum compound distance of the code. The proposed decoding algorithm is a generalized decoding method in which the decoding method for iterated codes indicated by Reddy and Robinson is a particular case. By this generalization, the proposed decoding algorithm can correct compound errors that cannot be corrected by conventional decoding methods. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 89(1): 60–72, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20035
Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.
Introduction: In modern systems for communication, data storage and processing the error-correction capability of codes are estimated for memoryless channels. In real channels the noise is correlated, which leads to grouping error in bursts. A traditional method to fight this phenomenon is channel decorrelation, which does not allow developing of coding schemes, mostly utilizing the channel capacity. Thus the development of bursts decoding algorithms for arbitrary linear codes is the actual task. Purpose: To develop a single error burst decoding algorithm for linear codes, to estimate the decoding error probability and computational complexity. Results: Two approaches are proposed to burst error correction. The first one is based on combining the window sliding modification of well-known bit-flipping algorithm with preliminary analysis of the structure of parity check matrix. The second one is based on the recursive procedure of constructing the sequence of certain events which, in the worst case, performs the exhaustive search of error bursts, but in many cases the search may be significantly decreased by using the proposed heuristics. The proposed recursive decoding algorithm allows a guaranteed correction of any single error bursts within burst-correction capability of the code, and in many cases beyond the burst-correction capability. The complexity of this algorithm is significantly lower than that of a bit flipping algorithm if the parity-check matrix of the code is sparse enough. An alternative hybrid decoding algorithm is proposed utilizing the bit-flipping approach and showing the error probability and completion time comparable to the recursive algorithm, however, in this case the possibility of a guaranteed burst correction hardly can be proved. Practical relevance: The proposed decoding methods may be used in modern and perspective communication systems, allowing energy saving and increasing reliability of data transmission by better error performance and computational complexity.
We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.
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.