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

Comptes Rendus De L Academie Bulgare Des Sciences

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

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

Published Jan 1, 1993• 0 citations
OpenAlex

Abstract

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:

Related papers

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

On decoding linear error-correcting codes--I

Neal Zierler

A technique is described for finding simply computable numerical-valued functions of a received binary word whose value indicates where errors in transmission have occurred. Although it seems that a certain condition must usually be fulfilled for such functions to exist, or for our method to constitute an efficient procedure for finding them, there is, on the one hand, a strong tendency for "good" codes to satisfy the condition, while, on the other, it appears to be straightforward to construct codes which are good for a specified channel and also fulfill the condition. An advantage of the resulting decoding procedure is that it corrects and detects all possible errors; more precisely, if a worduis received and the coset\bar{u}to whichubelongs has a unique leadere, the procedure concludes thatu + ewas sent, while ifuhas no unique leader, that fact, along with the weight of\bar{u}(and sometimes a little more) can be indicated. The ideas and techniques are illustrated by the construction of decoding procedures for the perfect (23, 12) three-error-correcting code.

IEEE Transactions on Information Theory•Sep 1, 1960•12 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•180 citations

List Message Passing Decoding of Non-binary Low-Density Parity-Check Codes

Emna Ben Yacoub

A decoding algorithm for $q$ -ary low-density parity-check codes over the $q$ -ary symmetric channel is introduced. The exchanged messages are lists of symbols from $\mathbb{F}_{q}$ . A density evolution analysis for maximum list sizes 1 and 2 is developed. Thresholds for selected regular low-density parity-check code ensembles are computed showing gains with respect to a similar algorithm in the literature. Finite-length simulation results confirm the asymptotic analysis.

•Jan 1, 2021•3 citations

Nonbinary codeword-stabilized quantum codes

Xie Chen, Bei Zeng, Isaac L. Chuang

The codeword-stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [see A. Cross et al., e-print arXiv:0708.1021], but only for binary states. Here we generalize the CWS framework to the nonbinary case (of both prime and nonprime dimensions) and map the search for nonbinary quantum codes to a corresponding search problem for classical nonbinary codes with specific error patterns. We show that while the additivity properties of nonbinary CWS codes are similar to the binary case, the structural properties of the nonbinary codes differ substantially from the binary case, even for prime dimensions. In particular, we identify specific structure patterns of stabilizer groups, based on which efficient constructions might be possible for codes that encode more dimensions than any stabilizer codes of the same length and distance; similar methods cannot be applied in the binary case. Understanding of these structural properties can help prune the search space and facilitate the identification of good nonbinary CWS codes.

arXiv:0808.3086•Physical Review A•Dec 8, 2008•31 citations
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:
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 .
A technique is described for finding simply computable numerical-valued functions of a received binary word whose value indicates where errors in transmission have occurred. Although it seems that a certain condition must usually be fulfilled for such functions to exist, or for our method to constitute an efficient procedure for finding them, there is, on the one hand, a strong tendency for "good" codes to satisfy the condition, while, on the other, it appears to be straightforward to construct codes which are good for a specified channel and also fulfill the condition. An advantage of the resulting decoding procedure is that it corrects and detects all possible errors; more precisely, if a worduis received and the coset\bar{u}to whichubelongs has a unique leadere, the procedure concludes thatu + ewas sent, while ifuhas no unique leader, that fact, along with the weight of\bar{u}(and sometimes a little more) can be indicated. The ideas and techniques are illustrated by the construction of decoding procedures for the perfect (23, 12) three-error-correcting code.
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 decoding algorithm for qqq -ary low-density parity-check codes over the qqq -ary symmetric channel is introduced. The exchanged messages are lists of symbols from Fq\mathbb{F}_{q}Fq​ . A density evolution analysis for maximum list sizes 1 and 2 is developed. Thresholds for selected regular low-density parity-check code ensembles are computed showing gains with respect to a similar algorithm in the literature. Finite-length simulation results confirm the asymptotic analysis.
The codeword-stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [see A. Cross et al., e-print arXiv:0708.1021], but only for binary states. Here we generalize the CWS framework to the nonbinary case (of both prime and nonprime dimensions) and map the search for nonbinary quantum codes to a corresponding search problem for classical nonbinary codes with specific error patterns. We show that while the additivity properties of nonbinary CWS codes are similar to the binary case, the structural properties of the nonbinary codes differ substantially from the binary case, even for prime dimensions. In particular, we identify specific structure patterns of stabilizer groups, based on which efficient constructions might be possible for codes that encode more dimensions than any stabilizer codes of the same length and distance; similar methods cannot be applied in the binary case. Understanding of these structural properties can help prune the search space and facilitate the identification of good nonbinary CWS codes.