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 Transactions on Information Theory

Error-correcting codes for list decoding

Peter Eliaš

Published Jan 1, 1991• 180 citations
Publisher

Abstract

In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p>

DOI
10.1109/18.61123

Related papers

Improved Analysis of List Decoding and Its Application to Convolutional Codes and Turbo Codes

Chunlong Bai, Bartosz Mielczarek, Witold A. Krzymień +1 more

A list decoder generates a list of more than one codeword candidates, and decoding is erroneous if the transmitted codeword is not included in the list. This decoding strategy can be implemented in a system that employs an inner error correcting code and an outer error detecting code that is used to choose the correct codeword from the list. Probability of codeword error analysis for a linear block code with list decoding is typically based on the “worst case” lower bound on the effective weights of codewords for list decoding evaluated from the weight enumerating function of the code.

IEEE Transactions on Information Theory•Jan 23, 2007•10 citations

Error-correcting codes

Jacobus H. Lint, Gerard van der Geer

We shall not go into details concerning all the technical applications of error-correcting codes. These include satellite pictures, telephone messages via glass fibre using light, compact disc audio system. The idea is as follows. We consider “information” presented as a very long sequence of symbols from a finite set called the “alphabet”. In this course the alphabet will be a finite field IF q . In the sequence each symbol occurs with equal probability. This information is sent to a receiver over a so-called “noisy channel”. In the model that we consider there is a fixed (small) probability p e that a symbol, that is sent over the channel, is changed into one of the other symbols (again, all equally likely). Such an event is called a “symbol-error” and p e is the symbol-error probability. As a result a fraction p e of the transmitted symbols arrives incorrectly at the receiver end of the channel. The aim of coding theory is to lower the probability of error (considerably) at the expense of spending some of the transmission time or energy on redundant symbols. The idea is explained in one sentence as follows. When we read printed text we recognize a printing error in a word because in our vocabulary there is only one word that resembles (is “sufficiently close to”) the printed word.

Birkhäuser Basel eBooks•Jan 1, 1988•20 citations

On error correction with feedback under list decoding

Ofer Shayevitz

This work provides some preliminary results on the problem of error correction in the presence of noiseless feedback, where list-of-L decoding is allowed. The methods introduced by Berlekamp for the list-of-1 setting are generalized, and some basic finite-block constraints are described. These constraints are then combined to derive an upper bound on the asymptotically achievable rates for a large family of strategies, as a function of the maximal error fraction p and the list size L.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•1 citation

Codes

Edward F. Assmus, Jennifer D. Key

Introduction Error-correcting codes were introduced in the 1940s in order to implement a theorem of Shannon's [260] which guaranteed that virtually error-free communication could be obtained even over a noisy channel. The message to be communicated is first “encoded”, i.e. turned into a codeword, by adding "redundancy". The codeword is then sent through the channel and the received message is “decoded” by the receiver into a message resembling, as closely as possible, the original message. The degree of resemblance will depend on how good the code is in relation to the channel. The usual pictorial representation of this communication link is shown in the schematic diagram Figure 2.1. Here a message is first given by the source to the encoder that turns the message into a codeword, i.e. a string of letters from some alphabet, chosen according to the code used; the encoded message is then sent through the channel, where it may be subjected to noise and hence altered; this possibly-altered message, when it arrives at the decoder belonging to the receiver, is, first of all, equated with the most likely codeword, i.e. the one (should that exist) that, in a probabilistic sense depending on the channel, was probably sent; finally this “most likely” codeword is decoded and the message is passed on to the receiver. Example 2.1.1 Suppose we use an alphabet of just two symbols, 0 and 1, and we have only two messages, for example “no” corresponding to 0, and "yes” corresponding to 1. We wish to send the message “no”, and we add redundancy by simply repeating the message five times. Thus we encode the message as the codeword (00000). The channel interferes, perhaps, with the message and could, for example, change it to (01100). The decoder assesses the message and decides that of the two possible codewords, i.e. (00000) and (11111), the former is the more likely, and hence the message is decoded, correctly, as “no”. Notice that we have made several assumptions here: for example we have assumed that the probability of an error at any position in the word is less than, that each codeword is equally likely to be sent, and that the receiver is aware of the code used.

Cambridge University Press eBooks•Aug 28, 1992•0 citations

Error detection, correction and decoding

San Ling, Chaoping Xing

We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .

Cambridge University Press eBooks•Feb 12, 2004•0 citations

