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 .
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.
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.
There are some bounds that are placed on the size of error correcting codes. Some of the well-known bounds are discussed in the following sections. 6.1 Definitions Let n be fixed, and let M denote the size of a code C (i.e., the number of codewords in C), and d the minimum distance between the codewords. For example, (i) for the code C = {00, 01, 10, 11} : n = 2,M = 4; d = 1; (ii) for the code C = {000, 011, 101, 110} : n = 3,M = 4, d = 2; and (iii) for the code C = {00000, 00111, 11111} : n = 5,M = 3, d = 2. Then for a q-ary (n,M, d) code, the transmission rate (also known as the information rate) is defined by R(C) = log q M n , and the relative minimum distance by δ(C) = (d − 1)/n. Note that this distance is also defined by d/n, but neater formulas are obtained by defining it as (d − 1)/n. For the binary repetition code C = {00 . . .0︸ ︷︷ ︸ 11 . . .1︸ ︷︷ ︸ n }, which is an (n, 2, n) code, we find that R(C) = log 2 2 n = n → 0 and δ(C) = n− 1 n → 0 as n→∞.
There are two basic methods of error control for communication, both involving coding of the messages. With forward error correction, the codes are used to detect and correct errors. In a repeat request system, the codes are used to detect errors and, if there are errors, request a retransmission. Error detection is usually much simpler to implement than error correction and is widely used. However, it is given a very cursory treatment in almost all textbooks on coding theory. Only a few older books are devoted to error detecting codes. This book begins with a short introduction to the theory of block codes with emphasis on the parts important for error detection. The weight distribution is particularly important for this application and is treated in more detail than in most books on error correction. A detailed account of the known results on the probability of undetected error on the q-ary symmetric channel is also given.
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.
This chapter discusses recent advances in modern coding theory, in particular the use of popular graph-based codes and their low complexity decoding algorithms. We describe absorbing sets as the key object for characterizing the performance of iteratively-decoded graph-based codes and we propose several directions for future investigation in this thriving discipline. Chapter Overview Every engineered communication system, ranging from satellite communications to hard disk drives to Ethernet must operate under noisy conditions. The key to reliable communication and storage is to add an appropriate amount of redundancy to make the system reliable. The field of channel coding is concerned with constructing channel codes and their decoding algorithms: controlled redundancy is introduced into a message prior to its transmission over a noisy channel (the encoding step), and this redundancy is removed from the received noisy string to unveil the intended message (the decoding step). The encoded message is referred to as the codeword. The collection of all codewords is a channel code. Assuming all the messages have the same length, and all the codewords have the same length, the ratio of message length to codeword length is the code rate. To make coding systems implementable in practice, channel codes must provide the best possible protection to noise while their decoding algorithms must be of acceptable complexity. There is a clear tension with this dual goal: if a channel code protects a fairly long encoded message with relatively few but carefully derived redundancy bits (necessary for high performance), the optimal, maximum likelihood decoding algorithm has exponential complexity.