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

arXiv:1701.07112

Attaining Capacity with Algebraic Geometry Codes through the $(U|U+V)$ Construction and Koetter-Vardy Soft Decoding

Irene Márquez-Corbella, Jean–Pierre Tillich

Published Jan 24, 2017• 0 citations
arXivHTMLPDF

Abstract

In this paper we show how to attain the capacity of discrete symmetric channels with polynomial time decoding complexity by considering iterated $(U|U+V)$ constructions with Reed-Solomon code or algebraic geometry code components. These codes are decoded with a recursive computation of the {\em a posteriori} probabilities of the code symbols together with the Koetter-Vardy soft decoder used for decoding the code components in polynomial time. We show that when the number of levels of the iterated $(U|U+V)$ construction tends to infinity, we attain the capacity of any discrete symmetric channel in this way. This result follows from the polarization theorem together with a simple lemma explaining how the Koetter-Vardy decoder behaves for Reed-Solomon codes of rate close to $1$. However, even if this way of attaining the capacity of a symmetric channel is essentially the Arıkan polarization theorem, there are some differences with standard polar codes. Indeed, with this strategy we can operate succesfully close to channel capacity even with a small number of levels of the iterated $(U|U+V)$ construction and the probability of error decays quasi-exponentially with the codelength in such a case (i.e. exponentially if we forget about the logarithmic terms in the exponent). We can even improve on this result by considering the algebraic geometry codes constructed in \cite{TVZ82}. In such a case, the probability of error decays exponentially in the codelength for any rate below the capacity of the channel. Moreover, when comparing this strategy to Reed-Solomon codes (or more generally algebraic geometry codes) decoded with the Koetter-Vardy decoding algorithm, it does not only improve the noise level that the code can tolerate, it also results in a significant complexity gain.

DOI
10.48550/arxiv.1701.07112

Related papers

Attaining capacity with iterated (U|U + V) codes based on AG codes and Koetter-Vardy soft decoding

Irene Márquez-Corbella, Jean–Pierre Tillich

In this paper we show how to attain the capacity of discrete symmetric channels with polynomial time decoding complexity by considering iterated (U | U + V) constructions with algebraic geometry (AG) code components. These codes are decoded with a recursive computation of the a posteriori probabilities of the code symbols together with decoding the AG components with the Koetter-Vardy algorithm. We show that, when the number of levels of the iterated (U | U + V) construction tends to infinity, we attain the capacity of any discrete symmetric channel. Moreover the error probability decays quasi-exponentially with the codelength in the case of Reed-Solomon code constituents and exponentially with Tsfasman-Vladuts-Zink code constituents.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•6 citations

Using concatenated algebraic geometry codes in channel polarization

Abdulla Eid, Iwan Duursma

Polar codes were introduced by Arikan in 2008 and are the first family of error-correcting codes achieving the symmetric capacity of an arbitrary binary-input discrete memoryless channel under low complexity encoding and using an efficient successive cancellation decoding strategy. Recently, non-binary polar codes have been studied, in which one can use different algebraic geometry codes to achieve better error decoding probability. In this paper, we study the performance of binary polar codes that are obtained from non-binary algebraic geometry codes using concatenation. For binary polar codes (i.e. binary kernels) of a given length $n$, we compare numerically the use of short algebraic geometry codes over large fields versus long algebraic geometry codes over small fields. We find that for each $n$ there is an optimal choice. For binary kernels of size up to $n \leq 1,800$ a concatenated Reed-Solomon code outperforms other choices. For larger kernel sizes concatenated Hermitian codes or Suzuki codes will do better.

arXiv:1310.7159•Oct 27, 2013•3 citations

Polar Codes: Characterization of Exponent, Bounds, and Constructions

Satish Babu Korada, Eren Şaşoğlu, Rudiger L. Urbanke

Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the $2 \times 2$ matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of $\frac12$, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding $\frac12$. We first show that any $\ell \times \ell$ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding $\frac12$. Further, we give a general construction based on BCH codes which for large $n$ achieves exponents arbitrarily close to 1 and which exceeds $\frac12$ for size 16.

arXiv:0901.0536•Jan 5, 2009•30 citations

Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes

Ryuhei Mori, Toshiyuki Tanaka

Polar codes, introduced by Arıkan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.

arXiv:1007.3661•IEEE Information Theory Workshop (ITW)•Aug 1, 2010•94 citations

