Blog divulgativo sulla matematica applicata

Codici Correttori di Errori (Parte 2)

In questo post cercheremo di vedere come utilizzare campi finiti per costruire codici correttori di errori. Negli esempi precedenti abbiamo visto come una parola codice non sia altro che una stringa di lunghezza fissa n composta da simboli che fanno parte di un insieme fisso chiamato alfabeto. L’idea di base è utilizzare come alfabeto per il nostro codice correttore di errori un campo finito (guarda qui).

L’importanza di usare un campo finito, ovvero codici lineari

La scelta di utilizzare come alfabeto un campo finito non è di per sé importante se non decidiamo di restringere lo studio di codici correttori di errori ai soli codici lineari. Consideriamo un campo \mathbb{F}_q e l’insieme di tutte le stringhe di lunghezza n che è possibile creare utilizzando elementi di \mathbb{F}_q. Questo insieme viene indicato con \mathbb{F}_q^n e ora consideriamo due operazioni definite nel seguente modo:

  1.  + :\mathbb{F}_q^n \times \mathbb{F}_q^n \to \mathbb{F}_q^n definita da (a_1,a_2,\ldots,a_n)+(b_1,b_2,\ldots,b_n)=(a_1+b_1,a_2+b_2,\ldots,a_n+b_n), ovvero sommando componente per componente (a_1,a_2,\ldots,a_n) e (b_1,b_2,\ldots,b_n).
  2. \cdot :\mathbb{F}_q \times \mathbb{F}_q^n \to \mathbb{F}_q^n definita da \lambda \cdot (a_1,a_2,\ldots,a_n)= (\lambda a_1,\lambda a_2,\ldots, \lambda a_n), ovvero moltiplicando ogni componente per \lambda \in \mathbb{F}_q.

Si può dimostrare che rispetto al + l’insieme \mathbb{F}_q^n è un gruppo abeliano con elemento neutro (0,0,\ldots,0) e il \cdot gode delle seguenti proprietà:

  • \mu \cdot (\lambda \cdot (a_1,a_2,\ldots,a_n))=(\mu \lambda)\cdot(a_1,a_2,\ldots,a_n);
  • 1 \cdot (a_1,a_2,\ldots,a_n) = (a_1,a_2,\ldots,a_n);
  • (\mu +\lambda) \cdot (a_1,a_2,\ldots,a_n)=\mu \cdot (a_1,a_2,\ldots,a_n) +\lambda \cdot (a_1,a_2,\ldots,a_n);
  • \lambda\cdot ( (a_1,a_2,\ldots,a_n) + (b_1,b_2,\ldots,b_n)) = \lambda \cdot (a_1,a_2,\ldots,a_n) + \lambda \cdot (b_1,b_2,\ldots,b_n).

Tutte queste proprietà fanno si che \mathbb{F}_q^n con queste due operazioni + e \cdot sia uno spazio vettoriale sopra \mathbb{F}_q.

In generale un codice correttore di errori di lunghezza n sopra \mathbb{F}_q è semplicemente un sottoinsieme di \mathbb{F}_q^n. Un codice lineare è invece un sottoinsieme \mathcal{C}\subset \mathbb{F}_q^n che soddisfa

\forall \ \lambda, \mu \in \mathbb{F}_q, \forall \ (a_1,a_2,\ldots,a_n),(b_1,b_2,\ldots,b_n) \in \mathcal{C} \Longrightarrow (\lambda a_1+\mu b_1,\lambda a_2+\mu b_2,\ldots,\lambda a_n+\mu b_n) \in \mathcal{C}.

Un sottoinsieme di uno spazio vettoriale che soddisfa la proprietà precedente prende il nome di sottospazio vettoriale. Si osservi come un sottospazio vettoriale contenga sempre lo 0-vettore di \mathbb{F}_q^n, ovvero l’elemento (0,0,\ldots,0). Quindi un codice lineare (correttore di errori) di lunghezza n sopra \mathbb{F}_q non è altro che un sottospazio vettoriale di \mathbb{F}_q^n.

Calcolo della distanza minima

hamming

Richard W. Hamming

Come abbiamo visto nel post precedente, uno dei parametri più importanti di un codice è la sua distanza minima (di Hamming) perché ci permette di determinare quanto sia buono il nostro codice nel correggere gli errori. Tuttavia il calcolo della distanza minima necessita del calcolo della distanza di tutte le coppie di parole codice. Se il nostro codice ha M parole codice dovremmo quindi calcolare all’incirca M^2/2 coppie per determinare la distanza minima del codice. Esiste tuttavia un modo più semplice e veloce per calcolare la distanza minima di codici lineari.

