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)

List decoding of product codes by the MinSum algorithm

Alexander Barg, Gilles Zémor

Published Jul 1, 2011• 1 citation
Publisher

Abstract

We introduce a MinSum-based list decoder for product codes and analyze its performance. We show that it can guarantee successful list decoding for decoding radii that lie above half the code's minimum distance.
DOI
10.1109/isit.2011.6033741

Related papers

List decoding of concatenated codes: improved performance estimates

Alexander Barg, Andrew McGregor

An improved bound is proved on the list-decoding radius of a concatenated code relying upon a combination of (soft-decision) algebraic list decoding and generalized minimum distance (GMD) decoding in the outer level. This bound is further improved if the inner code is a random linear code.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•0 citations

Polynomial of correctable patterns of product codes

Nicolas Sendrier

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.>

IEEE International Symposium on Information Theory (ISIT)•Dec 17, 2002•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•26 citations

Generalized minimum distance decoding algorithms for Qary output channels (Corresp.)

Christopher C.H. Yu, Daniel J. Costello

A new condition for a generalized minimum distance decoder to guarantee correct decoding is developed. Based on this condition, decoding algorithms for block codes, product codes, and completely orthogonalizable codes onQary output channels are presented. The results of computer simulations comparing the performance of these decoding algorithms with several other soft-decision decoding algorithma are also presented.

IEEE Transactions on Information Theory•Mar 1, 1980•23 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•6 citations

Scaling Exponent of List Decoders with Applications to Polar Codes

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed and the trade-off between block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under $\rm MAP$ decoding with list size $L$ for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under $\rm MAP$ decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.

arXiv:1304.5220•Apr 18, 2013•3 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.>
Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed and the trade-off between block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under MAP\rm MAPMAP decoding with list size LLL for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under MAP\rm MAPMAP decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.