Codici auto-correttori

Giulio Cesare Barozzi
CIRAM - Università di Bologna

[Revisione: luglio 2001.  http://eulero.ing.unibo.it/~barozzi/MI2]

Questo notebook rappresenta una prosecuzione del notbook CodiceHamming-7, ed ha lo scopo di costruire un codice costituito da 16 parole con possibilità di correggere gli errori singoli e rilevare (ma non correggere) gli errori doppi.

Clear["Global`"]

Introduciamo una matrice di Hamming modificata, di dimensione 4 × 8:

H = {{0,0,0,0,1,1,1,1},
	 {0,0,1,1,0,0,1,1},
	 {0,1,0,1,0,1,0,1},
	 {1,1,1,1,1,1,1,1}}; 
MatrixForm[%]

Le colonne della matrice iniziale rappresentano (in base 2) i numeri dispari da 1 a 15.
Consideriamo due vettori di ((GF(2))^8), che indichiamo  x  e  y :

x = {1,0,1,0,1,0,1,0}; y = {1,0,0,1,1,1,1,0};

Verifichiamo che x  appartiene al nucleo (= spazio nullo = kernel) della matrice H , mentre y non gli appartiene:

{Mod[H.x,2], Mod[H.y, 2]}

I vettori che appartengono al nucleo della matrice di Hamming (si tratta di un sottospazio vettoriale di ((GF(2))^8), costituito da 16 elementi) sono le parole del codice, dunque  x  è una parola-codice, y non lo è. 
Vogliamo studiare più da vicino il nucleo della matrice H. Selezioniamo quattro colonne di tale matrice che formino un minore di ordine 4 diverso da 0; ad esempio la prima, la seconda, la terza e la quinta colonna. Tale scelta è dettata dal seguente esame:

RowReduce[H];

MatrixForm[%]

Ht  =  Transpose[H];

Scegliamo le colonne in questione:

H1  =  
        Transpose[{Ht[[1]],  
            Ht[[2]], 
            Ht[[3]], 
            Ht[[5]]} ];

% // MatrixForm

Scegliamo le restanti colonne della matrice H :

H2  =  
        Transpose[{Ht[[4]],  
            Ht[[6]], 
            Ht[[7]], 
            Ht[[8]]} ];

% // MatrixForm

Si osservi che i ruoli delle matrici H1 e H2 sono invertiti rispetto a quanto abbiamo fatto nel notebook CodiceHamming-7.nb, Calcoliamo l'inversa di H1

Inverse[H1]//MatrixForm

... e riduciamola modulo 2:

invH1 = Mod[%, 2];
MatrixForm[%]

Moltiplichiamo l'inversa di  H1  per  H2 :

matKer = Mod[invH1.H2, 2];
MatrixForm[%]

Per ogni vettore x , ricaviamo  x4, x6, x7 e x8 in funzione di  x1, x2, x3, x5:

{x4,x6,x7,x8} = matKer.{x1,x2,x3,x5};
MatrixForm[%]

Una generica parola del codice si scrive

c = {x1,x2,x3,x4,x5,x6,x7,x8}; 
MatrixForm[%]

Elenchiamo tutte le parole del codice:

Table[c,{x1, 0,1},{x2, 0,1},{x3, 0,1},{x5, 0,1}];

codice = Mod[Flatten[%, 3], 2];
MatrixForm[%]

Riprendiamo in considerazione un vettore non appartenente a nucleo di H, ad esempio

x ={1,0,0,1,1,1,0,1};

Verifica:

Mod[H.x, 2]

... oppure

MemberQ[x, codice]

Se il vettore ottenuto è una delle colonne della matrice H, allora possiamo correggere x modificando un solo bit, quello corrispondente alla colonna in questione:

bin = {8,4, 2, 1};

Procuriamoci i vettori della base canonica di ((GF(2))^8). Cominciamo dalla matrice unità di dimensione 8:

e = IdentityMatrix[8]; e//MatrixForm

Le righe di tale matrice ci forniscono i vettori in questione. Consideriamo ancora il vettore  x  di prima. Visto che H.x coincide con la sesta colonna di  H e questa non è altro che  H.e[[6]], andiamo a sommare (modulo 2) x  con e[[6]], cioè invertiamo il sesto bit di x :

Mod[x + e[[6]], 2]

Dico che il risultato è una parola del codice:

Mod[H.%, 2]

Costruiamo un criterio per la correzione dei vettori in ingresso. Se la parola in ingresso (è la parola ricevuta) appartiene al codice, essa viene restituita in uscita, altrimenti se esiste una parola del codice che dista 1 dalla parola ricevuta viene restituita in uscita tale parola; infine se non esiste una parola del codice a distanza 1 dalla parola ricevuta, si restituisce in uscita la parola ricevuta con l'aggiunta di un asterisco in coda.

corr[x_] :=
	Module[{bin = {8,4,2,1}, e = IdentityMatrix[8], p, y = x},
		p = Mod[H.x,2].bin;
		If[Mod[p,2] == 1, y = Mod[x + e[[(p+1)/2]],2],
		If[p > 0, AppendTo[y,"*"]]];
		y
	]

Proviamo con il vettore  x di prima:

{x, corr[x]}

Ricordiamo la distanza di Hamming (si tratta di una distanza di indice 1) in  ((GF(2))^8): essa conta in quante posizioni i bit del vettore x differiscono dai corrispondenti bit del vettore y :

distH[x_, y_] := Apply[Plus, Mod[x + y, 2]]

Calcoliamo le mutue distanze tra gli elementi del codice:

Table[
        distH[codice[[i]],  
          codice[[j]]], {i, 16}, {j, 
          16}] // MatrixForm

Come si vede, la minima distanza tra elementi distinti del codice è 4 (in gergo DMIN = 4).

Data una parola del codice, possiamo elencare tutti i vettori di ((GF(2))^8)a distanza 1 da esso. Costruiamo dapprima tutto ((GF(2))^8):

GF28  =  
        Flatten[Table[{x1, x2, x3, x4, x5, x6, x7, 
              x8}, 
{x1, 0, 1}, {x2, 0, 1}, {x3, 0, 
              1}, {x4, 0, 1}, {x5, 0, 1}, {x6, 0, 1}, {x7, 0, 1}, {x8, 0, 
              1}], 7];

... e poi selezioniamo gli elementi a distanza 1 da un vettore del codice, ad esempio:

Select[
      GF28,  (distH[
              codice[[10]], #] == 
            1) &]

Inversamente, possiamo selezionare dal codice tutte le parole a distanza 1 oppure 2 da una parola di  ((GF(2))^8).

Select[
      codice,  (distH[
              GF28[[11]], #] == 
            1) &]

Select[
      codice,  (distH[
              GF28[[11]], #] == 
            2) &]

Visualizzazione

Costruiamo una funzione che trasforma ogni vettore di ((GF(2))^(8 ))in una poligonale con vertici a coordinate intere, contenuta nel primo quadrante, con il seguente criterio: leggendo i bit da sinistra a destra, ogni bit uguale e 0 determina uno spostamento di un passo a destra, ogni bit uguale a uno determina uno spostamento verso l'alto (vedi il precedente notebook).

traccia[x_] := 
      Module[{asc,  ord, y}, 
ord =  
          FoldList[Plus, 0, x]; 
y = Mod[x + 1, 2]; 
        asc  =  FoldList[Plus, 0, y]; 
punti = 
          Transpose[{asc, ord}]; 
punti]

Ad esempio:

traccia[codice[[11]]]

Tracciamo la poligonale:

grafPoli[x_]  :=  
        ListPlot[traccia[x], PlotJoined -> True, 
          AspectRatio -> 
            Automatic, 
PlotRange -> {{0, 8}, {0, 8}}, 
          PlotStyle -> {RGBColor[1, 0, 0], 
              Thickness[0.01]}, 
DisplayFunction -> 
            Identity];

Tracciamo un reticolo di riferimento:

retUno  =  Table[{{0, k}, {8 - k, k}}, {k, 1, 8}];

retDue  =  Map[RotateLeft, %, {2}];

reticolo  = Join[retUno, retDue];

grafReticolo  = Graphics[Map[Line,  reticolo]];

Tutto insieme, per visualizzare il 13-esimo elemento del codice :

Show[{grafReticolo, 
          grafPoli[ codice[[13]] ] }, 
        DisplayFunction -> $DisplayFunction, 
        AspectRatio -> Automatic, Axes -> True, 
        Ticks -> {Range[8], Range[8]}];

Mettiamo a confronto i grafici di un vettore non appartenente al codice e del vettore che rappresenta la sua "correzione":

{x,  corr[x]}

Show[{grafReticolo, grafPoli[ x ] }, 
        DisplayFunction -> Identity, AspectRatio -> Automatic, 
        Axes -> True, Ticks -> {Range[8], Range[8]}];

Show[{grafReticolo, grafPoli[corr[x ]] }, 
        DisplayFunction -> Identity, AspectRatio -> Automatic, 
        Axes -> True, Ticks -> {Range[8], Range[8]}];

Show[GraphicsArray[{%%, %}], 
        DisplayFunction -> $DisplayFunction];

Come si vede la"correzione" ha modificato il bit numero 6; in generale l'indice del bit da modificare è dato da

h  =  (Mod[H . x, 2] . bin + 1)/2

come è mostrato nel corpo della funzione corr. Cerchiamo di evidenziare con un diverso colore il lato della poligonale che corrisponde alla correzione. Il segmento da evidenziare è:

Take[traccia[corr[x]], {h, h + 1}]

Definiamo una funzione che individui il segmento in cui la poligonale che rappresenta corr[x] si distacca da quella che rappresenta x :

segmento[x_, p_] :=Line[Take[traccia[x], {h, h + 1}]];

Tutto insieme:

graf[
          x_] := 
Module[{y =  corr[x], 
            p  = Mod[H . x, 2] . bin }, 
  If[
            y == 
              x, 
Show[{grafReticolo, grafPoli[ x ] }, 
              DisplayFunction -> $DisplayFunction, 
              AspectRatio -> Automatic, Axes -> True, 
              Ticks -> {Range[8], Range[8]}], 
If[
              Length[y] > 
                Length[x], 
Show[{grafReticolo, 
                  grafPoli[ x ] }, 
                DisplayFunction -> $DisplayFunction, 
                AspectRatio -> Automatic, Axes -> True, 
                Ticks -> {Range[8], Range[8]}, 
                Prolog -> {RGBColor[0.3, 1, 
                      0]}], 
Show[{grafReticolo, 
                  grafPoli[x], grafPoli[y], 
                  Graphics[{RGBColor[0, 0, 1], Thickness[0.01], 
                      segmento[y, p]}] }, 
                DisplayFunction -> $DisplayFunction, 
                AspectRatio -> Automatic, Axes -> True, 
                Ticks -> {Range[8], 
                    Range[8]}]
]
]
];

Ad esempio:

graf[x];

Sperimentazione:

graf[Table[Random[Integer, {0, 1}], {8}]  ];

La poligonale contenente il segmento blu (se esiste) rappresenta corr[x], altrimenti viene mostrata soltanto la poligonale corrispondente a  x  su un reticolato nero se  x  è una parola del codice, infine la poligonale corrispondente a  x  su reticolato in colore se  x  è una parola non del codice ma non "correggibile" modificando un solo bit.