718
Modeling Arithmetic, Computation, and Languages
1. The received n-tuple is identical to one of the code words. In this case,
maximum-likelihood decoding will assume that no errors have occurred.
This is actually based on another assumption, namely that the probability
of errors occurring is very low, so that the probability of no errors is very
high. Therefore the probability that a received code word is the same code
word that was originally transmitted is more likely than that the transmitted code word was scrambled into a different code word.
2. The received n-tuple does not match any code word. Maximum-likelihood
decoding suggests that the received n-tuple should be decoded as the
closest code word, as this would be the result of the fewest bit errors and
therefore has the highest probability of giving the correct result.
Keep in mind throughout this section that maximum-likelihood decoding
does not guarantee 100% accurate results; it guarantees only results with the highest probability of being accurate.
To determine the “closest” code word, we need to define what we mean by the
distance between binary n-tuples. Hamming distance, defined here, is named for
Richard W. Hamming, an American mathematician who pioneered the study of
error-detecting and error-correcting codes in 1950.
Definition hAMMinG DistAnCE
Let X and Y be binary n-tuples. The hamming distance between X and Y,
H(X, Y ), is the number of components in which X and Y differ. The minimum
distance of a code is the minimum Hamming distance between all possible pairs
of distinct code words.
PrACtiCe 38 For X = 01011 and Y = 11001, what is H(X, Y )?
■
Each error that occurs in the transmission of a code word adds one unit to the
Hamming distance between that code word and the received word. Suppose we
picture the code words as specific binary n-tuples distinguished from the set S of
all binary n-tuples, as in Figure 9.1. Suppose also that the minimum distance of
the code is at least d + 1. Then any time a code word X is corrupted by d or fewer
errors, it will be changed to an n-tuple X ′ that is not another code word, and the
occurrence of errors can be detected. Conversely, if any combination of d or fewer
errors can be detected, code words must be at least d + 1 apart.
d + 1
S
figure 9.1
Modeling Arithmetic, Computation, and Languages
1. The received n-tuple is identical to one of the code words. In this case,
maximum-likelihood decoding will assume that no errors have occurred.
This is actually based on another assumption, namely that the probability
of errors occurring is very low, so that the probability of no errors is very
high. Therefore the probability that a received code word is the same code
word that was originally transmitted is more likely than that the transmitted code word was scrambled into a different code word.
2. The received n-tuple does not match any code word. Maximum-likelihood
decoding suggests that the received n-tuple should be decoded as the
closest code word, as this would be the result of the fewest bit errors and
therefore has the highest probability of giving the correct result.
Keep in mind throughout this section that maximum-likelihood decoding
does not guarantee 100% accurate results; it guarantees only results with the highest probability of being accurate.
To determine the “closest” code word, we need to define what we mean by the
distance between binary n-tuples. Hamming distance, defined here, is named for
Richard W. Hamming, an American mathematician who pioneered the study of
error-detecting and error-correcting codes in 1950.
Definition hAMMinG DistAnCE
Let X and Y be binary n-tuples. The hamming distance between X and Y,
H(X, Y ), is the number of components in which X and Y differ. The minimum
distance of a code is the minimum Hamming distance between all possible pairs
of distinct code words.
PrACtiCe 38 For X = 01011 and Y = 11001, what is H(X, Y )?
■
Each error that occurs in the transmission of a code word adds one unit to the
Hamming distance between that code word and the received word. Suppose we
picture the code words as specific binary n-tuples distinguished from the set S of
all binary n-tuples, as in Figure 9.1. Suppose also that the minimum distance of
the code is at least d + 1. Then any time a code word X is corrupted by d or fewer
errors, it will be changed to an n-tuple X ′ that is not another code word, and the
occurrence of errors can be detected. Conversely, if any combination of d or fewer
errors can be detected, code words must be at least d + 1 apart.
d + 1
S
figure 9.1