Universita degli studi di Trieste

Dipartimento di Ingegneria e Architettura

Tesi di Laurea in

Ingegneria Informatica

Algoritmo probabilistico di tipoMontecarlo per il List Decoding

Relatore Candidato

Prof. Francesco Fabris Daniele Nicassio

Anno Accademico 2015/2016

al caro amico Marco Dalle Feste

Indice

1 Introduzione 7

2 Codifica di canale 11

2.1 Generalita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Codici correttori . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Decodifica di canale . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3.1 Distanza di Hamming e distanza minima di un codice . . . . 13

2.3.2 Decodifica a distanza minima . . . . . . . . . . . . . . . . . 14

2.3.3 Sfera di Hamming . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.4 Raggio di copertura . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.5 Codici perfetti . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.4 Codici lineari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.4.1 Campi finiti . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4.2 Struttura e codifica dei codici lineari . . . . . . . . . . . . . 17

2.4.3 Codice duale e sindrome di un ennupla . . . . . . . . . . . . 18

2.5 Codici ciclici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5.1 Costruzione di un codice ciclico a partire dalle radici . . . . 19

2.6 Codici di Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.7 Codici BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 List decoding 23

3.1 Generalita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Formalizzazione del problema . . . . . . . . . . . . . . . . . . . . . 24

3.3 Limitazione di Johnson . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.4 Algoritmi per il list decoding . . . . . . . . . . . . . . . . . . . . . . 25

3.4.1 Algoritmo di Sudan . . . . . . . . . . . . . . . . . . . . . . . 25

3.4.2 Algoritmo Guruswami-Sudan . . . . . . . . . . . . . . . . . 28

3.4.3 Algoritmo di Wu . . . . . . . . . . . . . . . . . . . . . . . . 29

3.5 Limiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5

4 Studio dello spazio delle parole di codice 334.1 Distanza minima, raggio di copertura e Johnson bound . . . . . . . 334.2 Calcolo della percentuale di copertura . . . . . . . . . . . . . . . . . 374.3 Copertura dello spazio vicino alle parole di codice . . . . . . . . . . 39

5 Proposta di un algoritmo probabilistico 415.1 Motivazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2 Probabilita di successo . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.2.1 Descrizione del modello di decodifica . . . . . . . . . . . . . 435.2.2 Calcolo probabilita di successo . . . . . . . . . . . . . . . . . 445.2.3 Condizioni di funzionamento dell’algoritmo . . . . . . . . . . 45

5.3 Calcolo del numero di tentativi Ni . . . . . . . . . . . . . . . . . . . 455.4 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.5 Condizione di arresto dell’algoritmo . . . . . . . . . . . . . . . . . . 48

6 Implementazione 496.1 Libreria di codifica/decodifica BCH . . . . . . . . . . . . . . . . . . 49

6.1.1 Libreria C . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.1.2 Libreria MATLAB . . . . . . . . . . . . . . . . . . . . . . . 506.1.3 Confronto tra prestazioni MATLAB e C . . . . . . . . . . . 50

6.2 Implementazione dell’algoritmo in MATLAB . . . . . . . . . . . . . 516.3 Programma per la validazione dell’algoritmo . . . . . . . . . . . . . 53

7 Risultati 577.1 Verifica probabilita di successo . . . . . . . . . . . . . . . . . . . . . 577.2 Simulazioni dell’algoritmo completo . . . . . . . . . . . . . . . . . . 58

8 Conclusioni 618.1 Obbiettivi raggiunti . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.2 Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

8.2.1 Confronto con lo stato dell’arte . . . . . . . . . . . . . . . . 618.2.2 Analisi ulteriore della probabilita di successo . . . . . . . . . 62

6

Capitolo 1

Introduzione

I codici correttori sono strumenti che servono a garantire una trasmissione robustae affidabile attraverso un canale rumoroso. Queste codifiche si realizzano introdu-cendo una certa quantita di ridondanza nel messaggio originale, in modo che anchein seguito a un limitato numero di errori di trasmissione quest’ultimo possa essererecuperato con successo.

Sotto opportune condizioni, la tecnica di decodifica piu intuitiva e piu utiliz-zata e la cosiddetta decodifica a distanza minima, che consiste nel decodificare laennupla ricevuta con la (o le) parole di codice piu vicine secondo una certa metri-ca. La metrica utilizzata comunemente e la distanza di Hamming la quale, datedue ennuple, rappresenta il numero di posizioni in cui i simboli delle due ennupledifferiscono.

La decodifica a distanza minima e tuttavia un problema di non facile risolu-zione: una ricerca esauriente delle parole di codice piu vicine ha una complessitacomputazionale esponenziale. E’ stato infatti dimostrato che il problema delladecodifica a distanza minima e in generale NP-Hard, anche nel caso di codicistrutturati come i codici lineari; nell’articolo [1], Berlekamp, McEliece e van Til-borg dimostrarono che il relativo problema decisionale risulta NP-completo. Tuttocio rese improbabile la realizzazione di un algoritmo efficiente, anche se solo perqualche classe speciale di codici, che fosse in grado di restituire la piu vicina paroladi codice fino a una certa distanza t dal messaggio ricevuto (fissato t massimovalore di dissimilarita tollerabile). Per questo motivo il problema di trovare unadecodifica efficiente e stato uno dei punti cruciali per lo sviluppo della teoria deicodici correttori d’errore.

Uno dei primi risultati importanti in questo campo fu ottenuto da Elwyn Ber-lekamp [2], che nel 1968 riuscı a realizzare un algoritmo polinomiale per la deco-difica dei codici lineari BCH, che erano stati da poco introdotti. James Massey[6] generalizzo successivamente il lavoro di Berlekamp ai codici di Reed-Solomon.

7

Successivamente a questi risultati si sono susseguiti un numero sempre maggioredi studi finalizzati alla ricerca di algoritmi efficienti per la decodifica.

Tutti gli algoritmi inizialmente sviluppati erano algoritmi per la decodifica uni-voca, il cui scopo era individuare la parola piu vicina all’ennupla ricevuta. Questascelta limita pero la capacita correttiva del codice al massimo valore teorico dit = bdmin−1

2c errori, con dmin pari alla minima distanza tra tutte le possibili cop-

pie di parole di codice. Questo limite aveva spinto gia negli anni ’50 Elias [3] eWozencraft [9] a sviluppare una tecnica di decodifica alternativa, detta list deco-ding. Il list decoding consiste nell’individuazione, come risultato della decodifica,di una lista di parole di codice possibili, invece che di una unica, come nel casodella decodifica univoca. Anche in questo caso la selezione delle parole restituite sibasa su un criterio di distanza minima, ovvero l’algoritmo restituisce una lista diparole “vicine” all’ennupla ricevuta. Il vantaggio principale di questa tecnica e chepermette, da un punto di vista teorico, di superare la massima capacita correttivabdmin−1

2c, limite invalicabile nel caso di decodifica univoca.

Dopo la sua introduzione, la tecnica list decoding rimase inutilizzata nella pra-tica per l’impossibilita di realizzare un algoritmo efficiente che attuasse questo tipodi decodifica. Bisogna aspettare appena il 1998 perche si presenti qualche nuovorisultato a proposito: in quell’anno infatti Madhu Sudan del MIT [8] propone unalgoritmo polinomiale per la decodifica list decoding. Questo e il primo algoritmopolinomiale di decodifica che permette una capacita correttiva pari a τ ≥ t. L’al-goritmo proposto da Sudan e pero limitato alla classe di codici Reed-Solomon cheabbiano un tasso inferiore ad 1

3.

L’anno successivo Venkatesan Guruswami [4], studente PhD del MIT, realizzaassieme allo stesso Sudan una versione migliorata dell’algoritmo; essa permettedi superare il precedente limite sul tasso estendendo la procedura ai codici Reed-Salomon di tasso arbitrario. La nuova versione dell’algoritmo permette inoltre dicreare una lista di parole di codice distanti al piu τ dall’ennupla ricevuta, con unτ maggiore rispetto a quello della versione precedente; in particolare si riesce aportare il valore di τ alle soglie della limitazione di Johnson, limite che assicurache la lista prodotta non assuma dimensioni esponenziali.

Questi risultati gettanorono le basi per il lavoro di Yingquan Wu [10], chenel 2007 realizza un altro algoritmo polinomiale di list decoding per codici Reed-Solomon e BCH binari. Questo nuovo algoritmo e in grado di raggiungere lo stessolimite di capacita correttiva dell’algoritmo Guruswami-Sudan (GS) per i codiciReed-Solomon, mentre per la prima volta si applica anche ai codici BCH; anche inquesto caso si raggiunge un valore di τ pari alla limitazione di Johnson. L’algoritmoe sempre polinomiale, ma migliora la complessita computazionale che era stataraggiunta dall’algoritmo GS, portandola a O(n6(1 −

√1−D)8), con D = dmin

n

distanza minima relativa del codice.

8

Nonostante questi importanti progressi nelle tecniche di decodifica di list de-coding, sfortunatamente gli algoritmi proposti presentano ancora una complessitacomputazionale troppo alta per consentirne un utilizzo in molte applicazioni reali.

Tutti i precedenti algoritmi sono infatti basati su tecniche di geometria algebricaalquanto pesanti dal punto di vista algoritmico, che riconducono il problema delladecodifica a degli equivalenti problemi di tipo geometrico. Nel caso dell’algoritmoGS il problema e riformulato come due consecutive operazioni di interpolazione efattorizzazione di opportuni polinomi. Nel caso dell’algoritmo di Wu il problemaviene invece trasformato in un equivalente problema di rational curve fitting. Que-sti modelli algebrico-geometrici si rivelano dunque utili per trovare delle soluzioniesatte al problema del list decoding, ma danno luogo a degli algoritmi molto pe-santi dal punto di vista computazionale, anche se formalmente appartenenti allacategorie dei problemi trattabili.

E quindi evidente la necessita di continuare lo studio e la ricerca di algoritmialternativi per la realizzazione di questa decodifica, in modo da cercare di trovareuna soluzione che possa finalmente portare il list decoding, dopo piu di mezzo secolodalla sua iniziale introduzione, a un impiego piu diffuso.

Dalle precedenti considerazioni si puo capire che la realizzazione di un algoritmoesatto per il list decoding e una sfida molto impegnativa, che ha radici forti nellageometria algebrica e che richiede delle solide basi teoriche in questa disciplina.

In questa tesi proveremo allora a usare un approccio alternativo a quello dellacostruzione di un algoritmo esatto, che costituisce lo stato dell’arte. L’approccioe sicuramente molto meno ambizioso, poiche e basato sulla realizzazione di unalgoritmo probabilistico di tipo Montecarlo; dovremo quindi rinunciare all’idea diottenere la lista completa di tutte le parole di codice entro una certa distanza e do-vremo accontentarci di limitare l’impiego dell’algoritmo ad alcune classi di codiciBCH; non solo: dovremo limitare anche i valori dei parametri, visto l’esplosio-ne della complessita che deriva spingendosi oltre tali valori. In cambio potremodisporre di soluzioni corrette con una probabilita controllabile e arbitrariamenteprossima a 1.

Di seguito riassumiamo brevemente il contenuto dei capitoli di questa tesi.

Nel capitolo 2 presenteremo le piu importanti definizioni e i teoremi di baserelativi alla codifica di canale, cercando di dare delle basi teoriche per affrontare ilproblema della decodifica.

Nel capitolo 3 parleremo del list decoding e analizzeremo piu nel dettagliogli algoritmi di Sudan, di Guruswami-Sudan e di Wu, che costituiscono lo statodell’arte.

