Appunti di Trasmissione Numerica

=I

˜ = 

 . ..

.. ..

k ..

 

. .

| .

 

|

0 0 0 1 p p . . . p

k,1 k,2 k,n−k

La moltiplicazione matriciale righe per colonna segue le regole classiche, con

l’eccezione che si una una somma modulo 2 invece della somma convenzionale.

Non esiste un metodo analitico per determinare gli elementi della sotto-

matrice P e per metterli in relazione con d .

min

4.9 Codice di Hamming

Un codice di Hamming è un codice lineare a blocchi per il quale sono verificate

le seguenti relazioni:

• − ≤

q = n k 3

q

• −

n = 2 1

E’ possibile affermare che la distanza minima e fissa e vale d = 3 Pertanto

min

un codice di Hamming può rilevare due errori o correggere un errore per ogni

parola di codice. Per costruire un codice di Hamming sistematico basta scegliere

una sotto-matrice P costituita da righe di q bit aventi tutte e due o più bit a 1.

4.9.1 Decodifica di un codice lineare sistematico a blocchi

Supponiamo di trasmettere la parola di codice X e di ricevere un vettore Y . Se

6

sono avvenuti degli errori di trasmissione, X = Y .

Un modo per effettuare la rivelazione degli errori è confrontare Y con ognuna

k

→

delle parole di codice è necessario memorizzare tutte le 2 parole di codice.

4.9.2 Decodifica matrice di controllo parità

Un metodo più efficiente per effettuare la decodifica e rilevare gli errori consiste

nell’utilizzare la sotto-matrice P . Si definisce la matrice di controllo parità H

come: T

|I

H =

˜ P q

Tale matrice ha la seguente proprietà:

T

XH = (0, 0, 0, ..., 0)

31

dove X è una parola di codice. Se Y non è una parola di codice, il prodotto

T

Y H contiene almeno un elemento non nullo.

4.10 Decodifica a sindrome

T

La quantità S = Y H viene definita sindrome e consente di rilevare gli errori

presenti nel vettore ricevuto Y . Se S è un vettore nullo, possiamo essere in uno

tra i 2 possibili scenari:

1. non si sono verificati errori.

2. si sono verificati errori e Y è uguale ad una parola di codice differente da

quella della trasmessa (gli errori non sono rilevabili).

Se la sindrome S contiene almeno un elemento non nullo di è in presenza di

errori.

La correzione degli errori è più complessa, ma si può ugualmente sfruttare

le proprietà della sindrome S. Definiamo un vettore di errore E costituito da n

bit. Tale vettore indica la posizione degli errori di trasmissione contenuti in Y

con 1.

La sindrome dipende solo dagli errori occorsi e non dalla specifica parola di

codice X trasmessa. n −1,

PROBLEMA: I possibili errori su una parola codificata con n bit sono 2

n−k

− −

ma essendo la sindrome costituita da n k bit, può rappresentare solo 2 1

→

errori. Ad ogni vettore di sindrome S corrispondono più vettori di errore

E. Si deve quindi identificare l’errore che ha la maggiore probabilità di essere

associato ad ogni specifico valore della sindrome.

4.10.1 Decodifica a massima vero-somiglianza

La strategia nota col nome di decodifica a massima vero-somiglianza consiste

nello scegliere, tra tutti i possibili vettori E che generano òa stessa sindrome

T

S = EH , il vettore errore Ê più probabile. Si può dimostrare che tale vettore è

quello che contiene il numero minore di bit sbagliati. Questa scelta corrisponde

a determinare la parola di codice X̂ che ha la minore distanza di Hamming dal

vettore ricevuto Y . La decodifica a massima vero-somiglianza è ottima nel senso

che minimizza la probabilità di errore per parola P .

we

4.11 Codici ciclici

E’ possibile dimostrare che, affinché un codice utilizzato per effettuare cor-

≥

rezione di errori abbia capacità correttiva t 1 e R =1

˜ è necessario avere

c

n >> 1 e k >> 1. Purtroppo però la complessità hardware necessaria per

codificare decodificare parole di codice con elevata lunghezza è troppo. Al fine

di superare questa limitazione, sono stati concepiti i codici ciclici.

I codici ciclici sono una sotto-classe dei codici lineari a blocchi la cui struttura

consente una riduzione della complessità del codificatore e del decodificatore

anche in presenza di parole di codice caratterizzate da elevata lunghezza.

Considerando una generica parola di codice costituita da n bit, un codice

ciclico è detto tale se:

• soddisfa la proprietà di linearità.

32

• ogni scorrimento ciclico (shitf ciclico) dei bit della parola di codice X

genera un’altra parola di codice.

I codici ciclici possono esser trattati matematicamente associando alla parola di

codice X un polinomio X(p) con p variabile reale arbitraria.

La potenza di codice del bit rappresentato dal coefficiente associato a p. Per

quanto visto sopra, i codici vengono anche definiti codici polinomiali.

4.11.1 Formulazione matematica

La formulazione matematica che fornisce le basi teoriche per la trattazione dei

codici è costituita dai campi di Galois. Assumiamo quanto segue:

1. la somma di due polinomi è ottenuta mediante la somma modulo 2 dei

rispettivi coefficienti. →

2. poiché tali coefficienti possono solo valere 0 o 1 la somma e la differenza

si equivalgono come operazioni.

0

Il polinomio dopo lo scorrimento X (p) è legato a X(p) secondo la seguente

formula: 0 n

X (p) = pX(p) + x (p + 1)

n−1

Ogni codice ciclico può essere rappresentato dal polinomio generatore G(p)

avente la seguente forma q q−1 · · ·

