0.2 Block code performance

Block code error correction capability

Hamming distance

Consider two distinct five digit codewords C1 = 00000 and C2 = 00011. These have a binary digit difference (or Hamming distance) of 2 in the last two digits. The minimum distance in binary digits between any two codewords is known as the minimum Hamming distance, $D_{\min }$

For block codes the minimum Hamming distance or the smallest difference between the digits for any two codewords in the complete code set, $D_{\min }$ , is the property which controls the error correction performance. We can thus calculate the error detecting and correcting power of a code from the minimum distance in bits between the codewords.

Thus for a code with a minimum distance $D_{\min }$ = 3 then this code can be used to correct:

Note in the earlier example of two five digit codewords C1 = 00000 and C2 = 00011 which had a Hamming distance of 2 there is only one codeword (e.g. A = 00001 or B = 00010) which lies inbetween these two codewords. Now if there was an error result (e.g. A = 00001) we cannot tell whether it came from C1 or C2 so we can thus only used this to detect that an error has occurred.

If the two five digit codewords had been C1 = 00000 and C2 = 00111, which have a Hamming distance of 3, there are then two words which lie inbetween these codewords (e.g. A = 00001 and B = 00011) and these can thus be used EITHER to detect two errors without any correction capability OR if detection is not required they can used to correct a single error (e.g. C1 = 00000 distorted into A = 00001 or C2 = 00111 distorted into B = 00011), [link] .

When performing the correction operation we require to insert the decision boundary as shown in Example 1 below. If in this example we had wished to perform detection only as shown in the lower part of [link] then we would ignore whether the received code A = 00001 resulted from a single error from a C1 transmission or a double error from a C2 code transmission and only identify it as a detected error.

Example 1 – error correction

C1 = 00000

A = 00001

---------------

B = 00011

C2 = 00111

This explains further the detailed operation of the equations in [link] where detection only operation does not require the decision boundary to aid identification of the origination of the error.

Block error probability and correction capability

If we have an error correcting code which can correct R’ errors, than the probability of a codeword not being correctable is the probability of having more than R’ errors in n digits. The probability of having more than R’ errors is given in [link] . We can this calculate this probability by summing all the induvidual error probabilities up to and including R' errors in the block.

The probability of j errors occurring in an n digit codeword is given in [link] . $P_e$ is the probability of error in a single binary digit and n is the block length. [link] also shows how to calculate the nCj term representing all the possible number of ways or error positions that j errors can occur within a block of length n binary digits.