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

Cambridge University Press eBooks

Error Correcting Codes

Thomas Watson

Published Oct 9, 2026• 0 citations
Publisher

Abstract

This chapter covers error correcting codes, which protect data transmissions from accidental corruption. The chapter describes constructions, analyses, and decoding algorithms for some classic codes. Bounds on the best possible parameters of codes are also presented. The chapter shows how to construct finite fields whose elements are bit strings, which is useful for some applications of error correcting codes.

DOI
10.1017/9781009752329.012

Related papers

The 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.

•Jan 1, 2009•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

Bounds and Constructions for Codes Protecting Against Asymmetric Errors

J. Martin Borden

We study binary error-correcting and error-detecting codes suitable for use on a completely asymmetric or Z channel. This channel accepts inputs of 0 and 1 and reproduces these faithfully as outputs, except that occasionally the input of a 1 will erroneously result in the output of a 0. We construct block codes protecting against this error and bound the performance of the best possible codes.

University Microfilms International eBooks•Jan 1, 1981•0 citations

An Introduction to Error-Correcting Codes

Susan Loepp, William K. Wootters

In the preceding chapter we mentioned the inevitable errors that occur when one tries to send quantum signals over, say, an optical fiber, even when there is no eavesdropper. But errors in transmission are not a problem just for quantum cryptography. For this entire chapter we forget about sending quantum information and instead focus on simply transmitting ordinary data faithfully over some kind of channel. Moreover, we assume that the data either is not sensitive or has already been encrypted. Unfortunately, many methods for transmitting data are susceptible to outside influences that can cause errors. How do we protect information from these errors? Error-correcting codes provide a mathematical method of not only detecting these errors, but also correcting them. Nowadays error-correcting codes are ubiquitous; they are used, for example, in cell-phone transmissions and satellite links, in the representation of music on a compact disk, and even in the bar codes in grocery stores. The story of modern error-correcting codes began with Claude Shannon's famous paper “A Mathematical Theory of Communication,” which was published in 1948. Shannon worked for Bell Labs where he specialized in finding solutions to problems that arose in telephone communication. Quite naturally, he started considering ways to correct errors that occurred when information was transmitted over phone lines. Richard Hamming, who also worked at Bell Labs on this problem, published a groundbreaking paper in 1950 on the subject.

Cambridge University Press eBooks•Jul 10, 2006•0 citations

TAP for Parity Check Error Correcting Codes

David Saad, Yoshiyuki Kabashima, Renato Vicente

We employ the methods presented in the previous chapter for decoding corrupted codewords, encoded using sparse parity check error correcting codes. We show the similarity between the equations derived from the TAP approach and those obtained from belief propagation, and examine their performance as practical decoding methods.

The MIT Press eBooks•Jun 8, 2001•1 citation

Quantum error correction

Anirban Pathak

In Chapter 4 we introduced different quantum gates and quantum circuits and in Chapter 5 we described several quantum algorithms. So far the analysis of the algorithms and the circuits has been made with the assumption that the required unitary operations can be implemented exactly without any error. This is an abstraction. In an actual physical system that implements a quantum algorithm or a quantum circuit there are several sources of errors. The situation is similar in classical computation and to circumvent this problem error correcting codes are used in classical digital computing. Since qubits are more delicate and more susceptible to errors we need to introduce quantum error correcting codes. It is very important, as without such codes it will not be possible to build a scalable quantum computer. Such quantum error correcting codes are introduced in this chapter. However, we will not limit ourselves to the discussion of error correcting codes alone. We will also discuss more general aspects of errors and error correction, like decoherence, decoherence free subspace and fault-tolerance.

CRC Press eBooks•Jun 20, 2013•33 citations
This chapter covers error correcting codes, which protect data transmissions from accidental corruption. The chapter describes constructions, analyses, and decoding algorithms for some classic codes. Bounds on the best possible parameters of codes are also presented. The chapter shows how to construct finite fields whose elements are bit strings, which is useful for some applications of error correcting codes.
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.
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 preceding chapter we mentioned the inevitable errors that occur when one tries to send quantum signals over, say, an optical fiber, even when there is no eavesdropper. But errors in transmission are not a problem just for quantum cryptography. For this entire chapter we forget about sending quantum information and instead focus on simply transmitting ordinary data faithfully over some kind of channel. Moreover, we assume that the data either is not sensitive or has already been encrypted. Unfortunately, many methods for transmitting data are susceptible to outside influences that can cause errors. How do we protect information from these errors? Error-correcting codes provide a mathematical method of not only detecting these errors, but also correcting them. Nowadays error-correcting codes are ubiquitous; they are used, for example, in cell-phone transmissions and satellite links, in the representation of music on a compact disk, and even in the bar codes in grocery stores. The story of modern error-correcting codes began with Claude Shannon's famous paper “A Mathematical Theory of Communication,” which was published in 1948. Shannon worked for Bell Labs where he specialized in finding solutions to problems that arose in telephone communication. Quite naturally, he started considering ways to correct errors that occurred when information was transmitted over phone lines. Richard Hamming, who also worked at Bell Labs on this problem, published a groundbreaking paper in 1950 on the subject.
In Chapter 4 we introduced different quantum gates and quantum circuits and in Chapter 5 we described several quantum algorithms. So far the analysis of the algorithms and the circuits has been made with the assumption that the required unitary operations can be implemented exactly without any error. This is an abstraction. In an actual physical system that implements a quantum algorithm or a quantum circuit there are several sources of errors. The situation is similar in classical computation and to circumvent this problem error correcting codes are used in classical digital computing. Since qubits are more delicate and more susceptible to errors we need to introduce quantum error correcting codes. It is very important, as without such codes it will not be possible to build a scalable quantum computer. Such quantum error correcting codes are introduced in this chapter. However, we will not limit ourselves to the discussion of error correcting codes alone. We will also discuss more general aspects of errors and error correction, like decoherence, decoherence free subspace and fault-tolerance.