Back to the on-screen lesson ·
Detecting d − 1 and correcting ⌊(d − 1)/2⌋ errors by nearest-codeword decoding.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to describe a binary block code by its length, dimension and rate, count its codewords and its redundant bits, analyse the repetition and single-parity codes and compute the error probability of majority decoding, and explain why redundancy is what makes error control possible. You will compute Hamming distances, define the minimum distance of a code, and prove from the triangle inequality that a code with minimum distance $d$ detects up to $d - 1$ errors and corrects up to $\lfloor (d - 1)/2 \rfloor$ by nearest-codeword decoding.
The Hamming distance $d(x, y)$ between two words of the same length is the number of positions in which they differ; it is a metric, so the triangle inequality holds. The minimum distance $d$ of a code is the smallest distance between two distinct codewords. It decides everything about error handling. Detection: fewer than $d$ errors can never carry one codeword onto another, so any pattern of up to $d - 1$ errors is detected. Correction: nearest-codeword decoding is right whenever the number of errors $t$ satisfies $2t < d$, that is $t \le \lfloor (d - 1)/2 \rfloor$, because by the triangle inequality every other codeword is then farther away; equivalently, the Hamming balls of radius $t$ around the codewords are disjoint. A code with $d = 3$ corrects one error, $d = 5$ corrects two, $d = 7$ corrects three. The $3$-repetition code has $d = 3$, the parity-bit code $d = 2$. A code with parameters $(n, k, d)$ is the object the rest of the unit constructs and bounds.
Another way: picture
Two codewords $d = 5$ apart on a line of positions. Around each, a ball of radius $2$: the balls do not touch, so a word with two errors is decoded to its own codeword. A word with three errors falls into the other ball and is decoded wrongly, though a word with up to four errors is at least seen to be damaged.
Another way: steps
The Hamming distance $d(x, y)$ counts the positions where two words of the same length differ — XOR them and count the ones. It is a metric, so the triangle inequality $d(x, z) \le d(x, y) + d(y, z)$ holds, and that single inequality is what turns distance into error correction. The minimum distance $d$ of a code is the smallest distance between two distinct codewords, and it fixes both capabilities:
| $d$ | errors detected $d - 1$ | errors corrected $\lfloor (d-1)/2 \rfloor$ | example |
|---|---|---|---|
| $2$ | $1$ | $0$ | single parity |
| $3$ | $2$ | $1$ | Hamming, $3$-repetition |
| $4$ | $3$ | $1$ | extended Hamming |
| $5$ | $4$ | $2$ | $5$-repetition |
| $7$ | $6$ | $3$ | Golay $[23, 12, 7]$ |
Detection: fewer than $d$ errors can never carry one codeword onto another, so every pattern of up to $d - 1$ errors leaves a non-codeword and is noticed. Correction: nearest-codeword decoding is right whenever $2t < d$. The proof is one line of the triangle inequality. Let $c$ be sent, $r$ received with $d(r, c) \le t$, and $c'$ any other codeword. Then $$d(r, c') \ge d(c, c') - d(r, c) \ge d - t > 2t - t = t \ge d(r, c),$$ so $c$ is strictly nearer than every rival and the decoder picks it.
The same fact drawn: balls of radius $t$ around the codewords do not overlap when $2t < d$, so every word inside a ball decodes to its centre. Note the trade: a code can either detect $d - 1$ errors or correct $\lfloor (d-1)/2 \rfloor$, and correction costs about twice the distance detection does, because the decoder must not merely notice the damage but name it.
Common mistakes
$d(1011010, 1001110)$: positions $3$ and $5$ differ, distance $2$.
Count the differing positions.
A code whose closest pair is at distance $5$ detects $4$ errors and corrects $\lfloor 4/2 \rfloor = 2$.
Received $r$ with $d(r, c) \le t$ for the sent codeword $c$; for any other codeword $c'$, $d(c, c') \ge d > 2t$.
Triangle inequality: $d(r, c') \ge d(c, c') - d(r, c) > 2t - t = t \ge d(r, c)$, so $c$ is the unique nearest codeword.
Compare position by position: they agree on $1$ and $2$, differ on $3$, $4$ and $5$.
XOR: $11100 \oplus 11011 = 00111$, which has weight $3$.
The weight of the XOR is the distance.
$d = 3$: a code whose closest pair is this far apart corrects one error.
Detection: $d - 1 = 6$ errors, since seven could land on another codeword.
Correction: $\lfloor 6/2 \rfloor = 3$ errors.
$2 \cdot 3 = 6 < 7$, so the balls of radius $3$ are disjoint.
The Golay $[23, 12, 7]$ code is exactly this case, and its balls tile the space (lesson 21).
Detects $6$ errors.
Corrects $\lfloor 6/2 \rfloor = 3$ errors.
What is the Hamming distance between $101010$ and $101010$?
Computed value: answer
A code has minimum distance $d = 6$. Up to how many errors per codeword can it correct?
Computed value: answer
A code has minimum distance $10$. Up to how many errors per codeword is it guaranteed to detect?
Computed value: answer
What is the Hamming distance between $1011010$ and $1001110$?
Computed value: answer
A code has minimum distance $7$ and a received word lies at Hamming distance $3$ from codeword $c$. Why is nearest-codeword decoding to $c$ guaranteed correct?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A code has minimum distance $d = 7$. Up to how many errors per codeword can it correct?
Computed value: answer
You can size a block code and read its error-handling power off its minimum distance. Next: linear codes, where a matrix does the encoding and another does the checking.
9. Your turn: $d = 7$, step 2