Codifica di Canale Codici a...

INFO-COM Dpt.

Dipartimento di Scienza e Tecnica

dell’Informazione e della Comunicazione

Università degli Studi di Roma Sapienza

Codifica di CanaleCodifica di Canale

R. Cusani, F. Cuomo – Telecomunicazioni – Codifica di Canale – Aprile 2010

Codifica di CanaleCodifica di CanaleCodici a bloccoCodici a blocco

TELECOMUNICAZIONITELECOMUNICAZIONI

Profs. Roberto Cusani – Francesca Cuomo

2

Codici di canaleCodici di canale

� Contesto in cui si utilizzano i codici “di canale”: un sistema di

trasmissione (o di memorizzazione) soggetto ad errori di trasmissione

(o di recupero dell’informazione)

� Obiettivo della codificazione: ridurre la probabilità di errore nella

trasmissione di un messaggio, tramite introduzione di ridondanza nel

messaggio trasmesso


messaggio trasmesso

� Codici semplici e noti:

� lingua parlata

� codice a ripetizione

� codice a controllo di parità

� Si fa riferimento a messaggi e sistemi binari e quindi a codici binari

3

Codici di canaleCodici di canale

� Esempi pratici:

� codice fiscale

� codici a barre

� numerazione assegni

� biglietti aerei


� biglietti aerei

� La ridondanza implica un allungamento del messaggio trasmesso,

con conseguenze indesiderate del tipo: aumento dello spazio di

memoria richiesto (“ storage”) aumento di tempi di trasmissione

(e/o memorizzazione) aumento della banda richiesta (es.

applicazioni real-time)

4

Applicazioni della codifica di canaleApplicazioni della codifica di canale

� L’importanza della codifica di canale cresce con le trasmissioni digitali

� Primo impiego dei codici: trasmissioni con lo spazio profondo:� canale AWGN, banda illimitata, pochi ricevitori (costi trascurabili)

� Memorie di massa:� compact disc, digital versatile disc, nastri magnetici

� Comunicazioni digitali senza filo (“wireless”):� GSM, UMTS, wifi, wimax


� GSM, UMTS, wifi, wimax

� Comunicazioni digitali su filo (“wired”):� Modem per linea telefonica

� Broadcasting digitale:� DAB, DVB

5

Prestazioni e complessità della codificazionePrestazioni e complessità della codificazione

� I primi sistemi di comunicazione numerici sono stati progettati

cercando di ottenere una bassa probabilità di errore con l’uso di

elevata potenza oppure bande più larghe

� In trasmissione tale approccio è adeguato se la probabilità di errore

richiesta non è troppo bassa, ed è basato sul concetto di ottenere


richiesta non è troppo bassa, ed è basato sul concetto di ottenere

buone prestazioni acquistandole con le risorse più preziose, cioè

potenza e banda

� Grazie ai risultati ottenuti da C. E. Shannon si è visto che l’impiego

di complesse tecniche di co-decodifica, consentite dal progresso

tecnologico, si possono ottenere elevate prestazioni al prezzo di

aumentare la complessità del sistema

Modello di Sistema di Trasmissione


� Sequenza binaria (data stream) emessa dalla sorgente� Il data stream va in ingresso al codificatore di canale che

effettua l’operazione di codifica (introduzione di ridondanza)� Code stream in uscita dal codificatore. � In ricezione il decodificatore, rimuovendo la ridondanza, effettua

rivelazione o correzione di eventuali errori introdotti dal canale

Errori sui bit

� Il canale di comunicazione (attraverso la sua risposta impulsiva) può introdurre distorsioni nel segnale ricevuto

– Condizioni di Nyquist non verificate in ricezione� Negli apparati in ricezione è presente una componente additiva di

rumore termico– Disturbo sovrapposto al segnale ricevuto


– Disturbo sovrapposto al segnale ricevuto� Entrambi questi fenomeni possono portare ad errori sul flusso

binario in uscita al demodulatore numerico

Ex: Tx [001010001] Rx [000010001]

Errore sul terzo bit

Effetto della codifica di canale� Mediante l’introduzione di ridondanza nel flusso binario trasmesso

l’operazione di codifica di canale mira a

– Rilevare la presenza di errori

• Ex: codice di parità

00-0 01-1 10-1 11-0

