Tesi - Algoritmi di codifica e decodifica per codici Low Density Parity Check

6

Indice

1 Introduzione 9

..................................................................................................................

1.1 Codifica di Canale 9

..............................................................................................

1.2 Codifica di codici a blocco binari 9

.......................................................................

1.3 Decodifica di codici a blocco binari 10

.................................................................

1.3.1 MAP 11

..........................................................................................................

1.3.2 ML 11

.............................................................................................................

2 Codici Low Density Parity Check 13

.............................................................................

2.1 Introduzione ai codici LDPC 13

.................................................................................

2.2 Rappresentazione grafica 14

.......................................................................................

2.2.1 Prestazioni 14

......................................................................................................

2.3 Costruzione della matrice di controllo di parità 16

....................................................

2.3.1 Metodo di Gallagher 16

.......................................................................................

2.3.2 Metodo di Reed-Solomon 17

...............................................................................

2.3.2.1 Proprietà del codice accorciato C 18

...........................................................

b

2.3.2.2 Procedura di costruzione della matrice di controllo di parità 18

..................

2.3.3 Metodo Progressive Edge Growth 19

..................................................................

2.4 Standard che utilizzano i codici LDPC 21

.................................................................

2.4.1 DVB-S2 21

..........................................................................................................

2.4.2 10GBase-T 23

......................................................................................................

2.4.3 Wi-Fi (802.11n) 23

..............................................................................................

2.4.4 G.hn 28

................................................................................................................

3 Decodifica di codici LDPC: Algoritmo Sum-Product 31

.............................................

3.1 A Posteriori probability 31

.........................................................................................

3.3 Test dell’Algoritmo Sum Product su un codice (4,2) 34

............................................

3.4 Decodifica di codici LDPC tramite Algoritmo Sum-Product 39

................................

3.4.1 FFG per la decodifica di codici LDPC 39

...........................................................

3.4.2 SPA applicato ai codici LDPC 40

........................................................................

3.4.3 Aggiornamento dei check node e variable node 41

.............................................

Bibliografia 43

.....................................................................................................................

7

8

Capitolo 1.

Introduzione

1.1 Codifica di Canale

La codifica di canale ha lo scopo di garantire la corretta trasmissione dei dati attraverso

un canale rumoroso. A tal proposito si trasforma il messaggio di partenza u∈U in uno più

lungo c∈C. La codifica di canale rappresenta dunque, assieme alla codifica di sorgente,

uno dei vantaggi di trasmettere in digitale rispetto alle vecchie trasmissioni in analogico.

Esistono due diverse metodologie che il ricevitore può utilizzare per correggere il

messaggio ricevuto e sono:

• ARQ (Automatic Repeat reQuest): questa tecnica permette di rilevare se ci

sono stati errori in fase di trasmissione. Tuttavia, questi errori

non vengono corretti, ma viene richiesta in modo automatico la ritrasmissione

dei pacchetti cosiddetti “corrotti”.

• quest’altra tecnica, invece, permette non

FEC (Forward Error Correction):

solo di rilevare se ci sono stati errori, ma anche di tentare di correggerli

basandosi sulle informazioni trasportate dai bit aggiuntivi introdotti in fase di

codifica

È chiaro come utilizzando la seconda opzione non vi è garanzia che il messaggio

corretto in maniera esatta. L’ ARQ risulta invece assai più

contenente errori venga

affidabile ma, il tempo richiesto per la ritrasmissione può risultare svantaggioso,

soprattutto nel caso di applicazioni real-time.

Questa tesi tratta i codici LDPC che sono di tipo FEC.

1.2 Codifica di codici a blocco binari

Considerando una parola di codice u lunga k, che codificata diventa c lunga n, dove: