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

List decoding for noisy channels

Peter Eliaš

Published Jan 1, 1957• 337 citations
OpenAlex

Related papers

Weight distribution bounds to relate minimum distance, list decoding, and symmetric channel performance

Donald Kougang-Yombi, Jan Hązła

We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a $q$-ary code of relative distance $δ$ has vanishing error probability on the symmetric channel up to the Johnson radius $J_q(δ)$. We improve upon this bound in the case of linear codes, for a range $δ$, for $q\ge 4$. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.

arXiv:2604.02994•Apr 3, 2026•1 citation

Analysis of List Decoding for Convolutional Codes

Kamil Sh. Zigangirov, Harro Osthoff

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

Error-correcting codes for list decoding

Peter Eliaš

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>

IEEE Transactions on Information Theory•Jan 1, 1991•184 citations

Stochastic Decoding of Error-Correcting Codes

François Leduc-Primeau, Saied Hemati, Vincent Gaudet +1 more

Springer eBooks•Jan 1, 2019•1 citation

Channel capacities of classical and quantum list decoding

Masahito Hayashi

We focus on classical and quantum list decoding. The capacity of list decoding was obtained by Nishimura in the case when the number of list does not increase exponentially. However, the capacity of the exponential-list case is open even in the classical case while its converse part was obtained by Nishimura. We derive the channel capacities in the classical and quantum case with an exponentially increasing list. The converse part of the quantum case is obtained by modifying Nagaoka's simple proof for strong converse theorem for channel capacity. The direct part is derived by a quite simple argument.

arXiv:quant-ph/0603031•Mar 4, 2006•5 citations

On superdense coding with noisy channels

Z. Shadman, Hermann Kampermann, Dagmar Bruß

Verhandlungen der Deutschen Physikalischen Gesellschaft•Jan 1, 2009•0 citations
We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a qqq-ary code of relative distance δδδ has vanishing error probability on the symmetric channel up to the Johnson radius Jq(δ)J_q(δ)Jq​(δ). We improve upon this bound in the case of linear codes, for a range δδδ, for q≥4q\ge 4q≥4. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.
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>
We focus on classical and quantum list decoding. The capacity of list decoding was obtained by Nishimura in the case when the number of list does not increase exponentially. However, the capacity of the exponential-list case is open even in the classical case while its converse part was obtained by Nishimura. We derive the channel capacities in the classical and quantum case with an exponentially increasing list. The converse part of the quantum case is obtained by modifying Nagaoka's simple proof for strong converse theorem for channel capacity. The direct part is derived by a quite simple argument.