Burst-Error CorrectionLe parole di un codice RS(n, t), con n = 2m − 1, suGF (2m) possono essere viste come parole binarie dilunghezza mn

Sia C una parola codice di RS(n, t). Supponiamo diinviare sul canale la versione binaria di C. Indichiamocon E il vettore degli errori e con R = C + E il vettorericevuto.

Def. Error-Burst≡ la più lunga sequenza di simboli di Eche comincia e finisce con un simbolo diverso da 0.

. – p.1/35

Burst-Error CorrectionEsempio Consideriamo la parola C = (α3, α, α, 1, 0, α3, 1)del codice RS(7, 2). La versione binaria di C èC = (011, 010, 010, 001, 000, 011, 001)

Supp. che durante la trasmissione avvengano 4 errori:

E = (000 000 0

error−burst︷ ︸︸ ︷11 101 000 000 000)

e di conseguenza R = (011 010 001 100 000 011 001)

Il vettore E, considerato come vettore su GF (8), hapeso 2:

E = (0, 0, α3, α6, 0, 0, 0)

Quindi se convertiamo il vettore binario R in un vettoresu GF (8), possiamo correggere i 2 errori.

. – p.2/35

Burst-Error CorrectionIn generale, un codice RS(2m − 1, t) può essere visto come

un codice su GF (2) di lunghezza m(2m − 1). Tale codice

può correggere qualsiasi error-burst che non altera più di t

simboli della parola codice originaria su GF (2m).

. – p.3/35

Interleaved CodesC(i) = (c

(i)0 , c

(i)1 , . . . , c

(i)n−1), i = 1, . . . , λ: parole di codice

(n, k)

disponiamo parole in matrice λ× n

c(1)0 c

(1)1 ... c

(1)n−1

c(2)0 c

(2)1 ... c

(2)n−1

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

c(λ)0 c

(λ)1 ... c

(λ)n−1

trasmettiamo parola ottenuta leggendo le colonne dellamatrice una dopo l’altra:

C′ = (c(1)0 , c

(2)0 , . . . , c

(λ)0 , c

(1)1 , c

(2)1 , . . . , c

(λ)1 , . . . , c

(1)n−1, c

(2)n−1, . . . , c

(λ)n−1)

. – p.4/35

Interleaved CodesPassiamo da codice (n, k) a codice (nλ, kλ)

Questo nuovo codice viene detto interleaving diprofondita λ del codice di partenza.

Un error-burst di lunghezza λt, modifica al più tcomponenti di ciascuna delle λ parole originarie

⇒ se il codice (n, k) di partenza corregge t errori allorail nuovo codice corregge λt errori

. – p.5/35

Interleaved Codescodice RS(n, t) su GF (2m)

l’ interleaving di profondità λ del codice RS(n, t)consente di correggere λt errori.

consideriamo versione binaria del codice RS(n, t)

ciascun simbolo ci ≡ sequenza di m bitC = (c0, . . . , cn−1) =(c00, . . . , c0(m−1), . . . , c(n−1)0, . . . , c(n−1)(m−1))

un error-burst di lunghezza t in GF (2m) corrispondead un error-burst di lunghezza tm in GF (2).versione binaria di RS(n, t) corregge error-burst dilunghezza tm⇒ un interleaving di profondità λ della versionebinaria di un codice RS(n, t) consente di correggereλtm errori.

. – p.6/35

Codici ConcatenatiVantaggi della concatenazione:

costruire codici “lunghi” a partire da codici “corti”

codifica/decodifica più semplice e di minore complessitàrispetto a quella di codici "lunghi" equivalenti.

Idea alla base della concatenazione:

sistema “codificatore-canale-decodificatore” visto comeun unico canale (outer-channel)

. – p.7/35

Codici Concatenatisi usa un codice a correzione per “combattere” ilrumore che agisce sull’outer channel.

. – p.8/35

Codici ConcatenatiEsempio

Inner code: Codice di Hamming con n1 = 7 e k1 = 4

Outer code: RS(15,2) (n2 = 15 e k2 = 11)

