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 » 12.Codici a blocco lineari


Codici a blocco lineari

Sommario:

  • Struttura dei codici lineari
  • Codificatore e decodificatore
  • Prestazioni dei codici lineari

Struttura dei codici lineari

Un codice a blocco (n,k) è completamente definito se sono assegnate le 2k sequenze binarie (parole codice) di lunghezza n:


Struttura dei codici lineari

Assumiamo che L=2 cioè consideriamo i codici binari con

Ogni parola codice è un vettore n-dimensionale con componenti con valori 0 oppure 1.


Proprietà dei codici lineari

Un codice (binario) è lineare se ogni combinazione lineare di parole codice è ancora una parola codice

La linearità di un codice dipende solo dalle parole codice è non da come esse sono associate ai blocchi di informazione.


Proprietà dei codici lineari

Per un codice lineare si ha:


Proprietà dei codici lineari

Esempio:

La proprietà di chiusura (rispetto alla somma modulo 2) e la presenza di c0=(0000…0) implica che C è un sottospazio vettoriale dello spazio costituito da tutti i vettori n-dimensionali binari


Proprietà dei codici lineari

Il sottospazio vettoriale C può essere generato da un sottoinsieme di vettori di C cioè da una base.

Esempio 1:

Il codice (5,2) con C={00000, 10100, 01111, 11011} è lineare perché verifica la proprietà di chiusura e ha la parola codice (00000).

Proprietà dei codici lineari

E’ naturale associare ad ogni parola codice ci una sequenza di informazione xi e ad ogni cj↔xj in modo che:

xi⊕xj ↔ ci⊕cj∀i , j a

Se consideriamo questa associazione per il codice C(5,2):

00 → 00000

01 → 01111

10 → 10100

11 → 11011

è facile constatare che la proprietà a è soddisfatta.

Proprietà dei codici lineari

Se consideriamo questa altra associazione:

00 → 10100

01→ 01111

10 → 11011

11 → 11011

La proprietà a non è soddisfatta. Comunque, In entrambi i casi il codice è lineare.

Assumiamo da questo momento che il codice lineare C verifica la proprietà a.

Definizioni di peso e distanza

Definizioni:

  • Il peso di Hamming di una parola codice w(ci)=il numero di “1″.
  • La distanza dij tra due parole codice è il peso di Hamming w(ci-cj).
  • La distanza minima di un codice è dmin:

Definizioni di peso e distanza

Per un codice lineare dmin:

Il codice C(5,2) che stiamo considerando ha una distanza minima dmin=2.


Codifica a blocchi

In ogni codice lineare C è possibile individuare k parole codice dalle quali poter ottenere tutte le parole codice di C attraverso combinazioni lineari.

Assumiamo di considerare le sequenze di informazione (vedi immagine):

Queste k parole codici gi definiscono una matrice binaria kxn detta matrice generatrice del codice.


Matrice generatrice


Matrice generatrice

Esempio:

Trovare una matrice G per il codice lineare C(5,2) dell’esempio 1.


Equazione di parità

Dalla matrice generatrice G si evince che le componenti di c=(c1,c2,c3,c4,c5) con


Codice sistematico

Il codice è sistematico perché i primi k (k=2) simboli della parola codice coincidono con i simboli della sequenza di informazione.

La matrice G in questo caso si scrive:


Codice sistematico

Nell’esempio 1:


Codice duale

Definizione del codice duale del codice C:

E’ il codice C(n,n-k) che ha matrice generatrice H pari


Codice duale

Si può dimostrare che le parole codice di C sono ortogonali alle parole codice di CT:

cHt = 0 ∀cC

cGt = 0 ∀cCT

La matrice H è detta matrice controllo di parità del codice C.

Poiché tutte le righe di G sono parole codice si ha: GHt=0.

Codici di Hamming

I codici di Hamming sono codici lineari a blocco con C(2m-1, 2m-1-m) e dmin=3 costruiti nel seguente modo:

Le colonne della matrice H del codice sono tutte le sequenze binarie di lunghezza m esclusa quella con tutti “0” il cui numero è pari a 2m-1.

Codici di Hamming

Esempio: costruire il codice di Hamming con m=3 cioè il codice di Hamming C(7,4).

I codici di Hamming avendo una dmin=3 possono correggere un errore.


Codici di Hamming

Determinare il dizionario del codice di Hamming (7,4), la distribuzione dei pesi e verificare che la distanza minima è 3.


Codici di Hamming

Determinare la matrice H e la matrice G per un codice di Hamming (15,11).


Codici di Hamming

Dimostrare che la distanza minima di un codice di Hamming è pari al minimo numero di colonne della matrice di controllo di parità H linearmente dipendenti.

La matrice H può essere espressa nella forma:

Sia c=[c1,...,cn] una parola codice con l componenti non nulle. Denotiamo con ci1,…,cil le l componenti uguali a 1.

Codici di Hamming

Poichè cHt = 0 ⇒

c1h1+c2h2+…+cnhn = 0 ⇒

ci1hi1+ci2hi2+…+cinhin = 0

Quindi se una parola codice ha peso di Hamming l, allora l colonne di H saranno linearmente dipendenti.

Se un codice ha distanza minima dmin, allora esiste almeno una parola codice di peso dmin, e, quindi, dmin è il numero minimo di colonne di H linearmente dipendenti.

Codificatore per codici lineari


Decodificatore per codici lineari

L’obiettivo della codifica a blocchi è quello di aumentare la distanza euclidea tra i segnali per aumentare le prestazioni (la P(e)) a parità di potenza e pagando in banda.