permette di rilevare la presenza di un errore


permette di rilevare la presenza di un errore– Correggere un numero limitato di errori

• Ex: codice a ripetizione

0-000 1-111

� Diminuzione della probabilità di errore sul bit SENZA AUMENTARE LA POTENZA TRASMESSA

9

Classificazione dei codici di canaleClassificazione dei codici di canale

Codici dicanale

Codici ablocchi

Codici adalbero


Codici lineari

Codici nonlineari

Codici lineari(convoluzionali)

Codici nonlineari

Codiciciclici

TCM Turbocodici

10

Codici a blocchiCodici a blocchi

� Data stream (non codificato) e code stream (codificato) vengono

segmentati in blocchi di lunghezza prestabilita (dataword e codeword)

� Per un codice a blocchi (n,k) le data word consistono in k bit e le

codeword in n bit (n<k)

� Codice di canale: è l’insieme delle 2k n-ple di bit, le code word x


� Codice di canale: è l’insieme delle 2k n-ple di bit, le code word x

� Codificatore: è l’insieme delle 2k coppie (u, x) con

� u = data word (k-pla di bit)

� x = corrispondente code word (n-pla di bit)

11

Esempi di codici elementariEsempi di codici elementari

Codice a ripetizione (3,1) ovvero n=3,

k=1

� Nel codice si usano solo 2 delle 8

possibili sequenze di lunghezza 3

Data words Code words0 0001 111

codificatore


Codice a controllo di parità (3,2)

� L’ultimo bit è un bit di parità rispetto

ai primi 2.

Data words Code words00 00001 01110 10111 110

codificatore

12

Esempio di codice Esempio di codice didi controllocontrollo di parità (4,3)di parità (4,3)

Esempio di codice di parità (4, 3):

[0000], [0011], [0101], [0110]

[1001], [1010], [1100], [1111]

� Il numero di 1 presenti in tutte le parole è sempre pari


� Il numero di 1 presenti in tutte le parole è sempre pari

� La ricezione della parola: [0100]

è affetta da errore poiché contiene un numero dispari di 1

13

Esempio di codice Esempio di codice didi controllocontrollo di parità (6,3)di parità (6,3)

� Esempio di codice di parità (6, 3):

[000000], [001011], [010110], [011101]

[100101], [101110], [110011], [111000]

� gli ultimi 3 bit sono calcolati sommando bit 1-2, 2-3 e 1-3 rispettivamente


� Ricevendo la seguente parola:

[010111]

si rivela un errore dal momento che il bit 6 è diverso dalla somma del bit

1 e 3

14

Codici a blocchi Codici a blocchi –– (senza memoria)(senza memoria)

� Differenza tra “codice” e “codificatore” :

Codice: è una collezione di code word, indipendente dal modo nel

quale le code word stesse sono ottenute

Codificatore: si riferisce alla corrispondenza uno-a-uno tra data word e

code word, e si applica anche al dispositivo che realizza tale compito


� Il codice (n,k) è a blocchi quando il codificatore è senza memoria, cioè

quando agli stessi k bit della data word corrispondono sempre gli stessi

n bit della code word

� Il rapporto Rc = k/n è la frequenza del codice (“rate”)

� Ogni dataword (blocco) viene codificata indipendentemente senza

interazioni con le data word precedenti o successive

15

Codici ad alberoCodici ad albero

� La corrispondenza tra data word e code word ha memoria: gli n bit

della codeword dipendono anche da alcune data word precedenti

� Riferimento a data stream infinitamente lunghi ed a code stream che

iniziano al tempo zero e continuano indefinitamente nel futuro

� il data stream viene diviso in segmenti (data frame) di k0 data bit, con


k0 (generalmente) un intero piccolo

� Codificatore: macchina a stati finiti che mantiene una certa memoria

delle data frame precedenti:

� Nel caso più semplice memorizza le m data frame più recenti inviate

16

Codici lineari e non lineariCodici lineari e non lineari

Codice lineare

� L’insieme delle code word (ovvero code stream per i codici ad

albero) è chiuso per la somma modulo 2, ovvero:

� considerate due qualsiasi code word, la loro somma modulo 2 è

ancora una code word


ancora una code word

� ciò implica che la parola di tutti zeri è una code word

Codice non lineare

� In caso di non validità della proprietà precedente

