Le correzioni degli errori

La correzione degli errori rappresenta una tecnica importante per garantire la corretta ricezione e trasmissione dei dati digitali. Esistono diverse tecniche per rilevare errori in un flusso di dati, una delle più famose e utilizzate è sicuramente il bit di parità. Con l’andare del tempo si è giunti poi a mettere a punto un’altra tecnica chiamata codice a ridondanza ciclica (CRC o cyclic redundancy codes). 

Questa tecnica garantisce un controllo più accurato; infatti, a ciascun flusso di dati, suddiviso in frame, è aggiunto un particolare valore chiamato anche stringa di controllo. La tecnica basata sul CRC permette di rilevare anche raffiche di errori consecutivi, cosa che suscita maggiore interesse rispetto al singolo bit di parità. Ma che cosa succede se viene individuato un errore? In questo caso esistono due possibilità: o richiedere la ritrasmissione del frame o cercare di correggere, in maniera autonoma, i dati ricevuti.

Nel secondo caso non si fa altro che applicare la forward error correction, o FEC. Questa soluzione è ampiamente utilizzata nelle applicazioni di dati audio o video. Le due tecniche più diffuse per ottenere la FEC sono la codifica convoluzionale e la codifica Reed-Solomon (RS). La codifica Reed-Solomon è stata messa a punto da S. Irving Reed e Gustave Solomon del MIT Labs attraverso un paper presentato sulla Journal of Society for Industrial and Applied Mathematics nel 1960. In questa codifica non si specifica la dimensione del blocco e nemmeno il numero di simboli da controllare, ma questi sono valori che si potranno impostare in base alla singola esigenza e dell’applicazione utilizzata. Così, per applicazioni di tipo DVB-T si utilizza una codifica RS DVB(188,204).  Il segnale digitale è organizzato in frame di 204 byte composti da due parti: un parte informativa (188) e una di controllo (16) in grado di correggere fino a 8 errori per frame.

Chiaramente, in applicazioni di questo tipo è possibile utilizzare anche il sistema chiamato Inner Coder: in questo caso si inserisce nel frame ulteriori bit per la gestione degli errori. I codici di Reed-Solomon sono codici a correzione d’errore basati sui codici a blocco; infatti, questi sono codici a blocco lineari e appartengono ai gruppi BCH. In sostanza, un codificatore Reed-Solomon prende un blocco di dati e aggiunge dei bit di ridondanza. Un codificatore Reed-Solomon suddivide  i dati in gruppi di k bit e ad ogni blocco aggiunge 2t simboli per formare una parola di codice di n bit. Dato un simbolo di dimensione s, la parola di codice può essere al massimo lunga n = 2s - 1. Un decodificatore Reed-Solomon può correggere fino a t simboli che contengono errori. Ogni blocco in Reed-Solomon, chiamato anche codeword, è composto da due gruppi: uno è composto da simboli informativi e l’altro da simboli di parità. Inoltre, ogni simbolo è composto da un certo numero di bit, tipicamente otto. Per questa ragione,  il numero massimo di a simboli in un codeword è pari a 2 -1, con a è il numero di bit per simbolo. In base a questo calcolo possiamo senz’altro affermare che la lunghezza massima di un blocco è pari a 255 bit. In questo modo la dimensione massima di n è di 511 per codici RS a 9 bit o 1023 per 10 bit. In ogni codeword sono presenti K simboli di informazione e R simboli di controllo. La figura 1 mostra una rappresentazione RS.

Figura 1: rappresentazione RS

Dalla figura 1 è possibile affermare che i codici Reed-Solomon sono normalmente definiti come (N,K) = N – K. Il numero degli errori che possono essere corretti dipende interamente dal valore di R, ed è indipendente dal rapporto R/N, o K. L’overhead, o rapporto R/N, può essere utilizzato per confrontare le prestazioni dei vari codici RS per una data applicazione.  Il numero degli errori che possono essere corretti è dato dal rapporto R/2. In una applicazione DVB (204,188), dove R= N – K, o 16, possono essere corretti fino a otto errori random. In una decodifica un codice di Reed-Solomon riesce a correggere fino a t errori e 2t cancellature.  Il listato 1 fornisce un esempio di una possibile implementazione, scritta in C, di un encoder Reed-Solomon.

