A noisy channel can change a transmitted word. Redundancy helps only when the permitted words are sufficiently separated: otherwise the same received word could plausibly have come from two messages. We make that separation precise, then use linear algebra to locate a single error.
Definitions
Definition 1.1.1
(Hamming distance, weight and minimum distance)
For words , the Hamming distance is the number of coordinates in which they differ. The weight is the number of nonzero coordinates. Hence . A binary code is a nonempty subset of ; if it has at least two words, its minimum distance is
Distance satisfies the triangle inequality: at each coordinate where and differ, at least one of or differs. Counting coordinates gives .
Theorem 1.1.2
(Correction radius)
For a nonnegative integer , a code with at least two words corrects every pattern of at most errors by unique nearest-neighbor decoding if and only if .
Proof
(Disjoint balls, and a midpoint word when they meet)
Suppose , the codeword is sent and is received with . For any other codeword , the triangle inequality gives
So is the unique nearest codeword to . Conversely, if two codewords differ in positions, construct by changing of those positions in the first word to the corresponding values of the second. Then its distances to the two words are and , both at most . The word can arise from either codeword with at most errors, and a decoder outputs only one word, so no decoder can guarantee the right answer for both possible transmissions.
Proof X-ray
Where the factor two comes from
The forward direction uses the triangle inequality once, with the transmitted word as the middle point: the errors are subtracted from a separation of at least , and what remains, at least , still beats . The converse needs a received word that is simultaneously within of two codewords. The key move is to change of the differing positions, giving distances and . Both are at most exactly when , and such a exists exactly when ; the balanced choice always lies in that range. The hypothesis of at least two words matters only so that is defined; a one-word code needs no decoding.
For a nonnegative integer , detection has a different threshold: all nonzero patterns of at most changes are detected exactly when . The word may be detected as invalid without identifying the original word. For example the repetition code has distance three, detects two errors and corrects one; it cannot guarantee correction of two.
Theorem/proposition
Definition 1.1.3
(Linear code, generator and parity-check matrices, syndrome)
A binary linear code is a subspace ; an code has dimension and words. A generator matrix has rows forming a basis of , and a row message encodes as . A parity-check matrix satisfies . The syndrome of a received word is .
For a nonzero linear code, its minimum distance equals the smallest nonzero codeword weight: differences of distinct codewords are precisely nonzero codewords, and each nonzero codeword is a difference from zero. If is received, its syndrome is , independent of the transmitted codeword. Thus a table of likely error patterns can associate a syndrome with a correction. The syndrome alone does not establish which error actually occurred: multiple error patterns can share it.
Take the binary code whose parity-check matrix has as columns the seven distinct nonzero binary 3-vectors, ordered as
Its rank is three because the first three columns are the identity, so its kernel has dimension four. No weight-one word is in the kernel, because no column is zero; no weight-two word is in the kernel, because the columns are distinct. The first, second and fourth columns sum to zero, so is a codeword of weight three. Thus its minimum distance is exactly three and it corrects one error.
Worked example 1.1.4
(Correcting one error in the seven-bit code)
Suppose is received. Its syndrome is the sum of columns 1 and 4, namely , column 2. The single-error rule flips coordinate 2 and outputs . If two errors actually occurred, this rule can return a different codeword; the correction radius theorem promises correction only for at most one error.
Packing and a limit on parameters
The binary radius- ball has words: choose the coordinates to flip. Disjointness of these balls yields a bound on the size of any correcting code.
Theorem 1.1.5
(Hamming bound)
If a binary code of length corrects every pattern of at most errors, then
Proof
(Counting pairs of a codeword and a word in its ball)
Associate each pair consisting of a codeword and a word in its radius- ball with the latter word. The balls are disjoint: a word within of two codewords could arise from either of them, so it could not be decoded correctly for both. Hence different pairs cannot produce the same received word. There are pairs, and they inject into the possible received words.
For the example, : its radius-one balls partition the whole space. Equality is a counting fact here, not a promise that every error has weight at most one.
Quick check
(Can a binary code of length five with eight words correct every single error?)
Apply the Hamming bound with .
Solution · Answer
No. The Hamming bound would require , but .
Exercises
Quick check
(In the displayed seven-bit code, decode under the assumption of at most one error.)
Compute the syndrome and compare it with the columns of .
Solution · Answer
Its syndrome is column 3, . Flip coordinate 3 to obtain . This is a valid codeword, and the assumption together with minimum distance three makes it the unique possible transmitted word within distance one.
Why syndrome tables have limits
Counterexample mode
A syndrome does not identify every error
For any two error vectors , their syndromes agree exactly when , or equivalently . Thus errors in the same coset of are indistinguishable from syndrome information alone. For the seven-bit code, the errors and have the same syndrome. If the first occurs after transmitting zero, a single-error decoder instead flips the second coordinate and outputs . This is a valid codeword, but it is not the transmitted word. The calculation exhibits an actual two-error failure rather than merely asserting that failure might occur.
There are syndromes for a full-rank parity-check matrix, because the linear map is onto. Every syndrome class has vectors: if has a given syndrome, every vector in the class is uniquely with . A minimum-weight representative of each class is a coset leader. Correcting by subtracting such a representative is a nearest-codeword rule, because is a codeword exactly when has the same syndrome as , and its distance from is the weight of . If minimum-weight representatives tie, a deterministic choice may be made but a unique decoding guarantee does not follow.
Quick check
(Explain why two errors in the seven-bit example cannot have the same nonzero syndrome if both have weight one.)
What is the syndrome of a weight-one vector?
Solution · Answer
A weight-one vector has syndrome equal to the corresponding column of . All seven columns are distinct and nonzero, so the coordinate of a single error is determined. This statement does not cover errors of weight two or greater.
Worked examples
Theorem 1.1.6
(Minimum distance from dependent columns)
For a binary linear code containing a nonzero word, its minimum distance is the smallest number of columns of whose sum is zero. This statement counts selected columns by their positions, even when two columns happen to be equal.
Proof
(Multiplying by a word selects columns)
Multiplying by a binary column adds precisely those columns indexed by the nonzero entries of . Therefore exactly when those selected columns sum to zero, and the number selected is the weight of . Taking the minimum over nonzero gives the claim, since the minimum distance of a linear code is its smallest nonzero weight.
This criterion is practical because it replaces a search through all codewords with questions about column dependence. A zero column gives a weight-one codeword; two equal columns give a weight-two codeword. Conversely, if every set of fewer than columns is independent, no nonzero codeword has weight below . To conclude the minimum distance is exactly , however, one must also exhibit a dependent set of columns. For the displayed seven-bit matrix, the first three columns are independent, but the first, second and fourth sum to zero.
Concept lensCombinatorial
Weight-three codewords as lines of the Fano plane
Read the seven columns of as the seven points of the Fano plane, whose lines are the triples of distinct nonzero vectors in . By the theorem above, a weight-three codeword is exactly a set of three distinct columns with zero sum, that is, a line. Each line contains three of the pairs of points and each pair lies on one line, so there are lines and exactly codewords of weight three. The codeword is the line .
Common mistake
(Checking one set of columns instead of all of them)
It would be wrong to infer distance four from the independence of only the first three columns of the seven-bit matrix: all triples must be considered to rule out weight three, and the triple of columns 1, 2 and 4 is dependent.
Worked example 1.1.7
(A single overall parity check)
Consider the parity-check matrix . Its kernel consists of even-weight binary four-vectors. It has dimension three, because the single row is nonzero, and distance two: no column is zero, while any two columns sum to zero. For example, and are distance two apart. This code detects any single error but cannot uniquely correct every single error. Receiving is equally compatible with transmitting and flipping coordinate 1, or transmitting and flipping coordinate 2.
The code also illustrates the distinction between a parity check and an error location. Its single-bit syndrome says whether the received word has odd weight. A nonzero syndrome reveals that an odd number of flips occurred, but says nothing about which of the four coordinates was flipped. An even number of flips can give zero syndrome, so an accepted word is not proof that no error occurred.
Counting the decoding balls carefully
For a word , its radius- ball consists of all words differing from it in at most coordinates. If , there are exactly words at distance , because a binary coordinate has exactly one alternative value. Summing over gives the ball size in the Hamming bound. For the ball is the whole space and the sum may instead be stopped at .
Meeting the Hamming bound with equality means that the balls cover the space, but it does not imply an arbitrary high-weight error is corrected. In the seven-bit example every received word belongs to exactly one ball of radius one; a word produced by two errors falls in some ball, but its center may be the wrong transmitted word.
Quick check
(Let a binary linear code have parity-check columns . Determine its dimension and minimum distance.)
Find the rank of , then the fewest columns summing to zero.
Solution · Answer
The first two columns show that the matrix has rank two, so the kernel dimension is . There is no zero column, excluding weight one. The third and fourth columns agree, so selecting them yields the weight-two codeword . The minimum distance is therefore two. The conclusion uses both a lower bound and an attained example.
Constructing a check matrix from a generator
A generator matrix in systematic form gives a particularly transparent parity-check matrix over the binary field:
Indeed, because the characteristic is two, so every generated word lies in . The identity block makes have rank , and rank-nullity gives its kernel dimension . The row space of also has dimension , since is a block of . The inclusion between these equal-dimensional spaces is consequently equality. The plus sign here relies on characteristic two; over a general field the appropriate matrix is .
Worked example 1.1.8
(Check matrix of a code)
Let . Here , so . Its kernel is the set of even-weight binary triples. The generator rows are independent, and the four codewords are . The nonzero weights are all two, so the minimum distance is two. A single parity-check bit adds redundancy and detects one error, but by the correction radius theorem it cannot correct all single errors.
Common mistakes
Common mistake
(One pair at distance three does not prove distance three)
Minimum distance is a property of the entire code, not of one selected pair of words. A single pair at distance three proves only that the minimum is at most three; to prove equality, rule out all smaller distances as well. For a linear code this lower-bound problem can be simplified by considering nonzero weights, but that shortcut depends on closure under subtraction and is not valid for arbitrary subsets.
Common mistake
(Zero syndrome does not mean no error)
A nonzero syndrome certifies that the received word is not a codeword, but zero syndrome only certifies membership in the code. An undetected error may carry one codeword to another. In particular, adding any nonzero codeword to a transmitted codeword gives another codeword, so its syndrome is zero. Whether such an event is likely depends on the channel model, which has not been specified here.