otteniamo un codice binario (105,44) con dmin ≥dminHamming · dminRS = 3 · 5 = 15.

. – p.9/35

Codici Concatenati

. – p.10/35

Codici Concatenaticodice concatenato corregge errori se nella decodificac0, . . . , c14 prodotta dall’inner coder, il numero di paroleerroneamente decodificate è al più 2 (ciascuna parolacorrisponde ad un simbolo ci di F24).

. – p.11/35

Codici ConcatenatiQuali codici sono più adatti ad essere usati come outercode?

se ci 6= ci ⇒ tra le sequenze binarie corrispondenti disolito non vi è alcuna somiglianza

⇒ errori provocati dall’outer channel tendono adavvenire in burst di lunghezza k1

⇒ RS adatti ad essere usati come outer code

. – p.12/35

Applicazione dei RS ai lettori CDI compact disc si comportano come canali burst-error

La Sony e la Philips hanno adottato un potente schemaper il controllo degli errori noto con il nome diCross-Interleave Reed-Solomon Code (CIRC)

CIRC usa tre livelli di interleaving e due codici RS(n,k)concatenati: i l’ inner code è un codice RS(32, 28); l’outer code è un codice RS(28, 24) (entrambi i codicisono ottenuti modificando codici RS standard e hannodmin = 5)

CIRC corregge burst di circa 4000 bit

Prima dell’avvento di CIRC anche un minuscologranello di polvere evrebbe impedito la correttariproduzione di un CD. CIRC permette di riprodurreanche CD graffiati o addirittura cosparsi di fori deldiametro di 8 mm!

. – p.13/35

Decodifica in Presenza di CancellazioniUn codice può correggere e errori ed f cancellazioni sedmin ≥ 2e+ f + 1

Se e = 0, ovvero vogliamo correggere solocancellazioni, è sufficiente dmin ≥ f + 1

dmin ≥ f + 1⇒ se cancelliamo entrate in f posizionii1, . . . , if da tutte le parole del codice, otteniamo paroleche differiscono in almeno una posizione.

Se f > 0 ed e > 0, allora dmin ≥ 2e+ f + 1⇒dmin − f ≥ 2e+ 1

⇒ se cancelliamo entrate in f posizioni i1, . . . , if datutte le parole del codice, otteniamo parole chedifferiscono in almeno 2e+ 1 posizioni.

. – p.14/35

Decodifica in Presenza di CancellazioniPer i codici RS(n, t) si ha dmin = 2t+ 1

⇒ se vogliamo correggere e errori ed f cancellazionibasta scegliere un valore di t che soddisfa 2t ≥ 2e+ f .

. – p.15/35

Secret Sharing

. – p.16/35

. – p.17/35

Schemi di Secret Sharing a sogliaUno schema di Secret Sharing a Soglia (n, k) è unsistema per la condivisione di un segreto tra npartecipanti in modo tale che solo gruppi di almeno kpartecipanti possano ricostruire il segreto

. – p.18/35

Schemi di Secret Sharing a sogliaSia il segreto da condividere un valore di un campoGF (r)

Il noto schema di Shamir si basa sull’interpolazione diun polinomio di grado k − 1 su GF (r):

a0 + a1x+ . . . + ak−1xk−1,

dove a0 è il segreto e a1, . . . , ak−1 sono scelti in modocasuale in GF (r).

le share consistono di n punti di interpolazionese k partecipanti mettono insieme le proprie shareriescono a interpolare il polinomio e a risalire alsegretose meno di k partecipanti mettono insieme le proprieshare non riescono ad ottenere alcuna informazionesul segreto (qualsiasi punto di GF (r) ha la stessaprobabilità di essere a0)

. – p.19/35

Secret Sharing con RSLo schema di Shamir può essere implementato usandoil codice RS(n, t) su GF (r), con n = r − 1 = 2m − 1 er − 1− k = 2t

Codifichiamo vettore di informazionea = (a0, a1, . . . , ak−1), dove a0 è il segreto e a1, . . . , ak−1

sono scelti in modo casuale in GF (r)

Le share sono le n entrate della codifica di a

