Introduction: The generator and parity-check matrices We have already noted that the channel coding theorem (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 suggested 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.
Introduction: The generator and parity-check matrices We have already noted that the channel coding theorem (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 suggested 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.
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 consider block codes with a certain structure, which are defined over alphabets that are fields. Specifically, these codes, which we call linear codes, form linear spaces over their alphabets. We associate two objects with these codes: a generator matrix and a parity-check matrix. The first matrix is used as a compact representation of the code and also as a means for efficient encoding. The parity-check matrix will be used as a tool for analyzing the code (e.g., for computing its minimum distance) and will also be part of the general framework that we develop for the decoding of linear codes. As examples of linear codes, we will mention the repetition code, the parity code, and the Hamming code with its extensions. Owing to their structure, linear codes are by far the predominant block codes in practical usage, and virtually all codes that will be considered in subsequent chapters are linear. Definition Denote by GF( q ) a finite ( Galois ) field of size q . For example, if q is a prime, the field GF( q ) coincides with the ring of integer residues modulo q , also denoted by ℤ q . We will see more constructions of finite fields in Chapter 3. An ( n, M, d ) code C over a field F = GF( q ) is called linear if C is a linear subspace of F n over F ; namely, for every two codewords c 1 , c 2 ∈ C and two scalars a 1 , a 2 ∈ F we have a 1 c 1 + a 2 c 2 ∈ C .
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.
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
This is a complete presentation of all important theoretical and experimental work done on low-density codes. Low-density coding is one of the three techniques thus far developed for efficient communication over noisy channels with an arbitrarily low probability of error. A principal result of information theory is that if properly coded information is transmitted over a noisy channel at a rate below channel capacity, the probability of error can be made to approach zero exponentially with the code length. Any practical use of this theorem, however, requires a coding scheme in which the cost of storage and computation equipment grows slowly with code length. The present book analyzes a class of coding schemes for which costs grow approximately linearly with code length. It demonstrates that error probability approaches zero exponentially with a root of the block length and cites experimental evidence that this coding scheme has profitable aplicability in many communications situations.
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.