Section 9.2 Coding Theory
719
Now suppose that the minimum distance of the code is at least 2d + 1. Then
any time a code word X is corrupted by d or fewer errors, the received word X ′
will be such that H(X, X ′) ≤ d but for any other code word Y, H(X ′, Y) ≥ d + 1.
Therefore X ′ will be correctly decoded as X, the closest code word. Conversely,
to correct any received word with d or fewer errors, the minimum distance of the
code must be at least 2d + 1 so that neighborhoods of radius d around code words
do not intersect (Figure 9.2).
S
2d + 1
figure 9.2
As a result, we see that a code is d-error detecting if and only if its minimum
distance is at least d + 1, and it is d-error correcting if and only its minimum
distance is at least 2d + 1. As one would expect, it requires a stronger condition
to correct errors than to merely detect them.
example 20
Suppose a code has a minimum distance of 6. It can then detect any combination
of ≤ 5 errors. It can correct any combination of ≤ 2 errors. If code words X and
Y are such that H(X, Y ) = 6, then there will be a word X ′ produced by 4 errors
on X that will be incorrectly decoded as Y; there will be a word X ″ produced by 3
errors on X that can be arbitrarily decoded correctly as X or incorrectly as Y. This
code is double-error correcting, 5-error detecting.
The set of code words will be a subset of the set of all binary n-tuples, Z
n
2 .
We want these code words to be sufficiently widely scattered in Z
n
2 so that the
minimum distance is large enough to allow some error correction. The minimum
distance of the code is easy to compute if the code words form a subgroup of the
group 3Z
n
2 , + 2 4. In this case we have a group code; the identity is the n-tuple of all
0s (we’ll call this 0 n ), and each code word is its own inverse. Denote by W(X ) the
weight of a code word X, meaning the number of 1s it contains.
tHeoRem on MiniMuM DistAnCE of GrouP CoDE
The minimum distance of a group code equals the minimum weight of all the
nonzero code words.
To prove this theorem, let d be the minimum distance of a group code; then
there are two distinct code words X and Y with H(X, Y ) = d. Because it’s a group
code, closure holds and X + 2 Y = Z is a code word. Z ∙ 0 because X and Y are
distinct. Z will have 1s in exactly those components where X and Y differ, so
719
Now suppose that the minimum distance of the code is at least 2d + 1. Then
any time a code word X is corrupted by d or fewer errors, the received word X ′
will be such that H(X, X ′) ≤ d but for any other code word Y, H(X ′, Y) ≥ d + 1.
Therefore X ′ will be correctly decoded as X, the closest code word. Conversely,
to correct any received word with d or fewer errors, the minimum distance of the
code must be at least 2d + 1 so that neighborhoods of radius d around code words
do not intersect (Figure 9.2).
S
2d + 1
figure 9.2
As a result, we see that a code is d-error detecting if and only if its minimum
distance is at least d + 1, and it is d-error correcting if and only its minimum
distance is at least 2d + 1. As one would expect, it requires a stronger condition
to correct errors than to merely detect them.
example 20
Suppose a code has a minimum distance of 6. It can then detect any combination
of ≤ 5 errors. It can correct any combination of ≤ 2 errors. If code words X and
Y are such that H(X, Y ) = 6, then there will be a word X ′ produced by 4 errors
on X that will be incorrectly decoded as Y; there will be a word X ″ produced by 3
errors on X that can be arbitrarily decoded correctly as X or incorrectly as Y. This
code is double-error correcting, 5-error detecting.
The set of code words will be a subset of the set of all binary n-tuples, Z
n
2 .
We want these code words to be sufficiently widely scattered in Z
n
2 so that the
minimum distance is large enough to allow some error correction. The minimum
distance of the code is easy to compute if the code words form a subgroup of the
group 3Z
n
2 , + 2 4. In this case we have a group code; the identity is the n-tuple of all
0s (we’ll call this 0 n ), and each code word is its own inverse. Denote by W(X ) the
weight of a code word X, meaning the number of 1s it contains.
tHeoRem on MiniMuM DistAnCE of GrouP CoDE
The minimum distance of a group code equals the minimum weight of all the
nonzero code words.
To prove this theorem, let d be the minimum distance of a group code; then
there are two distinct code words X and Y with H(X, Y ) = d. Because it’s a group
code, closure holds and X + 2 Y = Z is a code word. Z ∙ 0 because X and Y are
distinct. Z will have 1s in exactly those components where X and Y differ, so