Ferkans — Interactive Telecom Tutor

Definition:
Block Code

An $(n, k)$ binary block code $\mathcal{C}$ is a set of $2^k$ binary codewords, each of length $n$ bits. The code maps a $k$ -bit message $\mathbf{u} \in \{0,1\}^k$ to an $n$ -bit codeword $\mathbf{c} \in \{0,1\}^n$ .

The code rate is $R_c = k/n$ , representing the fraction of bits that carry information. The remaining $n - k$ bits provide redundancy for error detection and correction.

A code is linear if the sum (modulo 2) of any two codewords is also a codeword. All codes discussed in this chapter are linear.

Definition:
Generator Matrix and Parity-Check Matrix

For a linear $(n, k)$ code, the generator matrix $\mathbf{G}$ is a $k \times n$ binary matrix such that every codeword is

$\mathbf{c} = \mathbf{u} \mathbf{G} \pmod{2}$

The parity-check matrix $\mathbf{H}$ is an $(n-k) \times n$ binary matrix satisfying

$\mathbf{H} \mathbf{c}^T = \mathbf{0} \pmod{2}$

for every codeword $\mathbf{c} \in \mathcal{C}$ . The matrices are related by $\mathbf{G} \mathbf{H}^T = \mathbf{0}$ .

In systematic form, $\mathbf{G} = [\mathbf{I}_k \mid \mathbf{P}]$ and $\mathbf{H} = [-\mathbf{P}^T \mid \mathbf{I}_{n-k}]$ (over $\mathrm{GF}(2)$ , $-1 = 1$ ).

The syndrome $\mathbf{s} = \mathbf{H} \mathbf{r}^T$ of a received word $\mathbf{r}$ identifies the error pattern. If $\mathbf{s} = \mathbf{0}$ , either no errors occurred or the error pattern is an undetectable codeword.

Definition:
Hamming Distance

The Hamming distance $d(\mathbf{c}_i, \mathbf{c}_j)$ between two binary vectors is the number of positions in which they differ:

$d(\mathbf{c}_i, \mathbf{c}_j) = \|\mathbf{c}_i \oplus \mathbf{c}_j\|_H = \sum_{\ell=1}^{n} (c_{i,\ell} \oplus c_{j,\ell})$

The minimum distance of the code is

$d_{\min} = \min_{\mathbf{c}_i \neq \mathbf{c}_j \in \mathcal{C}} d(\mathbf{c}_i, \mathbf{c}_j)$

For a linear code, $d_{\min}$ equals the minimum Hamming weight (number of ones) among all non-zero codewords.

Theorem: Error Detection and Correction Capability

A code with minimum distance $d_{\min}$ can:

Detect up to $d_{\min} - 1$ errors.
Correct up to $t = \lfloor (d_{\min} - 1) / 2 \rfloor$ errors.

Equivalently, a code can correct $t$ errors if and only if $d_{\min} \geq 2t + 1$ .

If all codewords are at least $d_{\min}$ apart, then $t$ errors move a codeword to a point that is still closer to the original codeword than to any other, provided $t < d_{\min}/2$ . The decoder picks the nearest codeword and recovers the original.

Proof

Detection capability

An error pattern of weight $e \leq d_{\min} - 1$ cannot transform one codeword into another (since codewords are at least $d_{\min}$ apart), so the error is always detectable.

Correction capability

If $e \leq t = \lfloor (d_{\min}-1)/2 \rfloor$ , then the received word $\mathbf{r}$ satisfies $d(\mathbf{r}, \mathbf{c}_{\text{sent}}) = e \leq t$ , while for any other codeword $\mathbf{c}'$ :

$d(\mathbf{r}, \mathbf{c}') \geq d_{\min} - e \geq d_{\min} - t > t$

by the triangle inequality. Hence the nearest-codeword decoder uniquely recovers $\mathbf{c}_{\text{sent}}$ . $\blacksquare$

,

Hamming Sphere Packing Geometry

Visualises the geometric intuition behind error correction: codewords are points separated by minimum distance

d_{\min}

, and Hamming spheres of radius

t

around each codeword must be disjoint for unique decoding.

Error correction as sphere packing: the decoder maps any received word to the nearest codeword within its Hamming sphere.

Hamming Code Error Correction Demo

Explore how $(n, k)$ Hamming codes detect and correct errors. Adjust the code parameters to see the generator matrix, parity-check matrix, minimum distance, and a simulation of error correction performance.

Parameters

Code length n7

Information bits k4

Example: The (7, 4) Hamming Code

The $(7, 4)$ Hamming code has the systematic generator matrix

$\mathbf{G} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}$