/****************************
Encoder
****************************/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define mm 4          /* RS code over GF(2**4) - change to suit */
#define nn 15         /* nn=2**mm -1 length of codeword */
#define tt 3          /* number of errors that can be corrected */
#define kk 9          /* kk = nn-2*tt */
int pp [mm+1] = { 1, 1, 0, 0, 1} ; /* specify irreducible polynomial coeffts */
/*int alpha_to [nn+1], index_of [nn+1], gg [nn-kk+1] ;*/
  /****Setting Up The Galois Fields and Indices*******/
  /* In practice they are generated ‘on the fly’ depending on the ‘packet’ sizes and parity bits
which are defined earlier. We are using a fixed packet size of 9 with 6 parity bits and thus these
       are the Galois Fields and Indices */
int gg[] = {6,9,6,4,14,10,0,0,0,0,0,0,0,0,0,0};
int alpha_to[] = {1,2,4,8,3,6,12,11,5,10,7,14,15,13,9,0};
int index_of[] = {-1,0,1,4,2,8,5,10,3,14,9,7,6,13,11,12};
int recd [nn], data [kk], bb [nn-kk] ;
void encode_rs();
/********Driver Program*******/
main(int argc, char **argv)
{ int count = 0;
  /*****Get User Input******/
  if(argc!=10)
  { printf(“Usage: a.out d1 d2 d3 d4 d5 d6 d7 d8 d9\n”);
    printf(“Where d1, d2, ..., etc. are the integer data values (0-15)\n”);
    printf(“Unix Example: a.out 1 2 3 4 5 6 7 8 9 [enter]\n”);
    printf(“ DOS Example: rs-encode 1 2 3 4 5 6 7 8 9 [enter]\n”);
    exit(0);
}
/****Convert ascii string to a float******/
for(count=0; count <kk; count++)
{ data[count] = atoi(argv[count+1]);
  if( count==0) {printf(“Input is: “);}
  printf(“%d “,data[count]);
}
encode_rs();
/**Print final contents of the parity bits**/
printf(“\nThe parity bits are: “);
for(count=0; count<nn-kk; count++) { printf(“%d “,bb[count]); }
printf(“\nFinished.\n”);
}
/* take the string of symbols in data[i], i=0..(k-1) and encode systematically to produce 2*tt
parity symbols in bb[0]..bb[2*tt-1]. data[] is input and bb[] is output in polynomial form. Encoding
is done by using a feedback shift register with appropriate connections specified by the
elements of gg[], which was generated above. Codeword is c(X)=data(X)*X**(nn-kk)+ b(X)
*/
void encode_rs()
{
   register int i,j;
   int feedback;
   for (i=0; i<nn-kk; i++) bb[i] = 0 ;
   for (i=kk-1; i>=0; i—)
   {
        feedback = index_of[data[i]^bb[nn-kk-1]] ;
        if (feedback != -1)
         {
         
             for (j=nn-kk-1; j>0; j—)
              {
               if (gg[j] != -1)
               {
                       bb[j] = bb[j-1]^alpha_to[(gg[j]+feedback)%nn] ;
               }
               else
               {
                       bb[j] = bb[j-1] ;
               }
             }
             bb[0] = alpha_to[(gg[0]+feedback)%nn] ;
     }
     else
      {
          for (j=nn-kk-1; j>0; j—) { bb[j] = bb[j-1] ; }
          bb[0] = 0 ;
       }
   }
}
Listato 1

 

Una risposta

  1. Maurizio Di Paolo Emilio Maurizio Di Paolo Emilio 4 febbraio 2017

Scrivi un commento

ESPertino è la nuova scheda per IoT compatibile ARDUINO.
Scopri come averla GRATIS!