In the Data Link Layer of computer networks, block coding adds controlled redundancy so that transmission errors can be detected and, in some schemes, corrected before data is delivered upward.2 A source message is divided into $k$-bit datawords and each dataword is mapped to an $n$-bit codeword with $n>k$. The added $r=n-k$ bits carry no new payload information, but they create structure in the code space that helps the receiver recognize corruption.2

A central metric in this structure is the Hamming distance, defined as the number of differing bit positions between two binary words of equal length.2 For binary vectors $x$ and $y$, it can be computed by XOR and bit counting:

$$d(x,y)=w(x\oplus y),$$

where $w(\cdot)$ is the number of $1$s in the result, also called the Hamming weight.2 The design quantity that matters most is the minimum Hamming distance $d_{min}$, because it determines how many errors the code can reliably detect or correct.3

In network-theory context, block coding is not merely abstract algebra: it expresses the tradeoff among reliability, bandwidth efficiency, and decoder complexity. A higher code rate $k/n$ preserves more bandwidth, while a larger $d_{min}$ improves resilience to noise. This section develops the mapping from datawords to codewords, the difference between error detection and error correction, the geometry of Hamming space, and the formal results

$$d_{min}=s+1 \qquad\text{and}\qquad d_{min}=2t+1,$$

which characterize guaranteed detection of $s$ errors and guaranteed correction of $t$ errors.3

Footnotes

1. Data Link Layer - Akshay Jain - Lecture notes covering block coding, Hamming distance, minimum distance, and detection/correction conditions. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Data Link Layer - Data link layer notes explaining datawords, codewords, redundancy, and minimum-distance rules. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Introduction to binary block codes - MIT material on Hamming space, spheres, and geometric interpretation of block codes. ↩

4. Minimum Hamming Distance - GeeksforGeeks - Accessible explanation of Hamming weight, Hamming distance, and examples. ↩ ↩²

5. Codewords and Hamming Distance • Error Detection: parity - MIT - MIT notes summarizing how minimum distance determines detectable and correctable errors. ↩ ↩² ↩³

Block Coding Model

A block code can be described as an $(n,k)$ scheme: each $k$-bit dataword is transformed into an $n$-bit codeword, where $n=k+r$ and $r$ is the number of redundant bits. Because there are $2^k$ possible datawords, an encoder must assign one valid codeword to each of those $2^k$ inputs. Not every $n$-bit word is valid; only the selected set of codewords belongs to the code. This restriction is what makes error detection possible.2

For example, consider a simple $(3,2)$ code:

Only four of the eight possible $3$-bit patterns are valid. If the receiver gets $001$, it can immediately declare an error because $001$ is not one of the legal codewords. This is the essence of error detection.

A stronger code may also support error correction by choosing the valid codeword nearest to the received word in Hamming distance.2 In that case, codewords must be separated more widely so that the “regions of influence” around them do not overlap.2

A useful rate measure is

$$\text{Code rate}=\frac{k}{n},$$

which quantifies efficiency. Higher redundancy lowers rate but can increase $d_{min}$ and therefore reliability.

Footnotes

1. Data Link Layer - Data link layer notes explaining datawords, codewords, redundancy, and minimum-distance rules. ↩ ↩² ↩³ ↩⁴

2. Data Link Layer - Akshay Jain - Lecture notes covering block coding, Hamming distance, minimum distance, and detection/correction conditions. ↩ ↩² ↩³

3. Codewords and Hamming Distance • Error Detection: parity - MIT - MIT notes summarizing how minimum distance determines detectable and correctable errors. ↩ ↩²

4. Introduction to binary block codes - MIT material on Hamming space, spheres, and geometric interpretation of block codes. ↩

Worked Examples of Hamming Distance

Let us compute distances directly.

Example 1
For $x=000$ and $y=011$:

$$x\oplus y = 000\oplus 011 = 011$$

The XOR result has two $1$s, so

$$d(000,011)=2.$$

This example is standard in block-coding discussions.2

Example 2
For $x=10101$ and $y=11110$:

$$10101\oplus 11110 = 01011$$

The XOR result contains three $1$s, hence

$$d(10101,11110)=3.$$

Again, the distance equals the number of differing bit positions.2

Example 3
For $x=1100101$ and $y=1001100$:

$$1100101\oplus 1001100 = 0101001$$

The XOR result has three $1$s, so

$$d(1100101,1001100)=3.$$

For an entire code, we calculate all pairwise distances among valid codewords and choose the smallest. That smallest value is $d_{min}$.2 If a code has codewords $\{000,011,101,110\}$, the pairwise distances are all $2$, so

$$d_{min}=2.$$

In this code, every valid codeword is separated from every other valid codeword by at least two bit changes, so any single-bit corruption moves a transmitted codeword to an invalid word rather than another valid one.

Footnotes

1. Data Link Layer - Akshay Jain - Lecture notes covering block coding, Hamming distance, minimum distance, and detection/correction conditions. ↩ ↩² ↩³

2. Data Link Layer - Data link layer notes explaining datawords, codewords, redundancy, and minimum-distance rules. ↩ ↩² ↩³ ↩⁴