(a) Find the parity-check matrix $\mathbf{H}$ .

(b) Determine $d_{\min}$ and the error-correcting capability.

(c) Encode the message $\mathbf{u} = [1\; 0\; 1\; 1]$ and decode the received word $\mathbf{r} = [1\; 0\; 1\; 1\; 1\; 0\; 0]$ (which has a single bit error).

Solution

Parity-check matrix

From $\mathbf{G} = [\mathbf{I}_4 \mid \mathbf{P}]$ , we get $\mathbf{H} = [\mathbf{P}^T \mid \mathbf{I}_3]$ :

$\mathbf{H} = \begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}$

Minimum distance

The minimum-weight non-zero codeword has weight 3 (e.g., $\mathbf{u} = [1\; 0\; 0\; 0] \to \mathbf{c} = [1\; 0\; 0\; 0\; 1\; 1\; 0]$ with weight 3). Hence $d_{\min} = 3$ and $t = 1$ : the code corrects any single-bit error.

Encoding and decoding

Encoding: $\mathbf{c} = \mathbf{u}\mathbf{G} = [1\; 0\; 1\; 1\; 1\; 0\; 0] \oplus [0\; 0\; 0\; 0\; 0\; 0\; 0] = [1\; 0\; 1\; 1\; 1\; 1\; 0]$ .

Actually computing row by row mod 2: $\mathbf{c} = [1\;0\;1\;1] \mathbf{G} = [1\; 0\; 1\; 1\; 1\; 0\; 0]$ (mod 2).

Wait — let us compute carefully: Row 1: $[1\;0\;0\;0\;1\;1\;0]$ , Row 3: $[0\;0\;1\;0\;1\;0\;1]$ , Row 4: $[0\;0\;0\;1\;1\;1\;1]$ . Sum mod 2: $[1\;0\;1\;1\;1\;0\;0]$ .

Syndrome: $\mathbf{s} = \mathbf{H}\mathbf{r}^T$ . With $\mathbf{r} = [1\;0\;1\;1\;1\;0\;0]$ ... but this equals $\mathbf{c}$ , so $\mathbf{s} = \mathbf{0}$ — no error detected.

Suppose instead $\mathbf{r} = [1\;0\;1\;1\;0\;0\;0]$ (error in position 5). Then $\mathbf{s} = \mathbf{H}\mathbf{r}^T = [1\;0\;0]^T$ , which is column 5 of $\mathbf{H}$ . The decoder flips bit 5, recovering $\mathbf{c}$ . $\blacksquare$

Definition:
Coding Gain

The coding gain $\gamma_c$ of a code is the reduction in $E_b/N_0$ (in dB) required to achieve a target BER compared to uncoded transmission:

$\gamma_c = \left.\frac{(E_b/N_0)_{\text{uncoded}}}{(E_b/N_0)_{\text{coded}}}\right|_{\text{same BER}}$

For a binary code with rate $R_c$ and minimum distance $d_{\min}$ , the asymptotic coding gain (at high SNR) is

$\gamma_c \approx R_c \cdot d_{\min}$

In dB: $\gamma_c\,(\text{dB}) = 10\log_{10}(R_c \cdot d_{\min})$ .

Soft-decision decoding provides approximately 2-3 dB additional coding gain compared to hard-decision decoding, effectively doubling $d_{\min}$ in terms of effective Euclidean distance.

Quick Check

A linear block code has minimum distance $d_{\min} = 7$ . How many errors can it correct?

2

3

6

7

Correction:

3

$t = \lfloor (d_{\min}-1)/2 \rfloor = \lfloor 6/2 \rfloor = 3$ . The code can correct any pattern of 3 or fewer errors.