Nel capitolo 4 verranno presentati una serie di risultati sulla struttura dellospazio delle ennuple e delle parole di codice, risultati funzionali all’introduzionedei concetti che porteranno poi allo sviluppo dell’algoritmo probabilistico.

9

Nel capitolo 5 presenteremo l’idea dell’algoritmo e lo studio della probabilita disuccesso, cioe della probabilita che l’algoritmo trovi le parole di codice ricercate.

Nel capitolo 6 si potra trovare una serie di listati di codice che sono statiutilizzati per le simulazioni dell’algoritmo e per lo studio dello spazio delle soluzioni,mentre riserveremo al capitolo 7 la discussione dei risultati ottenuti e al capitolo8 le conclusioni.

10

Capitolo 2

Codifica di canale

2.1 Generalita

La codifica di canale e quel processo che ha come scopo l’aumento della probabilitadi trasmettere con successo bit di informazione attraverso un canale disturbato.Essa si realizza tramite l’aggiunta di ridondanza che permette, con il processo didecodifica, di rilevare o correggere un certo numero di errori che si possono essereverificati durante la trasmissione delle parole di codice.

Il processo di codifica di canale e fondamentale nel campo delle telecomunica-zioni, dove e richiesto che grandi quantita d’informazione vengano trasmesse senzaerrori attraverso un canale, quale ad esempio un doppino telefonico, una fibra ot-tica, l’etere nel caso di comunicazioni wireless, ecc. Ogni canale reale viene peroaccompagnato da una certa probabilita di errore, che puo essere dovuta a rumore,interferenze, perdite di pacchetti... Si rende dunque necessaria l’introduzione diuna codifica che permetta di correggere eventuali errori verificati durante la tra-smissione, in modo da aumentare l’affidabilita della comunicazione.

Lo studio di questa problematica trova le sue radici nel lavoro di Claude ElwoodShannon [7], che nel 1948 e il primo ad affrontare in modo rigoroso e matematicola teoria delle telecomunicazioni. Nella sua trattazione propone per la prima voltala nozione di codifica di canale, studiata negli anni successivi prima da MarcelGolay e poi da Richard Hamming [5], che inventeranno nei due anni successivi iprimissimi codici a correzione d’errore. Dagli anni ’50 l’argomento guadagna uninteresse sempre maggiore che portera, nei decenni successivi, allo studio e allarealizzazione di un gran numero di codici a correzione d’errore basati su strutturealgebriche e geometriche sempre piu complesse. Al giorno d’oggi i codici corretto-ri sono largamente usati nel campo delle telecomunicazioni (modem, wifi, sistemi

11

satellitari, ecc.) ma anche in altri campi come ad esempio la memorizzazione diinformazione (CD, DVD, dispositivi di archiviazione magnetici, ecc).

2.2 Codici correttori

Shannon propone, nella sua teoria, il seguente modello: la sorgente d’informazionetrasmette un messaggio di informazione, codificato con un alfabeto Σ. Poichela probabilita di errore su un canale reale e maggiore di 0, c’e la possibilita cheil messaggio emesso dalla sorgente non coincida con quello ricevuto. Shannonpropone quindi un’aggiunta sistematica di ridondanza al messaggio originale: essaconsiste nel mappare il messaggio, formato da k elementi di Σ, con una n-upla piulunga di elementi di Σ, definendo cosı la funzione di codifica:

C : Σk −→ Σn

con n > k.In questa tesi considereremo principalmente il caso binario, ovvero quello in cui

Σ = {0, 1}, che porta quindi alla funzione di codifica seguente:

C : {0, 1}k −→ {0, 1}n

I k bit del messaggio originale sono detti bit d’informazione, mentre gli n bitrisultanti formano la parola di codice. L’insieme di tutte le parole di codice formainvece il dizionario D del codice.

Definizione 2.1. Un codice correttore (o codice blocco) binario, di parametri n ek, e la terna C = ({0, 1}k, C,D). I parametri n e k vengono detti rispettivamentelunghezza e dimensione (o rango) del codice.

Definizione 2.2. Dato un codice correttore C di parametri n e k, si definiscetasso del codice il rapporto RC = k

n; esso indica la frazione di bit di informazione

trasmessa per ogni parola di codice. Piu alto e il tasso, minore e la ridondanza in-trodotta e conseguentemente minore sara la capacita correttiva del codice. D’altrocanto, a parita di bit d’informazione k, piu basso e il tasso e minore e la quantitad’informazione trasmessa a parita di n.

2.3 Decodifica di canale

Le parole di codice formano un sottoinsieme dello spazio {0, 1}n. Se consideriamopero che ogni bit ha una certa probabilita di essere modificato da un errore di

12

trasmissione, l’insieme delle ennuple che possono essere ricevute e l’intero insieme{0, 1}n. Si rende quindi necessaria una funzione che prenda l’ennupla ricevutay e produca una stima c della parola di codice originalmente trasmessa. Questafunzione, detta funzione di decodifica, e definita come segue:

D : Σn −→ D

Essa associa una qualsiasi ennupla ricevuta y alla propria stima c ∈ D, sulla basedella decodifica effettuata dal decodificatore di canale. Tramite questa funzionelo spazio Σn viene partizionato nelle cosiddette regioni di decodifica, definite comel’insieme delle ennuple che vengono decodificate con la stessa parola di codice:

Ri = {y ∈ Σn|D(y) = ci} i = 1..M

con M = |C| numero di parole di codice.

2.3.1 Distanza di Hamming e distanza minima di un codice

Diamo ora tre importanti definizioni che ci aiutano a caratterizzare lo spazio delleparole di codice di un determinato codice.

Definizione 2.3. Siano u = (u0, u1, ..., un−1),v = (v0, v1, ..., vn−1) ∈ Σn; si defini-sce distanza di Hamming dH(u,v) il numero di elementi tali che ui 6= vi

dH(u,v) = |{i | ui 6= vi}|

Si verifica con facilita che la distanza di Hamming cosı definita risulta essereuna metrica nello spazio Σn.

Definizione 2.4. Sia u = (u0, u1, ..., un−1) ∈ Σn; si definisce peso di Hammingwt(u) il numero di elementi di u diversi da 0:

wt(u) = dH(u,0)

dove 0 e il vettore nullo.

Definizione 2.5. Sia C un codice correttore di dimensione n. Si definisce distanzaminima di C la distanza di Hamming tra le due parole di codice piu vicine:

dmin(C) = mini 6=j

dH(wi,wj)

con wi,wj parole del codice C, con i, j ∈ {1..M}

La distanza minima e un parametro molto importante di un codice, poichee direttamente collegata al massimo numero di errori che il codice e in grado dicorreggere correttamente utilizzando la decodifica a distanza minima.

13

2.3.2 Decodifica a distanza minima

Esistono diversi metodi per attuare la decodifica dell’ennupla ricevuta, ognuno deiquali definisce una specifica funzione di decodifica D. Il criterio piu utilizzato e lacosiddetta decodifica a distanza minima, che consiste nell’associare alla n-upla yricevuta la parola di codice stimata c che e piu vicina ad y secondo la distanza diHamming.

Utilizzando una funzione di decodifica di questo tipo, si puo facilmente calco-lare il massimo numero di errori che il codice riesce a decodificare correttamente.Una decodifica corretta si realizza quando la stima c = D(y) corrisponde a c, laparola di codice trasmessa originalmente.

Supponiamo ora di avere un codice C e la relativa funzione di decodifica a di-stanza minima D. Sia c l’ennupla trasmessa e y quella ricevuta; D(y) corrispondealla parola di codice w ∈ D piu vicina secondo la distanza di Hamming. Definiamoinoltre l’ennupla di errore e, ovvero la ennupla tale che y = c+e, Ora, ricordandoche dmin e la distanza di Hamming tra le due parole di codice piu vicine, possiamoenunciare il seguente

Teorema 2.3.1. Sia c la parola di codice trasmessa, appartenente al dizionario delcodice C. Sia y = c+e l’ennupla ricevuta, con e ennupla di errore dovuta al rumoredurante la trasmissione. Ogni ennupla y = c+e tale che wt(e) ≤ bdmin(C)−1

2c sara

decodificata correttamente, ovvero D(y) = c = c. Questo equivale a dire che il

codice C e in grado di correggere con certezza t = bdmin(C)−12c errori di trasmissione

(per ogni parola trasmessa).

Criterio a massima verosimiglianza

Il criterio di decodifica a massima verosimiglianza e il criterio di decodifica cheassocia all’ennupla ricevuta y la parola di codice w che ha piu alta probabilita diessere stata trasmessa. La relativa funzione di decodifica sara quindi definita comesegue

Dmv : y −→ w

con w tale chep(Tw/Ry) = max

w∈Dp(Tw/Ry)

con Tw evento che rappresenta la trasmissione di w e Ry evento che rappresentala ricezione di y.

Si puo dimostrare che il criterio di decodifica a distanza minima corrispondeal criterio di massima verosimiglianza sotto opportune ipotesi di stazionarieta e

14

assenza di memoria del canale di trasmissione.

Si puo facilmente verificare che per correggere un numero di errori pari a tcon il criterio a distanza minima e necessario avere una dmin ≥ 2t + 1. Per potereffettuare la decodifica correttamente e infatti necessario che l’ennupla ricevuta ysia piu vicina all’originale c che a qualunque altra ennupla. Costruendo un codicecon dmin = 2t+ 1, e immediato verificare che, se si sono verificati t errori, abbiamo

dH(y, c) = t

e poiche dmin e la distanza minima, per definizione

minw∈D\{c}

dH(c,w) ≥ dmin

Cambiando t bit di c, secondo la distanza di Hamming ci allontaniamo di t unitada c:

minw∈D\{c}

dH(y,w) ≥ dmin − t = 2t+ 1− t = t+ 1

quindi

dH(y, c) = t < t+ 1 ≤ minw∈D\{c}

dH(y,w)

che equivale a dire che c e la parola a distanza minima.

2.3.3 Sfera di Hamming

Definizione 2.6. Dato lo spazio qn delle ennuple su un alfabeto q-ario, si definiscesfera di Hamming centrata in y e di raggio d l’insieme delle ennuple di qn chedistano al massimo d da y secondo la distanza di Hamming:

Sy,d = {w | dH(w,y) ≤ d}

2.3.4 Raggio di copertura

Definizione 2.7. Si definisce raggio di copertura di un codice C la minima distanzaR tale che ogni ennupla dello spazio Σn disti al massimo R dalla parola di codicepiu vicina. In altre parole esso costituisce il minimo raggio delle sfere di Hammingcentrate nelle parole di codice tale che l’unione delle sfere corrisponda all’interospazio Σn:

R = min{r | ∀y ∈ Σn,minw∈D

dH(w,y) ≤ r}

15

2.3.5 Codici perfetti

Prendiamo in considerazione le regioni di decodifica. Per un codice con capacitacorrettiva t, sappiamo che una generica regione di decodifica e formata da tuttele ennuple che distano al piu t dalla parola di codice presa in considerazione. Ilvolume delle regioni di decodifica per una capacita correttiva t, che corrispondeal volume della sfera di Hamming centrata su una qualunque parola di codice, equindi pari a

Vd =t∑i=0

(n

i

)nel caso binario.

Definizione 2.8. Sia C un codice binario di lunghezza n, con un numero di bitdi informazione k e capacita correttiva t. Si dice che C e un codice perfetto sel’unione delle regioni di decodifica e pari all’intero spazio delle ennuple 2n. Uncodice di questo tipo garantisce che per ogni y ricevuta la decodifica porti sempreall’individuazione di una parola di codice con una distanza ≤ t. Formalmente, seVd e il volume delle regioni di decodifica del codice, un codice si dice perfetto se

2kVd = 2kt∑i=0

