Luigi Paura » 11.Linear block codes

Linear block codes

Outline:

• Linear code structure
• Coder and decoder
• Linear code performance

Linear code structure

Linear code structure

Linear code structure

A (binary) code is linear if every linear combination of code words is also a code word

modulo -2 addition

The linearity of a code depends only on the code words and not on how the information blocks are mapped to the code words.

Linear code structure

Linear code structure

Example:

If ci=(11001) ∈ C cj=(11000) ∈ C →

(11001) ⊕ (11000) = (00001) ∈ C

Closure property (under the modulo 2 addition) and the presence of c0=(0000…0) → C is a vector subspace of the space formed by all the n-dimensional binary vectors.

Linear code structure

The vector subspace C can be generated by a set of vectors, namely by a base
Example 1:
A (5,2) code defined by
C={00000, 10100, 01111, 11011} is linear because it verifies the closure property and the code word (00000) is in the code.

Linear code structure

Linear code structure

Linear code structure

Linear code structure

Linear code structure

Linear code structure

Linear code structure

Linear code structure

Linear code structure

Dual code

Dual code

It is possible to show that code words of C are orthogonal to the code words of C^T:

cH^t=0 ∀ c ∈ C

cG^t=0 ∀ c ∈ C^T

The matrix H is called the parity check matrix of the code C.
Since all rows of the generator matrix are code words we have

GH^t = 0

Hamming codes

The Hamming codes are linear block codes with
C(2m-1, 2m-1-m) and dmin=3

built in the following way.
The columns of the parity check matrix H are all binary sequences of length m except the all zero sequence which number is equal to 2^m-1.

Hamming codes

Hamming codes

Hamming codes

Hamming codes

Show that the minimum Hamming distance of a linear block code is equal to the minimum number of columns of its parity check matrix that are linearly dependent.
The parity check matrix H can be expressed as:

H=[h₁, h₂, ..., h_n] with hi a (n-k)-coumn vector

Let c = [c₁,.....c_n] a code word with l non-zero components.
Let us denote with c_i1,…c_il the l components equal to 1.

Hamming codes

Since cH^t = 0 →

c₁h₁+c₂h₂+…-c_nh_n = 0 →

c_i1h_i1+c_i2h_i2+…+c_inh_in = 0

If a code word has Hamming weight 1 → l column of H is linearly independent
If a code has the minimum distance d_min → there exists at least a code word with weight d_min →d_min is the minimum number of columns of H linearly dependent.

Coder for Linear Codes