Common Mistake: Hard vs. Soft Decision Decoding

Mistake:

Using hard-decision decoding (quantising channel output to 0/1 before decoding) and expecting the same performance as soft-decision decoding.

Correction:

Hard-decision decoding discards reliability information from the channel. Soft-decision decoding uses the actual channel output values (e.g., LLRs) and achieves approximately 2-3 dB better performance. For the AWGN channel, this difference stems from the fact that hard decisions lose $10\log_{10}(\pi/2) \approx 2$ dB of information at the quantiser.

Modern systems (turbo, LDPC, polar codes) universally use soft-decision decoding.

Hard vs. Soft Decision Decoding

Property	Hard Decision	Soft Decision
Input to decoder	Binary bits (0 or 1)	Real-valued LLRs or channel outputs
Information preserved	Only bit identity	Bit identity + reliability
Typical coding gain loss	Reference (0 dB)	2-3 dB better than hard
Decoder complexity	Lower	Higher (real-valued arithmetic)
Example algorithms	Syndrome decoding, algebraic	Viterbi (soft), BCJR, belief propagation
Used in modern systems	Rarely	Universally (turbo, LDPC, polar)

Historical Note: Richard Hamming and Error-Correcting Codes (1950)

1950

Richard Hamming, working at Bell Labs, developed the first error-correcting codes in 1950 after becoming frustrated with unreliable relay-based computers that would discard his weekend computing jobs when a single bit error occurred. He asked: "If the machine can detect an error, why can't it locate the position of the error and correct it?" His $(7, 4)$ Hamming code — the first single-error-correcting code — launched the field of coding theory. He also introduced the concepts of Hamming distance and Hamming weight that remain fundamental today.

Key Takeaway

The minimum Hamming distance $d_{\min}$ is the single most important parameter of a block code: it determines the error-correcting capability ( $t = \lfloor (d_{\min}-1)/2 \rfloor$ ), the asymptotic coding gain ( $\gamma_c = R_c \cdot d_{\min}$ ), and on fading channels, the diversity order. Soft-decision decoding recovers 2-3 dB that hard-decision decoding discards at the quantiser.

⚠️Engineering Note

Finite-Precision LLR Representation

In hardware implementations, log-likelihood ratios (LLRs) are represented with finite precision (typically 5-8 bits for the integer + fractional parts). This introduces quantisation effects:

Saturation: Large-magnitude LLRs are clipped, losing information about very reliable bits. Typical clipping range is $[-8, +8]$ or $[-16, +16]$ .
Granularity: Small LLR differences are rounded, affecting decoder convergence for marginal bits.
Performance impact: Moving from floating-point to 6-bit fixed-point typically costs 0.05-0.1 dB; moving to 4-bit costs 0.2-0.5 dB.

The scale factor between channel LLRs and decoder internal precision must be carefully chosen — too small clips reliable bits, too large wastes resolution on unreliable bits.

Practical Constraints

•
LLR quantisation typically 5-8 bits in hardware decoders
•
Clipping range must balance saturation vs. resolution
•
4-bit quantisation incurs 0.2-0.5 dB loss; 6-bit costs < 0.1 dB

Block Code

A mapping from $k$ -bit messages to $n$ -bit codewords ( $n > k$ ). A linear block code forms a $k$ -dimensional subspace of $\{0,1\}^n$ under modulo-2 arithmetic.

Hamming Distance

The number of positions in which two binary strings of equal length differ. The minimum Hamming distance of a code determines its error detection and correction capability.

Coding Gain

The reduction in required $E_b/N_0$ to achieve a given BER when using channel coding versus uncoded transmission. Measured in dB.

Related: Rate, Minimum Distance

Parity-Check Matrix

An $(n-k) \times n$ binary matrix $\mathbf{H}$ that defines a linear code as its null space: $\mathcal{C} = \{\mathbf{c} : \mathbf{H}\mathbf{c}^T = \mathbf{0}\}$ . Used for syndrome-based error detection and decoding.

Fundamentals of Error-Correcting Codes

Definition: Block Code

Definition: Generator Matrix and Parity-Check Matrix

Definition: Hamming Distance