(n

i

)= 2n ⇐⇒

t∑i=0

(n

i

)= 2n−k

Purtroppo, i codici perfetti sono molto rari. Gli unici esempi non banali dicodici perfetti sono i codici a ripetizione, quelli di Hamming e i codici isolati diGolay.

2.4 Codici lineari

In linea teorica si potrebbe costruire un codice senza preoccuparsi della sua strut-tura, elencando semplicemente le parole di codice che lo compongono. Tuttavia, seil dizionario del codice avesse una dimensione molto grande, come di fatto succedequasi sempre, il numero di parole di codice da analizzare sarebbe molto elevato erenderebbe il processo di codifica e decodifica altamente inefficiente. Per questomotivo sono state studiate varie strutture che permettano di costruire un codice inmodo sistematico, garantendo una codifica e una decodifica computazionalmentepiu efficiente: una delle piu importanti famiglie di codici cosı generata sono i codicilineari.

I codici lineari sono una famiglia di codici costruiti sulla teoria algebrica deicampi finiti di Galois, di cui diamo qualche rapida definizione prima di parlare piunel dettaglio delle loro proprieta.

16

2.4.1 Campi finiti

Definizione 2.9. Un campo F e un insieme dotato di due operazioni interne,addizione (+) e moltiplicazione (·), che soddisfano le seguenti

1. (F,+) e un gruppo abeliano

2. (F \ {0}, ·) e un gruppo abeliano

3. + e · soddisfano la legge distributiva

Definizione 2.10. Dato q ∈ N, se esiste un campo con q elementi, esso e dettocampo finito di Galois e viene indicato con GF (q) o Fq.

2.4.2 Struttura e codifica dei codici lineari

Dato p primo, m ∈ N+ e fissato quindi q = pm, indichiamo con Fq un campodi Galois di q elementi. Consideriamo ora l’insieme Fnq formato dalle ennuple dielementi di Fq, che risulta essere uno spazio vettoriale sul campo Fq.

Definizione 2.11. Un codice lineare C di lunghezza n e rango k e un sottospaziovettoriale di Fnq di dimensione k.

Un codice lineare C individua un dizionario di parole di codiceD, che e l’insiemedelle qk n-uple costruite su Fq. Poiche D ⊂ Fnq e uno spazio vettoriale, la somma didue parole di codice e ancora una parola di codice, cosı come il vettore nullo. Daqueste considerazioni possiamo dedurre un’interessante proprieta che caratterizzala distanza minima di un codice lineare:

dmin = mini 6=j

dH(wi,wj) = mini 6=j

wt(wi −wj) = minw∈C

wt(w)

poiche wi −wj = w e ancora una parola di codice.

Per i codici lineari la codifica si riduce ad una mappa tra spazi vettoriali, inparticolare dallo spazio dei messaggi GF (qk) al sottospazio vettoriale rappresen-tato dall’insieme delle parole del codice C. Di conseguenza la funzione puo esseredefinita da una matrice G denominata matrice generatrice di C:

C : GF (qk) −→ D

la funzione C mappa quindi messaggi a in parole di codice w ottenute tramite lamoltiplicazione tra a e G:

C(a) = w = aG

Le righe della matrice G rappresentano quindi una base per il sottospazio vettorialeD.

17

2.4.3 Codice duale e sindrome di un ennupla

Dato un codice C, definito come sottospazio vettoriale di GF (qn), possiamo consi-derare il suo complemento ortogonale, che rappresenta un sottospazio di dimensionen− k di GF (qn). Il codice C⊥ corrispondente a questo sottospazio viene detto co-dice duale di C. Consideriamo ora la matrice generatrice di C⊥, che denotiamo conH. Si ha che ogni n-upla w e parola di codice di C se e solo se e ortogonale adogni riga di H:

w ∈ C ⇐⇒ HwT = 0

La matrice H e detta matrice di controllo per il codice C, da cui si procede adefinire la seguente

Definizione 2.12. Data un n-upla y ∈ GF (q)n, viene detta sindrome di y ilvettore

s = HyT

In base a quanto detto della matrice H, sappiamo che se s = 0 allora y e unaparola di codice, altrimenti notiamo che, se prendiamo w ∈ C parola di codice:

y = w + e ⇐⇒ s = HyT = H(wT + eT ) = HwT +HeT = HeT

Quindi la sindrome di una generica ennupla r corrisponde alla sindrome del vettoredi errore e che rappresenta la differenza tra y e una parola di codice.

Si puo mostrare inoltre che la sindrome puo essere espressa anche come segue:

s =ν∑j=1

eijhij

con i = i1, ..., iν posizioni in cui si e verificato un errore. Nel caso binario l’espres-sione si riduce a

s =ν∑j=1

hij

La sindrome della ennupla ricevuta rappresenta, proprio grazie a questa proprieta,il punto di partenza per realizzare metodi di decodifica nei codici lineari.

2.5 Codici ciclici

I codici ciclici sono un sottoinsieme dei codici lineari. Sono costruiti imponendoun’ulteriore proprieta ai codici lineari e sono inoltre molto legati alla struttura deicampi di Galois, permettendo cosı tecniche di codifica e decodifica ancor piu facili.I codici ciclici vengono cosı definiti:

18

Definizione 2.13. Un codice lineare C e un codice ciclico se ogni permutazioneciclica di una sua qualunque parola di codice e ancora una parola di codice.

(w0, w1, ..., wn−1) ∈ C =⇒ (wn−1, w0, ..., wn−2) ∈ C

Definiamo ora un’equivalenza tra l’insieme Fnq , gia visto per i codici lineari, eFq[x]/(xn − 1), ovvero l’anello delle classi residue di Fq[x] modulo (xn − 1). Inquesto modo una generica ennupla rappresentata da (w0, w1, ..., wn−1) ∈ Fnq verraora rappresentata dal polinomio w(x) = w0 +w1x+ ...+wn−1x

n−1 ∈ Fq[x]/(xn−1).Denotiamo l’anello Fq[x]/(xn − 1) con Rn. Usando questa notazione, una permu-tazione ciclica di w corrisponde ad una moltiplicazione per x nell’anello Rn.

La matrice generatrice di un codice ciclico e direttamente identificata dal cosid-detto polinomio generatore, l’unico polinomio monico di grado minimo f , denotatog(x) ∈ Rn. Il polinomio generatore e tale che ogni parola di codice e individuatatramite la moltiplicazione del polinomio a(x) che rappresenta il messaggio e g(x).

w(x) = a(x)g(x)

La matrice generatrice G e invece composta come segue:

G =

g(x)

xg(x). . .

xk−1g(x)

=

g0 g1 . . . gn−k

g0 g1 . . . gn−k. . . . . .

g0 g1 . . . gn−k

2.5.1 Costruzione di un codice ciclico a partire dalle radici

Dato un campo finito GF (pm), i suoi elementi rappresentano tutte e sole le radicidel polinomio xp

m − 1. In particolare se poniamo n = pm − 1, il polinomio xn − 1si fattorizza come

xn − 1 =n−1∏i=0

(x− αi)

con α elemento primitivo, generatore del campo. Ogni divisore di xn − 1 avraquindi come radici un sottoinsieme delle αi, e possiamo usare questa proprietaper progettare il codice: si puo imporre che una serie di elementi β1, ..., βt sianoradici del polinomio generatore g(x), e di conseguenza di ogni parola di codice, chericordiamo sono date da w(x) = g(x)a(x). Cosı facendo si definisce la matrice di

19

controllo H del codice, costruita come segue:

H =

1 β1 β2

1 . . . βn−11

1 β2 β22 . . . βn−1

2...

...1 βt β2

t . . . βn−1t

Si enuncia ora un’importante teorema riguardante i codici costruiti in questo modo:

Teorema 2.5.1. Sia C un codice ciclico costruito assegnando d − 1 potenze con-secutive di una radice ennesima dell’unita α

αb, αb+1, . . . , αb+d−2

per un certo b ≥ 0, e abbiamo quindi che

g(αb) = g(αb+1) = . . . = g(αb+d−2) = 0

Allora la distanza minima del codice e maggiore o uguale alla distanza di progettod.

Ricapitolando, per costruire un codice con distanza minima pari almeno a ddistanza di progetto, si eseguono i seguenti punti:

(i) Si sceglie β, una radice n-esima dell’unita, con β ∈ GF (pm)

(ii) Si impone che il polinomio generatore g(x) sia costituito dai polinomi minimidi β, β2, . . . , βd−1.

2.6 Codici di Hamming

I codici di Hamming sono un’importante famiglia di codici lineari, proposti daRichard Hamming nel 1950 e capaci di correggere un singolo errore. Poiche sonocodici 1-correttori e necessario che la distanza minima del codice sia pari a 3. Sipuo mostrare che per un codice q-ario, se la matrice H ha m righe, il numero divettori colonna necessari a garantire che non ci siano coppie di colonne linearmentedipendenti e al massimo qm−1

q−1. Pertanto e possibile realizzare un codice di Ham-

ming q-ario con dimensioni n = qm−1q−1

e k = qm−1q−1− m. Nel caso binario questi

valori si riducono quindi a n = 2m − 1 e k = 2m −m− 1.

20

2.7 Codici BCH

I codici BCH sono una famiglia di codici nati come generalizzazione dei codici diHamming, e sono in grado di correggere fino a t errori, a seconda della distan-za di progetto d = 2t + 1. Furono studiati e proposti indipendentemente da A.Hocquenghem nel 1959 e da R. C. Bose e D. K. Ray-Chaudhuri nel 1960.

Definizione 2.14. I codici BCH sono codici ciclici binari t-correttori, con lun-ghezza n e d = 2t + 1 distanza di progetto. Sono costruiti assegnando d− 1 = 2tradici consecutive

αb αb+1 . . . αb+d−2

con b ≥ 0 e α radice n-esima dell’unita.

Se b = 1 si parlera di codice BCH in senso stretto. Se consideriamo i codiciBCH binari, in senso stretto e primitivi, abbiamo n = 2m−1, e possiamo costruirela matrice di controllo H nel seguente modo:

H =

1 α α2 . . . αn−1

1 α2 α4 . . . α2(n−1)

......

1 αd−1 α2(d−1) . . . α(d−1)(n−1)

21

22

Capitolo 3

List decoding

3.1 Generalita

Negli anni cinquanta Elias e Wozencraft proposero un’alternativa al metodo classi-co di decodifica univoca, presentando la tecnica di list decoding. Con questa tecnicasi cerca di risolvere i principali problemi individuati nelle decodifica classiche, pri-mo fra tutti l’impossibilita di correggere un numero di errori maggiore di t. Comevisto nel precedente capitolo, un codice con distanza minima dmin puo garantirela decodifica corretta di un numero di errori al massimo pari a t = bdmin−1

2c.

Un altro problema della decodifica classica e che per la grande maggioranza deicodici non e garantito che l’unione delle regioni di decodifica sia uguale all’interospazio delle ennuple possibili. In questo caso esistono delle ennuple esterne alleregioni di decodifica e per esse non sara possibile produrre una decodifica che portia una stima del messaggio inviato. Con la decodifica classica, quindi, ogni parolache subisca un numero di errori di trasmissione maggiore di t viene decodificata inmodo errato o porta ad un fallimento della decodifica.

Il list decoding punta a risolvere questo problema introducendo la possibilita direstituire, come risultato della decodifica, una lista di parole di codice possibili alposto dell’unica stima disponibile nel caso della decodifica univoca. In questo mo-do le regioni di decodifica possono sovrapporsi, ed eventualmente estendersi, finoad avere raggio pari al raggio di copertura, garantendo cosı che qualsiasi ennuplaricevuta possa essere decodificata.

