10.20 Consider the (7, 4) Hamming code of Example 10.10. The generator matrix G and the parity-check matrix H of the code are described in that example. Show that these two matrices satisfy the condition HGT=0 EXAMPLE 10.10 Hamming Codes Consider a family of (n,k) linear block codes that have the following parameters: Block length: Number of message bits: Number of parity bits: n-2-1 k=2"-m-1 n-k=m where m ≥3. These are the so-called Hamming codes. Consider, for example, the (7, 4) Hamming code with n = 7 and k = 4, corresponding to m = 3. The generator matrix of the code must have a struc- ture that conforms to Eq. (10.73). The following matrix represents an appro- priate generator matrix for the (7, 4) Hamming code. G= 1 1 0 1 0 0 0] 01 10 100 1110010 1010001 P I The corresponding parity-check matrix is given by H= [1 0 0|1 0 1 01 0 1 1 1 0 0010111 Im-k PT With k 4, there are 2 = 16 distinct message words, which are listed in Table 10.4. For a given message word, the corresponding codeword is ob- tained by using Eq. (10.74). Thus, the application of this equation results in the 16 codewords listed in Table 10.4. = In Table 10.4 we have also listed the Hamming weights of the individual codewords in the (7, 4) Hamming code. Since the smallest of the Hamming weights for the nonzero codewords is 3, it follows that the minimum distance of the code is 3. Indeed, Hamming codes have the property that the minimum dis- tance dmin 3, independent of the value assigned to the number of parity bits m. To illustrate the relation between the minimum distance dmin and the structure of the parity-check matrix H, consider the codeword 0110100. In the matrix multiplication defined by Eq. (10.77), the nonzero elements of this TABLE 10.4 Codewords of a (7, 4) Hamming code 376 Message Word Codeword Weight of Codeword Message Weight of Word Codeword Codeword 0000 0000000 0 1000 1101000 3 0001 1010001 3 1001 0111001 4 0010 1110010 4 1010 0011010 3 0011 0100011 3 1011 1001011 0100 0110100 3 1100 1011100 0101 1100101 4 1101 0001101 0110 1000110 3 1110 0111 0010111 4 1111 0101110 1111111 44347 codeword sift out the second, third, and fifth columns of the matrix H yielding 8-8-8-8 We may perform similar calculations for the remaining 14 nonzero code- words. We thus find that the smallest number of columns in H that sums to zero is 3, confirming the earlier statement that dmin = 3. An important property of Hamming codes is that they satisfy the con- dition Eq. (10.86) with the equality sign, assuming that = 1. This means that Hamming codes are single-error correcting binary perfect codes. Assuming single-error patterns, we may formulate the seven coset leaders listed in the right-hand column of Table 10.5. The corresponding syndromes, listed in the left-hand column, are calculated in accordance with Eq. (10.81). The zero syndrome signifies no transmission errors. Suppose, for example, the code vector [1110010] is sent, and the received vector is [1100010] with an error in the third bit. Using Eq. (10.80), the syndrome is calculated to be [1 0 0] 010 001 s=[1100010] 1 1 0 =[001] 0 From Table 10.5 the corresponding coset leader (i.e., error pattern with the highest probability of occurrence) is found to be [0010000], indicating correctly that the third bit of the received vector is erroneous. Thus, adding this error pattern to the received vector, in accordance with Eq. (10.87), yields the correct code vector actually sent. Richard W. Hamming (1915-1998) When Richard W. Hamming joined Bell Laboratories, he shared an office with Claude Shannon. While Shannon worked on information theory, Hamming worked on coding theory at the same time and in the same place. In an interview taped in 1977, just about three decades after the discovery of the first binary codes, Hamming recalled his frustration working on a mechanical re- lay computer, to which he had access only on weekends: "Two weekends in a row I came in and found that all my stuff had been dumped and nothing was done... And so I said: "Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?" It was that question that led to the discovery of the first binary error-correcting codes by Hamming. The history of the origin of coding theory has a controversy of its own. The publication of Hamming's paper in the Bell System Technical Journal in 1949 was held up for some time due to patent reasons. In that same year, Golay published a paper in the Proceedings of the IRE (later re- named the IEEE), in which his (23,12) and (11,6) codes were described. For an inter- esting exposé of how this controversy played out, see the last section of Chapter 1 of Thompson's book (1983). Dual Code. Given a linear block code, we may define its dual as follows. Taking the transpose of both sides of Eq. (10.76), we have GHT=0 where H is the Transpose of the parity-check matrix of the code, and 0 is a new zero matrix. This equation suggests that every (n.k) linear block code with generator matrix G and parity-check matrix H has a dual code with parameters (n, n- erator matrix H and parity-check matrix G. TABLE 10.5 Decoding table for the (7,4) Hamming code defined in Table 10.4 Syndrome Error Pattern 0000000 k), gen- 000 100 1000000 010 0100000 CYCLIC CODES 001 0010000 The set of linear block codes is large. One important subclass of linear block codes is known as cyclic codes, as they are characterized by the fact that any cyclic shift a codeword is also a codeword. Important examples of cyclic codes are: 110 0001000 011 0000100 111 0000010 101 0000001 Hamming codes, of which we have already given an example. 377