Back to the on-screen lesson ·
(n, k) codes, rate, redundancy, repetition codes and their error probability.
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.
A binary $(n, k)$ block code maps each of the $2^k$ messages of $k$ bits to a distinct codeword of $n$ bits; the rate is $R = k/n$ and the $n - k$ extra bits are redundancy. The channel coding theorem promises that good codes exist at any rate below capacity; this unit builds concrete ones. The simplest is the repetition code: send each bit $m$ times and decode by majority. Over a $\text{BSC}(p)$ with $m = 3$ the decoded bit is wrong with probability $3p^2(1 - p) + p^3$, about $0.028$ at $p = 0.1$, a real improvement bought at rate $\tfrac{1}{3}$; but driving the error to zero needs $m \to \infty$ and the rate to zero, exactly what Shannon showed is unnecessary. A single parity bit appended to $k$ bits gives a $(k + 1, k)$ code of high rate that detects one error but corrects none. Between these extremes lie the codes of the coming lessons, judged by two numbers: the rate and the minimum distance that decides how many errors they detect and correct.
Another way: picture
The $2^n$ binary words as dots; the $2^k$ codewords highlighted, spread out. A transmitted codeword is jolted by noise to a nearby dot; if codewords are far apart the receiver can see which one it came from.
Another way: steps
An $(n, k)$ binary block code maps each of the $2^k$ messages to a distinct codeword of $n$ bits. Three numbers follow immediately: the rate $R = k/n$, the number of codewords $2^k$, and the redundancy $n - k$, the extra bits that carry no message. The $2^n - 2^k$ words that are not codewords are the whole point: a received word that is not a codeword announces that something went wrong.
| code | $n$ | $k$ | rate | redundancy $n - k$ | $d$ | what it does |
|---|---|---|---|---|---|---|
| uncoded | $1$ | $1$ | $1$ | $0$ | $1$ | nothing |
| $3$-repetition | $3$ | $1$ | $1/3$ | $2$ | $3$ | corrects $1$ |
| single parity | $5$ | $4$ | $4/5$ | $1$ | $2$ | detects $1$ |
| Hamming | $7$ | $4$ | $4/7$ | $3$ | $3$ | corrects $1$, detects $2$ |
| Hamming | $15$ | $11$ | $11/15$ | $4$ | $3$ | corrects $1$ at a better rate |
The repetition code is the honest baseline: send each bit $m$ times, decode by majority. Over a $\text{BSC}(p)$ with $m = 3$ the decoded bit is wrong when two or three of the three copies flip, $$P_e = 3p^2(1 - p) + p^3,$$ which is $0.028$ at $p = 0.1$ — a real improvement over $0.1$, bought at rate $\tfrac{1}{3}$.
| repetitions $m$ | rate | decoded-bit error on $\text{BSC}(0.1)$ | errors corrected |
|---|---|---|---|
| $1$ | $1$ | $0.1$ | $0$ |
| $3$ | $1/3$ | $0.028$ | $1$ |
| $5$ | $1/5$ | $0.0086$ | $2$ |
| $7$ | $1/7$ | $0.0027$ | $3$ |
| $m \to \infty$ | $\to 0$ | $\to 0$ | $\to \infty$ |
Read the last row of the table and you see the problem Shannon solved: repetition drives the error to zero only by driving the rate to zero. The channel coding theorem (lesson 15) says that is unnecessary — reliable codes exist at any fixed rate below capacity, which for $\text{BSC}(0.1)$ is $0.531$, far above $\tfrac{1}{3}$. The rest of this unit builds codes that do better than repetition at the same rate.
Common mistakes
Codewords $000$ and $111$; majority decoding fails on two or three flips: $3(0.1)^2(0.9) + (0.1)^3 = 0.027 + 0.001 = 0.028$.
Down from $0.1$.
Rate $\tfrac{1}{3}$; with $5$ repetitions the error drops to $0.0086$ at rate $\tfrac{1}{5}$: reliability bought with rate, the opposite of what capacity promises.
Append to $1011$ a bit making the number of ones even: $10111$. The $(5, 4)$ code has rate $0.8$.
One flip gives odd parity, detected; two flips give even parity again, missed; nothing can be corrected, since every non-codeword is one flip from several codewords.
Detects $1$, corrects $0$.
Rate $= 11/15 \approx 0.733$: eleven message bits per fifteen sent.
Codewords: $2^{11} = 2048$; words of length $15$: $2^{15} = 32768$.
Non-codewords: $32768 - 2048 = 30720$, and four redundant bits are what makes them exist.
This is the Hamming $[15, 11]$ code of lesson 20.
Two flips: $3 p^2 (1 - p) = 3 \cdot \tfrac{1}{36} \cdot \tfrac{5}{6} = \tfrac{15}{216}$.
Three ways to choose which two copies flip.
Three flips: $p^3 = \tfrac{1}{216}$.
$P_e = \tfrac{16}{216} = \tfrac{2}{27} \approx 0.074$, against $\tfrac{1}{6} \approx 0.167$ uncoded.
Rate $11/15 \approx 0.733$; $2^{11} = 2048$ codewords among $2^{15} = 32768$ words.
Four redundant bits per codeword; it is in fact a Hamming code that corrects one error.
A block code carries $9$ message bits in codewords of length $16$. What is its rate? Give a fraction.
Computed value: answer
An $(n, k) = (13, 10)$ binary block code: how many codewords does it have, and how many binary words of length $13$ are not codewords? Enter the number of non-codewords.
Computed value: answer
A $3$-repetition code sends each bit three times over a channel with bit error probability $1/7$ and decodes by majority. What is the probability that a decoded bit is wrong? Give a fraction.
Computed value: answer
A block code carries $11$ message bits in codewords of length $15$. What is its rate? Give a fraction.
Computed value: answer
What does the redundancy of a block code buy, and what does it cost?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
An $(n, k) = (13, 10)$ binary block code: how many codewords does it have, and how many binary words of length $13$ are not codewords? Enter the number of non-codewords.
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: a $(15, 11)$ code, step 2