# Luigi Paura » 11.Linear block codes

### Linear block codes

Outline:

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

### Linear code structure

A (binary) code is linear if every linear combination of code words is also a code word $\sum_l c_l\inC~~~\forall c_l$

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

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

The code is systematic because the first k (k=2) symbols of the code word coincide with the symbols of the information sequence followed by some extra bits called parity check bits.
The matrix G in this case is written belowe.

### Dual code

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

cHt=0 ∀ c ∈ C

cGt=0 ∀ c ∈ CT

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

GHt = 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 2m-1.

### 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=[h1, h2, ..., hn] with hi a (n-k)-coumn vector

Let c = [c1,.....cn] a code word with l non-zero components.
Let us denote with ci1,…cil the l components equal to 1.

### Hamming codes

Since cHt = 0 →

c1h1+c2h2+…-cnhn = 0 →

ci1hi1+ci2hi2+…+cinhin = 0

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

### Coder for Linear Codes

Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion

Fatal error: Call to undefined function federicaDebug() in /usr/local/apache/htdocs/html/footer.php on line 93