Error Control Coding

Hamming Distance, Minimum Hamming Distance & Linear Block

Codes

Instructor Reference Textbook

Md. Mahedi Hassan Senior Data Communications and
Lecturer Dept. of Software Networking Behrouz A. Forouzan
Engineering Daffodil International Chapter 10: Error Detection &
University Correction
Learning Objectives
By the end of this lecture, students will be able to:

01

Define Hamming Distance

Calculate the Hamming distance between any two codewords using the XOR
method as described by Forouzan.

02

Determine Minimum Hamming Distance

Find the minimum Hamming distance for a set of codewords and relate it to error
detection and correction capacity.

03

Analyze Linear Block Codes

Understand the linear block code structure, the linearity property, and how
redundancy bits are added.

04

Apply Generator & Parity-Check Matrices

Use the Generator Matrix and Parity-Check Matrix to encode messages and detect
errors.
CHAPTER 1 OF 3 HAMMING DISTANCE

What Is Hamming Distance?

Formal Definition Simple Illustration

The Hamming distance between two codewords of equal length is defined Consider two 5-bit codewords:
as the number of bit positions in which the two codewords differ. It is
denoted as d(x, y). Word A: 0 1 0 1 0
Forouzan states: "The Hamming distance between two words is the
Word B: 1 1 0 0 1
number of differences between corresponding bits." ↑ ↑ ↑ ← 3 differences
Why It Matters
Therefore, d(A, B) = 3. The positions that differ are bit 1, bit 4,
Hamming distance is the fundamental metric underlying all error detection and bit 5.
and correction theory. It determines how many errors a code can detect or
correct.
Hamming distance is always a non-negative integer
and satisfies the triangle inequality.
 HAMMING DISTANCE

The XOR Method for Hamming Distance

Forouzan's textbook presents an elegant computational approach: XOR the two codewords bit-by-bit, then count the number of 1s in the
result. This count is the Hamming distance.

1 2 3

Step 1: XOR the Codewords Step 2: Count the 1s Step 3: Interpret the Result
Apply the exclusive-OR operation to each Count the total number of 1-bits in the XOR The result equals the Hamming weight of
corresponding bit pair. A 1 appears result. This count directly gives the the XOR pattern — the number of positions
wherever the bits differ; a 0 where they Hamming distance. where the codewords disagree.
match.

Codeword x: 0 1 0 1 0
Codeword y: 1 1 0 0 1
←
XOR result: 1 0 0 1 1 Three 1s → d(x, y) = 3
 HAMMING DISTANCE

Worked Example: Calculating Hamming Distance

This is a direct exercise from Forouzan's textbook. We compute the Hamming distance between the two 5-bit codewords 01010 and 11001 step
by step.

Step-by-Step XOR Calculation Final Answer

Bit 1 2 3 4 5
d(01010, 11001) = 3
Position
The two codewords differ in 3 bit positions. The XOR result 10011

Codewo 0 1 0 1 0 has exactly three 1-bits, confirming the Hamming distance is 3.

rd A

Always verify by directly comparing each bit position — the

Codewo 1 1 0 0 1
count of mismatches must equal the number of 1s in the
rd B
XOR output.

XOR (A 1 0 0 1 1
⊕ B)

The XOR result is 10011. Counting the 1s: positions 1, 4, and 5 differ.
HAMMING DISTANCE

Hamming Weight
Definition Examples of Hamming Weight

The Hamming weight of a codeword, denoted w(x), is the

Codeword Weight Notes
number of 1-bits it contains. It is the Hamming distance
between x and the all-zeros word.
00000 0 All zeros

w(x) = d(x, 0)
10101 3 Three 1-bits

Connection to Hamming Distance

11110 4 Four 1-bits
For linear codes, the Hamming distance between any two
codewords equals the weight of their XOR: 11111 5 Maximum
weight
d(x, y) = w(x ⊕ y)
Key Property
In a linear block code, the minimum Hamming distance of the code equals
the minimum weight of any nonzero codeword. This simplifies the search
for minimum distance considerably.
HAMMING DISTANCE

Properties of Hamming Distance

Non-Negativity Symmetry

d(x, y) ≥ 0 d(x, y) = d(y, x)

d(x,y) = 0 if and only if x = y. Distance is always a non-negative The order in which we compare codewords does not affect the
integer. result — XOR is commutative.

Triangle Inequality Metric Space

Together these three properties confirm that Hamming distance
d(x, z) ≤ d(x, y) + d(y, z)
defines a valid metric on the space of binary strings of length n.

The distance through an intermediate codeword is always at least

as large as the direct distance.
 CHAPTER 2 OF 3 MINIMUM HAMMING DISTANCE

Minimum Hamming Distance:

Concept Why Is Critical
Given a set of valid codewords, the minimum Hamming distance is Error Detection
defined as the smallest Hamming distance computed over all
A code with can detect up to single-bit errors in a received
possible distinct pairs of codewords in the set:
codeword.
dmin = min d(x, y)
​ ​

