Algoritmo probabilistico di tipo montecarlo per il list decoding
-
Upload
danielenicassio -
Category
Engineering
-
view
19 -
download
2
Transcript of Algoritmo probabilistico di tipo montecarlo per il list decoding
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