⇒ codifica sistematica non va bene: a0 apparirebbenella parola codice

Codifica: D = (D1, . . . , Dr−1), dove Di =∑k−1

j=0 ajαji−1

{α0, . . . , αr−2} sono gli elementi diversi da 0 del campo.

. – p.20/35

a0 = −∑r−1i=0 Di

Dim.r−1∑

i=1

Di =r−1∑

i=1

k−1∑

j=0

ajαji−1 =

k−1∑

j=0

aj

r−1∑

i=1

αji−1

=

k−1∑

j=1

aj

r−1∑

i=1

αji−1 + (r − 1) a0

Siccome (r − 1)a0 = ra0 − a0 = 2ma0 − a0 = −a0 e

r−1∑

i=1

αji−1 =r−1∑

i=1

α(i−1)j =r−2∑

i=0

(αj)i

=α(r−1)j − 1

αj − 1=

1− 1

α− 1= 0 (1),

allora a0 = −∑n−1i=0 Di . – p.21/35

D ∈ RS(n, t)

Dim.

HDT =

α0 ... αr−2

... ... ...

α2t0 ... α2t

r−2

D1

...

Dr−1

=

S1

...

S2t

S` =r−1∑

i=1

Diα`i−1 =

r−1∑

i=1

k−1∑

j=0

ajαji−1α

`i−1

=

k−1∑

j=0

aj

r−1∑

i=1

αj+`i−1 = 0 (per la (1))

. – p.22/35

Applicazioni dei RS al Secret SharingSe s partecipanti mettono insieme le proprie sharerecuperano s entrate di D. Possiamo pensare aller − 1− s entrate mancanti come a delle cancellazioni

Se abbiamo s ≥ k share⇒ ci sono ≤ r − 1− kcancellazioni

r−1−k = r−1−(r−1−2t) = 2t < dmin ⇒ possiamo ricostruire D

Se abbiamo s < k share⇒ ci sono≥ r − k = 2t+ 1 = dmin cancellazioni

⇒ non riusciamo a ricostruire D e ciascun elemento diGF (r) ha la stessa probabilità di essere il segreto a0

. – p.23/35

Applicazioni dei RS al Secret SharingSe tra le s share ci sono e share sbagliate ≡r − 1− s = f cancellazioni ed e errori

s− 2e ≥ k ⇒ r − 1− s+ 2e ≤ r − 1− k = 2t⇒ riusciamoa ricostruire D

s− 2e < k ⇒ (r − 1− s) + 2e > 2t⇒ non riusciamo aricostruire D

⇒ gli schemi di secret sharing basati sui codici RSpermettono di gestire situazioni in cui alcuni deipartecipanti mentono circa il valore delle proprie shareallo scopo di impedire la ricostruzione del segreto. Ilnumero dei partecipanti “disonesti” non deve superare(s− k)/2.

. – p.24/35

Communication ComplexityAlice ha una stringa x ∈ {0, 1}k e Bob ha una stringay ∈ {0, 1}k.Alice e Bob vogliono trovare il valore di f(x, y) per unacerta funzione booleana f : {0, 1}k × {0, 1}k → {0, 1}nota ad entrambi

Per esempio se Alice e Bob vogliono determinare se lestringhe x and y sono uguali, allora f è la funzione EQdefinita da

EQ(x, y) =