Ottenuta la lista di possibili parole di codice, verra successivamente attuata lascelta della singola parola impiegata come stima della parola trasmessa. In genereviene scelta la parola della lista piu vicina alla ennupla ricevuta, utilizzando quindidi nuovo il criterio a distanza minima; ma questa non e l’unica opzione. E impor-

23

tante quindi che le dimensioni della lista siano limitate al fine di rendere possibileun’analisi computazionalmente vantaggiosa da parte dell’algoritmo di decodifica.Dal punto di vista pratico bisogna stare attenti a non far esplodere combinato-riamente la dimensione della lista, che deve essere sempre di tipo polinomiale, epossibilmente lineare.

3.2 Formalizzazione del problema

Diamo ora una definizione piu formale del problema del list decoding : dato uncodice C e una ennupla ricevuta y, il list decoding si realizza individuando tuttele parole di codice distanti al massimo e da y, con e > t, poiche il caso in cuie = t rappresenta la decodifica univoca. Si definisce quindi una nuova funzione didecodifica, che restituira piu di una parola di codice come risultato:

Dlist : Σn −→ Dvi

con vi dimensione della lista di parole restituita dall’algoritmo, che puo variare aseconda della ennupla presa in considerazione. Per garantire la possibilita di effet-tuare un’analisi computazionalmente efficiente della lista per tutti i casi possibili,e necessario che il massimo valore di vi sia limitato. Torna utile a questo propositointrodurre la limitazione di Johnson.

3.3 Limitazione di Johnson

Fissata una qualsiasi parola di codice di partenza w, la limitazione di Johnsonidentifica un limite al numero di parole di codice che possono trovarsi a distanza eda w. In particolare, essa individua un limite che se non superato garantisce cheil numero di parole di codice presenti a questa distanza cresca al piu linearmentecon n.

Indichiamo con la notazione Jq(n, d, e) il massimo numero di parole che si pos-sono trovare all’interno di una sfera di Hamming di raggio e. Si ha ovviamenteche

Jq(n, d,

⌊d− 1

2

⌋) = 1

Definizione 3.1. Sia δ = dn

la distanza minima relativa del codice e q la cardinalitadell’alfabeto Σ. si definisce la quantita

Jq(δ) =

(1− 1

q

)(1−

√1− q

q − 1δ

)e chiamiamo eJ(n, d, q) = Jq(δ)n il raggio di Johnson.

24

Teorema 3.3.1. Se e < eJ(n, d, q) allora vale la limitazione di Johnson

Jq(n, d, e) ≤ qnd

Questo risultato e molto utile se si vuole creare un algoritmo che voglia analiz-zare le parole di codice che si trovano a distanza e > t, poiche garantisce che sottol’ipotesi e < eJ(n, d, q), la lista di parole che si trovano a distanza e e limitata dauna funzione lineare. In questo modo si possono realizzare algoritmi efficienti dilist decoding, che possano restituire una stima della parola trasmessa anche se ilnumero di errori verificati e superiore a quelli normalmente correggibili dal codicemediante decodifica univoca.

3.4 Algoritmi per il list decoding

Nonostante l’idea del list decoding fosse stata concepita gia negli anni ’50, perdiversi anni non si fu in grado di realizzare un algoritmo di decodifica efficiente.L’algoritmo naive, che consiste nella ricerca sequenziale delle soluzioni nello spa-zio delle ennuple, presenta infatti una complessita esponenziale che pregiudica ilsuo utilizzo in casi pratici. Inoltre, un importante articolo del 1978 di Berlekamp,McEliece e van Tilborg [1] dimostra come il problema generale della decodificadi codici lineari sia NP-completo, introducendo ulteriori perplessita sulla effettivapossibilita di realizzare algoritmi efficienti aldila dei gia noti algoritmi per delleparticolari istanze di codici lineari. Bisogna attendere fino al 1997, quando MadhuSudan del MIT realizza il primo algoritmo polinomiale di list decoding per unaclasse di codici limitata, i codici Reed-Solomon con tasso minore di 1

3. Successiva-

mente prima Guruswami e poi Wu daranno importanti contributi che estendonoi codici per i quali e possibile realizzare un algoritmo di complessita polinomiale,migliorando anche la capacita di correzione. Nelle prossime sezioni vedremo unpo’ piu nel dettaglio il funzionamento di questi algoritmi. Essi vengono descrittiin questa tesi per completezza, ma per comprenderne a fondo il funzionamentosono necessari strumenti di algebra e geometria che non sono stati introdotti inquesto documento e nei corsi della nostra laurea magistrale. Non ci si aspettaquindi dal lettore una piena comprensione del loro funzionamento; la descrizionedegli algoritmi e volta solo a far intuire la loro complessita e a mostrarne la naturafortemente algebrico-geometrica.

3.4.1 Algoritmo di Sudan

Sudan propone un algoritmo per il list decoding per i codici Reed-Solomon cheriduce il problema dell’individuazione delle parole della lista ad un’operazione diinterpolazione e una di fattorizzazione di opportuni polinomi in due variabili [8].

25

Il problema e formalizzato nel seguente modo:

Sia assegnato un campo F e dati n punti {(xi, yi)}ni=1, xi, yi ∈ F , e due parame-tri k e t interi; poniamoci il problema di trovare tutti i polinomi p(x) in una varia-bile e di massimo grado k tali che p(xi) = yi per almeno n−t valori di i ∈ {1, .., n}.

Per comprendere l’algoritmo in modo piu intuitivo, si puo immaginare la se-guente analogia geometrica: si immagini di avere un insieme di punti e di dovertrovare tutte le rette passanti almeno per 5 punti:

Si puo notare che esistono solo due linee f1(x) = x e f2(x) = −x che soddisfanole proprieta richieste. Inoltre, se Q(x, y) e una curva di grado 4 che attraversa tuttii punti, allora tale curva deve necessariamente contenere le rette f1 e f2. Questoperche Q(x, fj(x)) risulta un polinomio di quarto grado avente piu di quattroradici, essendo Q(xi, fj(xi)) = 0 per un numero ≥ 5 di punti. In altri terminiQ(x, fj(x)) ≡ 0, e quindi y − fj(x)|Q(x, y).Una possibile espressione per la curva interpolante e data da Q(x, y) = (x−y)(x+y)(x2 + y2 − 1), in cui le linee di interesse f1(x) e f2(x) compaiono come fattori,oltre al restante polinomio di grado superiore x2 + y2 − 1 indicato in blu.

26

Descriviamo ora l’algoritmo di list decoding di Sudan [8].

Algoritmo di Sudan

Input: n, k,D ∈ N, y = (y1, . . . , yn) ∈ Fnq parola ricevuta, t parametro d’errore

Passo 1 : Interpolazione. Viene costruito su Fq un polinomio non nullo in duevariabili

Q(x, y) =∑i,j

ai,jxiyj

con le seguenti proprieta:

(i) Q(αi, yi) = 0 per ogni i = 1, . . . , n

(ii) Q(x, y) ha il minimo grado pesato, dove il peso vale w = (1, k) (talescelta sara giustificata nel passo successivo).In altri termini, deg(1,k)Q(x, y) ≤ D, per D opportuno.

Passo 2 : Fattorizzazione. Il polinomio Q(x, y) viene fattorizzato in fattori ir-riducibili, e vengono selezionati tutti i fattori della forma (y − p(x)).

Output: p(x) ∈ Fq[x] tali che

(i) (y − p(x)) e un fattore di Q(x, y)

(ii) deg(p(x)) ≤ k

(iii) |{i : p(αi) 6= yi}| ≤ t

Osservazione 1. Il secondo punto individua tutti i polinomi p(x) di grado ≤ k taliche Q(x, p(x)) ≡ 0. Cio giustifica la scelta del peso k rispetto alla variabile y.

Osservazione 2. Definiamo

L = {p(x) ∈ Fq[x] : (y − p(x)) | Q(x, y)}

Si osservi che i polinomi (parole di codice) p(x) ∈ L possono essere di due tipi:

1. parole di codice con distanza di Hamming≤ t da y , ovvero possibili candidatiad essere l’effettiva parola di codice trasmessa

2. parole di codice con distanza > t da y

Dal passo 2 verranno quindi selezionati i polinomi p(x) ∈ L tali che |{i : p(αi) 6=yi}| ≤ t. Si osservi che tale operazione puo essere realizzata in maniera efficientefacendo un semplice controllo sequenziale su tutti gli elementi di L, a patto chela lista abbia dimensioni polinomiali. Una prima limitazione superiore per la lun-ghezza della lista e data dal numero di fattori del tipo (y − p(x)) di Q(x, y). Ilnumero di tali fattori sara ≤ degyQ(x, y) ≤ bD

kc.

27

L’algoritmo di Sudan tuttavia presenta un importante limite: esso e infattivalido solamente per codici Reed-Solomon con tasso inferiore ad 1

3.

3.4.2 Algoritmo Guruswami-Sudan

Due anni dopo il lavoro di Sudan, Venkatesan Guruswami, studente PhD di Sudanal MIT, introduce il concetto di molteplicita di interpolazione, che permette unmiglioramento del precedente algoritmo: grazie al lavoro dei due l’algoritmo diSudan viene esteso a codici Reed-Solomon RS(n, k + 1, n − k) di tasso arbitrarioe con capacita correttiva pari al limite individuato dalla limitazione di Johnson.L’algoritmo realizzato viene denominato algoritmo di Guruswami-Sudan [4].

Anche in questo caso un’analogia geometrica puo aiutare a comprendere laformulazione del problema. Consideriamo la configurazione di 10 punti mostratain figura 3.1, per la quale si vogliono determinare tutte le linee che attraversanoun numero di punti n− t = e >

√kn.

Fig. 3.1: Configurazione formata da 10 punti

In questo caso n = 10, k = 1 e e ≥ 4. Fissato e = 4, esistono esattamente 5linee che passano per almeno 4 punti.

28

Se vogliamo che queste 5 linee siano fattori di una curva Q(x, y), tale curvadovra avere grado D ≥ 5. Ma t = 4 e strettamente minore di D, per cui perqualche linea y = f(x) si deve avere Q(x, f(x)) 6= 0, ovvero y− f(x) non comparecome fattore in Q(x, y).Si noti, infine, che ogni punto e attraversato da due linee. Cio significa che unacurva Q(x, y) che contiene tali linee come fattori dovra attraversare ciascun puntocon molteplicita doppia.

Algoritmo di Guruswami-Sudan

Input: n, k,D ∈ N, y = (y1, . . . , yn) ∈ Fnq parola ricevuta, m ∈ N molteplicitadi interpolazione, t capacita correttiva.

Step 1 : Interpolazione. Viene costruito su Fq un polinomio non nullo in duevariabili

Q(x, y) =∑i,j

ai,jxiyj

con le seguenti proprieta:

(i) ord(Q : αi, yi) = m per ogni i = 1, . . . , n

(ii) deg(1,k)Q(x, y) ≤ D

Step 2 : Fattorizzazione. Il polinomio Q(x, y) viene fattorizzato in fattori irri-ducibili, e vengono selezionati tutti i fattori della forma (y − p(x)).

Output: p(x) ∈ Fq[x] tali che

(i) (y − p(x)) e un fattore di Q(x, y)

(ii) deg(p(x)) ≤ k

(iii) |{i : p(αi) 6= yi}| ≤ t

3.4.3 Algoritmo di Wu