Minimum Hamming Distance and Its Meaning

The minimum distance $d_{min}$ is the most important design parameter of a block code because the worst-separated pair of valid codewords determines the code’s guaranteed performance.2 Formally, if $C$ is the set of valid codewords, then

$$d_{min}=\min_{\substack{x,y\in C\\x\ne y}} d(x,y).$$

Interpretation:

• If valid codewords are too close, a small number of bit flips may transform one valid codeword into another, making reliable detection impossible.
• If valid codewords are far apart, more corruption is needed before ambiguity arises.2

A classic relation states:

• To detect up to $s$ errors in all cases, a code must satisfy $$d_{min}\ge s+1.$$
• To correct up to $t$ errors in all cases, a code must satisfy $$d_{min}\ge 2t+1.$$

These are often written in exact guaranteed-capability form as

$$s=d_{min}-1 \qquad\text{and}\qquad t=\left\lfloor\frac{d_{min}-1}{2}\right\rfloor.$$

The equalities $d_{min}=s+1$ and $d_{min}=2t+1$ describe the threshold values for exact guaranteed detection and correction limits.2

This explains familiar cases:

The correction count grows more slowly because correction requires not only noticing that an error occurred, but deciding which original codeword was sent.2

Footnotes

1. Data Link Layer - Akshay Jain - Lecture notes covering block coding, Hamming distance, minimum distance, and detection/correction conditions. ↩ ↩² ↩³ ↩⁴

2. Data Link Layer - Data link layer notes explaining datawords, codewords, redundancy, and minimum-distance rules. ↩

3. Codewords and Hamming Distance • Error Detection: parity - MIT - MIT notes summarizing how minimum distance determines detectable and correctable errors. ↩ ↩² ↩³

4. Introduction to binary block codes - MIT material on Hamming space, spheres, and geometric interpretation of block codes. ↩

Geometric View: Hamming Space, Spheres, and Decoding Regions

All binary words of length $n$ can be viewed as points in an $n$-dimensional Hamming space.2 Valid codewords occupy selected points in this space, and the Hamming distance measures how many coordinate changes are needed to move from one point to another.

For correction, we imagine a Hamming sphere of radius $t$ around each valid codeword. Every received word inside that sphere is decoded to the center codeword.2 To guarantee correction of $t$ errors, spheres of radius $t$ around distinct codewords must not overlap. If they overlapped, some received word would be within distance $t$ of two different codewords, causing ambiguity.2

For detection only, overlap is not the issue. Instead, we need every pattern of up to $s$ bit errors to move the transmitted codeword outside the set of all valid codewords.2 Therefore, no two codewords may be closer than $s+1$.

This geometric picture is especially valuable because it turns an algebraic rule into an intuitive one:

• Detection means corrupted words should not land on another legal codeword.
• Correction means corrupted words should remain closest to the true codeword.2

Footnotes

1. Introduction to binary block codes - MIT material on Hamming space, spheres, and geometric interpretation of block codes. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Hamming Metric and the Minimum Distance - UCSD notes providing proof ideas for correction capability via triangle inequality and Hamming spheres. ↩ ↩² ↩³

3. Data Link Layer - Akshay Jain - Lecture notes covering block coding, Hamming distance, minimum distance, and detection/correction conditions. ↩ ↩²

4. Data Link Layer - Data link layer notes explaining datawords, codewords, redundancy, and minimum-distance rules. ↩

5. Codewords and Hamming Distance • Error Detection: parity - MIT - MIT notes summarizing how minimum distance determines detectable and correctable errors. ↩

Network-Theory Interpretation

Within the data link layer, block coding supports reliable frame delivery across imperfect physical media.2 Although many practical systems use specialized error-detecting codes such as CRC for frame checking, the theory of block coding and Hamming distance provides the mathematical foundation for understanding why redundancy works at all.2 The key ideas transfer broadly:

• legal patterns are separated in code space,
• channel noise perturbs transmitted patterns,
• receiver logic exploits structure to detect or correct perturbations.2

From a design perspective, block coding creates a tradeoff:

$$\text{More redundancy} \Rightarrow \text{lower rate } \frac{k}{n} \Rightarrow \text{potentially larger } d_{min} \Rightarrow \text{better reliability}.$$

This is why coding theory sits naturally inside network performance analysis: it connects bandwidth, noise tolerance, and decoding certainty.

A concise summary is:

For this module, you should be able to compute distances between binary sequences, determine $d_{min}$ from a codebook, and prove or apply the thresholds for detection and correction.3

Footnotes

1. Data Link Layer - Akshay Jain - Lecture notes covering block coding, Hamming distance, minimum distance, and detection/correction conditions. ↩ ↩² ↩³

2. Data Link Layer - Data link layer notes explaining datawords, codewords, redundancy, and minimum-distance rules. ↩ ↩² ↩³

3. Introduction to binary block codes - MIT material on Hamming space, spheres, and geometric interpretation of block codes. ↩

4. Codewords and Hamming Distance • Error Detection: parity - MIT - MIT notes summarizing how minimum distance determines detectable and correctable errors. ↩ ↩² ↩³