{1, if x = y,0, if x 6= y.

Alice e Bob vogliono anche minimizzare il numero di bitche devono scambiarsi per poter computare f(x, y)

. – p.25/35

Communication ComplexityPer il momento assumiamo che l’interazione avvengasecondo un certo protocollo deterministico in cui imessaggi che Alice a Bob si scambiano dipendonoesclusivamente da x e da y.

. – p.26/35

I protocolli deterministiciUn protocollo deterministico funziona come segue:

Alice computa a1 ← A1(x) e lo spedisce a Bob;

Bob computa b1 ← B1(y, a1) e lo spedisce ad Alice;

Alice computa a2 ← A2(x, a1, b1) e lo spedisce a Bob;

Bob computa b2 ← B2(y, a1, b1, a2) e lo spedisce adAlice;

Ecc.

A1, A2, . . . , eB1, B2, . . . , denotano sequenze di algoritmi de-

terministici che modellano il comportamento di Alice e Bob.

. – p.27/35

I protocolli deterministiciLa prima delle due persone che determina il valoref(x, y) deve inviarlo all’altra e il protocollo termina.

per un k fissato, definiamo la communication complexitydi una funzione booleana f come segue:

CC(f) = minstrategieA←→B

[max

x,y∈{0,1}k(num. bit scambiati per det. f(x, y))

]

. – p.28/35

I protocolli deterministiciUn semplice protocollo funziona come segue:

Alice spedisce l’intera stringa x a Bob

Bob computa f(x, y)

Questo protocollo richiede lo scambio di k + 1 bit per cui

CC(f) ≤ k + 1

per ogni funzione f .

Esiste una funzione f per cui questo limite è “tight”,ovvero CC(f) = k + 1?

A. Yao ha dimostrato che CC(EQ) = k + 1.

. – p.29/35

I protocolli deterministiciModifichiamo il modello di comunicazione permettendo alleparti di adottare strategie probabilistiche

Si utilizzano le seguenti assunzioni:

Alice e Bob possono generare random bit per produrre ipropri messaggi ma ciascuno di essi non può rivelareall’altro i random bit che ha generato.

Il l protocollo probabilistico determina f se e solo se

per ogni x, y ∈ {0, 1}k, la probabilità che le particomputano f(x, y) correttamente è almeno 3/4.

La probabilistic communication complexity di unafunzione booleana f è denotata con PCC(f) ed èdefinita analogamente alla CC(f) con l’unica differenzache il minimo è calcolato su tutti i protocolliprobabilistici.

. – p.30/35

Probabilistic CCL’uso dei random bit serve a ridurre la communicationcomplexity?

Risposta: Sì. Esistono funzioni booleane per le quali l’usodi strategie probabilistiche riduce sostanzialmente lacommunication complexity.

Teorema PCC(EQ) = O(log k).

. – p.31/35

Probabilistic CCDim. Consideriamo il codice RS(n, t) su GF (2m), conn = 4k e 2t = 3k

NB: RS(n, t) può essere ottenuto accorciando il codiceRS(2m − 1, t) dove m è il più piccolo intero t.c. 4k < 2m − 1

Sia C la funzione di codifica del codice RS(n, t).Consideriamo il seguente protocollo probabilistico:

Alice sceglie un indice i ∈ {1, 2, . . . , n} a caso e invia(i, C(x)i) a Bob, dove C(x)i denota l’i-esima coordinatadi C(x) ;

Se C(x)i = C(y)i, allora Bob invia 1 ad Alice altrimentiinvia 0.

Se x = y allora Bob spedisce ad Alice il valore correttodi EQ(x, y).

. – p.32/35

Probabilistic CCSe x 6= y, allora le codifiche C(x) e C(y) differiscono inalmeno 2t+ 1 coordinate e di conseguenza la probabilitàche C(x) e C(y) differiscano nell’i-esima coordinata èalmeno (2t+ 1)/n ≥ 3/4

Alice trasmette dlog ne+m bit mentre Bob trasmette ununico bit. In totale il numero di bit trasmessi è O(log k)

. – p.33/35

Probabilistic CCConsideriamo lo scenario in cui Alice e Bob condividono iloro random bit. In questo caso il protocollo funziona nelseguente modo:

Alice e Bob generano una stringa random s

Successivamente Alice riceve x e Bob riceve y

Alice e Bob usano un protocollo deterministico in cuipossono usare la loro conoscenza di s.

. – p.34/35

Probabilistic CCIn questo scenario Alice e Bob possono determinareEQ(x, y) usando un protocollo simile a quello descritto nelladimostrazione del teorema in cui però l’indice i è generatoda entrambi.

Poichè in questo protocollo Alice non deve trasmetterel’indice i allora il numero totale di bit trasmessi è m+ 1

Se si sceglie un codice RS su un alfabeto di dimensione

costante, allora si trasmettono un numero costante di bit.

. – p.35/35