Udine, 24 Febbraio 2005
Principi di Teoria dei Codici
Andrea Tonello
e-mail: [email protected]
http://www.diegm.uniud.it/tlc/tonello
UNIVERSITÀ DEGLI STUDI DI UDINE
DIEGM DIPARTIMENTO DI INGEGNERIA ELETTRICA, GESTIONALE E MECCANICA
Sommario
‰ Approcci alla Codifica di Canale
‰ Codici a Blocco
‰ Prestazioni Codici a Blocco
‰ Codici Convoluzionali
Bibliografia:
– J. Proakis, Digital Communications
– S. Lin, D. Costello, Error Control Coding
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
2
Modello Sistema di Comunicazione
Codificatore
Sorgente
Codificatore
Canale
Modulatore
Numerico
Canale
De-Modul.
•
De-Cod.
Canale
De-Cod.
Sorgente
Lo scopo della Codifica di Canale e` di consentire la correzione e/o rivelazione degli
errori introdotti dal canale.
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
3
Codifica di Canale
Codificatore
b
c
•
Idea: Introdurre ridondanza in trasmissione, ad. es. ripetere l’informazione.
•
Il codificatore attua una trasformazione dalle parole di ingresso b alle parole di uscita
c con una certa legge:
b=[…,bi, bi+1,…] → c=[…,ci, ci+1,…]
•
Alfabeto: il campo cui appartengono gli elementi delle parole di ingresso, ad. es. GF(2).
•
Codice: insieme delle parole codificate.
•
Rate:
rapporto tra numero di simboli di ingresso e quello di uscita (<1).
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
4
Approcci alla Codifica di Canale
•
Codici Algebrici a Blocco
•
Codici Convoluzionali
•
Codifica e Modulazione Congiunta
– Modulazione codificata a traliccio (TCM)
•
Turbo Codici
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
5
Codici a Blocco
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
6
Codici a Blocco
•
Codice a blocco (n, k):
–
Parole (Vettori) di ingresso hanno lunghezza k : b=[b1,…,bk]
–
Parole di uscita hanno lunghezza n>k :
–
Alfabeto e` q-ario e le operazioni sono definite su un campo finito GF(q) con q primo o potenza di un
c=[c1,…,cn]
numero primo.
–
Se q e` primo, l’algebra e` modulo q.
•
Definizione: e` un insieme di qk parole di n elementi.
•
Codice Lineare: se c1 e c2 sono di codice allora ac1 + bc2=c3 e` di codice.
–
La parola nulla appartiene al codice.
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
7
Matrice di Codice
c=b G
•
Matrice di Codice
•
Le k righe di G sono vettori linearmente indipendenti e sono di codice.
•
I vettori di codice appartengono al sottospazio k-dimensionale generato dalle righe di G.
•
Forma sistematica
1×n
1×k
c = [b |c k +1 ,...,c n ]
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
k×n
. Elementi appartenti a GF(q)
⎡ 1 ... 0 p11 ... p1n−k ⎤
⎢
⎥
G = ⎢... ... ... ... ... ... ⎥
⎢
⎥
⎢ 0 ... 1 pk1 ... pkn−k ⎥
⎣
⎦
= [I |P]
8
Matrice di Controllo Parita`
•
Matrice di Controllo Parita`
T
(G) (H) = k×(n0−k )
k×n (n−k )×n
•
Le n-k righe di H sono vettori linearmente indipendenti e generano il codice duale (n-k,n)
•
Le parole del codice duale sono ortogonali a quelle del codice (n,k)
•
Se il codice e` in forma sistematica:
⎡−P ⎤
[Ik | P] ⎢ ⎥ = 0
⎢⎣In−k ⎥⎦
G
HT
H = ⎡⎣−PT
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
In−k ⎤⎦
9
Matrice di Controllo Parita`
•
Matrice di Controllo Parita`ci consente di verificare se un vettore e` di codice
⎧
= 0 se c ∈
⎪
⎪
cH ⎨
⎪
⎪
⎩≠ 0 se c ∉
T
s = cHT
•
Vettore Sindrome:
•
Assumendo il codice binario abbiamo:
1×(n−k )
– 2k vettori di ingresso e di codice.
– 2n possibile vettori di dimensione n, quindi 2n -2k non sono di codice.
– 2n-k sindromi.
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
10
Distanza e Peso di Hamming
•
Distanza di Hamming: numero di simboli di cui differiscono due parole con alfabeto q-ario
dH (r1,r2 )
•
Peso di Hamming: numero di simboli diversi da zero
wH (r1)
•
Vale la seguente:
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
dH (c1, c2 ) = wH (c1 − c2 )
11
Distanza Minima
•
Distanza Minima di Hamming: e` la minima distanza tra parole di codice
dH,min = min {dH (c1, c 2 )}
c1,c2
•
In un codice lineare la distanza minima e` pari al peso minimo:
dH,min = wH,min
Dim:
dH,min = min {dH (c1, c 2 )}
c1,c2
= min {w H (c1 − c 2 )}
c1,c2
= min {w H (c )}
c≠0
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
12
Singleton Bound
•
Bound di Singleton: In un codice lineare a blocco
dH,min ≤ n − k + 1
•
Codici a massima distanza verificano
dH,min = n − k + 1
Dim: Basta pensare alla forma sistematica.
•
Gli unici codici binari a massima distanza sono quelli ripetitivi altrimenti ci sono quelli di
Reed Solomon su GF(q).
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
13
Esempi di Codici Lineari a Blocco
•
Codici di Hamming.
•
Codici di Hadamard.
•
Codici BCH (Bose, Chaudhuri, Hocquenghem) e di Reed Solomon .
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
14
Codici di Hamming Binari
•
(n,k) = (2m-1,2m-1-m) m>1 intero n-k=m
•
La matrice H ha le n colonne ottenute prendendo tutti i vettori di m elementi binari
escluso il vettore nullo.
•
Codice di Hamming (7,4)
⎡1
⎢
T
H = [P | In−k ] = ⎢ 1
⎢
⎢0
⎣
⎡1
⎢
⎢0
G = [Ik | P] = ⎢
⎢0
⎢
⎢⎣0
•
0 1 1 | 1 0 0⎤
⎥
1 0 1 | 0 1 0⎥
⎥
1 1 1 | 0 0 1⎥⎦
0 0 0 0 1 1⎤
⎥
1 0 0 1 1 0⎥
⎥
0 1 0 1 0 1⎥
⎥
0 0 1 1 1 1⎥⎦
Il peso minimo e` uguale a 3
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
15
Codici di Hadamard
•
(n,k) = (2m,m+1) m>1 intero
•
Si ottengono dalle matrici di Hadamard cosi` definite
⎡M2 M 2 ⎤
⎡ 0 0⎤
⎥
⎥ M4 = ⎢
M2 = ⎢
⎢M M2 ⎥
⎣⎢0 1⎥⎦
⎣ 2
⎦
•
L’insieme delle parole di lunghezza n=4 ottenute dalle 4+4 righe di
M4
e di
M4
sono un codice a blocco lineare con k=3 e peso minimo dmin=n/2=2
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
16
Codici BCH e Reed Solomon
•
Binari (n,k) hanno parametri
– n=2m-1
– n-k ≤ mt
con m≥3 t≥1
– dmin=2t+1
•
Reed Solomon sono una sottoclasse non binaria.
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
17
Modello di Canale
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
18
Modello di Canale
Canale
Codificatore
b
De-Codificatore
Equivalente
c
y
b
•
Modulatore – Canale – Demodulatore possono essere visti come un blocco equivalente.
•
Bisogna definire la relazione ingresso-uscita. Essa dipende dal tipo di modulazione e
demodulazione/decodifica:
–
Demodulazione/Decodifica Congiunta.
–
Demodulazione/Decodifiva disgiunta:
• HARD
• SOFT
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
19
Modello di Canale
•
Alfabeto di codice binario, Modulazione 2-PAM, Rumore Additivo Gaussiano Bianco
yi = ES x i + ni
xi = 2c i − 1
c i ∈ {0,1}
xi ∈ {+1,−1}
ni = N(0,N0 / 2) ed indip.
•
In forma vettoriale possiamo raccogliere le n osservazioni in un vettore e scrivere
y = ES x + n
•
C’e` una relazione biunivoca tra c ed x
x = 2c − 1
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
20
Decodifica Soft
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
21
Decodifica Ottima a Massima Verosimiglianza
•
Il decodificatore ML decide per la parola di codice che massimizza la densita` di probabilita`
del vettore ricevuto condizionata dal vettore trasmesso:
n
pY|X ( y | x ) = ∏ p Yi|Xi (yi | xi )
i=1
n
=∏
i=1
1
πN0
−
e
−
= (πN0 )n / 2 e
•
1
( yi − ES xi )2
N0
1
||y− ES x||2
N0
Il decodificatore ML decide per il vettore di codice che e` a distanza Euclidea minima dal
vettore ricevuto
2
xˆ = argmin{|| y − ES x || }
x∈
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
2
|| y − ES x || =
n
∑ ( yi −
i=1
ES xi )2
22
Probabilita` Errore con Decodifica Soft
Pe = P[cˆ ≠ c] = P[ xˆ ≠ x ]
= ∑ P[ x = x i ]P[ xˆ ≠ x | x = x i ]
xi ∈
P[Eij ] ≤ P[ xˆ ≠ x | x = x i ] = P[∪ Eij ] ≤ ∑ P[Eij ]
j
j
Eij = {xˆ = x j ≠ x = x i }
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
23
Probabilita` Errore a Coppie
P[Eij ] = P[ x = x i → xˆ = x j ]
= P[dE ( y, ES xˆ ) < dE ( y, ES x )]
= P[|| ES ( x − xˆ ) + n ||2 − || n ||2 < 0]
= P[ES || x − xˆ ||2 −2 ES ( x − xˆ )nT < 0]
V.a. gaussia a media nulla e varianza:
2N0ES || x − xˆ ||2
⎛ E || x − xˆ ||2 ⎞
⎛ E d2 ( x, xˆ ) ⎞
⎟⎟
⎟⎟
⎜⎜ S E
P[Eij ] = Q ⎜⎜⎜ S
Q
=
⎟⎟
⎟⎟
⎜
2N0
2N0
⎜⎝
⎠⎟
⎝⎜
⎠⎟
Q(a) distribuzione gaussiana complementare
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
24
Probabilita` Errore Condizionata
P[ xˆ ≠ x | x = x i ] ≤ ∑ P[Eij ]
j
⎛ E d2 ( x , xˆ ) ⎞
⎜⎜ S E i j ⎟⎟
≤ ∑ Q⎜
⎟⎟
⎜⎜
2N0
xˆ j ≠ xi
⎝
⎠⎟
⎛ E d2 ⎞
⎜⎜ S E,min ⎟⎟
≤ ∑ Q⎜
⎟⎟
⎜
2N
⎜⎝
xˆ j ≠ xi
0
⎠⎟
⎛ E d2 ⎞
⎜⎜ S E,min ⎟⎟
≤ (2 − 1)Q ⎜
⎟
⎜⎜⎝
2N0 ⎠⎟⎟
k
dE,min =
min {|| x 1 − x 2 ||}
x1,x 2 ∈
Minima distanza Euclidea tra parole di codice 2-PAM
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
25
Probabilita` Errore
Pe = ∑ P[ x = x i ]P[ xˆ ≠ x | x = x i ]
xi ∈
⎛ E d2 ⎞
⎟
⎜
≤ (2k − 1)∑ P[ x = x i ]Q ⎜⎜ S E,min ⎟⎟
⎜⎜⎝
2N0 ⎠⎟⎟
xi ∈
⎛ E d2 ⎞
⎟
⎜
≤ (2 − 1)Q ⎜⎜ S E,min ⎟⎟
⎜⎜⎝
2N0 ⎠⎟⎟
k
Pe blocco
Pe bit
⎛ E d2 ⎞
⎛ E d2 ⎞
n. parole a dE,min
⎜⎜ S E,min ⎟⎟
⎜⎜ S E,min ⎟⎟
k
LQ ⎜
≤1
⎟ ≤ Pe ≤ (2 − 1)Q ⎜
⎟ L=
k
⎜⎜⎝
⎜⎝⎜
2N0 ⎠⎟⎟
2N0 ⎠⎟⎟
2
⎛
⎞
⎛ E d2 ⎞
2
L ⎜ ES dE,min ⎟⎟
⎜⎜ S E,min ⎟⎟
k
≤
≤
−
Q ⎜⎜
P
(2
1)Q
⎟
⎟
b
⎜⎜
k ⎜⎜⎝
2N0 ⎠⎟⎟
2N0 ⎠⎟⎟
⎜⎝
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
26
Confronto Sistema Codificato e Non Codificato
Pb,COD
⎛ 2E Rd
⎞
b
H.min ⎟
⎜
⎟⎟
= Q⎜
⎜⎜⎝
N0
⎠⎟
dE,min = 2dH,min
Pb,UNCOD
Eb = ES / R = ESn / k
Per mantenere la velocita` di TX uguale
bisogna incrementare la banda di 1/R
Esempio: Hamming (7,4)
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
⎛ 2E ⎞
b ⎟
⎟
= Q ⎜⎜
⎜⎜⎝ N ⎠⎟⎟
0
G = RdH,min
G = 3 × 4 / 7 = 2.34 dB
27
Canale Binario Simmetrico
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
28
Modello di Canale Binario Simmetrico (BSC)
Decodifica hard: operiamo la demodulazione ottenendo un canale equivalente binario
0
1-p
yi → ri ∈ {0,1}
p
1
•
0
1
Probabilita` di transizione (con trasmissione 2-PAM) e`
⎛ 2E ⎞
b ⎟
⎟
p = Pe = Q ⎜⎜
⎜⎜⎝ N ⎠⎟⎟
0
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
29
Decodifica ML in Canale BSC
•
In forma vettoriale abbiamo per il canale binario simmetrico senza memoria
r =c+e
•
Decodifica ML hard: massimizziamo la probabilita
n
P[r = rˆ | c = cˆ ] = ∏P[r = rˆi | c = cˆ i ]
i=1
n
= ∏P[ei = rˆi − cˆ i | c = cˆ i ]
i=1
ˆ ˆ
ˆ ˆ
= p wH (r−c ) (1− p)n−wH (r−c )
Se p<1/2, decidiamo per il vettore di codice a distanza di Hamming minima
cˆ = argmin{dH (r, c )}
c∈
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
30
Correzione
•
Con decodifica Hard possiamo correggere tutti i pattern di errore di peso minore uguale di
⎢1
⎥
t = ⎢ (dH,min − 1)⎥
⎢⎣ 2
⎥⎦
– Puo` accadere che correggiamo errori di peso > t
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
31
Rivelazione
•
Con decodifica Hard possiamo rivelare tutti i pattern di errore di peso minore uguale di
dH,min − 1
•
Con la decodifica a sindrome, un pattern di errore di peso dH,min-1 non puo` trasformare
la parola originaria in un’altra parola di codice.
•
Tuttavia possiamo anche rivelare pattern errore di peso maggiore di dH,min-1 poiche`:
– 2k di codice e 2n ricevute
– 2n-2k non sono di codice quindi rivelabili via decodifica a sindrome
– 2n -2n+2k = 2k non sono rivelabili
– Frazione di non rivelabili e` piccola: (2k – 1) /( 2n – 1) ~ 2k-n
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
32
Probabilita` di Errore
•
Con decodifica Hard possiamo correg. tutti i pattern di errore di peso minore uguale di t
⎛n⎞ i
Pe (blocco) ≤ P[w(e ) > t] = ∑ ⎜⎜ ⎟⎟⎟ p (1− p)n−i
⎜
i= t +1⎝ i ⎠
n
•
Tipicamente la decodifica Hard differisce per 1-2 dB da quella Soft in termine di Eb/No
per ottenere la stessa Pe.
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
33
Codici Convoluzionali
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
34
Codice Convoluzionale
•
Un codificatore convoluzionale e` una macchina a stati finiti lineare.
•
Codice convoluzionale binario di rate k/n genera ogni k bit d’ingresso n bit di uscita
combinando modulo 2 i contenuti di uno shif register di lunghezza kK:
bi
1
2
K
1 2 … k
1 2 … k
1 2 … k
+
+
+
c i1
c in
•
•
Gli shift sono k bit d’ingresso alla volta.
K e` detta constraint length (lunghezza di vincolo).
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
35
Codice Convoluzionale Binario 1/n
•
Esempio rate ½ e K=3
+
bi
1
2
K=3
+
•
c i1
c i2
Viene descritto da una sequenza generatrice (detta polinomio di codice)
g(1) = [101] → [5] in ottale
g(2) = [111] → [7] in ottale
•
Ciascuna uscita puo` essere ottenuta da un filtraggio modulo 2
(n)
c (n)
=
b
⊗
g
(i)
i
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
36
Diagramma a Traliccio (Trellis)
•
Ingresso-uscita puo` essere rappresentata da un traliccio
00
01
0/00
1/11
10
11
stato
transizioni ingresso/uscite
•
Numero di stati uguale a 2K-1
•
Numero di rami entranti/uscenti per stato uguale a 2 (rate 1/n)
•
Lungezza del traliccio uguale al numero totale di bit di ingresso
•
Se il codice e` terminato si parte dallo stato 0 e si ritorna allo stato 0
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
37
Decodifica ML
•
Il decodificatore soft a massima verosimiglinza cerca tra tutte le parole di codice
quelle a distanza euclidea minima (con rumore AWGN).
•
Se consideriamo trasmissione 2-PAM e rumore additivo bianco il modello e`:
yi =
•
ES x i + n i
2
|| y − ES x || =
∑ ( yi −
i
ES xi )2
Se assumiamo un codice di rate 1/n, allora
n
2
|| y − ES x || = dE ( y, ES x ) =
∑ ∑ ( yni+m −
i
ES xni+m )2
m=1
BM( xi )
=
∑ BM( xi ) = ∑ BM(x j ) + BM( x i )
i
j<i
PM(i−1)
•
La distanza totale e` ottenibile come somma di Branch metrics
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
38
Algoritmo di Viterbi
•
La ricerca esaustiva delle sequenza a distanza minima si ottiene con una
operazione ricorsiva di ADD, COMPARE, SELECT sul traliccio
00
01
10
11
•
Ciascun ramo puo` essere etichettato con il bit di ingresso, gli n bit di uscita, e la
metrica di ramo (Branch Metric).
•
Percorsi entranti in uno stesso stato (nodo) sono competitors e sopravvive solo
quello con metrica di percorso (Path Metric) piu` piccola.
•
Giunti alla fine del traliccio sompravviveranno un numero di percorsi pari al numero
di stati. Scelgo quello di metrica piu` piccola, da cui ottengo la sequenza di bit di
ingresso (sequenza decodificata).
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
39
Conclusioni
•
La codifica di canale e` essenziale per consentire comunicazioni affidabili.
•
Il codice deve essere progettato in funzione dell’applicazione e del canale
trasmissivo.
DIEGM UNIVERSITÀ DEGLI STUDI DI UDINE
40