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

Birkhäuser Basel eBooks

Error-correcting codes

Jacobus H. Lint, Gerard van der Geer

Published Jan 1, 1988• 20 citations
Publisher

Abstract

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.

DOI
10.1007/978-3-0348-9286-5_2

Related papers

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

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

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

Technical perspectiveThe beauty of error-correcting codes

Daniel Alan Spielman

Error-correcting codes are the means by which people compensate for interference in communication, and are essential for the accurate transmission and storage of digital data. All communication mechanisms and storage devices are subject to interference, typically called "noise," which corrupts communicated messages and stored data. Thus, for a communication system to faithfully transmit data, it must build redundancy into its transmissions in such a way that even if a transmission is partially corrupted, the intended message may be reconstructed. Error-correcting codes provide the mapping from messages to redundant transmissions. While a tremendous theoretical advance, more work is required before these codes can be used in practical communication systems. The decoding algorithms run in polynomial time, but need to be faster before they can be applied in practice.

Communications of the ACM•Feb 25, 2009•1 citation

Quantum Cryptography Revisited

Susan Loepp, William K. Wootters

Recall that in the Bennett–Brassard key distribution scheme, after Alice and Bob have obtained bit strings that ideally are supposed to be identical, they have to do some further processing to make sure they end up with strings that really are identical. Our first goal in this chapter is to show how they can do this. As you might expect, we will use error-correcting codes of the sort we have been discussing in the preceding chapter. However, the way we use error-correcting codes in quantum key distribution is not quite the same as in classical communication. Normally, one corrects errors by encoding one's message into special codewords that are sufficiently different from each other that they will still be distinguishable after passing through a noisy channel. But in quantum key distribution the “noise” of the channel might actually be the effect of an eavesdropper who is free to manipulate the signals sent by Alice. Ordinary error correction is not designed for such a setting. So instead of using codewords to encode the original transmission, we wait until all the bits have been sent and then use an error-correcting code after the fact . In this respect error correction in quantum key distribution is similar to the use of an error-correcting code in the “hat problem” discussed at the end of Chapter 4. There also, the error-correcting code is applied only after all the data – in that case the vector of hat colors – has been generated and conveyed to the participants.

Cambridge University Press eBooks•Jul 10, 2006•1 citation

On the efficiency of quantum error correction codes for the depolarising channel

Jonas Almlöf, Gunnar G. Bjork

Quantum error correction is the art of protecting quantum states from the detrimental influence from the environment. To master this art, one must understand how the system interacts with the environment and gives rise to a full set of quantum phenomena, many of which have no correspondence in classical information theory. Such phenomena include decoherence, an effect that in general destroys superpositions of pure states as a consequence of entanglement with the environment. But decoherence can also be understood as “information leakage”, i.e., when knowledge of an encoded code block is transferred to the environment. In this event, the block’s information or entanglement content is typically lost.In a typical scenario, however, not all types of destructive events are likely to occur, but only those allowed by the information carrier, the type of interaction with the environment, and how the environment “picks up” information of the error events. These characteristics can be incorporated into a code, i.e., a channel-adapted quantum error-correcting code.Often, it is assumed that the environment’s ability to distinguish between error events is small, and I will denote such environments “memory-less”. But this assumption is not always valid, since the ability to distinguish error events is related to the temperature of the environment, and in the particular case of information coded onto photons, kBTR «ℏω typically holds, and one must then assume that the environment has a “memory”. In the thesis I describe a short quantum error-correction code adapted for photons interacting with a “cold” reservoir, i.e., a reservoir which continuously probes what error occurred in the coded state.I also study other types of environments, and show how to distill meaningful figures of merit from codes adapted for these channels, as it turns out that resource-based figures reflecting both information and entanglement can be calculated exactly for a well-studied class of channels: the Pauli channels. Starting from these resource-based figures, I establish the notion of efficiency and quality and show that there will be a trade-off between efficiency and quality for short codes. Finally I show how to incorporate, into these calculations, the choices one has to make when handling quantum states that have been detected as incorrect, but where no prospect of correcting them exists, i.e., so-called detection errors.

•Jan 1, 2016•0 citations
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.
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 .
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 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.
Error-correcting codes are the means by which people compensate for interference in communication, and are essential for the accurate transmission and storage of digital data. All communication mechanisms and storage devices are subject to interference, typically called "noise," which corrupts communicated messages and stored data. Thus, for a communication system to faithfully transmit data, it must build redundancy into its transmissions in such a way that even if a transmission is partially corrupted, the intended message may be reconstructed. Error-correcting codes provide the mapping from messages to redundant transmissions. While a tremendous theoretical advance, more work is required before these codes can be used in practical communication systems. The decoding algorithms run in polynomial time, but need to be faster before they can be applied in practice.
Recall that in the Bennett–Brassard key distribution scheme, after Alice and Bob have obtained bit strings that ideally are supposed to be identical, they have to do some further processing to make sure they end up with strings that really are identical. Our first goal in this chapter is to show how they can do this. As you might expect, we will use error-correcting codes of the sort we have been discussing in the preceding chapter. However, the way we use error-correcting codes in quantum key distribution is not quite the same as in classical communication. Normally, one corrects errors by encoding one's message into special codewords that are sufficiently different from each other that they will still be distinguishable after passing through a noisy channel. But in quantum key distribution the “noise” of the channel might actually be the effect of an eavesdropper who is free to manipulate the signals sent by Alice. Ordinary error correction is not designed for such a setting. So instead of using codewords to encode the original transmission, we wait until all the bits have been sent and then use an error-correcting code after the fact . In this respect error correction in quantum key distribution is similar to the use of an error-correcting code in the “hat problem” discussed at the end of Chapter 4. There also, the error-correcting code is applied only after all the data – in that case the vector of hat colors – has been generated and conveyed to the participants.
Quantum error correction is the art of protecting quantum states from the detrimental influence from the environment. To master this art, one must understand how the system interacts with the environment and gives rise to a full set of quantum phenomena, many of which have no correspondence in classical information theory. Such phenomena include decoherence, an effect that in general destroys superpositions of pure states as a consequence of entanglement with the environment. But decoherence can also be understood as “information leakage”, i.e., when knowledge of an encoded code block is transferred to the environment. In this event, the block’s information or entanglement content is typically lost.In a typical scenario, however, not all types of destructive events are likely to occur, but only those allowed by the information carrier, the type of interaction with the environment, and how the environment “picks up” information of the error events. These characteristics can be incorporated into a code, i.e., a channel-adapted quantum error-correcting code.Often, it is assumed that the environment’s ability to distinguish between error events is small, and I will denote such environments “memory-less”. But this assumption is not always valid, since the ability to distinguish error events is related to the temperature of the environment, and in the particular case of information coded onto photons, kBTR «ℏω typically holds, and one must then assume that the environment has a “memory”. In the thesis I describe a short quantum error-correction code adapted for photons interacting with a “cold” reservoir, i.e., a reservoir which continuously probes what error occurred in the coded state.I also study other types of environments, and show how to distill meaningful figures of merit from codes adapted for these channels, as it turns out that resource-based figures reflecting both information and entanglement can be calculated exactly for a well-studied class of channels: the Pauli channels. Starting from these resource-based figures, I establish the notion of efficiency and quality and show that there will be a trade-off between efficiency and quality for short codes. Finally I show how to incorporate, into these calculations, the choices one has to make when handling quantum states that have been detected as incorrect, but where no prospect of correcting them exists, i.e., so-called detection errors.