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:2305.06691 · IEEE International Symposium on Information Theory (ISIT)

Correcting One Error in Non-Binary Channels with Feedback

Ilya Vorobyev, В. В. Лебедев, Alexey Lebedev

Published Jun 25, 2023• 3 citations
arXivHTMLPDF

Abstract

In this paper, the problem of correction of a single error in q-ary symmetric channel with noiseless feedback is considered. We propose an algorithm to construct codes with feedback inductively. For all prime power q we prove that two instances of feedback are sufficient to transmit over the q-ary symmetric channel the same number of messages as in the case of complete feedback. Our other contribution is the construction of codes with one-time feedback with the same parameters as Hamming codes for q that is not a prime power. We also construct single-error-correcting codes with one-time feedback of size qn−2for arbitrary q and n ≤ q + 1, which can be seen as an analog for Reed-Solomon codes.

DOI
10.1109/isit54713.2023.10207004

Related papers

Non¿binary error correcting codes with noiseless feedback, localized errors, or both

Rudolf Ahlswede, Christian Deppe, Vladimir Lebedev

The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•22 citations

Good error-detection codes satisfying the expurgated bound

Takeshi Hashimoto

A q-ary (n, k) linear code is said to be proper if, as an error-detection code, the probability of undetectable error P/sub ud/ satisfies P/sub ud//spl les/q/sup -(n-k)/ for completely symmetric channels. We show that a proper code, as an error-correction code, satisfies the expurgated bound on the decoding error probability for a class of channels with the associated Bhattacharyya distance being completely symmetric. Known results on the undetectable error probability then immediately imply that the expurgated exponent is satisfied exactly by, for example, all the binary perfect codes, binary first-order Reed-Muller codes, binary (extended) Hamming code, binary 2-error correcting primitive BCH code, and all the maximum distance separable (MDS) codes, and asymptotically by some class of the binary t-error-correcting primitive BCH codes.>

IEEE Transactions on Information Theory•Jan 1, 1995•5 citations

Finite-blocklength classical communication over the quantum erasure channel with and without classical feedback

Mark M. Wilde

We determine the optimal success probability for transmitting a fixed number of classical messages through a finite number of uses of the quantum erasure channel, assisted by noiseless classical feedback and without initial shared entanglement. For an input dimension $d$, an erasure probability $p$, a blocklength $n$, and $M$ equiprobable messages, the optimal success probability is equal to $E[\min\{1,d^K/M\}]$, where $K$ is binomial with parameters $n$ and $1-p$. The converse allows arbitrary adaptive quantum encoders, quantum memories, and receiver instruments. Its main ingredient is an elementary dimension bound for noiseless quantum communication with classical feedback, proved by fixing the classical controls without conditioning the sender's state on the observed transcript. A classical protocol that transmits the base-$d$ digits of an integer representing the message, repeating each digit until the receiver acknowledges its reception or the prescribed blocklength is reached, attains the bound for every integer $M$. We also establish a relative-majorization property of erasure-channel outputs and exactly evaluate a hypothesis-testing converse, recovering the same numerical bound without feedback. That converse need not be achievable without feedback: four uses of the qubit erasure channel and four messages give a strict gap. A product-state code employing tetrahedral qubit states nevertheless outperforms every classical binary erasure code with these parameters. We give an explicit message-size formula and show that the bounded-remainder normal approximation and the average-success strong-converse exponent are unchanged without feedback. We also determine the feedback-assisted error exponent below capacity, prove that it agrees with the no-feedback exponent above a critical rate, and give no-feedback bounds at lower rates.

quant-pharXiv:2610.00440•Oct 1, 2026•0 citations

Asymptotically dense nonbinary codes correcting a constant number of localized errors [Manuskript]

Rudolf Ahlswede, Leonid Alexandrovich Bassalygo, M.S. Pinsker

The binary case was studied in [1], but the method used there doesn't give the tight answer for nonbinary cases and we presented in [2] another method for the corresponding result.Here we formulate the main theorem and prove the auxiliary statements used in [2].During the transmission of q-ary words of length n over the channel at most t errors occur, and the encoder knows the set E of t positions, where these errors are possible.The decoder doesn't know anything about these positions.Let E t = E | E ⊆ {1, 2, . . ., n}, |E| = t be the set of all subsets from {1, 2, . . ., n} of size t and let M be a set of messages (|M| = M ) .A code word x(m, E) depends not only on the message m ∈ M but also on the configuration of possible errors E .So there exists the natural correspondence between the message m ∈ M and the list of code words E∈E t x(m, E) , which we use for the transmission of this message.Thus the code X for the set of messages M represents a collection of M lists E∈E t {x(m, E)}, m ∈ M .Sinde we can use the same word for different configurations, the size of a list can be essentially smaller than the size of the setLet us define the cylinder C(a, A) with the base a = (a, . . ., a n ) and the support A A ⊆ {1, 2, . . ., n} as the set of words (y 1 , . . ., y n ) with y i = a i , if i / ∈ A .It is clear that the size of the cylinder C(a, A) is equal to q |A| and the number of different cylinders with the same support A is equal to q n-|A| .As a result of the transmission of the codeword x(m, E) every word of C x(m, E), E can appear as output of the channel.The code X corrects t localized errors, if the decoder can correctly recover every message m ∈ M .The following condition is necessary and sufficient for it:

Comptes Rendus De L Academie Bulgare Des Sciences•Jan 1, 1993•0 citations

On error correction with errors in both the channel and syndrome

Serge G. Vladut, Grigory A. Kabatiansky, V. V. Lomakov

