Cambridge University Press eBooks

Codes

Edward F. Assmus, Jennifer D. Key

Published Aug 28, 1992• 0 citations

Abstract

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.

DOI: 10.1017/cbo9781316529836.003

Related papers

Error-correcting codes

Jacobus H. Lint, Gerard van der Geer

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.

Birkhäuser Basel eBooksJan 1, 198820 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 eBooksFeb 12, 20040 citations

Linear codes

Robert J. McEliece

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.

Cambridge University Press eBooksJul 15, 20040 citations

Linear codes

Robert J. McEliece

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.

Cambridge University Press eBooksApr 18, 20020 citations

A Universal Theory of Decoding and Pseudocodewords

Nathan Axvig, Deanna Dreher, Katherine Morrison +3 more

The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)

Jan 1, 20082 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 TheorySep 1, 196012 citations