Block Code - Error Detection and Correction Properties

Error Detection and Correction Properties

A codeword could be considered as a point in the -dimension space and the code is the subset of . A code has distance means that, there is no other codeword in the Hamming ball centered at with radius, which is defined as the collection of -dimension words whose Hamming distance to is no more than . Similarly, with (minimum) distance has the following properties:

• can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius, no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of, the errors are detected (but no guarantee to correct).
• can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius, the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word, as long as the number of errors is no more than, there is only one codeword in the hamming ball centered at with radius, therefore all errors could be corrected.
• In order to decode in the presence of more than errors, list-decoding or maximum likelihood decoding can be used.
• can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by -passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.