So-called linear codes create error-correction bits by combining the data bits linearly. The phrase "linear combination" means here single-bit binary arithmetic.

For example, let's consider the specific (⁢7,4) ( 7 , 4 ) error correction code described by the following coding table and, more concisely, by the succeeding matrix expression.

The length-KK block of data bits is represented by the vector bb, and the length- NN output block of the channel coder, known as a codeword, by cc. For example, if b=1000T b 1 0 0 0 , c=1000101T c 1000101 . The generator matrix GG defines all block-oriented linear channel coders.

In this (⁢7,4) ( 7 , 4 ) code, 24=16 2 4 16 of the 27=128 2 7 128 possible blocks arriving at the channel decoder correspond to error-free transmission and reception. In analyzing the error-correcting capability of this or any other channel code, we must have a systematic way of assigning a codeword to a received block when communication errors occur. Note that the number of possible received blocks is much larger than the number of codewords; the channel has ample opportunity to confuse us! Conceptually, we want to assign to each possible received length- NN block a length- KK block of data bits. This assignment should correspond to the most probable error pattern that could have transformed a transmitted block into the one received. Because the matched-filter receiver guarantees that the single-bit error probability p e p e of the digital channel will be less than 1/2 12 , the most probable error pattern is the one having the fewest errors. The way of assessing error patterns is to compute the distance between the received block and all codewords. The Hamming distance between blocks c 1 c 1 and c 2 c 2 , denoted by d⁢ c 1 c 2 d c 1 c 2 , equals the sum of the difference between the bit sequences comprising the two blocks. For example, if c 1 =1000101T c 1 1 0 0 0 1 0 1 and c 2 =1010101T c 2 1 0 1 0 1 0 1 , the difference equals 0010000T 0 0 1 0 0 0 0 , the number of nonzero terms equals one, and thus d⁢ c 1 c 2 =1 d c 1 c 2 1 . Interestingly, examination of the binary arithmetic table reveals that subtraction and addition are equivalent. We can express the Hamming distance as

Error correction amounts to searching for the codeword cc closest to the received block cc in terms of the Hamming distance between the two. The error correction capability of a channel code is limited by how close together any two error-free blocks are. Bad codes would produce blocks close together, which would result in ambiguity when assigning a block of data bits to a received block. The quantity to examine, therefore, in designing code error correction codes is the minimum distance between codewords.

Suppose this minimum distance is one; this means the channel code has two codewords with the not-so-desirable property that one error occurring somewhere within the NN-bit block transforms one codeword into another! The receiver would never realize that an error occurred in this case. Such a channel code would have no error-correction capability, and because the energy/bit must be reduced to insert error correction bits, we obtain larger error probabilities. Now suppose the minimum distance between error-free blocks is two. This situation is better than the previous one: If one error occurs anywhere within a block, no matter what codeword was transmitted, we can detect the fact that an error occurred. Unfortunately, we cannot correct the error. Because the minimum distance is two, a received block containing one error can be a distance of one from two (or more) codewords; we cannot associate such a block uniquely with a codeword. We must be resigned to the fact that to correct errors, we must have the minimum distance between error-free blocks be at least three.

How do we calculate the minimum distance between codewords? Because we have 2K 2 K codewords, the number of possible unique pairs equals 2K−1⁢(2K−1) 2 K 1 2 K 1 , which can be a large number. Recall that our channel coding procedure is linear, with c=G⁢b c G b . Therefore c i ⊕ c j =G⁢ b i ⊕ b j G c i c j G b i b j . Because b i ⊕ b j b i b j always yields another block of data bits, we find that the difference between any two codewords is another codeword! Thus, to find d min d min we need only compute the number of ones that comprise all non-zero codewords. Finding these codewords is easy once we examine the coder's generator matrix. Note that the columns of GG are codewords, and that all codewords can be found by all possible pairwise sums of the columns. To find d min d min , we need only count the number of bits in each column and sums of columns. For our example (⁢7,4) ( 7 , 4 ) ((Reference)), GG's first column has three ones, the next one four, and the last two three. No sum of columns has fewer than three bits, meaning d min =3 d min 3 , and we have a channel coder that can correct all occurrences of one error within a received 77-bit block.

We must question whether a (⁢7,4) ( 7 , 4 ) code's error correction capability compensates for the increased error probability due to the necessitated reduced bit energy. (For example, the repetition code does not meet this requirement.) Figure 3 shows that if the signal-to-noise ratio is large enough that channel coding indeed yields a smaller overall error probability.

Because the bit stream emerging from the source coder is segmented into four-bit blocks, the fair way of comparing coded and uncoded transmission is to compute the probability of a block error: the probability that any bit in a block remains in error despite error correction and regardless of whether the error occurs in the data or coding bits. Clearly, our (⁢7,4) ( 7 , 4 ) channel code does yield smaller error rates, and is worth the additional systems required to make it work.

Content actions

Footer

This work is licensed by Don Johnson under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.

Last edited by (Unknown) on Aug 9, 2001 12:00 am -0500.