Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

\sum_l c_l\inC~~~\forall c_l

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

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.


Linear code structure


Dual code


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


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=[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


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
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