We address the problem of error correction by linear block codes under the assumption that the syndrome of a received vector is found with errors. We propose a construction of parity-check matrices which allow to solve the syndrome equation even with an erroneous syndrome, in particular, parity-check matrices with minimum redundancy, which are analogs of Reed-Solomon codes for this problem. We also establish analogs of classical coding theory bounds, namely the Hamming, Singleton, and Gilbert-Varshamov bounds. We show that the new problem can be considered as a generalization of the well-known Ulam’s problem on searching with a lie and as a discrete analog of the compressed sensing problem.

Problems of Information Transmission•Apr 1, 2015•11 citations

Linear Binary Codes Correcting One or More Errors

Timofei Izhitskii

This paper examines linear binary codes capable of correcting one or more errors. For the single-error-correcting case, it is shown that the Hamming bound is achieved by a constructive method, and an exact expression for the minimal codeword length is derived. For the general case, a simple lower bound for the parameters of linear codes is derived from an analysis of the coset structure.

arXiv:2512.12591•Dec 14, 2025•0 citations
In this paper, the problem of correction of a single error in q-ary symmetric channel with noiseless feedback is considered. We propose an algorithm to construct codes with feedback inductively. For all prime power q we prove that two instances of feedback are sufficient to transmit over the q-ary symmetric channel the same number of messages as in the case of complete feedback. Our other contribution is the construction of codes with one-time feedback with the same parameters as Hamming codes for q that is not a prime power. We also construct single-error-correcting codes with one-time feedback of size qn−2for arbitrary q and n ≤ q + 1, which can be seen as an analog for Reed-Solomon codes.
The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors
A q-ary (n, k) linear code is said to be proper if, as an error-detection code, the probability of undetectable error P/sub ud/ satisfies P/sub ud//spl les/q/sup -(n-k)/ for completely symmetric channels. We show that a proper code, as an error-correction code, satisfies the expurgated bound on the decoding error probability for a class of channels with the associated Bhattacharyya distance being completely symmetric. Known results on the undetectable error probability then immediately imply that the expurgated exponent is satisfied exactly by, for example, all the binary perfect codes, binary first-order Reed-Muller codes, binary (extended) Hamming code, binary 2-error correcting primitive BCH code, and all the maximum distance separable (MDS) codes, and asymptotically by some class of the binary t-error-correcting primitive BCH codes.>
We determine the optimal success probability for transmitting a fixed number of classical messages through a finite number of uses of the quantum erasure channel, assisted by noiseless classical feedback and without initial shared entanglement. For an input dimension ddd, an erasure probability ppp, a blocklength nnn, and MMM equiprobable messages, the optimal success probability is equal to E[min⁡{1,dK/M}]E[\min\{1,d^K/M\}]E[min{1,dK/M}], where KKK is binomial with parameters nnn and 1−p1-p1−p. The converse allows arbitrary adaptive quantum encoders, quantum memories, and receiver instruments. Its main ingredient is an elementary dimension bound for noiseless quantum communication with classical feedback, proved by fixing the classical controls without conditioning the sender's state on the observed transcript. A classical protocol that transmits the base-ddd digits of an integer representing the message, repeating each digit until the receiver acknowledges its reception or the prescribed blocklength is reached, attains the bound for every integer MMM. We also establish a relative-majorization property of erasure-channel outputs and exactly evaluate a hypothesis-testing converse, recovering the same numerical bound without feedback. That converse need not be achievable without feedback: four uses of the qubit erasure channel and four messages give a strict gap. A product-state code employing tetrahedral qubit states nevertheless outperforms every classical binary erasure code with these parameters. We give an explicit message-size formula and show that the bounded-remainder normal approximation and the average-success strong-converse exponent are unchanged without feedback. We also determine the feedback-assisted error exponent below capacity, prove that it agrees with the no-feedback exponent above a critical rate, and give no-feedback bounds at lower rates.
The binary case was studied in [1], but the method used there doesn't give the tight answer for nonbinary cases and we presented in [2] another method for the corresponding result.Here we formulate the main theorem and prove the auxiliary statements used in [2].During the transmission of q-ary words of length n over the channel at most t errors occur, and the encoder knows the set E of t positions, where these errors are possible.The decoder doesn't know anything about these positions.Let E t = E | E ⊆ {1, 2, . . ., n}, |E| = t be the set of all subsets from {1, 2, . . ., n} of size t and let M be a set of messages (|M| = M ) .A code word x(m, E) depends not only on the message m ∈ M but also on the configuration of possible errors E .So there exists the natural correspondence between the message m ∈ M and the list of code words E∈E t x(m, E) , which we use for the transmission of this message.Thus the code X for the set of messages M represents a collection of M lists E∈E t {x(m, E)}, m ∈ M .Sinde we can use the same word for different configurations, the size of a list can be essentially smaller than the size of the setLet us define the cylinder C(a, A) with the base a = (a, . . ., a n ) and the support A A ⊆ {1, 2, . . ., n} as the set of words (y 1 , . . ., y n ) with y i = a i , if i / ∈ A .It is clear that the size of the cylinder C(a, A) is equal to q |A| and the number of different cylinders with the same support A is equal to q n-|A| .As a result of the transmission of the codeword x(m, E) every word of C x(m, E), E can appear as output of the channel.The code X corrects t localized errors, if the decoder can correctly recover every message m ∈ M .The following condition is necessary and sufficient for it:
We address the problem of error correction by linear block codes under the assumption that the syndrome of a received vector is found with errors. We propose a construction of parity-check matrices which allow to solve the syndrome equation even with an erroneous syndrome, in particular, parity-check matrices with minimum redundancy, which are analogs of Reed-Solomon codes for this problem. We also establish analogs of classical coding theory bounds, namely the Hamming, Singleton, and Gilbert-Varshamov bounds. We show that the new problem can be considered as a generalization of the well-known Ulam’s problem on searching with a lie and as a discrete analog of the compressed sensing problem.