Algoritmo probabilistico di tipoMontecarlo per il List Decoding

Laureando: Daniele Nicassio Relatore: prof. Francesco Fabris

Università degli studi di TriesteDipartimento di Ingegneria e Architettura

Corso di laurea magistrale di Ingegneria Informatica

Codifica di canale (1): cos’è

Obiettivo: rendere più affidabili le comunicazioni attraverso canali rumorosi

sorgente destinatariow= 010010 y= 010010

1

rumore,interferenze,

errori di trasmissione,

...

Obiettivo concreto: rilevare o correggere eventuali errori di trasmissione

Codifica di canale (2): come si realizza

si aggiunge ridondanza al messaggio originale:

c = 0110100codifica di canale

w = 01101001100

se la ridondanza è aggiunta in modo strutturato, la codifica e la decodifica possono essere realizzate in modo efficiente

Codifica di canale (3): codici correttori

I codici correttori:

● hanno una funzione di codifica e una funzione di decodifica

● garantiscono la capacità correttiva t: massimo numero di errori di trasmissione che possono essere corretti

Esempi: codici BCH, codici Reed-Solomon, codici di Hamming, ...

Codifica di canale (4): spazio delle ennuple

w1

t

w2

t w4

t

w3

t

w6

t

w5

t

● parole di codice possibili: w1..w6

● le zone verdi sono dette regioni di decodifica

● ennupla ricevuta in regione di decodifica di wi => decodificata con wi

● se l’ennupla è fuori da tutte le regioni di decodifica la decodifica fallisce

● solo se gli errori di trasmissione sono <= t la decodifica dà il risultato corretto

List decoding (1): generalità

Decodifica classica

● è univoca● limitata a t = floor((d-1)/2)

w1t

w2t w4

t

w3t

w6t

w5t

d

d = distanza minima del codice

List decoding

● non univoca● può avere capacità correttiva > floor((d-1)/2)

List decoding (2): storia● idea introdotta negli anni ‘50 da Elias● appena nel ‘98 si ha un primo algoritmo polinomiale per la decodifica

(Sudan)● Successivamente, prima Guruswami poi Wu migliorano l’algoritmo● la complessità raggiunta è polinomiale, ma comunque pesante:

● troppo inefficiente per molte applicazioni pratiche● tutti i 3 algoritmi proposti sono basati su strumenti di geometria algebrica

molto complessi

List decoding (3): algoritmo di Guruswami-Sudan1. si riceve la ennupla y2. Interpolazione: si trova il polinomio

tale che

3. Fattorizzazione: si fattorizza il il polinomio Q(x,y) nei fattori irriducibili in forma (y-p(x))

4. output: i polinomi p(x) tali che:

List decoding (4): algoritmo di Wu1. Si riceve la ennupla y2. Si applica l’algoritmo di Berlekamp con l’obiettivo di determinare le

funzioni del tipo che si annullino in al massimo in t valori di i

3. interpolazione: si costruisce il polinomio Q(x,y) passante per tutti gli n punti

4. fattorizzazione: si individuano i fattori di Q(x,y) nella forma 5. correzione degli errori: per ogni fattore individuato, si individua un

polinomio nella forma 6. le radici dei suddetti polinomi rappresentano le posizioni da modificare in y

per ottenere ognuna delle parole di codice candidate

List decoding (5): analogia geometricaSudan Guruswami-Sudan

List decoding (6): riassunto

● restituisce una lista di risultati invece che un risultato univoco

● problema difficile da trattare dal punto di vista computazionale

● lo stato dell’arte presenta degli algoritmi polinomiali ma con complessità molto pesante

● ancora inutilizzabile nella pratica

Il problema

non esiste un algoritmo di list decoding che sia:

● utilizzabile in pratica (almeno in qualche caso)

● capace di correggere un numero di errori maggiore di quelli della decodifica classica (univoca)

● non si avvalga di strumenti matematici avanzati come quelli usati negli algoritmi allo stato dell’arte

Idea: algoritmo probabilistico

L’idea proposta in questa tesi è un algoritmo di list decoding probabilistico di tipo Montecarlo:

● utilizzabile per correggere un numero di errori > t

● che abbia una probabilità di successo fissata, ovvero funzioni con una probabilità fissata pobj

Approccio completamente diverso dallo stato dell’arte

Algoritmo proposto (1)

L’algoritmo esplora lo spazio delle ennuple in modo iterativo:

1. ricevo y2. i=03. si decodificano Ni ennuple casuali lontane i da y4. se qualche decodifica ha successo, restituisco la lista di

parole trovate5. se non trovo nulla, incremento i6. mi fermo se i > Johnson bound, altrimenti torno al punto 3

Algoritmo proposto (2): illustrazione

y y

w1t

w1t

y

w1t

y

w1t

i = 0Ni=1

i = 3Ni=12

i = 2Ni=5

i = 1,Ni=2

list = {} list = {} list = {} list = {w1}

w2t

Algoritmo proposto (3): calcolo di Ni

1. si calcola la probabilità psuccess di trovare una parola a distanza i+t in un tentativo

2. si calcola il numero di tentativi Ni necessari per garantire una probabilità di trovare la parola pari a un fissato pobj

Algoritmo proposto (4): iterazione generica

Esempio di iterazione al passo i:● sono stati fatti Ni=6 tentativi● sono state trovate 2 parole,

w1 e w2● una parola non è stata trovata

Risultati (1): implementazione

● Sono state eseguite varie simulazioni in MATLAB per studiare la distribuzione delle parole nello spazio delle ennuple

● L’algoritmo proposto è stato realizzato in MATLAB, per la classe dei codici BCH

● Sono stati confrontati i tempi di decodifica delle librerie BCH di MATLAB e di C, stimando uno speedup se l’implementazione dovesse essere fatta in C

Risultati (2): validazioneL’algoritmo deve trovare le parole distanti i all’iterazione i-esima con probabilità fissata pobj

e = i + t

N = numero tentativi

n = lunghezza parolak = bit d’informazionet = capacità correttiva

Risultati (3): tempo medio e dimensione media lista per e=t+1,t+2

Conclusioni (1)

È stato quindi proposto un algoritmo probabilistico che:

● individua con una certa probabilità pobj fissata la lista di parole vicine

● funziona per un numero di errori > t

● ha un tempo medio di esecuzione piuttosto alto quando il numero di errori supera t+1 e n >=127

Conclusioni (2): sviluppi futuri

● Confronto con lo stato dell’arte: implementare l’algoritmo proposto e lo stato dell’arte con un linguaggio efficiente e confrontarne tempi e risultati

● Analisi ulteriore della probabilità di successo: tenere in considerazione la probabilità di trovare una parola al passo (i+1)-esimo