Error control formulas

Fraction of transmitted bits that carry message information; $0<R<1$ for an $(n,k)$ block code, since $n>k$.

A code with minimum distance $d_{min}$ is guaranteed to detect every pattern of up to $d_{min}-1$ bit errors, when it is used for detection only.

Guaranteed number of correctable errors when the receiver decodes to the nearest codeword (the spheres of radius $t$ around codewords do not overlap).

With this distance the decoder corrects every pattern of up to $t$ errors and, at the same time, detects (flags without miscorrecting) every pattern of $t+1$ up to $s$ errors. Here $s$ is a total number of errors, not extra errors.

Row vector $\mathbf{m}$ (length $k$) times $G$ gives the codeword $\mathbf{c}$ (length $n$), all operations modulo 2.

Message bits appear unchanged in the first $k$ positions of the codeword; $P$ is $k\times (n-k)$. Over GF(2), $-P^T=P^T$.

$H$ is $(n-k)\times n$. A word is a codeword exactly when every parity check is satisfied.

$\mathbf{s}=0$ means $\mathbf{r}$ is a valid codeword (no detectable error). A nonzero $\mathbf{s}$ means an error occurred.

Any binary $(n,k)$ code that corrects every pattern of up to $t$ errors must satisfy this: the $2^{n-k}$ syndromes must label every correctable error pattern, including the no-error pattern. A code that meets it with equality is called perfect.

Smallest $r$ that lets $m$ data bits be protected against any single error: the $r$ check bits must label the $m+r$ error positions plus the no-error case.

Full-length Hamming code, $r\ge 2$. Correct one error, or detect two (not both together). Since $1+n=2^r$, it meets the Hamming bound with $t=1$ exactly, so Hamming codes are perfect.

Probability that a block has more than $t$ errors. It is exactly the probability of not decoding the block correctly for a decoder that corrects every pattern of up to $t$ errors and no other (for example a Hamming code, $t=1$); for a decoder that also corrects some heavier patterns it is an upper bound.

For a linear code used for detection only: an error goes undetected exactly when the error pattern is itself a nonzero codeword. $A_i$ is the number of codewords of weight $i$.

Append $r$ zeros to the message, divide by $g(x)$ using XOR (no borrow), and the remainder $R(x)$ replaces the zeros. The transmitted word $T(x)$ is exactly divisible by $g(x)$.