Linear Block Codes

Fundamentals

An information source produces bits, segmented into messages of length $k$ ($2^k$ possible messages). Each message is encoded to $n$ bits, $n > k$: an $(n, k)$ code with $k$ message digits and $n - k$ parity check digits.

Over $\mathbb{F}_2$, $v = uG$, where $u \in \mathbb{F}_2^{1 \times k}$ is the message and $v \in \mathbb{F}_2^{1 \times n}$ the codeword.

$$G = [P \mid I_k], \qquad H = [I_{n-k} \mid P^T] \in \mathbb{F}_2^{(n-k) \times n}, \qquad GH^T = 0$$

so every codeword satisfies $vH^T = 0$.

Syndrome

A received word is $r = v + e$ with error pattern $e$. Its syndrome is

$$s = rH^T = eH^T$$

A single error in bit $i$ gives the $i$-th column of $H$. Select the $e$ with minimum weight for that syndrome, and the corrected codeword is $\hat{v} = r + e$.

Minimum Distance

$$d_{min} = \min_{v \neq w \in \mathcal{C}} d(v, w)$$

For linear codes, $d_{min}$ equals the minimum weight of a nonzero codeword, and the smallest number of columns of $H$ that sum to 0.

Error detection A block code detects all errors up to $d_{min} - 1$. For a BSC, with $A_i$ the number of codewords of weight $i$, the probability of not detecting errors is

$$P_u = \sum_{i = d_{min}}^{n} A_i p^i (1-p)^{n-i}$$

Error correction With $t$ the maximum number of errors the code can correct, $2t + 1 \le d_{min} \le 2t + 2$, so

$$t = \left\lfloor \frac{d_{min} - 1}{2} \right\rfloor, \qquad P_e \le \sum_{i = t+1}^{n} \binom{n}{i} p^i (1-p)^{n-i}$$

With standard array decoding on a BSC, $P_e = 1 - \sum_{i=0}^{n} \alpha_i p^i (1-p)^{n-i}$, where $\alpha_i$ is the number of coset leaders of weight $i$.

Standard Array and Syndrome Decoding

• Start with $e_1 = \vec{0}$, each column is a codeword.
• Select the next minimum-weight $e$ not yet in the array and add it to all the original codewords.
• There are $2^{n-k}$ coset leaders, and a coset leader is an error vector. All vectors with weight at most $t$ can be coset leaders.

Syndrome decoding Compute the syndrome of every coset leader, get the syndrome of the received message, and add $r + e$.

Hamming Codes

The columns of $H$ are all nonzero vectors in $\mathbb{F}_2^m$, $m \ge 2$.

$$n = 2^m - 1, \qquad k = 2^m - m - 1, \qquad n - k = m \text{ parity bits}, \qquad d_{min} = 3, \qquad t = 1$$

Perfect Codes

A code is perfect if every vector is within distance $t$ of exactly one codeword, i.e. there are no coset leaders of weight above $t$. Hamming codes are perfect.