6.26 Error-correcting codes: hamming distance  (Page 2/2)

To perform decoding when errors occur, we want to find the codeword (one of the filled circles in [link] ) that has the highest probability of occurring: the one closest to the one received. Note that if a datawordlies a distance of 1 from two codewords, it is impossible to determine which codeword was actually sent. This criterion means that if any two codewordsare two bits apart, then the code cannot correct the channel-induced error. Thus, to have a code that can correct all single-bit errors, codewords must havea minimum separation of three. Our repetition code has this property.

Introducing code bits increases the probability that any bit arrives in error (because bit interval durations decrease).However, using a well-designed error-correcting code corrects bit reception errors. Do we win or lose by using anerror-correcting code? The answer is that we can win if the code is well-designed. The (3,1) repetition code demonstrates that we can lose ( [link] ). To develop good channel coding, we need to develop first a general framework forchannel codes and discover what it takes for a code to be maximally efficient: Correct as many errors as possible usingthe fewest error correction bits as possible (making the efficiency $\frac{K}{N}$ as large as possible.) We also need a systematic way of finding the codeword closest to any received dataword. A much bettercode than our (3,1) repetition code is the following (7,4) code. $$\begin{array}{c}c(1)=b(1)\\ c(2)=b(2)\\ c(3)=b(3)\\ c(4)=b(4)\\ c(5)=b(1)\mathop{\mathrm{xor}}b(2)\mathop{\mathrm{xor}}b(3)\\ c(6)=b(2)\mathop{\mathrm{xor}}b(3)\mathop{\mathrm{xor}}b(4)\\ c(7)=b(1)\mathop{\mathrm{xor}}b(2)\mathop{\mathrm{xor}}b(4)\end{array}$$ where the generator matrix is $$G=\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1\\ 1 & 1 & 0 & 1\\ \end{pmatrix}$$ In this (7,4) code, $2^4=16$ of the $2^7=128$ possible blocks at the channel decoder correspond to error-freetransmission and reception.

Error correction amounts to searching for the codeword $c$ closest to the received block $\widehat{c}$ in terms of the Hamming distance between the two. The error correction capability of a channel code is limited by howclose together any two error-free blocks are. Bad codes would produce blocks close together, which would result in ambiguitywhen assigning a block of data bits to a received block. The quantity to examine, therefore, in designing code errorcorrection codes is the minimum distance between codewords.

How do we calculate the minimum distance between codewords? Because we have $2^K$ codewords, the number of possible unique pairs equals $2^{(K-1)}(2^K-1)$ , which can be a large number. Recall that our channel coding procedure is linear, with $c=Gb$ . Therefore $c_i\mathop{\mathrm{xor}}{c}_j=G(b_i\mathop{\mathrm{xor}}{b}_j)$ . Because $b_i\mathop{\mathrm{xor}}{b}_j$ always yields another block of data bits, we find that the difference between any two codewords isanother codeword! Thus, to find $d_{\min }$ we need only compute the number of ones that comprise all non-zero codewords. Finding these codewords is easy once weexamine the coder's generator matrix. Note that the columns of $G$ are codewords (why is this?), and that all codewords can be found by all possiblepairwise sums of the columns. To find $d_{\min }$ , we need only count the number of bits in each column and sums of columns. For our example (7, 4), $G$ 's first column has three ones,the next one four, and the last two three. Considering sums of column pairs next, note that because the upper portion of $G$ is an identity matrix, the corresponding upper portion of all column sums musthave exactly two bits. Because the bottom portion of each column differs from the other columns in at least one place, thebottom portion of a sum of columns must have at least one bit. Triple sums will have at least three bits because the upperportion of $G$ is an identity matrix. Thus, no sum of columns has fewer than threebits, which means that $d_{\min }=3$ , and we have a channel coder that can correct all occurrencesof one error within a received $7$ -bit block.