x,y∈C

x=y ​

Error Correction

This single number characterizes the error-control capability of the A code with can correct up to single-bit errors by choosing the
entire coding scheme. nearest valid codeword.
 MINIMUM HAMMING DISTANCE

Worked Example: Finding

Consider the following set of four codewords. We must compare every distinct pair to find the minimum distance (Forouzan, Chapter 10).

Pair Codeword 1 Codeword 2 XOR Result Distance

(A, B) 00000 01011 01011 3

(A, C) 00000 10101 10101 3

(A, D) 00000 11110 11110 4

(B, C) 01011 10101 11110 4

(B, D) 01011 11110 10101 3

(C, D) 10101 11110 01011 3

The minimum value across all pairs is 3. Therefore,

dmin = 3
​

for this code.

 MINIMUM HAMMING DISTANCE

Error Detection Capacity

The Formula Worked Example
To detect up to s errors in a received codeword, the minimum A code has d_{min} = 4. How many errors can it detect?
Hamming distance of the code must satisfy:
s + 1 ≤ dmin ⟹ s ≤ dmin − 1 = 3 ​

dmin ≥ s + 1
​

The code can detect up to 3 single-bit errors. If 4 or more bits are

Intuition: if any s bits are corrupted, the received word must still corrupted, the received word may coincidentally equal another valid
differ from every valid codeword, so it cannot be mistaken for a valid codeword, making the error undetectable.
transmission.

Detection does not tell the receiver which bits are wrong —
only that an error occurred.
MINIMUM HAMMING DISTANCE

Error Correction Capacity:

The Formula Worked Example

To correct up to t single-bit errors, the minimum Hamming distance A code has d_{min} = 7. What are its detection and correction limits?
must satisfy:
Detection:

dmin ≥ 2t + 1
s ≤ dmin − 1 = 6 errors detectable
​

Intuition
Correction:
Each valid codeword is surrounded by an "error sphere" of radius t.
dmin − 1
For correction to be unique, these spheres must not overlap. This t≤⌊ ⌋ = ⌊3⌋ = 3 errors correctable
​

2
​

requires valid codewords to be at least 2t + 1 apart.

A code with d_{min} = 7 can detect 6 errors or correct 3 errors, but

not both simultaneously at maximum capacity.
 MINIMUM HAMMING DISTANCE

Error Spheres and Correction Capability Visualization

Forouzan uses the concept of error spheres to visualize why minimum Hamming distance governs correction capability. Each valid codeword
occupies the center of a sphere containing all words within Hamming distance t.

dmin = 1 dmin = 3 dmin = 5 dmin = 7

No error detection or Can detect 2-bit errors or Can detect 4-bit errors or Can detect 6-bit errors or
correction possible. Adjacent correct 1-bit errors. Spheres correct 2-bit errors. Spheres correct 3-bit errors.
spheres overlap. are tangent. are separated. Maximum separation.
 CHAPTER 3 OF 3 LINEAR BLOCK CODES

Introduction to Linear Block Codes (LBC)

The Structure Key Parameters
A linear block code is characterized by two parameters: k message
Symbol Value Meaning
bits are encoded into n codeword bits, where n = k + r. The
difference r is the number of redundancy (parity-check) bits added
k Message Original data to be
for error control.
bits transmitted

n=k+r Redundancy Parity bits added by the

r
bits encoder

n Codeword Total bits sent over the

length channel

2k Datawords Total distinct messages

2n Possible Total -bit patterns

words
LINEAR BLOCK CODES

The Linearity Property

Formal Definition Verification Example
A block code is linear if and only if the XOR (modulo-2 sum) of any Code: {00000, 01011, 10101, 11110}
two valid codewords in the code produces another valid codeword.
Formally, for any two codewords 1:
01011 ⊕ 10101 = 11110 ✓ (in code)
This property means the set of all valid codewords is closed under 01011 ⊕ 11110 = 10101 ✓ (in code)
XOR. Equivalently, the codewords form a vector subspace over 10101 ⊕ 11110 = 01011 ✓ (in code)
GF(2).
All XOR combinations yield a member of the code — confirming
linearity.

The all-zeros codeword must always be present in a linear

block code, since any codeword XORed with itself gives
zero.
 LINEAR BLOCK CODES

Parity-Check Bit Generation

In a systematic linear block code, the message bits appear unchanged in the codeword, and the parity-check bits are computed as linear
(XOR) combinations of the message bits.

For a code, the encoder takes a 4-bit message and computes 3 parity bits. The resulting 7-bit codeword is transmitted. At the receiver, a
syndrome calculator recomputes these parity bits and compares them to detect and correct errors.

Parity Equations (mod-2) Codeword Structure

For the (7,4) Hamming code, the 3 parity bits r1, r2, and r3 are
Codeword c = [ m1 m2 m3 m4 | r1 r2 r3 ]
computed from the 4 message bits m1, m2, m3, and m4 using XOR
combinations:
← 4 data bits →←
3 parity →
r1 = m1 ⊕ m2 ⊕ m4 Worked example