17

Codificatori sistematiciCodificatori sistematici

� Il Codificatore si dice sistematico quando i primi k bit di ogni code

word x coincidono con i k bit della data word u

� A volte si parla di sistematicità del codice, anziché del codificatore:


tuttavia, dal momento che la proprietà riguarda il mapping delle data

word nelle code word, è propria del codificatore

18

Rivelazione di errore e ritrasmissioniRivelazione di errore e ritrasmissioni

� In accordo a come il sistema fa uso delle capacità del codice, si

distingue tra: Codici a rivelazione d’errore e Codici a correzione

d’errore

� Questa distinzione non riguarda i codici ma piuttosto le strategie

seguite dal sistema di co-decodificazione


seguite dal sistema di co-decodificazione

� Nella rivelazione d’errore il decodificatore osserva la sequenza

ricevuta all’uscita del demodulatore/decisore, e rileva se sono

avvenuti errori o meno

19Rivelazione d’erroreRivelazione d’erroreAutomatic Repeat reQuest Automatic Repeat reQuest -- ARQARQ

� Nel monitoraggio dell’errore (error monitoring), il decodificatore

fornisce all’utente una indicazione continua sulla qualità della

sequenza ricevuta, in modo che si possa scartare la sequenza se

La rivelazione d’errore è utilizzata per realizzare uno di due possibili

schemi:


sequenza ricevuta, in modo che si possa scartare la sequenza se

l’affidabilità diviene troppo bassa

� Nella richiesta di ripetizione (ARQ, Automatic Repeat reQuest) si

chiede al trasmettitore di ripetere le trasmissioni fallite e, dunque,

deve essere disponibile un canale di ritorno (feedback) dal ricevitore

al trasmettitore

20

Correzione Correzione d’errore (d’errore (ForwardForward ErrorError CorrectionCorrection--FECFEC))

� Il decodificatore tenta di ripristinare la corretta sequenza trasmessa

quando vengono rilevati errori nella sequenza ricevuta

� A parità di codice la Forward Error Correction (FEC) richiede

algoritmi di decodifica più complessi rispetto alla rivelazione d’errore


algoritmi di decodifica più complessi rispetto alla rivelazione d’errore

con ARQ

21

Correzione d’errore (Forward Error Correction Correzione d’errore (Forward Error Correction -- FEC)FEC)

� Il decodificatore tenta di ripristinare la corretta sequenza trasmessa

ESEMPIO: Codice ciclico (6, 3):

[000000], [001011], [010110], [011101],

[100101], [101110], [110011], [111000]

utilizzato su un sistema con correzione di errore


� Sequenza di parole ricevute:

[000100] → [011101] → [101111] → [111000]

� La prima e la terza parola non appartengono al codice e quindi se ne

può tentare una correzione, ad esempio limitando al minimo il

numero di bit da modificare nelle parole errate:

[000000] → [011101] → [101110] → [111000]

22

Confronto tra ARQ e FECConfronto tra ARQ e FEC

� La scelta dipende dalla particolare applicazione e dalla complessità

del sistema di trasmissione considerato

� Lo schema ARQ è usualmente impiegato nelle comunicazioni tra

computer, essendo disponibile un canale di trasmissione a due vie

insieme a dispositivi con grande memoria che memorizzano le


informazioni entranti mentre effettuano, su richiesta, la procedura di

trasmissione

� Lo schema FEC si adotta quando si vuole proteggere l’informazione

in un canale a una via oppure quando è richiesto il tempo reale

oppure ritardi controllati (es. trasmissioni vocali digitali interattive,

deep-space communications)

23

Codici a blocco lineariCodici a blocco lineari

� Un codice a blocco è lineare se l’insieme delle codeword è chiuso per

la somma modulo 2, ovvero, considerate due qualsiasi codeword, la

loro somma modulo 2 è ancora una codeword

� Le operazioni di somma nelle sequenze binarie sono trattate con

l’aritmetica modulo 2 ovvero definendo un Campo di Galois GF(2)


� Nella pratica tale aritmetica è realizzata tramite operatori logici:

somma prodotto

0+0 = 0 0 x 0 = 0

0+1 = 1 0 x 1 = 0

1+0 = 1 1 x 0 = 0

1+1 = 0 1 x 1 = 1