Quantum Advantage from Soft Decoders

André Chailloux, Jean–Pierre Tillich

In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called Decoded Quantum Interferometry that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the $ISIS_{\infty}$ problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy [KV03]. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.

arXiv:2411.12553•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•4 citations

Decoding concatenated codes using soft information

Venkatesan Guruswami, Madhu Sudan

We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.

IEEE Conference on Computational Complexity (CCC)•Jun 25, 2003•16 citations
Attaining Capacity with Algebraic Geometry Codes through the (U∣U+V)(U|U+V)(U∣U+V) Construction and Koetter-Vardy Soft Decoding
In this paper we show how to attain the capacity of discrete symmetric channels with polynomial time decoding complexity by considering iterated (U∣U+V)(U|U+V)(U∣U+V) constructions with Reed-Solomon code or algebraic geometry code components. These codes are decoded with a recursive computation of the {\em a posteriori} probabilities of the code symbols together with the Koetter-Vardy soft decoder used for decoding the code components in polynomial time. We show that when the number of levels of the iterated (U∣U+V)(U|U+V)(U∣U+V) construction tends to infinity, we attain the capacity of any discrete symmetric channel in this way. This result follows from the polarization theorem together with a simple lemma explaining how the Koetter-Vardy decoder behaves for Reed-Solomon codes of rate close to 111. However, even if this way of attaining the capacity of a symmetric channel is essentially the Arıkan polarization theorem, there are some differences with standard polar codes. Indeed, with this strategy we can operate succesfully close to channel capacity even with a small number of levels of the iterated (U∣U+V)(U|U+V)(U∣U+V) construction and the probability of error decays quasi-exponentially with the codelength in such a case (i.e. exponentially if we forget about the logarithmic terms in the exponent). We can even improve on this result by considering the algebraic geometry codes constructed in \cite{TVZ82}. In such a case, the probability of error decays exponentially in the codelength for any rate below the capacity of the channel. Moreover, when comparing this strategy to Reed-Solomon codes (or more generally algebraic geometry codes) decoded with the Koetter-Vardy decoding algorithm, it does not only improve the noise level that the code can tolerate, it also results in a significant complexity gain.
In this paper we show how to attain the capacity of discrete symmetric channels with polynomial time decoding complexity by considering iterated (U | U + V) constructions with algebraic geometry (AG) code components. These codes are decoded with a recursive computation of the a posteriori probabilities of the code symbols together with decoding the AG components with the Koetter-Vardy algorithm. We show that, when the number of levels of the iterated (U | U + V) construction tends to infinity, we attain the capacity of any discrete symmetric channel. Moreover the error probability decays quasi-exponentially with the codelength in the case of Reed-Solomon code constituents and exponentially with Tsfasman-Vladuts-Zink code constituents.
Polar codes were introduced by Arikan in 2008 and are the first family of error-correcting codes achieving the symmetric capacity of an arbitrary binary-input discrete memoryless channel under low complexity encoding and using an efficient successive cancellation decoding strategy. Recently, non-binary polar codes have been studied, in which one can use different algebraic geometry codes to achieve better error decoding probability. In this paper, we study the performance of binary polar codes that are obtained from non-binary algebraic geometry codes using concatenation. For binary polar codes (i.e. binary kernels) of a given length nnn, we compare numerically the use of short algebraic geometry codes over large fields versus long algebraic geometry codes over small fields. We find that for each nnn there is an optimal choice. For binary kernels of size up to n≤1,800n \leq 1,800n≤1,800 a concatenated Reed-Solomon code outperforms other choices. For larger kernel sizes concatenated Hermitian codes or Suzuki codes will do better.
Polar codes were recently introduced by Arıkan. They achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the 2×22 \times 22×2 matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was shown by Arıkan and Telatar that this construction achieves an error exponent of 12\frac1221​, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding 12\frac1221​. We first show that any ℓ×ℓ\ell \times \ellℓ×ℓ matrix none of whose column permutations is upper triangular polarizes symmetric channels. We then characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding 12\frac1221​. Further, we give a general construction based on BCH codes which for large nnn achieves exponents arbitrarily close to 1 and which exceeds 12\frac1221​ for size 16.
Polar codes, introduced by Arıkan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.
In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called Decoded Quantum Interferometry that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the ISIS∞ISIS_{\infty}ISIS∞​ problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy [KV03]. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.
We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.