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 ∀c∈C
cGt = 0 ∀c∈CT
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:
- Demodulazione (r(t) attraverso il filtro adattato e campionamento con passo T).
- Decisione a soglia (quantizzazione a due livelli).
- 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:
- La prima riga è costituita dalle parole codice.
- 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.
- 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:
- Gli elementi appartengono alla stessa riga (coset ). In questo caso si ha (vedi figura in alto)
- 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:
- Calcoliamo s: yHt=s
- 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
Le lezioni del Corso
1. Schema canonico di un sistema di trasmissione numerico punto-punto
4. Rappresentazione geometrica dei segnali
5. Trasmissione numerica su canale AWGN
6. Prestazioni del ricevitore ottimo su canale AWGN I
7. Prestazioni del ricevitore ottimo su canale AWGN II
8. Demodulazione MV non coerente di segnali FSK
9. Trasmissione su canale AWGN a banda limitata
10. Capacità di canale e codifica
11. Codifica di canale a blocchi
13. Codici ciclici