Somma algebrica modulo 2

EXOR logico

0+0 = 0 0⊕0 = 0

0+1 = 1 0⊕1 = 1

1+0 = 1 1⊕0 = 1

1+1 = 2 � 0 1⊕1 = 0

Prodotto algebrico

AND logico

0 x 0 = 0 0∧0 = 0

0 x 1 = 0 0∧1 = 0

1 x 0 = 0 1∧0 = 0

1 x 1 = 1 1∧1 = 1

24

Codici a blocco lineariCodici a blocco lineari

� Un codice lineare possiede le seguenti proprietà:

– La somma di due codeword è ancora una codeword.

– La n–pla di tutti zeri è sempre una codeword

� Un codificatore a blocco (n, k) lineare è una corrispondenza tra:

dataword u = [u0,…, uk-1] di k digit e


dataword u = [u0,…, uk-1] di k digit e

codeword x = [x0,…, xn-1] di n digit

� È realizzabile tramite una coppia di registri a scorrimento connessi tra

di loro attraverso un banco di sommatori modulo 2 (EXOR logici)

25

Codici sistematiciCodici sistematici

� Codificatore (n, k) sistematico: i primi k bit delle codeword generate

corrispondono ai bit delle dataword che le generano

� La sistematicità è una proprietà del CODIFICATORE, ovvero della regola di

associazione tra dataword e codeword (un codice può, al limite, essere

esprimibile in forma sistematica, i.e. contiene parole che iniziano come le

dataword)


dataword)

� Semplifica la struttura in decodifica

� Si può dimostrare che, dato un codice lineare con date prestazioni

(probabilità di rilevare e/o correggere una parola errata) ne esiste sempre

uno equivalente esprimibile in forma sistematica

26

Esempi di codici a blocco lineariEsempi di codici a blocco lineari

� Codice a ripetizione (4,1):0 � 00001 � 1111

x0 = u0 x1 = u0

x2 = u0 x3 = u0

u0

n = 4

k = 1

x2 x1 x0x3


� Codice a parità doppia (4,2):

00 � 000001 � 001110 � 110111 � 1110

x0 = u0 x1 = u1

x2 = u0+u1 x3 = u0+u1

u1

x2 x1 x0

u0

x3

27

Codice Codice di di HammingHamming (7,4)(7,4)

Il codice è sistematico ed utilizza solo 24 = 16 delle 27 = 128 possibili sequenze

Il codice è dato da:

k=4

u u u uxi = ui i=1,2,3,4

Codice di Hamming (7,4)


0001 0001 011

0010 0010 110

0011 0011 101

0100 0100 111

0101 0101 100

0110 0110 001


x7 x6 x5 x4 x3 x2 x1

n=7

u4 u3 u2 u1

+ + +

x5 = u1+u2+u3

x6 = u2+u3+u4

x7 = u1+u2+u4

0110 0110 001

0111 0111 010

1000 1000 101

1001 1001 110

1010 1010 011

1011 1011 000

1100 1100 010

1101 1101 001

1110 1110 100

1111 1111 111

28

Matrice generatrice del codiceMatrice generatrice del codice

� Il codice viene specificato dalle connessioni tra gli stadi del registro di

ingresso ed i sommatori

� Se il codice è sistematico, vanno assegnate solo le (n-k) equazioni

del controllo di parità


� L’informazione che specifica la regola di codifica (ovvero, la

� struttura del codificatore) è rappresentabile in modo sintetico da una

matrice binaria G di dimensioni k x n (matrice generatrice del codice)

� L’elemento (i,j) di G vale 1 se l’i-esima cella del registro d’ingresso è

connessa al j-esimo sommatore, altrimenti vale 0

29


� Si può quindi scrivere: x = u G (1)

con x = [x1,…,xn] vettore (1 x n) ed u = [u1,…,uk] vettore (1 x k)

� Dalla (1), x viene ottenuto sommando le righe di G che

corrispondono agli 1 nella u


corrispondono agli 1 nella u

30

EsempioEsempio

� Per il codice di Hamming (7,4), la matrice generatrice G può essere

ricavata per ispezione dal codificatore:

xi = ui i=1,2,3,4

x5 = u1+u2+u3

x6 = u2+u3+u4

x = u +u +u

1 0 0 0 1 0 1