Il confronto tra i codici può essere fatto con le distanze di Hamming poiché quelle euclidee aumentano con esse.

Possiamo avere due alternative:

  • decodifica con decisione soft (ricevitore a Massima verosimiglianza);
  • decodifica con decisione hard.

Decodifica con decisione soft

Supponiamo che si utilizza una segnalazione antipodale la parola codice ci=(ci1,ci2,…,cin) è associata al segnale:


Decodifica con decisione soft

Il ricevitore ottimo per AWGN calcola le distanze euclidee tra r(t) e si(t) e decide per il segnale più prossimo a r(t).


Decodifica con decisione hard

Il demodulatore hard esegue singole decisioni sugli n simboli di canali ricevuti e consegna la parola ricevuta al decodificatore che stima la parola codice calcolando le distanze tra la parola ricevuta e le M possibili parole codice.


Decodifica con decisione hard

Nella decodifica hard si riconoscono tre fasi:

  1. Demodulazione (r(t) attraverso il filtro adattato e campionamento con passo T).
  2. Decisione a soglia (quantizzazione a due livelli).
  3. Decodifica ricercando la parola codice più vicina a quella ricevuta.

La decodifica si realizza sulla base della costruzione dell’array standard che individua le 2k regioni di decisione.

Decodificatore per demodulazione hard: Array Standard

La procedura di costruzione dell’array standard consente di ripartire lo spazio di osservazioni costituito da 2n vettori in 2k regioni di decisione.

L’array si costruisce nel seguente modo:

  1. La prima riga è costituita dalle parole codice.
  2. La seconda riga si costruisce predisponendo nella prima posizione della seconda riga una sequenza di lunghezza n non ancora presente nella prima riga e di peso minimo. La riga si completa sommando questa sequenza con le corrispondenti parole codice.
  3. La terza riga si costruisce nello stesso modo inserendo nella prima posizione una sequenza di peso minimo ancora non presente nell’array e inserendo nelle posizioni successive la somma di tale sequenza con la corrispondente parola codice.

Array Standard


Proprietà dell’array standard

Tutti gli elementi dell’array sono distinti

Assumiamo che due elementi siano uguali. Ciò può accadere solo in due casi:

  1. Gli elementi appartengono alla stessa riga (coset ). In questo caso si ha (vedi figura in alto)
  2. Gli elementi non appartengono alla stessa riga (vedi figura in basso)

Proprietà dell’array standard

Se y1 e y2 appartengono allo stesso coset allora


Proprietà dell’array standard

Tutti gli elementi di una riga (coset) sono caratterizzati dalla seguente proprietà:


Proprietà dell’array standard

Ogni coinsieme può essere identificato univocamente da una sindrome s.

E’ possibile definire una tabella di corrispondenze (s,e) (vedi figura in alto)

Strategia di decodifica:

  1. Calcoliamo s: yHt=s
  2. Si ricercare nella tabella la corrispondente conf. di errore e operiamo la correzione (vedi figura in basso)

Struttura del ricevitore con demodulazione hard


Decodifica hard con array standard

Esempio: codice di Hamming (7,4)


Decodifica con decisione soft


Decodifica con decisione soft


Decodifica con decisione soft

Applicando l’Union Bound si ha:


Decodifica con decisione soft 4/5

Esercizio: Confrontare le prestazioni di un sistema che non utilizza la codifica con un sistema che utilizza un codice di Hamming (7,4) con R=10 Kbit/sec, P=10-6W, N0/2 =10-11W/Hz e una segnalazione binaria PSK.

Senza codifica (vedi figura)


Decodifica con decisione soft

Sistema con codifica


Prestazioni per decodifica con decisione hard

In questo caso la cascata mod.+AWGN+ demod. hard è un canale BSC (vedi figura):

Perché, essendo il codice lineare, dipendono solo dalla distribuzione dei pesi wk con k=1,…,M-1.

La probabilità di corretta decisione può essere calcolata come la probabilità che si verifichi una configurazione di errore correggibile (vedi costruzione array standard). Essa può essere anche stimata con la maggiorazione dell’unione.


Prestazioni per decodifica con decisione hard

(vedi figura in alto)

Affinché le sfere di decisione non si sovrappongano il loro raggio ec (il numero di errori correggibili) dipende dalla dmin.

(vedi figura in basso)


Prestazioni per decodifica con decisione hard


Prestazioni per decodifica con decisione hard

Poiché il decodificatore opera a minima distanza di Hamming si ha:


Prestazioni per decodifica con decisione hard


Confronto tra codifica con decisione soft e hard

Il decodificatore con decisione hard riesce ad ottenere le stesse prestazioni di quello ottimo (decisione soft) pagando un prezzo in termini di Eb/N0<2 dB per prestazioni di interesse applicativo.

Se si demodula con 8 livelli si riduce il prezzo cioè Eb/N0<0.1 dB.

Esempio

Si supponga di utilizzare un codice di Hamming (7,4) con R=104 bps, P=10-6 W, N0/2=10-11 W, un BPSK, e un demodulatore hard con decodifica a MV (minima distanza di Hamming):


Esempio

Alternativamente:


Considerazioni conclusive

Riassunto della lezione

  • Sono stati introdotti i codici lineari e ne sono state descritte le proprietà.
  • Sono stati presentati i codici di Hamming.
  • Sono state mostrate le strutture del codificatore e del decodificatore per codici lineari.
  • Sono state descritte le tecniche di decodifica soft e hard e ne sono state valutate le prestazioni.

Prossima lezione

Codici ciclici

Argomenti della lezione 13

  • Cenni sui codici ciclici
  • 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