Dato un elemento {\bf v}=(a_1,a_2,\ldots,a_n) \in \mathbb{F}_q^n si definisce peso di Hamming w({\bf v}) il numero di elementi a_i diversi da 0, ovvero

w((a_1,a_2,\ldots,a_n))=\#\{i \in \{1,\ldots,n\} \ : \ a_i \neq 0\}.

Il risultato fondamentale in questa direzione afferma che se \mathcal{C} \subset \mathbb{F}_q^n è un codice lineare allora la sua distanza minima equivale al suo peso minimo, ovvero il minimo dei pesi di Hamming delle parole codice diverse da quella nulla: in formule

\min_{{\bf v} \in \mathcal{C}\setminus \{\overline{0}\}} w({\bf v}).

Per finire si noti come calcolare il peso minimo di un codice di cardinalità M preveda la determinazione di M-1 pesi, un netto miglioramento rispetto al calcolo delle circa M^2/2 distanze tra coppie di parole codice.

Due diversi modi di descrivere un codice lineare

Esiste un altro aspetto nel quale avere a che fare con codici lineari offre un notevole vantaggio rispetto ad un codice “normale”. Infatti per descrivere un codice non lineare, l’unico modo è listarne tutte le parole codice, il che non è sempre fattibile o computazionalmente efficiente. Esistono tuttavia altri modi per descrivere in maniera compatta un codice lineare. Ad un sottospazio vettoriale \mathcal{C} di \mathbb{F}_q^n possiamo associare (in maniera non univoca) una lista \{{bf v}_1, {\bf v}_2,\ldots, {\bf v}_k\} di suoi elementi detta base del sottospazio vettoriale con le seguenti proprietà:

  1. ogni elemento {\bf v} di \mathcal{C} può essere scritto come {\bf v} = \lambda_1 {\bf v}_1+\lambda_2 {\bf v}_2+\cdots+\lambda_k {\bf v}_k, dove \lambda_1,\ldots,\lambda_k \in \mathbb{F}_q;
  2. la lista \{{bf v}_1, {\bf v}_2,\ldots, {\bf v}_k\} è in un certo senso minimale, ovvero non esiste una lista più corta di elementi di \mathcal{C} che soddisfano il punto 1.

Dato \mathcal{C} esistono molte basi distinte, ma tutte hanno la stessa lunghezza. Questo numero prende il nome di dimensione di \mathcal{C} e si può facilmente dimostrare che se la dimensione è k  allora il numero di parole codice di \mathcal{C} è esattamente q^k.

Una matrice generatrice di un codice \mathcal{C}\subset \mathbb{F}_q^n di dimensione k è una tabella con k righe e n colonne di elementi di \mathbb{F}_q del tipo

codice_correttori_img1

dove le righe (a_{11},a_{12},a_{13},\ldots,a_{1n})(a_{21},a_{22},a_{23},\ldots,a_{2n}),\ldots,(a_{k1},a_{k2},a_{k3},\ldots,a_{kn})

sono una base di \mathcal{C}. Possiamo quindi descrivere il codice \mathcal{C} attraverso la sua matrice generatrice, invece che listando tutte le sue parole codice, con un notevole risparmio.

Una matrice controllo di parità di un codice \mathcal{C}\subset \mathbb{F}_q^n di dimensione k è una tabella con n-k righe e n colonne di elementi di \mathbb{F}_q del tipo

H= \left( \begin{array}{ccccc}b_{11} & b_{12} & b_{13} & \cdots & b_{1n}\\b_{21} & b_{22} & b_{23} & \cdots & b_{2n}\\\vdots&\vdots& \vdots && \vdots\\b_{k1} & b_{k2} & b_{k3} & \cdots & b_{kn}\\\end{array}\right),

tali che ogni parola codice (a_1,a_2,\ldots,a_n) è tale che

a_1b_{i1}+a_2b_{i2}+a_3b_{i3}+\cdots+a_nb_{in}=0.

Le n-k righe della matrice H sono scelte in maniera tale da essere massimali, nel senso che non sia possibile trovare altre righe (b_1,b_2,\ldots,b_n) tali che

a_1b_{1}+a_2b_{2}+a_3b_{3}+\cdots+a_nb_{n}=0

per ogni parola codice (a_1,a_2,\ldots,a_n).

Sia la matrice generatrice che la matrice controllo di parità di un codice \mathcal{C} sono strumenti molto importanti per dedurre caratteristiche del codice.

Parametri di un codice lineare

Infine, nel terminare questo post, riassumiamo i principali parametri di un codice lineare. Se \mathcal{C}\subset \mathbb{F}_q^n ha dimensione k e distanza minima (ovvero peso minimo) pari a d, allora diciamo che \mathcal{C} è un [n,k,d]_q-codice.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>