0 1 0 0 1 1 1

0 0 1 0 1 1 0G

=


� Ad esempio, la code word che corrisponde alla data word u =

[1100] si calcola sommando (mod. 2) le prime due righe di G:

code word(coincide con risultato nella tabella del codificatore)

x7 = u1+u2+u4 0 0 0 1 0 1 1

1000101 +0100111 =

1100010

x = u G

31


� Per un codice sistematico le prime k colonne di G formano una

matrice identità k x k, ovvero Ik ,e si ha: G = [ I k ¦ P ]

dove P è una matrice di dimensioni [k x (n-k)] contenente le

informazioni relative ai controlli di parità

� Per un codice sistematico la conoscenza di P definisce in modo


� Per un codice sistematico la conoscenza di P definisce in modo

completo la regola di codifica

� ESEMPIO Per il codice di Hamming (7,4) si ha:

1 0 0 0 1 0 1

0 1 0 0 1 1 1

0 0 1 0 1 1 0

0 0 0 1 0 1 1

G

=

4

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

I

=

1 0 1

1 1 1

1 1 0

0 1 1

P

=

32

Proprietà dei codici a controllo di paritàProprietà dei codici a controllo di parità

� Proprietà 1: Ogni code word è una somma di righe della matrice generatrice

� Proprietà 2: Il codice a blocchi è costituito da tutte le possibili somme delle righe della matrice generatrice

� Proprietà 3: La somma di due code word è ancora una code word


� Proprietà 3: La somma di due code word è ancora una code word

� Proprietà 4: La n-pla di tutti zeri è sempre una code word

� Dalle proprietà 1-4, i codici a controllo di parità sono anche detti codici lineari

� In effetti, la linearità viene espressa dalla: x = u G

33

Equivalenza tra codici a blocchi e sistematiciEquivalenza tra codici a blocchi e sistematici

� Ogni codice a blocchi (n,k) non sistematico è equivalente a un codice

sistematico (n,k) a blocchi

� Quindi si possono considerare solo codici sistematici

� Infatti due codici con matrici generatrici ottenibili l’una dall’altra con

operazioni sulle righe e permutazioni sulle colonne hanno la stessa


probabilità di rilevare una parola errata � codici “equivalenti”

� la probabilità di errore sul bit può essere diversa: codici equivalenti

possono avere codificatori diversi e, cioè, diversi mapping tra le data

word e le code word

� Se interessa la probabilità di rilevare una parola errata si possono

considerare solo codici sistematici

34

Peso e distanza di Peso e distanza di HammingHamming, e distanza minima, e distanza minima

� Peso di Hamming di una code word: numero di 1 contenuti

� Distribuzione dei pesi del codice: insieme di tutti i pesi di un codice, insieme al numero di code word di quel peso

� Codici equivalenti hanno la stessa distribuzione dei pesi

� Distanza di Hamming dij tra due code word xi e xj: numero di posizioni in cui le due code word differiscono. Si ha : 0 ≤ dij ≤ n


posizioni in cui le due code word differiscono. Si ha : 0 ≤ dij ≤ n

� Distanza minima dmin del codice: la più piccola tra le distanze di Hamming di distinte code word (i≠j)

� TEOREMA: la distanza minima di un codice a blocchi lineare è il peso minimo della code word diversa da zero

35

Peso e distanza di Peso e distanza di HammingHamming, e distanza minima, e distanza minima

TEOREMA: la distanza minima di un codice a blocchi lineare è il peso

minimo della code word diversa da zero

Dimostrazione

� in un codice lineare: la somma di due parole è una parola di codice e

restituisce la parola nulla se e solo se le due parole sono uguali


restituisce la parola nulla se e solo se le due parole sono uguali

� la distanza di Hamming tra due parole è pari al peso della somma

� le possibili distanze di Hamming tra coppie di parole diverse corri-

spondono ai pesi delle parole del codice diverse dalla parola nulla

� La distanza minima di Hamming è il peso minimo tra i pesi delle

parole di codice diverse dalla parola nulla.

36

EsempioEsempio

Per il codice di Hamming (7,4) si ha la seguente distribuzione dei pesi:

Peso Numero di code words0 1

3 7

Codice di Hamming (7,4)


0001 0001 011

0010 0010 110

0011 0011 101

0100 0100 111

