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 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.
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 .
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>
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.
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.
Introduction Quantum error-correcting codes (QECCs) have turned out to have many applications; but their primary purpose, of course, is to protect quantum information from noise. This need manifests itself in two rather different situations. The first is in quantum computing. The qubits in a quantum computer are subject to noise due both to imprecision in the operations (or gates) and to interactions with the external environment. They undergo errors when they are acted upon, and when they are just being stored (though hopefully not at the same rate). All the qubits in the computer must be kept error-free long enough for the computation to be completed. This is the principle of fault tolerance. A rather different situation occurs in quantum communication . Here, the sender and receiver (Alice and Bob) are assumed to be physically separated, and the qubits travel from the sender to the receiver over a (presumably noisy) channel. This channel is assumed to be the dominant source of errors. While the qubits may undergo processing before and after transmission, errors during this processing are considered negligible compared to the channel errors. This picture of transmission through a channel is similar in spirit to the paradigm underlying much of classical information theory.