r2 = m1 ⊕ m3 ⊕ m4
Message m = [1, 0, 1, 1]
r3 = m2 ⊕ m3 ⊕ m4 ⊕⊕
r1 = 1 0 1 = 0
⊕⊕
r2 = 1 1 1 = 1
Each parity bit covers a specific subset of message bits, ensuring ⊕⊕
r3 = 0 1 1 = 0
any single-bit error produces a unique syndrome. Codeword c = [1, 0, 1, 1, 0, 1, 0]
 LINEAR BLOCK CODES

The Generator Matrix

Structure of G Example: (7,4) Generator Matrix G
The Generator Matrix G is a k×n matrix used to encode a k-bit For a Hamming code, the generator matrix is:
message into an n-bit codeword. For a systematic code, G has the
form: m1 m2 m3 m4 | r1 r2 r3
G=[1 0 0 0 |1 1 0]
G = [Ik ∣ P ]
​

[0 1 0 0 |1 0 1]
[0 0 1 0 |0 1 1]
where I_k is the k×k identity matrix and P is the k×(n-k) parity sub-
[0 0 0 1 |1 1 1]
matrix.

Encoding Rule The left 4×4 block is I_k (identity matrix), preserving the original

A message vector m of length k is encoded as: message bits. The right 4×3 block P defines the parity-check
relationships. All arithmetic is modulo-2 (binary XOR).
c=m⋅G (mod 2)

This produces an n-bit codeword c.

For the (7,4) Hamming code: k = 4 message bits, n = 7 codeword

bits, 3 parity bits.
 LINEAR BLOCK CODES

Matrix Encoding: Step-by-Step Example

Using the generator matrix from Forouzan's textbook, encode the 4-bit message.

The Calculation: Result

c = [1 0 1 1 0 1 0]
m = [1 0 1 1]
The 4-bit message 1011 is encoded as the 7-bit codeword
[1 0 0 0 1 1 0]
1011010.
G=[0 1 0 0 1 0 1]
[0 0 1 0 0 1 1]
[0 0 0 1 1 1 1] Notice the first 4 bits of the codeword match the
original message exactly — confirming this is a
c1 = 1·1+0·0+1·0+1·0 = 1 (mod 2) = 1 systematic code.
c2 = 1·0+0·1+1·0+1·0 = 0 (mod 2) = 0
c3 = 1·0+0·0+1·1+1·0 = 1 (mod 2) = 1
Parity Bits
c4 = 1·0+0·0+1·0+1·1 = 1 (mod 2) = 1
c5 = 1·1+0·1+1·0+1·1 = 2 (mod 2) = 0 The parity bits are r1=0, r2=1, r3=0 appended after the 4
c6 = 1·1+0·0+1·1+1·1 = 3 (mod 2) = 1 message bits.
c7 = 1·0+0·1+1·1+1·1 = 2 (mod 2) = 0
LINEAR BLOCK CODES

The Parity-Check Matrix

Definition & Structure Syndrome Calculation

The Parity-Check Matrix is an matrix used at the receiver to verify For a received vector, the syndrome is computed as:
whether a received word is a valid codeword. For a systematic
code: s = r ⋅ HT (mod 2)

H = [P T ∣ Ir ] ​
No error syndrome Error syndrome

No error detected. The An error is detected. The

where is the transpose of the parity sub-matrix, and is the identity
received word is a valid syndrome pattern identifies
matrix.
codeword (or error is the error location for single-
The Fundamental Relationship undetectable). bit correction.

G ⋅ HT = 0 (mod 2)
Summary & Key Formulas
Hamming Distance Minimum Distance

d(x, y) = w(x ⊕ y) dmin = min d(x, y)

​ ​


x=y

Count of differing bit positions. Computed via XOR and counting

Smallest pairwise distance across all distinct codeword pairs in
1s.
the code.

Error Detection Error Correction

dmin ≥ s + 1
​ dmin ≥ 2t + 1
​

To detect up to s errors. The received word stays outside all valid To correct up to t errors. Error spheres of radius t must not
codeword neighborhoods. overlap.

LBC Structure Encoding & Syndrome

n=k+r c=m⋅G s = r ⋅ HT

k message bits, r parity bits, n total codeword bits. Generator matrix encodes; Parity-Check matrix detects errors via
syndrome.
Q&A & Conclusion
What We Covered Today Further Study

1 Hamming Distance
~ Textbook
Definition, XOR computation
Forouzan, Chapter 10 — Error
method, and Hamming weight.
Detection & Correction.
Review all worked examples
2 Minimum Hamming Distance and exercises.

How governs detection (detection

capacity) and correction (correction
Thank you! Questions
capacity).
are welcome. Please
review the parity-check
3 Linear Block Codes matrix derivation and try
encoding your own 4-bit
The structure, linearity property,
messages using the
and matrix-based
encoding/decoding.
(7, 4)

generator matrix.