About the peculiarities of searching for Information Sets of Block-Permutation LDPC-Codes when Correcting Error Bursts

M. N. Isaeva, Andrei A. Ovchinnikov

Modern communication standards use error-correcting coding, especially LDPC codes. Various algorithms are used to decode them, including decoding by information sets. The algorithm for decoding over information sets has exponential complexity. Errors may occur on any communication channel when transmitting messages. Traditionally, independent errors are considered when researching decoding algorithms. However, in real systems, errors are grouped into bursts. This article discusses the probability of detecting information sets while correcting error bursts. Random matrices and block permutation matrices are considered. Graphs of the dependence of the probability of finding information sets on the number of positions that are considered when searching for information sets are given.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)•May 29, 2023•1 citation
In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p>
A list decoder generates a list of more than one codeword candidates, and decoding is erroneous if the transmitted codeword is not included in the list. This decoding strategy can be implemented in a system that employs an inner error correcting code and an outer error detecting code that is used to choose the correct codeword from the list. Probability of codeword error analysis for a linear block code with list decoding is typically based on the “worst case” lower bound on the effective weights of codewords for list decoding evaluated from the weight enumerating function of the code.
We shall not go into details concerning all the technical applications of error-correcting codes. These include satellite pictures, telephone messages via glass fibre using light, compact disc audio system. The idea is as follows. We consider “information” presented as a very long sequence of symbols from a finite set called the “alphabet”. In this course the alphabet will be a finite field IF q . In the sequence each symbol occurs with equal probability. This information is sent to a receiver over a so-called “noisy channel”. In the model that we consider there is a fixed (small) probability p e that a symbol, that is sent over the channel, is changed into one of the other symbols (again, all equally likely). Such an event is called a “symbol-error” and p e is the symbol-error probability. As a result a fraction p e of the transmitted symbols arrives incorrectly at the receiver end of the channel. The aim of coding theory is to lower the probability of error (considerably) at the expense of spending some of the transmission time or energy on redundant symbols. The idea is explained in one sentence as follows. When we read printed text we recognize a printing error in a word because in our vocabulary there is only one word that resembles (is “sufficiently close to”) the printed word.
Introduction Error-correcting codes were introduced in the 1940s in order to implement a theorem of Shannon's [260] which guaranteed that virtually error-free communication could be obtained even over a noisy channel. The message to be communicated is first “encoded”, i.e. turned into a codeword, by adding "redundancy". The codeword is then sent through the channel and the received message is “decoded” by the receiver into a message resembling, as closely as possible, the original message. The degree of resemblance will depend on how good the code is in relation to the channel. The usual pictorial representation of this communication link is shown in the schematic diagram Figure 2.1. Here a message is first given by the source to the encoder that turns the message into a codeword, i.e. a string of letters from some alphabet, chosen according to the code used; the encoded message is then sent through the channel, where it may be subjected to noise and hence altered; this possibly-altered message, when it arrives at the decoder belonging to the receiver, is, first of all, equated with the most likely codeword, i.e. the one (should that exist) that, in a probabilistic sense depending on the channel, was probably sent; finally this “most likely” codeword is decoded and the message is passed on to the receiver. Example 2.1.1 Suppose we use an alphabet of just two symbols, 0 and 1, and we have only two messages, for example “no” corresponding to 0, and "yes” corresponding to 1. We wish to send the message “no”, and we add redundancy by simply repeating the message five times. Thus we encode the message as the codeword (00000). The channel interferes, perhaps, with the message and could, for example, change it to (01100). The decoder assesses the message and decides that of the two possible codewords, i.e. (00000) and (11111), the former is the more likely, and hence the message is decoded, correctly, as “no”. Notice that we have made several assumptions here: for example we have assumed that the probability of an error at any position in the word is less than, that each codeword is equally likely to be sent, and that the receiver is aware of the code used.
We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .
Modern communication standards use error-correcting coding, especially LDPC codes. Various algorithms are used to decode them, including decoding by information sets. The algorithm for decoding over information sets has exponential complexity. Errors may occur on any communication channel when transmitting messages. Traditionally, independent errors are considered when researching decoding algorithms. However, in real systems, errors are grouped into bursts. This article discusses the probability of detecting information sets while correcting error bursts. Random matrices and block permutation matrices are considered. Graphs of the dependence of the probability of finding information sets on the number of positions that are considered when searching for information sets are given.