We saw in Chapter 1 how the 3-fold repetition code would drastically reduce the probability of messages being wrongly decoded, and discussed the price which this entailed. Then in Chapter 2 we saw how the Hamming code solved the same problem of guaranteeing to correct every instance of a single error per codeword at much less cost. The way in which it achieved its impressive performance was by ensuring that amongst the 16 7-bit codewords, no pair of them was separated by a Hamming distance less than 3. We also developed general results, Theorems 2.1 and 2.2, to connect the minimum distance of the code with its error detecting and correcting potential.
We saw in Chapter 1 how the 3-fold repetition code would drastically reduce the probability of messages being wrongly decoded, and discussed the price which this entailed. Then in Chapter 2 we saw how the Hamming code solved the same problem of guaranteeing to correct every instance of a single error per codeword at much less cost. The way in which it achieved its impressive performance was by ensuring that amongst the 16 7-bit codewords, no pair of them was separated by a Hamming distance less than 3. We also developed general results, Theorems 2.1 and 2.2, to connect the minimum distance of the code with its error detecting and correcting potential.
In any engineering discipline, one looks for methods of solving a given class of problems and then for methods of quantifying the performance and complexity of those solutions. Accordingly, in this chapter, we shall study performance in terms of the composition structure of block codes, and the probabilities of decoding error and of decoding failure. Later, after satisfactory methods are in hand, one turns to questions of optimality. Are these methods the best methods, and if not, in what ways and by how much are they inferior? To answer such questions, one needs to know how good are the known codes and how good are the best possible codes. Generally, we cannot answer either of these questions satisfactorily. Although for any given rate and blocklength, not too small, the best possible code is not known, a number of bounds are known – bounds beyond which no codes can exist, and bounds within which codes are sure to exist. We shall give some such bounds on the best possible codes later in this chapter. Knowledge of these bounds can deepen our understanding of the subject. Weight distributions of block codes If a linear block code has a minimum distance d min , then we know that at least one codeword of weight d min exists. Sometimes, we are not content with this single piece of information; we wish to know how many codewords have weight d min , and what are the weights of the other codewords.
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 .
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.
In this final chapter we present a number of bounds on the minimum dis tance of a quantum error correcting code (QECC). Sections 7.1-7.3 derive the quantum Hamming, Gilbert-Varshamov, and Singleton bounds, respectively. The corresponding classical bounds were derived in Section 1.2.5. Section 7.4 introduces quantum generalizations of the classical MacWilliams identities, and of weight and shadow enumerators [1,2]. With these tools in hand, the problem of finding an optimal upper bound on the code distance is reduced to solving a problem in linear programming [3-5]. Finally, we close in Section 7.5 by showing how QECCs can be connected to the process of entanglement pu rification [6,7]. This final section allows our study of QECCs to segue into the developing field of quantum information theory [8,9], and provides a good place to bring the discussion in this book to a close.
Introduction: The generator and parity-check matrices We have already noted that the channel coding Theorem 2.4 is unsatisfactory from a practical standpoint. This is because the codes whose existence is proved there suffer from at least three distinct defects: (a) They are hard to find (although the proof of Theorem 2.4 suggests that a code chosen “at random” is likely to be pretty good, provided its length is large enough). (b) They are hard to analyze . (Given a code, how are we to know how good it is? The impossibility of computing the error probability for a fixed code is what led us to the random coding artifice in the first place!) (c) They are hard to implement . (In particular, they are hard to decode: the decoding algorithm sugggested in the proof of Theorem 2.4—search the region S (y) for codewords, and so on—is hopelessly complex unless the code is trivially small.) In fact, virtually the only coding scheme we have encountered so far which suffers from none of these defects is the (7, 4) Hamming code of the Introduction. In this chapter we show that the Hamming code is a member of a very large class of codes, the linear codes , and in Chapters 7–9 we show that there are some very good linear codes which are free from the three defects cited above.
In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.