G(p) = p + g p + + g p + 1

q−1 1 n

dove i coefficienti g sono tale che il polinomio sia un fattore di (p + 1)

i ∗

Ogni parola del codice può essere scritta come: X(p) = Q (p) G(p)

M

dove Q (p) è il polinomio che rappresenta un blocco di k bit di messaggio.

M n

Ogni fattore di (p + 1) che ha grado q può essere utilizzato come polinomio

generatore.

4.11.2 Tabella di confronto tra codici ciclici

Codice Hamming BCH Golay

n 7 15 31 15 31 63 23

k 4 11 26 7 21 45 12

R 0.57 0.73 0.84 0.46 0.68 0.71 0.52

c

d 3 3 3 5 5 7 7

min

G(p) 1011 10011 100101 111010001 11101101001 1111000001011001111 101011100011

4.11.3 Codici ciclici sistematici e non sistematici

Un codice ciclico può essere sistematico o non sistematico. Ciò dipende dalla

struttura del termine Q (p). Nel seguito incentreremo la nostra attenzione sui

M

codici ciclici sistematici.

Affinché il codice sia sistematico, la parola X(p) relativa al messaggio M (p)

deve essere espressa come: q

X(p) = p M (p) + C(p)

33

dove M (p) è il polinomio dei bit di informazione e C(p) quello dei bit di controllo.

Il polinomio dei bit di controllo può essere ottenuto come resto della divisione

q

tra p M (p) e G(p) q

C(p) = [p M (p)]mod[G(p)]

Nei codici ciclici si può effettuare la decodifica utilizzando la sindrome:

S(p) = [Y (p)]mod[G(p)]

Se S(p) = 0 non si ha rilevato la presenza di errori, in caso contrario la parola

di codice ottenuta è stata corrotta.

VANTAGGI:

• semplicità di codifica.

• semplicità nel calcolo della sindrome.

• Struttura matematica ben definita che permette lo sviluppo di metodi di

decodifica molto efficienti.

4.12 Codici convoluzionali

I codici convoluzionali non generano sequenze organizzate in parole di codice

ben definite. Il bit codificato x dipende dall’ingresso m e dallo stato del re-

i i

gistro (dagli L bit di messaggio precedenti). Il bit di messaggio m influenza

i

i successivi L + 1 bit. Il meccanismo permette di trasformare una sequenza

di bit in un sequenza differente, ma non aggiunge ridondanza (a patto di non

aggiungere due o più sommatori a modulo 2 che vanno a creare i bit di controllo).

In generale, se si usano n sommatori modulo 2, si ottiene una code rate R = 1/n.

c

Il bit di messaggio m influenza i successivi n(L + 1) bit. La quantità n(L + 1)

i

viene definita constraint length. Si definisce invece memoria la quantità L (la

lunghezza dello shift register ). Analogamente a quanto fatto per i codici a bloc-

chi, si parla di codici convoluzionali(n,k,L). ≥

Per ottenere una code rate di R > 1/n è necessario utilizzare k 2 shitf

c

register. In particolare utilizzando k shitf register si ottiene una code rate

R > k/n.

c OSSERVAZIONI: Per ottenere una code rate R > 1/n è possibile utilizzare

c

un solo registro di lunghezza kL + 1 e fare scorrere i bit a gruppi di k.

I codici convoluzionali tipicamente sono usati in sistemi FEC reali con k e n

piccoli e una constraint length compresa tra 10 e 30.

Per studiare i codici convoluzionali vengono usate 3 principali rappresenta-

zioni:

1. ad albero.

2. a traliccio.

3. diagramma degli stati. 34

4.12.1 Distanza libera

Abbiamo visto che la capacità correttiva e/o rivelativa di un codice a blocchi

dipende dalla distanza minima del codice. Nei codici a blocchi la distanza

minima è determinata analizzando i pesi delle parole del codice. Nel caso di

un codi ce convoluzionale, non essendo individuabili delle parole di codice, si

considera il peso dell’intera sequenza X generata da una determinata sequenza

di messaggi. Si definisce distanza libera la quantità:

6

d = [w(X)] : X = (0, 0, 0, . . . )

l min

Il calcolo può essere effettuato facilmente senza analizzare il peso w di tutte

le possibili sequenze di w(X). Si deve identificare il percorso a peso minimo

che ”stacca” dal percorso tutto nullo per riportarsi in esso in modo ”stabile”.

Supponiamo di terminare la sequenza con una serie di 0 in modo da riportare

lo shitf register al suo stato iniziale. Tale procedura elimina alcuni rami dalle L

transizioni finali del traliccio del codice.

Un approccio per il calcolo della distanza libera consiste nel considerate la fun-

zione generatrice di un codice convoluzionale. Tale funzione può essere vista

come la funzione di trasferimento del codificatore rispetto alle transizioni degli

stati. La funzione generatrice fornisce importati indicazioni sulla distanza libera

e sulla probabilità di errore che si può ottenere in decodifica.

4.12.2 Metodi di decodifica

Esistono sostanzialmente tre metodi per la decodifica di codici convoluzionali:

→

1. Algoritmo di Viterbi effettua una decodifica ottima a massima vero-

somiglianza, ma richiede hardware molto complesso.

→

2. Decodifica Sequenziale può realizzare compromessi differenti tra com-

plessità hardware e bontà della decodifica.

→

3. Decodifica a Retroazione richiede hardware molto semplice ma degrada

le prestazione della decodifica.

4.13 Algoritmo di Viterbi

un decodificatore ottimo a massima vero-somiglianza deve esaminare l’intera

sequenza ricevuta Y e trovare il perco