Nel 2008, Wu [10] riformula il problema del list decoding per codici Reed-Solomon:utilizzando polinomi costruiti mediante l’algoritmo di Berlekamp-Massey (BM)[2, 6], riconduce il problema del list decoding ad un problema di rational curvefitting. Formalmente il problema e cosı ridefinito: se Λ(x) e B(x) sono i polinomilocatore e correttore di errore generati da BM, il list decoding determinera le cop-pie di polinomi λ(x) e b(x) tali che Λ∗(x) = λ(x)Λ(x) + b(x)xB(x) rappresenta unvalido candidato ad essere l’effettivo polinomio locatore. Quest’ultimo indicherale posizioni da correggere nella ennupla ricevuta, individuando cosı la lista delleparole di codice generate dalla proceduta di list decoding.

29

Algoritmo di Wu di list decoding per codici binari BCH

• Passo 0. Ricevuta una parola r(x) viene calcolata la relativa sindrome s(x).

• Passo 1: algoritmo di Berlekamp.

Input: s(x) sindrome

Output: Λ(x) e B(x)Questi polinomi permettono di ricostruire l’effettivo polinomio locatoredi errori Λ∗(x) mediante la relazione

Λ∗(x) = Λ(x)λ∗(x2) + x2B(x)b∗(x2) (3.1)

per certi polinomi λ∗(x) e b∗(x).

Obiettivo: determinare λ∗(x) e b∗(x)

Osservazione. La (3.1) si puo riscrivere come

Λ∗(x)

x2B(x)=

Λ(x)

x2B(x)λ∗(x2) + b∗(x2)

Se α−i e una delle t radici di Λ∗(x), allora

0 =Λ(α−i)

α−2iB(α−i)λ∗(α−2i) + b∗(α−2i) (3.2)

Definiamo, per per ogni i = 0, . . . , n− 1,

yi =

