Matematica Discreta III
Lezione del giorno 26 maggio 2008 Cenni sui codici non binari.
Si possono ovviamente considerare codici in cui le parole hanno le lettere in un alfabeto diverso da {0,1}, e in generale di cardinalità q>2.
Dato un alfabeto finito A di cardinalità q2, un codice q-ario di lunghezza n è un sottoinsieme non vuoto C di An (insieme delle parole di lunghezza n avente le lettere in A).
Le q lettere di A possono essere identificate per esempio con i numeri 0,1,….,q-1, ma anche con altri simboli: per esempio per q=3 le lettere di A spesso sono identificate con -1,+1,0 (dal punto di vista hardware le 3 lettere possono per esempio essere tradotte con voltaggi negativi, positivi o nulli).
Ognuna delle lettere dell’alfabeto A è detto byte e per motivi pratici dovuti alla trasmissione digitale può a sua volta corrispondere ad un numero binario formato da più bits 0,1, se q è una potenza di 2: per esempio se l’alfabeto A ha 256=28 bytes, essi si possono fare corrispondere ai numeri binari di 8 bits da (00000000)2=0 a (11111111)2=255.
Vediamo come le definizioni e le proprietà dei codici binari si adattano alla teoria dei codici q-ari.
Sia A=q: le parole di lunghezza n sono ovviamente in numero di qn: An=qn
Se C è un codice q-ario di lunghezza n, il rapporto logqC/n è il rateo di informazione (information rate) della codifica: il suo valore massimo è 1 e si ha per C=An.
Errore (di trasmissione): é la modifica di 1 singolo byte della parola inviata: quindi una lettera dell’alfabeto A nella parola trasmessa che si trasforma in una lettera diversa di A nella parola ricevuta.
Distanza di Hamming: date le parole v,wAn di lunghezza n, si chiama distanza (v,w) di v da w il numero di bytes (nella stessa posizione) in cui le due parole differiscono. La distanza di Hamming è una metrica nello spazio An. La distanza di un codice CAn è la minima distanza fra coppie di parole distinte di C.
Per ogni parola vAn ed ogni numero naturale s>0, la sfera Rs(v) di centro v e raggio s uguale all’insieme delle parole wAn tali che (v,w) ≤ s.
Continuano a valere tutte le considerazioni fatte sui codici che rilevano s errori (se s+1) e che correggono s errori (se ≥2s+1).
Fissati un intero s>0 ed una parola vAn, la sfera di centro v e raggio s ha cardinalità:
Rs(v) =
s 0
j j
n (q-1)j
(si deve tenere conto che in ognuna delle posizioni in cui i bytes differiscono vi possono essere q-1 bytes possibili).
Dato un (n, m, )-codice q-ario C e posto s=(-1)/2 si ha:
m
s 0
j j
n (q-1)j≤ 2n (*) (Hamming bound)
Il codice C é perfetto se nella formula precedente vale l’eguaglianza (le sfere di raggio s con centro in distinte parole del codice non si intersecano e ricoprono l’intero insieme An quindi ogni parola di An si trova a distanza ≤s da una e una sola parola del codice C).
Per arrivare al concetto di codice lineare occorre che nell’insieme A sia definita una struttura di campo: da alcuni risultati di algebra astratta si ha che un campo finito ha sempre cardinalità q=pn uguale alla potenza di un primo p, e che viceversa per ogni q=pn potenza di un primo p esiste un campo finito di cardinalità q.
Dunque se A è un campo finito di cardinalità q=pn uguale alla potenza di un primo p, si può definire su An una struttura di A-spazio vettoriale: un codice q-ario CAn sarà lineare se C è un sottospazio vettoriale di An, e in tale caso, se k è la dimensione di C, la cardinalità di C è m=qk, e diremo anche che C è un [n,k,]-codice lineare.
Un sottoinsieme non vuoto C di An sarà un codice lineare se e solo se è chiuso rispetto alla somma (quindi v, wC v+wC) e se per ogni scalare A ed ogni vC si ha vC.
Si può definire il peso (v) di una parola vAn uguale al numero di bytes non nulli di v: in tale caso, date le parole v, wAn si ha (v,w)=(v-w), e se C è un codice lineare la distanza coincide con il peso minimo di una parola non nulla di C.
Se k è la dimensione di un codice lineare q-ario CAn, una matrice generatrice M di C è una matrice kxn ad elementi in A che ha come righe i vettori di una base di C: al variare del vettore wAk, i prodotti righe per colonne wM danno tutte le parole di C.
Le definizioni di matrice generatrice in forma standard e di codice lineare sistematico si danno come nel caso dei codici binari.
Continua a valere il singleton bound: se C è un [n,k,]-codice lineare q-ario, si ha kn-+1.
Codici di Reed-Solomon.
Sono codici molto usati per esempio nella codifica dei dati su cd e dvd.
Supponiamo che l’alfabeto A sia dotato di struttura di campo, quindi sia di cardinalità q=pm dove p è un numero primo ed m un numero naturale.
Dalla teoria dei campi finiti segue che il gruppo moltiplicativo A*=A-{0} è un gruppo ciclico, quindi esiste un generatore A* di periodo uguale alla cardinalità q-1 di A*, e gli elementi distinti di A* sono le potenze di base ed esponente compreso fra 0 e q-2:
A* = {0=1, , 2, ….. , q-2}
Fissiamo due numeri naturali k, n con k<n≤q-1.
Vogliamo costruire un codice q-ario C (sull’alfabeto A) di dimensione k e lunghezza n (nei casi concreti spesso n=q-1).
L’informazione da codificare (di lunghezza k) sia formata dai bytes b0b1….bk-1 (con biA).
Affermiamo che:
esiste un unico polinomio p(x) a coefficienti in A di grado <k tale che p(i)=bi per ogni i=0,…,k-1.
Dimostrazione dell’esistenza di p(x) (interpolazione di Lagrange): fissato l’indice i=0,1,….,k-1 consideriamo il prodotto pi(x) dei k polinomi di primo grado della forma (i-j)-1(x-j) al variare di j=0,1,…,k-1, j≠i (notare che nel campo A gli elementi i, j con 0≤i,j≤k-1<q-1, i≠j, sono distinti, dunque (i-j)≠0 ed esiste perciò l’inverso (i-j)-1). Il polinomio pi(x) (fissato i) ha grado k-1, ed inoltre è tale che pi(i)=1 e pi(j)=0 per ogni j≠i. Se allora costruiamo p(x) uguale alla somma dei prodotti bipi(x) (al variare di i=0,1,…,k-1) otteniamo un polinomio di grado <k tale che p(i )=bi
per ogni i=0,…,k-1.
Dimostrazione dell’unicità di p(x): se per assurdo esistesse un polinomio p0(x) (di grado <k) con p0(x)≠p(x) tale che p(i)=bi=p0(i) per ogni i=0,1,…,k-1, il polinomio non nullo p(x)-p0(x) (di grado
<k) avrebbe k soluzioni distinte 0, 1,…., k-1, in contraddizione con la ben nota proprietà che un polinomio non nullo a coefficienti in un campo ha al più un numero di soluzioni distinte uguale al suo grado.
Una volta trovato il polinomio p(x) codifichiamo l’informazione b0b1….bk-1 costruendo la parola di n bytes c0c1…..cn-1 definita da ci=p(i) per ogni i=0,1,….,n-1.
Il codice così ottenuto è dunque formato da parole di lunghezza n della forma c0c1…..cn-1 tali che ci=p(i) per ogni i=0,1,….,n-1, dove p(x) è l’unico polinomio p(x) a coefficienti in A di grado <k tale che p(i)=bi per ogni i=0,…,k-1: si verifica facilmente che tale codice è lineare.
Inoltre notiamo che si ottiene un codice lineare “sistematico” perché nella codifica c0c1…..cn-1 i primi k bytes c0c1…..ck-1 coincidono con i bytes di informazione b0b1….bk-1 (per costruzione infatti si ha ci=p(i)=bi per ogni i=0,…,k-1).
Ricordiamo inoltre che per costruzione si ha p(x)=b0po(x)+b1p1(x)+…..+bk-1pk-1(x), dove per ogni i=0,1,….,k-1 si ha pi(x)=
i j j0,....,k1-
j 1 j
i α) (xα)
(α . Si ha allora, per i bytes della codifica c0c1….cn-1: ct=p(t)=b0po(t)+b1p1(t)+…..+bk-1pk-1(t) per ogni t=0,1,….,n-1
Da ciò segue che una matrice generatrice del codice è la matrice kxn che ha come elementi della colonna di indice t (supponendo che gli indici di colonna siano numerati con t=0,1,….,n-1) i valori:
po(t), p1(t), ….., pk-1(t)
(tale matrice sarà in forma standard perché il codice è sistematico).
Dunque nella colonna di indice t (con t=0,1,…,n-1) l’elemento di riga i (supponendo numerate le righe con i=0,1,….,k-1) è:
pi(t) =
i j j0,....,k1-
j t 1 j
i α)(α α)
(α
Il codice così ottenuto è dunque un [n,k,]-codice lineare q-ario detto codice di Reed-Solomon di parametri k,n.
Calcoliamo la distanza di tale codice: in una parola non nulla c0c1….cn-1 del codice, il numero di bits ci=p(i)=0 corrisponde ad altrettante soluzioni distinte del polinomio p(x) di grado <k, dunque il numero di bits=1 è >n-k cioè il peso della parola è n-k+1. Possiamo concludere dunque che la distanza del codice è n-k+1, e per il “singleton bound” si ha infine =n-k+1.
Il codice di Reed-Solomon di parametri k, n è allora in grado di correggere (al più) un numero di errori uguale a (n-k)/2.
Costruiremo un algoritmo di decodifica (Berlekamp-Welch) che, nel caso in cui il numero di errori sia s≤(n-k)/2, permette di calcolare il polinomio p(x) e quindi ricotruire i valori p(i)=bi dei bytes di informazione (i=0,1,…,k-1).
Ragioniamo a posteriori, supponendo di conoscere le s posizioni dei bytes errati: se la parola ricevuta è d0d1…..dn, supponiamo che esattamente nelle s posizioni i1,i2,…..,is vi sia errore, dunque ci≠di per i=i1,i2,…..,is, ci=di per i≠i1,i2,…..,is .
Poniamo t=(n-k)/2: si ha per ipotesi s≤t.
Costruiamo il polinomio e(x) a coefficienti in A ottenuto moltiplicando i polinomi di primo grado (x-αih ) con h=1,2,….,s , e poi moltiplicando ancora il risultato per xt-s: tale polinomio (detto polinomio errore) ha la proprietà di:
- avere grado t ed essere monico (cioè con coefficiente di grado massimo =1) - e(i)=0 per ogni i=i1,i2,…..,is
Ovviamente tale polinomio errore e(x) non si può costruire a priori, se non si conoscono il numero s di errori e le posizioni degli errori, ma le proprietà precedente sono soddisfatte da e(x), anche se non siamo in grado di costruirlo esplicitamente.
Affermiamo ora che:
esistono (non necessariamente unici) 2 polinomi non nulli f(x), g(x) a coefficienti in A con le seguenti proprietà:
- f(x) ha grado ≤k+t-1, g(x) è monico ed ha grado t (*) - per ogni i =0,1,….,n-1 si ha f(i) = dig(i) (**)
Basta infatti porre g(x)=e(x) (polinomio errore), f(x)=p(x)e(x): abbiamo già notato che e(x) è monico di grado t, ed ovviamente f(x)=p(x)e(x) ha grado ≤(k-1)+t (perché p(x) ha grado <k); inoltre per ogni i=0,1,….,n-1: se i=i1,i2,…..,is allora e(i)=0 dunque f(i)=g(i)=0 ossia f(i)=dig(i), mentre se i≠i1,i2,…..,is si ha ci=di da cui f(i)=p(i)e(i)=cig(i)=dig(i).
Ovviamente di nuovo è impossibile calcolare a priori una coppia di polinomi f(x), g(x) con le proprietà suddette (*), (**): ma possiamo egualmente notare che, qualunque sia la coppia f(x), g(x) con le proprietà suddette si ha sempre f(x)/g(x)=p(x). Infatti tale eguaglianza è vera per la coppia particolare f(x)=p(x)e(x), g(x)=e(x) già esaminata, ma se f0(x), g0(x) è un’altra coppia, si ha:
f(i)g0(i) = (dig(i))g0(i) = (dig0(i))g(i) =f0(i)g(i) per ogni i =0,1,….,n-1
e allora il polinomio f(x)g0(x)-f0(x)g(x) è =0 (in caso contrario avrebbe grado ≤(k+t-1)+t=k+2t- 1≤k+2(n-k)/2-1=n-1<n, e avrebbe n soluzioni distinte 0, 1,…., n-1 nel campo A, contraddizione).
Dunque p(x)=f(x)/g(x)=f0(x)/g0(x), come si voleva.
Cerchiamo allora di costruire una coppia di polinomi f(x), g(x) che soddisfino (*), (**).
Posto h=k+t-1, essendo il polinomio f(x) di grado ≤h, si può rappresentare (eventualmente con alcuni coefficienti nulli) nella forma:
f(x) = y0+y1x+y2x2+….+yhxh con yiA coefficienti da determinare (i=0,1,…,h) Essendo il polinomio g(x) monico di grado t, si può rappresentare nella forma:
g(x) = z0+z1x+z2x2+….+zt-1xt-1+xt con ziA coefficienti da determinare (i=0,1,….,t-1).
Imponendo le condizioni:
f(i) = dig(i) per ogni i =0,1,….,n-1
si ottiene un sistema di n equazioni lineari a coefficienti in Zq:
y0+y1i+y22i+….+yhhi-di(z0+z1i+z22i+….+zt-1(t-1)i+ti)=0
nelle incognite y0,y1,y2,….,yh,z0,z1,z2,….,zt-1 (che sono in numero di h+1+t=k+2tn): tale sistema è certamente risolubile (perché almeno la coppia f(x), g(x) costruita mediante il polinomio errore soddisfa le proprietà (*),(**), quindi i coefficienti di f(x), g(x) sono soluzioni del sistema).
Risolvendo allora il sistema suddetto con gli usuali metodi di algebra lineare, si trovano i coefficienti yi, zj (anche non in modo univoco) quindi dei valori per i polinomi f(x), g(x) e infine (con l’algoritmo della divisione fra polinomi) il quoziente f(x)/g(x)=p(x), risalendo al messaggio originale.
Un caso tipico di parametri per un codice di Reed-Solomon è quello di un campo di ordine q=28=256, con n=q-1=255, k=223, in grado di correggere al più 16 errori: ogni byte (lettera dell’alfabeto A) si può identificare con un numero binario di 8 bits, l’informazione è costituita da 223 bytes, mentre 32 sono i bytes di ridondanza (il rateo di informazione è 223/25587,5%).
Un tale tipo di codice è usato soprattutto in canali di trasmissione (non simmetrici) in cui gli errori nei singoli bits binari 0,1 si presentano a “raffiche” (burst), cioè con diversi bit consecutivi errati.
Se raccogliamo per esempio i bits 0,1 in bytes di 8 bits ciascuno, pensati come lettere di un alfabeto A di cardinalità 28=256 e utilizziamo un codice di Reed-Solomon di lunghezza n=255 e dimensione k=223, siamo in grado di correggere fino a 16 bytes errati (sui 255 di ogni parola): se in una parola una raffica di errori coinvolge non più di 16 bytes consecutivi, siamo in grado di correggerla.
Per verificare la maggiore efficienza di tale tipo di codice non binario rispetto ad uno binario, basti pensare che il codice di Reed-Solomon esaminato sopra è in grado di correggere una raffica di errori di 158+1=121 bits 0,1 consecutivi (perché essa coinvolge non più di 16 bytes consecutivi) mentre un codice binario con le stesse capacità correttive dovrebbe correggere almeno 121 errori sui singoli bits. Ovviamente però se nel canale gli errori sui singoli bits sono distribuiti in modo più casuale, la scelta di un codice binario rimane la migliore: per esempio un codice di Reed-Solomon come il precedente non sarebbe in grado di correggere 17 errori su singoli bits 0,1 se situati in 17 bytes diversi.
Esempio: come alfabeto scegliamo il campo A=Z7={0,1,2,3,4,5,6} di cardinalità q=7, con generatore =3:
{0=1, 1=3, 2=2, 3=6, 4=4, 5=5} = A*
Scegliamo la lunghezza n=6=q-1, e la dimensione k=2: il codice di Reed-Solomon che costruiremo sarà in grado di correggere (6-2)/3=2 bytes errati.
Supponiamo che l’informazione da trasmettere sia formata dai bytes b0=3, b1=2.
Costruiamo il polinomio p(x) di grado <k=2 tale che p(0)=p(1)=3, p(1)=p(3)=b1=2: facendo i calcoli con l’interpolazione di Lagrange si ottiene p(x)=3x.
La codifica dell’informazione è formata dai seguenti 6 bytes:
c0=p(0)=b0=3,c1=p(1)=b1=2,c2=p(2)=p(2)=6, c3=p(3)=p(6)=4,c4=p(4)=p(4)=5,c5=p(5)=p(5)=1 Quindi la parola inviata nel canale é 3 2 6 4 5 1.
Supponiamo che vi siano 2 errori nel primo e quarto byte e che la parola ricevuta sia 0 2 6 0 5 1, quindi con i bytes d0=0, d1=1, d2=6, d3=0, d4=5, d5=1.
Posto t=(6-2)/3=2, h=k+t-1=3, si devono costruire il polinomio di grado ≤h=3:
f(x) = y0+y1x+y2x+y3x3 con yiA coefficienti da determinare (i=0,1,2,3) e il polinomio monico di grado t=2:
g(x) = z0+z1x+x2 con ziA coefficienti da determinare (i=0,1) tali che siano verificate le n=6 condizioni:
f(i) = dig(i) per ogni i =0,1,2,3,4,5
le quali si traducono nel seguente sistema di equazioni lineari nelle incognite y0, y1, y2, y3, z0, z1:
y0+y1+y2+y3=0
y0+3y1+2y2+6y3+5z0+z1=4 y0+2y1+4y2+y3+z0+2z1=3 y0+6y1+y2+6y3=0
y0+4y1+2y2+y3+2z0+z1=3 y0+5y1+4y2+6y3+6z0+2z1=4
Risolvendo il sistema si trovano le soluzioni y0=0, y1=4, y2=0, y3=3, z0=6, z1=0 e i polinomi:
f(x)=4x+3x3 g(x)=6+x2
da cui p(x)=f(x)/g(x)=3x, e si ricava l’informazione originale corretta p(0)=b0=3, p(1)=b1=2.
