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

IEEE International Symposium on Information Theory (ISIT)

Polynomial of correctable patterns of product codes

Nicolas Sendrier

Published Dec 17, 2002• 0 citations
Publisher

Abstract

Product codes have a poor minimum distance, but an efficient low-complexity decoding algorithm. To measure the performance of a decoder, like Reddy-Robinson's for product codes, which decode error patterns beyond half the minimum distance, we use the notion of equivalent diameter of the decoding region [4]. We produce here a bound for the performance of product code which is, for the considered example, far below the simulated performance but still above the performance of known BCH codes with same parameters.>

DOI
10.1109/isit.1994.394985

Related papers

Concatenated Codes

Ron M. Roth

In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.

Cambridge University Press eBooks•Feb 23, 2006•0 citations

The Polynomial of correctable 2 Concatenated codes patterns of concatenated codes Let B(n

Nicolas Seiidrier

The polynomial of correctable patterns is defined In [l] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can be defined as well ([5] aid (61) These polynomials allow a compact representation of a decodiilg alient to compute the coriection probabillty and ability thiougli a memoryless symetric channel. Our purpose heie is to compute the polynomials of correctable patThese results are geneialised in [5] and [SI for erasure channels. terns of concatenated codes for dlffeient decoding algorithms. I) We give the weight distribution of the erior patterns correctable by the standard decoding algorithm. * We give bounds for the weight distribution of the error patterns correct able by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide to evaluate the standard algorithm. It will also give a with precision the performances of the Block-Zyablov decoding algorithm which needed, up to llow, a (much more expensive) simulation. ill compute the decoding performances of the rdstrom-Robinson ([4, p. 731) inlier code, and a Reed-Solomon (255,223,33) outer code over F2~6.

•Jan 1, 1992•0 citations

DECODING OF MATRIX-PRODUCT CODES

Fernando Hernando, Diego Ruano

We propose a decoding algorithm for the (u | u + v)-construction that decodes up to half of the minimum distance of the linear code. We extend this algorithm for a class of matrix-product codes in two different ways. In some cases, one can decode beyond the error-correction capability of the code.

arXiv:1107.1529•Journal of Algebra and Its Applications•Sep 1, 2012•29 citations

The Polynomial of correctable patterns of concatenated codes

Nicolas Sendrier

The polynomial of correctable patterns is defined in [1] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can redefined as well ([5] and [6]). These polynomials allow a compact representation of a decoding algorithm which is sufficient to compute the correction probability and the miscorrection probability through a memoryless symetric channel. These results are generalized in [5] and [6] for erasure channels. Our purpose here is to compute the polynomials of correctable patterns of concatenated codes for different decoding algorithms. We give the weight distribution of the error patterns correctable by the standard decoding algorithm. We give bounds for the weight distribution of the error patterns correctable by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide an efficient way to evaluate the standard algorithm. It will also give a way to evaluate with precision the performances of the Block- Zyablov decoding algorithm which needed, up to now, a (much more expensive) simulation. As an example, we will compute the decoding performances of the concatenation of the Nordstrom-Robinson ([4, p. 73]) inner code, and a Reed-Solomon (255,223,33) outer code over F/sub 256/.

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•0 citations

A new iterative decoder for product codes

K Kapustin Alexey, Iitp Ras, Zyablov Victor +2 more

The most popular decoder for product codes is an iterative decoder. It has low complexity and can correct many errors in average case, but it also has an uncorrectable errors of weight equal to one quoter code distance. To overcome this limitation we propose a new decoder algorithm, that utilizes iterative decoder, but has better error correction efficiency at low error rates. Thecomputer simulation showed that the increase in error correction efficiency is larger for high-rate codes.

•Jan 1, 2014•3 citations

Bounded-distance soft decision decoding of binary product codes

Ofer Amrani, Yair Be'ery

A two-step sub-optimal algorithm for decoding binary product codes is discussed. This algorithm realizes at least half the minimum Euclidean distance of the code. The fundamental geometric properties associated with the algorithm are investigated, and bounds on the number of nearest neighbors are derived. This investigation also results with an improved algorithm which achieves the minimum effective error coefficient, the number of minimum-weight codewords in the product code.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•5 citations
Product codes have a poor minimum distance, but an efficient low-complexity decoding algorithm. To measure the performance of a decoder, like Reddy-Robinson's for product codes, which decode error patterns beyond half the minimum distance, we use the notion of equivalent diameter of the decoding region [4]. We produce here a bound for the performance of product code which is, for the considered example, far below the simulated performance but still above the performance of known BCH codes with same parameters.>
In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.
The polynomial of correctable patterns is defined In [l] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can be defined as well ([5] aid (61) These polynomials allow a compact representation of a decodiilg alient to compute the coriection probabillty and ability thiougli a memoryless symetric channel. Our purpose heie is to compute the polynomials of correctable patThese results are geneialised in [5] and [SI for erasure channels. terns of concatenated codes for dlffeient decoding algorithms. I) We give the weight distribution of the erior patterns correctable by the standard decoding algorithm. * We give bounds for the weight distribution of the error patterns correct able by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide to evaluate the standard algorithm. It will also give a with precision the performances of the Block-Zyablov decoding algorithm which needed, up to llow, a (much more expensive) simulation. ill compute the decoding performances of the rdstrom-Robinson ([4, p. 731) inlier code, and a Reed-Solomon (255,223,33) outer code over F2~6.
The polynomial of correctable patterns is defined in [1] as the weight enumerator of the set of error patterns correctable by a given decoding algorithm. The polynomials of uncorrectable and miscorrected patterns can redefined as well ([5] and [6]). These polynomials allow a compact representation of a decoding algorithm which is sufficient to compute the correction probability and the miscorrection probability through a memoryless symetric channel. These results are generalized in [5] and [6] for erasure channels. Our purpose here is to compute the polynomials of correctable patterns of concatenated codes for different decoding algorithms. We give the weight distribution of the error patterns correctable by the standard decoding algorithm. We give bounds for the weight distribution of the error patterns correctable by Block- Zyablov algorithm. This new method for evaluating concatenated codes will thus provide an efficient way to evaluate the standard algorithm. It will also give a way to evaluate with precision the performances of the Block- Zyablov decoding algorithm which needed, up to now, a (much more expensive) simulation. As an example, we will compute the decoding performances of the concatenation of the Nordstrom-Robinson ([4, p. 73]) inner code, and a Reed-Solomon (255,223,33) outer code over F/sub 256/.