{− Λ(α−i)α−2iB(α−i)

se B(α−i) 6= 0

∞ se B(α−i) = 0(3.3)

In questo modo, se α−i e una radice di Λ∗(x), dalla (3.2) segue

0 = yiλ∗(α−2i)− b∗(α−2i)

Obiettivo: determinare funzioni del tipo yλ(x2)− b(x2) che si annullinoin (α−i, yi) per al piu t valori di i.

• Passo 2: interpolazione.Viene costruito un polinomio interpolante Q(x, y) passante per tutti gli npunti {(α−i, yi)}n−1

i=0 , ciascuno con un certo valore di molteplicita m.Scegliendo opportunamente i parametri, sara possibile far in modo cheQ(x2, y)contenga tutti i fattori della forma yλ(x2)−b(x2) che si annullano al massimoin t degli n punti.

30

• Passo 3: fattorizzazione.Vengono individuati tutti i fattori di Q(x, y) della forma y − b(x)

λ(x).

• Passo 4: correzione degli errori.Per ogni fattore ottenuto al passo precedente, viene costruito il polinomio

Λ′(x) = Λ(x)λ(x2) + x2B(x)b(x2)

Le sue radici indicheranno le posizioni di errore in r(x) che andranno modifi-cate: se la parola cosı ottenuta e una parola di codice, questa rappresenteraun candidato ad essere l’effettiva parola trasmessa, e verra inserita nella listain uscita.

L’uscita della procedura appena descritta sara quindi una lista di parole di codiceche si trovano entro una certa distanza dall’n-upla ricevuta r(x).Si puo osservare inoltre che la cardinalita della lista di output sara superiormentelimitata dal numero di fattori yλ(x)− b(x), limitato a sua volta dal grado in y diQ(x, y).

Questo algoritmo rappresenta lo stato dell’arte come algoritmo di list deco-ding: come l’algoritmo proposto da Sudan, esso si basa su i due processi di in-terpolazione e fattorizzazione, ma la riformulazione dell’algoritmo di Berlekamp-Massey attuata consente di implementare la decodifica anche per i codici BCH.Inoltre, utilizzando valori di molteplicita di interpolazione inferiori rispetto al-l’algoritmo di Guruswami-Sudan, permette di raggiungere una complessita pari aO(n6(1−

√1−D)8) con la stessa capacita correttiva τwu < n(1−

√1−D).

Riassumiamo brevemente le differenze tra gli algoritmi visti: L’algoritmo diSudan (S) e un algoritmo polinomiale per codici Reed-Solomon con tasso minore a13. L’algoritmo Guruswami-Sudan (GS) raffina il precedente estendendolo a codici

di tasso arbitrario, e raggiungendo il limite teorico dettato dalla limitazione diJohnson. L’algoritmo di Wu estende i concetti degli algoritmi S e GS anche aicodici BCH, con tasso arbitrario e ne migliora la complessita computazionale.

3.5 Limiti

Nonostante i grossi progressi portati dai risultati di Sudan, Guruswami ed infineWu, l’intrinseca complessita delle operazioni algebriche che interessano gli algorit-mi visti impedisce di implementarli con un’efficienza adeguata a molte applicazionipratiche. Infatti, nonostante la complessita computazionale degli algoritmi sia ineffetti polinomiale, e una complessita comunque piuttosto elevata: la complessita

31

dell’algoritmo di Wu e ad esempio pari a O(n6(1 −√

1−D)8). Per questo mo-tivo, ad oggi il list decoding non trova ancora posto nelle tecniche di decodificamaggiormente utilizzate.

32

Capitolo 4

Studio dello spazio delle parole dicodice

In questo capitolo prenderemo in considerazione alcune classi di codici BCH; ana-lizzeremo lo spazio delle parole di codice al fine di caratterizzarlo meglio, nell’otticadella realizzazione di un algoritmo probabilistico di list decoding per questo generedi codici, obiettivo della nostra tesi.

4.1 Distanza minima, raggio di copertura e John-

son bound

Come abbiamo visto nel capitolo relativo alla codifica di canale, i codici sono ca-ratterizzati da una distanza minima dmin, che e propria della struttura del codicee che indica la minima distanza di Hamming tra due parole di codice, garantendocosı una capacita correttiva del codice pari a t = bdmin−1

2c.

Abbiamo inoltre visto il concetto di raggio di copertura R, che e il minimo rag-gio delle sfere di Hamming centrate nelle parole di codice tale che la loro unionecopra l’intero spazio delle ennuple possibili, che sono in numero di qn. Questovalore e importante perche riuscire a raggiungere una capacita correttiva pari aR permetterebbe di avere un algoritmo che fornisce risultati per qualsiasi ennuplaricevuta, ovvero garantisce che il processo di decodifica non fallisca per alcunaennupla.

Un altro parametro che si rivela utile nel contesto di un algoritmo di list de-coding e il raggio di Johnson J (o Johnson bound) del codice. Questo e il valoreche garantisce che il numero di parole di codice distante al massimo J da unagenerica ennupla non sia esponenziale, consentendo un’analisi efficiente della lista.

33

Si intuisce quindi che un algoritmo di list decoding che punta ad essere computa-zionalmente efficiente dovrebbe prendere in considerazione questo limite per nonprodurre una lista di parole di dimensione computazionalmente intrattabile.

Prendiamo ora in considerazione una serie di codici BCH, caratterizzati daiparametri dmin, t, R e J , indicati nelle tabelle 4.1 e 4.2; lo scopo e quello dicominciare a farci un’idea dello spazio in cui operera un eventuale algoritmo di listdecoding che interessi questi codici. Come si nota, solo pochi valori sono presentiper quanto riguarda i raggi di copertura. Questo perche in generale non e banalecalcolare il raggio di copertura di un codice, ma e necessario studiarne lo spaziodelle soluzioni in modo puntuale per trarre delle considerazioni sulla sua struttura.

34

n k d t J R

7 4 3 1 2 115 11 3 1 1 115 7 5 2 3 315 5 7 3 5 531 26 3 1 1 131 21 5 2 2 331 16 7 3 4 531 11 11 5 7 731 6 15 7 12 1163 57 3 1 1 163 51 5 2 2 363 45 7 3 3 563 39 9 4 4 763 36 11 5 6 963 30 13 6 763 24 15 7 863 18 21 10 1363 16 23 11 1563 10 27 13 1963 7 31 15 27127 120 3 1 1127 113 5 2 2127 106 7 3 3127 99 9 4 4127 92 11 5 5127 85 13 6 6127 78 15 7 8127 71 19 9 10127 64 21 10 11127 57 23 11 12127 50 27 13 15127 43 29 14 16127 36 31 15 18127 29 43 21 27127 22 47 23 31127 15 55 27 40127 8 63 31 57

n k d t J R

255 247 3 1 1255 239 5 2 2255 231 7 3 3255 223 9 4 4255 215 11 5 5255 207 13 6 6255 199 15 7 7255 191 17 8 8255 187 19 9 9255 179 21 10 10255 171 23 11 12255 163 25 12 13255 155 27 13 14255 147 29 14 15255 139 31 15 16255 131 37 18 20255 123 39 19 21255 115 43 21 23255 107 45 22 24255 99 47 23 26255 91 51 25 28255 87 53 26 30255 79 55 27 31255 71 59 29 34255 63 61 30 35255 55 63 31 36255 47 85 42 53255 45 87 43 55255 37 91 45 59255 29 95 47 63255 21 111 55 81255 13 119 59 94255 9 127 63 119511 502 3 1 1511 493 5 2 2511 484 7 3 3511 475 9 4 4

Tabella 4.1: Caratterizzazione di alcuni codici BCH (1)

35

n k d t J R

511 466 11 5 5511 457 13 6 6511 448 15 7 7511 439 17 8 8511 430 19 9 9511 421 21 10 10511 412 23 11 11511 403 25 12 12511 394 27 13 13511 385 29 14 14511 376 31 15 16511 367 33 16 17511 358 37 18 19511 349 39 19 20511 340 41 20 21511 331 43 21 22511 322 45 22 23511 313 47 23 24511 304 51 25 26511 295 53 26 28511 286 55 27 29511 277 57 28 30511 268 59 29 31511 259 61 30 32511 250 63 31 33511 241 73 36 39511 238 75 37 40

n k d t J R

511 229 77 38 41511 220 79 39 43511 211 83 41 45511 202 85 42 46511 193 87 43 48511 184 91 45 50511 175 93 46 51511 166 95 47 52511 157 103 51 58511 148 107 53 60511 139 109 54 62511 130 111 55 63511 121 117 58 67511 112 119 59 68511 103 123 61 71511 94 125 62 72511 85 127 63 74511 76 171 85 108511 67 175 87 112511 58 183 91 119511 49 187 93 123511 40 191 95 127511 31 219 109 158511 28 223 111 164511 19 239 119 190511 10 243 121 198

Tabella 4.2: Caratterizzazione di alcuni codici BCH (2)

36

4.2 Calcolo della percentuale di copertura

Mettiamoci ora nel caso binario e consideriamo un generico codice BCH con distan-za minima dmin e di conseguenza con t = bdmin−1

2c. Possiamo facilmente calcolare

la percentuale dello spazio 2n coperto dalle regioni di decodifica. Sappiamo chel’intero spazio delle ennuple e formato da 2n ennuple. Il numero di ennuple ad unacerta distanza r da una generica ennupla e pari a

(nr

). Il volume di ogni regione di

decodifica e quindi pari a:

V (Ri) =t∑i=0

(n

i

)Poiche ci sono k bit d’informazione sappiamo che ci sono 2k regioni di decodificadisgiunte. Possiamo allora calcolare la percentuale di spazio coperto:

C% =2k V (Ri)

2n=

∑ti=0

(ni

)2n−k

Questa percentuale rappresenta la frazione di 2n per la quale la decodifica BCHfornisce una stima. Tentare di decodificare un’ennupla della frazione complemen-tare pari a 1−C% porta a un fallimento della decodifica. Nella tabella 4.3 vediamoalcuni valori di C% calcolati per alcuni valori di n e k.

37

n k n− k d t C%

31 26 5 3 1 131 21 10 5 2 0.48531 16 15 7 3 0.15231 11 20 11 5 0.19731 6 25 15 7 0.10663 57 6 3 1 163 51 12 5 2 0.49263 45 18 7 3 0.15963 39 24 9 4 0.03863 36 27 11 5 0.057127 120 7 3 1 1127 106 21 5 2 0.004127 78 49 15 7 1.68e-04127 43 84 29 14 9.11e-08127 15 112 55 27 7.75e-07255 247 8 3 1 1255 207 48 13 6 0.0013255 123 132 39 19 4.37e-12255 71 184 59 29 6.22e-18255 21 234 111 55 1.66e-14511 502 9 3 1 1511 403 108 25 12 1.83e-09511 295 216 53 26 3.42e-22511 193 318 87 43 1.60e-33511 85 426 127 63 2.68e-47

Tabella 4.3: Percentuale di copertura per alcuni codici BCH

38

Dalla tabella si osserva che all’aumentare della capacita correttiva del codice ilvalore C% diminuisce sensibilmente; cio e dovuto alla circostanza che le sfere cen-trate nelle parole diventano sempre piu grandi, le parole diminuiscono e aumentalo spazio vuoto lasciato negli interstizi delle sfere. In altre parole aumenta in modosignificativo la parte dello spazio delle 2n ennuple che rimane fuori dalle regioni didecodifica; la decodifica delle ennuple appartenenti a questa regione esterna portaa un fallimento. Gli unici codici che presentano una percentuale di copertura del100% sono i codici perfetti, che sono pero molto rari: i codici perfetti che vediamonella tabella sono i codici di Hamming 1-correttori.

4.3 Copertura dello spazio vicino alle parole di

codice

Sebbene la percentuale di copertura totale teorica calcolata sia corretta, e benenotare che non e detto che le parole di codice siano distribuite in modo omogeneonello spazio delle ennuple. Si puo quindi caratterizzare ulteriormente lo spaziocercando di capire quante parole si trovano vicino alle regioni di decodifica diun’altra parola di codice. Sono state eseguite delle simulazioni per verificare, peralcuni tipi di codici, quale percentuale delle ennuple possibili a distanza t + 1 et+ 2 facesse parte di qualche regione di decodifica: in particolare, con riferimentoalla figura 4.1, fissato w, si cerca di capire quante delle ennuple che si trovanonella fascia arancione (t+ 1) e verde (t+ 2) vengono decodificate correttamente inuna qualche parola di codice dall’algoritmo di decodifica BCH. Eventuali parolea questa distanza saranno sicuramente diverse da w, poiche differiscono da w perpiu bit di quanti il codice sia in grado di correggere, ovvero t. Nella tabella 4.4 sivedono i risultati di queste simulazioni.

codice (n,k,t) t+ 1 t+ 2

(31,21,2) 0.614 0.4303(31,16,3) 0.1595 0.1688(31,11,5) 0.1043 0.097(31,6,7) 0.0077 0.0059(63,51,2) 0.488 0.4847

Tabella 4.4: Percentuale di copertura a distanza t+ i dalle parole di codice

39

Fig. 4.1: Analisi dello spazio prossimo alla regione di decodifica delle parole dicodice

Si noti come ai codici correttori con capacita correttiva piu alta corrispondanovalori percentuali molto bassi; in questi casi sara probabilmente piu facile ritrovarela parola originale anche nell’eventualita di un numero di errori maggiore di t. Sarainfatti piu difficile imbattersi in un’altra regione di decodifica che risiede vicino aquella obbiettivo.

40

Capitolo 5

Proposta di un algoritmoprobabilistico

5.1 Motivazioni

Come abbiamo visto nel capitolo relativo al list decoding, lo stato dell’arte perquanto riguarda la decodifica list decoding e l’algoritmo di Wu, che presenta unacomplessita computazionale pari a O(n6(1−

√1−D)8). Questa complessita, nono-

stante non sia esponenziale, e ancora proibitiva per consentire un impiego praticodell’algoritmo e delle tecniche di list decoding in generale. Per altro tale algoritmoe basato su tecniche raffinate di geometria algebrica, e per sperare di migliorarloe verosimile si debba operare ancora in questo settore, per il quale non si hannocompetenze adeguate nei corsi di studio di Ingegneria. Un’alternativa possibile equella di individuare un algoritmo molto meno sofisticato dal punto di vista teori-co, ma che funzioni solo con una certa probabilita, che si possa magari controllare.Lo scopo di questa tesi e quindi lo studio e la realizzazione di un algoritmo al-ternativo di tipo probabilistico per il problema del list decoding dei codici BCH.Poiche nello spazio metrico di Hamming tutto cresce con velocita esponenziale,ci si aspetta di poter usare questo algoritmo solo per un ristretto intervallo deiparametri.L’idea sulla quale si basa l’algoritmo probabilistico di list decoding e quella diesplorare lo spazio delle soluzioni costruendo a caso un certo numero Ni di ennupleche stanno a una certa distanza i dall’ennupla ricevuta; chiameremo i-perturbatetali ennuple. Cio significa che l’ennupla ricevuta sara modificata in i posizionidistribuite casualmente sugli n bit della parola. Questa operazione viene fatta apartire da i = 0 (che corrisponde a non inserire errori e a preservare l’ennuplaricevuta), incrementando via via il valore di i. Si procede poi a decodificare leennuple i-perturbate con l’algoritmo classico di decodifica BCH; la speranza e che

41

qualcuna di queste ennuple cada all’interno della regione di decodifica di qualcheparola di codice vicina all’ennupla ricevuta. Se cio accade l’algoritmo restituisce,per ciascun passo i dell’iterazione, una lista di parole di codice che derivano dalledecodifiche delle ennuple i-perturbate che hanno avuto successo. L’insieme delleparole di codice ottenute iterando i costituisce la lista finale ottenuta dalla decodifi-ca di tipo list decoding. Per meglio comprendere l’idea, si veda la rappresentazionedi una iterazione in figura 5.1: y e la ennupla ricevuta, in verde e in rosso scuro sivedono le Ni ennuple i-perturbate che sono state decodificate rispettivamente consuccesso e senza successo. In verde chiaro vediamo le aree di decodifica delle paroletrovate, in ocra le aree di decodifica delle parole non trovate. Nel caso illustrato,la lista risultante conterra le parole w1 e w3.

Fig. 5.1: Rappresentazione di una generica i-esima iterazione dell’algoritmo

42

5.2 Probabilita di successo

5.2.1 Descrizione del modello di decodifica

Creiamo ora un modello che ci aiuti a calcolare la probabilita che il nostro proce-dimento abbia successo, ovvero che trovi la parola originalmente trasmessa.

Sia C un codice BCH di lunghezza n, con k bit di informazione e con capacitacorrettiva t. Supponiamo che in fase di codifica il messaggio c sia codificato conla parola di codice w. Questa viene trasmessa e subisce un numero e di errori ditrasmissione, ovvero wt(e) = e, con e vettore di errore. Denotiamo con y l’ennuplaricevuta; risulta quindi y = w + e.

L’algoritmo riceve la parola y e procede a una sua i-perturbazione, modificandocasualmente i posizioni tra le n disponibili; cio significa che la parola perturbata ea distanza i da y. Successivamente si prova la decodifica BCH, verificando se essaporta o meno a una parola di codice.Analizziamo ora nel dettaglio una generica iterazione i dell’algoritmo, che portaalla generazione di ennuple i-perturbate ottenute modificando in i posizioni l’en-nupla ricevuta y. L’algoritmo genera Ni ennuple i-perturbate yi(j), 1 ≤ j ≤ Ni

a distanza i da y; a seguito della decodifica si individua un certo numero D diparole di codice, che chiamiamo wi(r) con r = 1..D e D ≤ Ni; infatti non e det-to che per tutte le yi(j) esista una decodifica; oppure potrebbe succedere che cisiano piu ennuple i-perturbate yi(j) che portano alla stessa parola di codice wi(r).

Nel fare la simulazione dovremo allora procedere secondo il seguente schema:

1. si sceglie una parola di codice w lunga n bit;

2. si introducono e errori in w, ovvero si invertono i valori di e bit di w,ottenendo y. Questa operazione simula il rumore del canale;

3. si generano Ni ennuple yi(j), 1 ≤ j ≤ Ni, distanti i da y, ognuna ottenutaintroducendo i errori in posizioni casuali di y;

4. si decodifica ciascuna delle yi(j); se la decodifica ha avuto successo perD ennuple, si ottiene una lista di D parole di codice wi(m) decodificatecorrettamente, con m = 1..D e D ≤ Ni;

5. se w ∈ Wi = {wi(m) | m = 1..D} la parola originale e stata trovata, e ladecodifica list decoding ha avuto successo.

Con queste premesse proveremo a calcolare la probabilita di trovare la parolaoriginale, distante e dalla parola y ricevuta.

43

5.2.2 Calcolo probabilita di successo

Sia t la capacita di correzione del codice BCH scelto, e il numero di errori intro-dotti in fase di trasmissione, e sia i il numero di ulteriori errori introdotti nel passo3.Pensando ora alla ennupla y che contiene gia e errori rispetto alla w originale, sipensi all’introduzione dei nuovi i errori come un tentativo di correggere gli e erroriprecedentemente causati dalla trasmissione. Proviamo quindi a calcolare la pro-babilita che gli errori totali causati da queste due ’perturbazioni’ di w ci portinoall’interno della sfera di Hamming di w di raggio t, che e equivalente a dire che lasuccessiva decodifica porta nuovamente a w.

Definiamo ora p come il numero di errori, tra gli i errori introdotti al passo 3,che hanno la stessa posizione di uno degli e errori di trasmissione, ovvero il nume-ro di errori di trasmissione che siamo riusciti a correggere introducendo i nuovi ierrori. Ovviamente si ha che p ≤ i e p ≤ e, e i p errori sono l’intersezione tra quellidi trasmissione e quelli aggiunti artificiosamente al passo 3. Inoltre osserviamo chei restanti i−p errori finiranno per ’sporcare’ ulteriormente y, allontanandola ancordi piu da w.

Si ha quindi che il numero di errori residui r sara dato dagli errori di trasmis-sione non corretti sommati agli errori artificialmente introdotti che non hannocorretto gli errori di trasmissione:

r = (e− p) + (i− p) = e+ i− 2p

Se ora imponiamo che il numero di errori residui sia al piu uguale a t, garantendocila corretta decodifica, abbiamo la condizione

e+ i− 2p ≤ t

Affinche la decodifica abbia successo e allora necessario che

p ≥ e+ i− t2

che, essendo p intero, equivale a

p ≥⌈e+ i− t

2

⌉Ora, fissato p numero di errori ‘corretti’, abbiamo che gli i errori possono esseredistribuiti nel seguente modo:

(ep

)modi di scegliere gli errori da correggere tra

quelli di trasmissione e(n−ei−p

)modi di scegliere in quali posizioni finiranno gli errori

44

non corretti.

Notiamo inoltre che tutti i modi possibili in cui si possono introdurre gli i er-rori su n bit e ovviamente

(ni

).

Alla luce di quanto esposto possiamo concludere con la formula che esprime laprobabilita che la parola generata da questo processo sia decodificata nuovamentecon w; chiamiamo psucc tale probabilita:

psucc =

∑min(i,e)

p=⌈

e+i−t2

⌉ (ep

)(n−ei−p

)(ni

)5.2.3 Condizioni di funzionamento dell’algoritmo

Analizzando le disequazioni presentate nella sezione appena vista, possiamo intuireche ci sono due casi in cui la decodifica non avra mai successo:

1. e > i+ t

2. e < i− t

La 1. e ragionevole: ci sono stati troppi errori e nemmeno correggerli contutti gli i errori introdotti ci porta all’interno della sfera di Hamming di w. Lacondizione 2. invece non e necessariamente ovvia: se ci sono stati troppi pochierrori di trasmissione, e gli errori i introdotti sono molti, la grande maggioranzadi questi, anche nel caso migliore, ci allontana da w, portandoci fuori dalla sfera.Tuttavia il problema relativo al punto 2 non dovrebbe mai presentarsi se abbiamoeseguito iterativamente l’algoritmo partendo con i = 0, incrementando tale valorea ogni iterazione.

5.3 Calcolo del numero di tentativi Ni

Denotiamo con psucc la probabilita di successo calcolata precedentemente, cioe laprobabilita che la parola venga trovata in un solo tentativo. Procediamo ora a cal-colare il numero di tentativi Ni da fare per garantirci una probabilita prefissata pobjdi trovare la parola originalmente trasmessa. I tentativi sono tutti indipendentiperche la perturbazione di ogni ennupla e eseguita aleatoriamente e con una proba-bilita uniforme. Possiamo quindi calcolare con la seguente formula la probabilitadi avere successo con n tentativi psucc(n), che equivale a 1− pinsucc(n):

psucc(Ni) = 1− (1− psucc)Ni

45

da cui possiamo esplicitare il numero di tentativi Ni da fare per garantire unaprobabilita fissata pobj:

psucc(Ni) = 1− (1− psucc)Ni ≥ pobj

1− pobj ≥ (1− psucc)Ni

passando ai logaritmi, e notando che 1 − psucc e sempre inferiore a 1, e quindi illogaritmo in questione e una funzione decrescente, abbiamo

log1−psucc(1− pobj) ≤ Ni

infine cambiando base al logaritmo otteniamo

Ni ≥log(1− pobj)log(1− psucc)

o equivalentemente, essendo Ni intero:

Ni =

⌈log(1− pobj)log(1− psucc)

⌉Utilizzando quindi questo valore di Ni, calcolato con la psucc vista in precedenza,possiamo garantire che troveremo la parola originale con una probabilita maggioreo uguale a pobj.

5.4 Algoritmo

L’algoritmo probabilistico sviluppato e quindi descritto nei seguenti passi. Nellafigura 5.2 si trova inoltre il diagramma di flusso dello stesso.

1. viene ricevuta una ennupla y;

2. si pone i = 0;

3. si calcola Ni come spiegato nella sezione precedente;

4. si generano Ni ennuple casuali yi(j), 1 ≤ j ≤ Ni, tali che dH(yi(j),y) = i;

5. si decodificano le yi(j) e si aggiungono alla lista le parole di codice wi(m)trovate;

6. se la lista e vuota e i < J si incrementa i e si torna al punto 3;

7. si restituisce la lista come risultato dell’algoritmo.

46

Fig. 5.2: Flow chart dell’algoritmo proposto

47

5.5 Condizione di arresto dell’algoritmo

Riferendoci al punto 6 dell’algoritmo, si puo notare che l’algoritmo si ferma quandotrova dei risultati a una certa distanza i, oppure se e stato raggiunta la limitazionedi Johnson. La scelta di fermarsi se la lista non e vuota e compatibile con il criteriodi decodifica a distanza minima. Difatti, se troviamo dei risultati a distanza i, essisono certamente (con probabilita pobj) piu vicini di eventuali risultati che troveremoa distanza i + 1. Se quindi il criterio che si vuole utilizzare per poi analizzare leennuple della lista e quello a distanza minima, non ha senso continuare a riempirela lista con risultati piu lontani. Se invece si volesse ottenere come risultato tuttele parole fino al Johnson bound J , basterebbe eliminare dal punto 6 la condizioneche la lista sia vuota, continuando a iterare sempre fino alle soglie di J .

48

Capitolo 6

Implementazione

6.1 Libreria di codifica/decodifica BCH

Per l’esecuzione dell’algoritmo proposto e necessario poter eseguire la decodificadelle ennuple generate con l’algoritmo di decodifica standard BCH. L’algoritmodi decodifica BCH e un algoritmo che si basa fortemente sulla teoria dei campifiniti e altri strumenti algebrici importanti quali il calcolo matriciale, ecc. Leattuali implementazioni sono frutto di anni di ricerca e ottimizzazioni che esulanodallo scopo di questa tesi. Di conseguenza si e scelto di affidarsi a librerie dicodifica/decodifica BCH preesistenti.

Per l’implementazione proposta sono state prese in considerazione due librerie,per due ambienti di sviluppo molto diversi tra loro, C e MATLAB.

6.1.1 Libreria C

E stata utilizzata per i primi test una libreria C, bch.c, parte integrante del piurecente kernel di Linux. Questa e la libreria che viene utilizzata dal kernel per lalettura e la scrittura su particolari device che utilizzano una gestione della codificasoftware. Sfortunatamente, la struttura della libreria limitava il suo utilizzo a queiparticolari codici BCH che avessero un numero di bit d’informazione, precedente-mente denotato con k, pari a un multiplo di 8. Questo fatto ha permesso di poterutilizzare e testare la libreria soltanto con il codice BCH con n = 31, k = 16, t = 3.

Non e stato quindi possibile utilizzare questa libreria per l’implementazionedell’algoritmo, ma il fatto che essa fosse utilizzabile per qualche codice ha dato lapossibilita di effettuare un confronto delle prestazioni tra questa libreria e la menoefficiente libreria MATLAB, che descriviamo di seguito.

49

6.1.2 Libreria MATLAB

MATLAB e un ambiente di sviluppo che offre una varieta di strumenti matematicimolto numerosa, e che quindi favorisce la realizzazione di algoritmi che operanocon strutture matematiche complesse quali ad esempio i campi di Galois. MA-TLAB include infatti anche le due funzioni bchdec() e bchenc(), che sono stateutilizzate nell’implementazione dell’algoritmo proposto e delle simulazioni trattatein questa tesi. Ovviamente, l’implementazione in MATLAB presenta un overheadmaggiore rispetto a quella piu di basso livello del C, e questo ha portato a tempidi esecuzione maggiori, che non sono aderenti a quello che ci si puo aspettare dallostesso algoritmo implementato piu a basso livello.

6.1.3 Confronto tra prestazioni MATLAB e C

Per avere un’idea dell’ordine di grandezza che separa un’implementazione C daquella in MATLAB, a scopo indicativo, sono state eseguite delle simulazioni di de-codifica di ennuple casuali, valutandone il tempo di esecuzione. Per la simulazionee stato utilizzato il codice BCH con n = 31, k = 16 e t = 3, che e uno dei codiciche si puo utilizzare con la libreria C.

Sono state eseguite un elevato numero di operazioni in ognuno dei due linguaggi,per ottenere un tempo medio piu affidabile possibile. In particolare, nella tabella6.1 vediamo il risultato della simulazione,

C MATLABN 1000000 10000t 0,370897 13,707723tN 3, 709 ∗ 10−7 1, 371 ∗ 10−3

Tabella 6.1: Tempi di decodifica per il codice BCH n = 31, k = 16

50

Nella tabella N equivale al numero di iterazioni eseguite, t al tempo in secondiche ha richiesto l’intera esecuzione. t

Ne invece il tempo medio in secondi richie-

sto da una singola decodifica. Come si puo notare i tempi di esecuzione sono didiversi ordini di grandezza superiori con MATLAB piuttosto che con una piu effi-ciente libreria C. In particolare, lo speedup che si ottiene lavorando in C rispetto aMATLAB, per questa simulazione, e pari a circa 3696.

6.2 Implementazione dell’algoritmo in MATLAB

Di seguito si riporta il listato del codice MATLAB che esegue la decodifica di unagenerica ennupla. In questa particolare versione dell’implementazione si includeanche il codice per la generazione dell’ennupla ricevuta. Questa viene infatti ge-nerata come una parola di codice casuale che viene perturbata con un numero dierrori pari a ERR STARTING WORD, impostato ad un numero maggiore di tcapacita correttiva del codice.

1 %code structure

2 m = 5;

3 n = 2^m-1; % Codeword length

4 k = 11; % Message length

5 t = 5; % Correction capabilty

6

7

8 %algoritm parameters

9 ERR_STARTING_WORD = 6;

10 PERC = 0.9999; %imposed confidence

11

12

13 %random starting word

14 a = randi ([0 1],1,k);

15 msgTx = gf(a);

16 enc = bchenc(msgTx ,n,k);

17 %noising it

18 b = enc + randerr(1,n,ERR_STARTING_WORD:ERR_STARTING_WORD);

19

20

21 received_word = b;

22 unique_list = [];

23

24 for d = 0:10; %this should stop to the johnson bound , not 10

25 disp([’Trying distance ’,num2str(d)]);

26 found = 0;

51

27 n_d = nchoosek(n,d);

28 %disp(n_d)

29

30 %we suppose the solution is distant t+d, which means n_e

= t+d, and n_d

31 %is d

32 n_e = t+d;

33 %calculate sum limits

34 s_start = ceil((n_e+d-t)/2);

35 s_end = min([n_e ,d]);

36

37 sum = 0;

38 for n_x = s_start:s_end;

39 sum = sum + nchoosek(n_e ,n_x)*nchoosek(n-n_e ,d-n_x);

40 end

41

42 p = sum/nchoosek(n,d);

43

44 N2 = ceil(log(1-PERC)/log(1-p));

45

46 %testing N2 random words

47 for i = 1:N2

48 c = received_word + randerr(1,n,d:d);

49 [msgRx ,numerr] = bchdec(c,n,k);

50 if numerr ~= -1;

51 unique_list = [unique_list;msgRx];

52 found = 1;

53 end

54 end

55

56 if found == 1;

57 disp([’Stopped at d=’,num2str(d)]);

58 break;

59 end

60

61 end

62

63 %unique_list

64

65 unique_list = unique(unique_list.x,’rows’);

66

67 found = 0;

68 if ~isempty(unique_list);

52

69 for i = 1: length(unique_list (:,1));

70 if unique_list(i,:) == enc(1:k);

71 found = found + 1;

72 else

73 end

74 end

75 disp(’found n of solutions:’)

76 disp(length(unique_list (:,1)))

77 disp(’original was found?’)

78 disp(found)

79 else

80 disp(’empty list of results ’);

81 end

6.3 Programma per la validazione dell’algoritmo

Riportiamo di seguito per completezza il listato del programma in MATLAB cheesegue la simulazione per verificare che la probabilita pobj sia rispettata: esso e so-stanzialmente una versione modificata dell’algoritmo visto in precedenza. Quantoottenuto da queste simulazioni sara poi presentato nel capitolo relativo ai risultati.

1 %code structure

2 m = 5;

3 n = 2^m-1; % Codeword length

4 k = 21; % Message length

5 t = 2;

6

7

8 %algoritm parameters

9 ERR_STARTING_WORD = 3;

10 PERC = 0.99; %imposed confidence

11

12 tot_found = 0;

13 TEST_COUNT = 1000;

14 for i=1: TEST_COUNT

15

16 %random starting word

17 a = randi ([0 1],1,k);

18 msgTx = gf(a);

19 enc = bchenc(msgTx ,n,k);

20 %noising it

53

21 b = enc + randerr(1,n,ERR_STARTING_WORD:

ERR_STARTING_WORD);

22

23

24 received_word = b;

25 unique_list = [];

26

27 %calculate binary johnson bound

28 J = floor(n/2*(1- sqrt (1 -2*(2*t+1)/n)));

29

30 for d = 0: ERR_STARTING_WORD -t ;%J-t;

31 disp([’Trying distance ’,num2str(d)]);

32 found = 0;

33 n_d = nchoosek(n,d);

34 %disp(n_d)

35

36 %we suppose the solution is distant t+d, which means

n_e = t+d, and n_d

37 %is d

38 n_e = t+d;

39 %calculate sum limits

40 s_start = ceil((n_e+d-t)/2);

41 s_end = min([n_e ,d]);

42

43 sum = 0;

44 for n_x = s_start:s_end;

45 sum = sum + nchoosek(n_e ,n_x)*nchoosek(n-n_e ,d-

n_x);

46 end

47

48 p = sum/nchoosek(n,d);

49

50 N2 = ceil(log(1-PERC)/log(1-p));

51

52 %provo N2 tentativi casuali

53 for i = 1:N2

54 c = received_word + randerr(1,n,d:d);

55 [msgRx ,numerr] = bchdec(c,n,k);

56 if numerr ~= -1;

57 unique_list = [unique_list;msgRx];

58 found = 1;

59 end

60 end

54

61

62 if found == 1;

63 continue; %not stopping when found a word , but

at the johnson bound

64 disp([’Stopped at d=’,num2str(d)]);

65 break;

66 end

67

68 end

69

70

71

72 found = 0;

73 if ~isempty(unique_list);

74 %unique_list

75 unique_list = unique(unique_list.x,’rows’);

76 for i = 1: length(unique_list (:,1));

77 if unique_list(i,:) == enc(1:k);

78 found = found + 1;

79 else

80 end

81 end

82 disp(’found num of solutions:’)

83 disp(length(unique_list (:,1)))

84 disp(’original found?’)

85 disp(found)

86

87 tot_found=tot_found+found;

88 else

89 disp(’empty list of results ’);

90 end

91 end

92

93 disp(’final rate of original found’)

94 disp(tot_found/TEST_COUNT);

55

56

Capitolo 7

Risultati

7.1 Verifica probabilita di successo

L’algoritmo e stato validato tramite una serie di simulazioni per verificare che laprobabilita di successo pobj fosse rispettata. E stata quindi realizzato un algoritmoche simulasse l’intero processo, come nei seguenti punti

1. si genera una parola di codice casuale

2. la si perturba con e ≥ t errori, simulando un canale rumoroso

3. si esegue l’algoritmo per l’i-esimo passo, con i pari a e− t, in modo da averecertamente una possibilita di trovare la parola originale

4. si verifica se la parola originale e nella lista restituita

Iterando questo processo N volte, possiamo calcolare la frequenza con cui la parolaoriginale e effettivamente trovata, e possiamo confrontarla con la pobj obbiettivo.Ricordiamo che pobj e la probabilita di trovare una parola che ha subito e > t errori

all’iterazione i-esima dell’algoritmo, con i pari a e− t. E questa la probabilita cheviene verificata in queste simulazioni.Nella tabella 7.1 vediamo i risultati di queste simulazioni.

57

Codice (n, k, t) N e pobj freq(31,21,2) 1000 3 0,99 0,989(31,21,2) 1000 3 0,8 0,823(31,11,5) 1000 6 0,99 0,995(31,11,5) 1000 6 0,8 0,895(31,11,5) 1000 7 0,99 0,991(31,11,5) 1000 7 0,8 0,815(63,7,15) 1000 16 0,99 0,986(63,7,15) 1000 16 0,8 0,849(63,7,15) 1000 18 0,99 0,99(63,7,15) 1000 18 0,8 0,801

Tabella 7.1: Confronto tra frequenza e pobj nelle simulazioni per alcuni codici

Si puo notare dalla tabella che la frequenza si avvicina notevolmente alla pro-babilita teorica calcolata, anche per codici con alta capacita correttiva. In alcunicasi i valori di freq sono abbastanza alti, ma ricordiamo che nel calcolo dei valoridi Ni prendiamo il primo intero tale che psucc(Ni) ≥ pobj, di conseguenza puo essereche in alcuni casi psucc(Ni) sia abbastanza maggiore di pobj, in particolare quandola probabilita di successo in una singola iterazione psucc e molto alta.

7.2 Simulazioni dell’algoritmo completo

Sono state eseguite molte simulazioni per verificare il funzionamento dell’algoritmo.Le simulazioni si sono svolte, utilizzando l’algoritmo proposto, nel seguente modo:

1. si esegue N volte il seguente processo

(a) si genera una parola di codice w casuale

(b) si perturba w con e > t errori, simulando gli errori di trasmissione

(c) si esegue l’algoritmo partendo dall’ennupla ottenuta

2. si misurano lunghezza della lista media e tempo medio di esecuzione dell’al-goritmo

Nella tabella 7.2 vediamo i risultati di queste simulazioni per dei valori di e pari at+ 1 e t+ 2.

58

Codice (n,k,t) J N e pobj tavg [s] νavg(31,11,5) 7 1000 6 0.99 0.0498 1.536(31,11,5) 7 1000 7 0.99 0.0998 2.018(63,7,15) 27 1000 16 0.99 0.0483 1.001(63,7,15) 27 1000 17 0.99 0.1925 1.002(127,50,13) 15 1000 14 0.99 0.1209 1(127,50,13) 15 1000 15 0.99 1.147 0.987(255,131,18) 20 1000 19 0.99 0.2675 1(255,131,18) 20 1000 20 0.99 3.6669 0.992

Tabella 7.2: Analisi del tempo medio tavg e dimensione media della lista νavg peralcuni tipi di codice BCH

Osservando i valori ottenuti, si possono fare alcune considerazioni:

• per e = t + 1 i tempi ottenuti sono abbastanza piccoli, considerando che,come visto nel capitolo relativo all’implementazione, una realizzazione del-l’algoritmo in un linguaggio piu efficiente come il C puo garantire uno speedupdi circa 3000.

• per e = t + 2 i tempi sono piu alti, ma ancora accettabili nel caso di codicicon n piccolo

• le dimensioni della lista ottenuta decrescono con l’aumentare di n, poiche leparole di codice sono in media piu distanti fra loro

• nei casi in cui e < J , la probabilita di ottenere almeno qualche risultatoe molto piu alta di pobj, questo perche se la parola, distante e non fossetrovata con probabilita pobj alla prima iterazione, l’algoritmo prosegue allaiterazione successiva nella quale la probabilita di trovare la stessa parola eancora maggiore di pobj.

• la dimensione della lista restituita risulta essere pittosto piccola. Questoe vero perche l’algoritmo si ferma nonappena trova le prime parole, quindiprima di raggiungere il limite posto dal Johnson bound. E utile comunquericordare che la limitazione di Johnson assicura un limite superiore alle paroletrovate e non implica quindi una dimensione minima della lista.

59

60

Capitolo 8

Conclusioni

8.1 Obbiettivi raggiunti

In questa tesi sono state esposte ed evidenziate le caratteristiche e i limiti deglialgoritmi di list decoding allo stato dell’arte. E stato quindi proposto un’algoritmodi list decoding probabilistico che utilizza un approccio completamente diversodagli algoritmi visti. Si e poi caratterizzato l’algoritmo proposto effettuando unostudio della probabilita di successo, potendo garantirne il funzionamento con unafissata probabilita, imposta come parametro dell’algoritmo.

Si e infine verificata la correttezza dell’algoritmo simulando la situazione didecodifica per casi in cui gli errori di trasmissione fossero maggiori di t, ottenendoche la decodifica e correttamente eseguita con probabilita pari alla pobj imposta.

8.2 Sviluppi futuri

8.2.1 Confronto con lo stato dell’arte

Un’importante sviluppo che potrebbe essere interessante prendere in considerazio-ne in un lavoro futuro e trovare una metrica per confrontare questo algoritmo conlo stato dell’arte. Un’analisi dal punto di vista della complessita non e necessa-riamente il miglior approccio, in quanto esso ha valenza asintotica, mentre i casipratici di utilizzo dei codici BCH hanno valori di n limitati, generalmente al massi-mo n = 512. Il modo ideale per mettere a confronto lo stato dell’arte e l’algoritmoproposto sarebbe quello di realizzare un’implementazione di entrambi gli algoritmiin un linguaggio efficiente ed eseguire sullo stesso hardware varie simulazioni condiversi tipi di codici confrontandone i tempi.

61

8.2.2 Analisi ulteriore della probabilita di successo

L’analisi della probabilita di successo condotta nel capitolo relativo all’algoritmorappresenta uno studio della probabilita di ottenere una parola distante e > t all’i-terazione i-esima dell’algoritmo, con i = e− t. Sulla base di questo risultato vienecalcolato il numero di tentativi Ni che garantiscono che la probabilita di trovarela parola in quell’iterazione sia maggiore o uguale ad una certa probabilita fissa-ta pobj. Tuttavia, se l’algoritmo non dovesse trovare nessuna parola alla i-esimaiterazione, e se i + t < J , l’algoritmo proseguirebbe a questo punto all’iterazionesuccessiva. Una eventuale parola che non fosse stata trovata nell’iterazione pre-cedente con probabilita 1− pobj avrebbe nell’iterazione successiva una probabilitaancora maggiore di essere trovata.Si potrebbe considerare questo fatto per diminuire il numero di tentativi Ni quan-do i < J− t, continuando a garantire una probabilita fissata che ogni parola vengatrovata nell’intera decodifica e non solo alla i-esima iterazione.

62

Bibliografia

[1] Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. On the inherentintractability of certain coding problems (corresp.). IEEE Transactions onInformation Theory, 24(3):384–386, 1978.

[2] Elwyn R Berlekamp. Algebraic coding theory. 1968.

[3] Peter Elias. List decoding for noisy channels. 1957.

[4] V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon andalgebraic-geometry codes. IEEE Trans. Inform. Theory, 45:1757–1767, 1999.

[5] Richard W Hamming. Error detecting and error correcting codes. Bell LabsTechnical Journal, 29(2):147–160, 1950.

[6] James Massey. Shift-register synthesis and bch decoding. IEEE transactionson Information Theory, 15(1):122–127, 1969.

[7] Claude Elwood Shannon. A mathematical theory of communication. ACMSIGMOBILE Mobile Computing and Communications Review, 5(1):3–55,2001.

[8] Madhu Sudan. Decoding of Reed-Solomon Codes beyond the Error-CorrectionBound. J. Complexity, 13:180–193, 1997.

[9] John M Wozencraft. List decoding. Quarterly Progress Report, 48:90–95,1958.

[10] Y. Wu. New list decoding algorithms for Reed-Solomon and BCH codes. IEEETrans. Inform. Theory, 54(8):2611–3630, 2008.

63

64

Ringraziamenti

Ringrazio i miei genitori per il supporto e la fiducia che hanno sempre riposto inme, ovviamente indispensabili per la realizzazione e il completamento di questopercorso.

Ringrazio il professor Francesco Fabris per la grande disponibilita dimostrata, si-curamente superiore a quella prevista dal suo ruolo.

Ringrazio inoltre tutti gli amici, in particolare Davide, Domenico, Enrico e Marcoper avermi aiutato e spronato nei momenti di necessita.

Ringrazio Nicola e Piero, per il supporto dimostrato e per essere stati semprepresenti soprattutto negli ultimi mesi.

Ringrazio di cuore tutti i coinquilini di Colonia Orsa per l’immenso regalo chemi hanno fatto permettendomi di vivere una nuova esperienza e di condivideremolti momenti, senza mai pretendere nulla in cambio, ma proprio nulla.

Ringrazio infine Silvia per avermi lasciato, sicuramente a malincuore, piu tem-po libero del solito per permettermi la stesura di questo documento, e quindi laconclusione del mio percorso.

Concludo con un augurio per il futuro della DMNK, che avra sicuramente unruolo centrale nelle esperienze che seguiranno questo momento.

65