0101 0101 100

0110 0110 001


Dalla proprietà (5) si ottiene: dmin = 3

3 7

4 7

7 1

0110 0110 001

0111 0111 010

1000 1000 101

1001 1001 110

1010 1010 011

1011 1011 000

1100 1100 010

1101 1101 001

1110 1110 100

1111 1111 111

37

Rivelazione d’erroreRivelazione d’erroreTEOREMA (SULLA RILEVAZIONE D’ERRORE):

Un codice lineare a blocchi (n,k) con distanza minima dmin può rilevare tutti i vettori errore di peso non maggiore di:

dmin -1

ovvero si rivela un numero massimo di errori pari a (dmin-1)


Una configurazione di errori tale da tramutare una parola di codice valida in un’altra parola di codice valida non è rilevabile (i.e. un numero di errori pari in un codice a parità)

La distanza minima tra due codeword valide è dmin

Un numero di errori minore di dmin è pertanto sempre rilevabile

Correzione di Errori

� Laddove si riceva una parola y si hanno due possibilità– y è una parola di codice valida

• Non vi sono errori• Vi sono errori tali da modificare la parola trasmessa in un’altra

parola di codice valida– y non è una parola di codice valida

• Si richiede la ri-trasmissione avendo rilevato la presenza di


• Si richiede la ri-trasmissione avendo rilevato la presenza di errori

• Si corregge la parola ricevuta– y è data dalla parola trasmessa più il vettore di errore– si assume sia stata trasmessa la parola di codice a

distanza minima da y (si ipotizza cioè che sia avvenuto il numero minimo di errori possibili) � DECODIFICA a MASSIMA VEROSIMIGLIANZA (ML)

39

Correzione di erroriCorrezione di errori

� L’algoritmo di decodifica basato sulla minima distanza ipotizza che e, il

vettore errore effettivamente occorso, sia quello a minimo peso

nell’insieme dei 2k vettori errore che portano alla sindrome associata

alla sequenza ricevuta y

TEOREMA (SULLA CORREZIONE D’ERRORE):


TEOREMA (SULLA CORREZIONE D’ERRORE):

un codice lineare a blocchi (n,k), con distanza minima dmin , può

correggere tutti i vettori d’errore contenenti un numero di errori non

maggiore di:

min( 1)

2

dt

− =

40

Decodifica a massima verosimiglianza (ML)Decodifica a massima verosimiglianza (ML)

Rappresentazione qualitativa delle regioni di decisione assegnate alle code words:

min min min

Detected Errors Corrected Errors

( 1) ( 1)/2

2 1 0

3 2 1

4 3 1

d d d− −


dmin

Code words Sequenze ricevute con errori

4 3 1

5 4 2

6 5 2

7 6 3

8 7 3

9 8 4

41

Decodifica a massima verosimiglianza (ML)Decodifica a massima verosimiglianza (ML)

� ESEMPIO: Il codice di Hamming (7,4) presenta dmin = 3 e quindi può

correggere errori, ovvero gli errori singoli

� Un codice a blocchi (n,k) con distanza minima dmin è un codice a

correzione di t errori (t-error correcting code), o codice (n,k,t)

(3 1) / 2 1t = − =


� L’obiettivo di un codice a blocchi (n,k) è di usare la propria ridondanza

per ottenere la maggiore dmin possibile

42

Probabilità di errore sul bit e sulla parolaProbabilità di errore sul bit e sulla parola

� Obiettivo generale della codifica: minimizzare la probabilità d’errore sul bit Pb(e)

� Codici a blocchi: si cerca di minimizzare la probabilità d’errore sulla parola codificata Pw(e)

� Nella correzione dell’errore, se il codice (n,k) corregge t errori:

� si ha un errore sulla parola quando si hanno almeno t+1 bit errati su


� si ha un errore sulla parola quando si hanno almeno t+1 bit errati su n della parola di codice ricevuta

� la parola di codice decisa, con errore, contiene almeno dmin= 2t+1bit errati su n

� nella parola dati ci sono, in media, k(2t+1)/n bit errati

� relazione tra probabilità d’errore sulla

parola e probabilità d’errore sul bit:2 1

( ) ( )b w

tP e P e

n

+≈

Codifica di Canale Codici a...

Documents

Transcript of Codifica di Canale Codici a...