more than one error occurs, and the number of ber of discrepancies) between it and all the valid codewords can be Block coding 14/5 calculated at the decoder; let the distance between the received If the syndrome of the received codeword is zero, the decoder codeword and valid codeword be If it is found that one of these assumes that it is correct, and the output dataword can be extracted distances d. is less than all the others, then assuming random errors directly from it (very easily, for a systematic code). it is more likely that the transmitted codeword was c. than any other. A non-zero syndrome is a certain indication of errors. If the (This is because for realistic bit error rates the probability that the transmitted codeword c is corrupted by the (modulo-2) addition of number of errors will be between 1 and d diminishes rapidly as d the n-bit error pattern e, the syndrome becomes as in Equation 14.8, increases). The decoder could therefore be made to output the 'most which is a function only of the error pattern. probably correct' codeword this is known as Maximum Likeli- hood or Minimum Distance error correction. Such error correction S =(c+e)H™ - HH = (14.8) is only possible if the number of errors is less than d/2, because otherwise the distance to two codewords could be equal, or the Hence the syndrome can be used to deduce, and remove, the distance to a wrong codeword could be less than the distance to the errors. There are only 2n-k) -1 different non-zero syndromes, but correct one. there are -1 different error patterns, so every syndrome (includ- In general it is possible to trade off error detection and correction ing zero) may be generated by many different error patterns. How- ability; a code which is required to allow correction of errors and ever, as mentioned above, error patterns with small numbers of detection of a further n errors must have a minimum distance given errors are more likely than those with large numbers of errors, so the by Equation 14.6. most likely cause of a given non-zero