Detectarea si corectarea erorilor in legatura de date

Informatiile schimbate intre diferite sisteme sunt codificate, pentru a realiza adaptarea statistica a sursei la canalul de comunicatie. Canalul de comunicatie poate fi afectat sau nu de perturbatii.Un canal neperturbat ar corespunde unei criptari sau compresii a informatiei, pe cind un canal perturbat transmisiei acesteia.
Sistemele actuale care inglobeaza calculatoare si echipamente automate necesita o transmisie cit mai corecta a informatiei; pentru aceasta semnalul trimis este prelucrat inainte de a fi emis. Prelucrarea semnalului se realizeaza foarte usor in cazul transmisiei de semnale discrete, prin codificare. Receptorul va decodifica semnalul primit si va incerca sa estimeze daca au aparut erori. Pentru tratarea codificarii/decodificarii s-a dezvoltat un amplu aparat matematic, bazat pe calculul vectorial si polinomial. Astfel, in cazul codurilor bloc, folosind alfabetul binar {0,1}, se pot realiza 2^n combinatii (cuvinte de cod de aceeasi lungime n) folosind n biti.
Aceste cuvinte de cod pot fi asimilate cu vectori sau cu polinoame. Daca toate cele 2^n combinatii reprezinta cuvinte utile (cu sens), atunci aparitia unei erori transforma un cuvint de cod in altul, fara a se putea realiza detectia sau corectia erorilor. De aceea, informatia utila va fi codificata pe k
Un program de calcul al codului de control ciclic CRC-CCITT este urmatorul:


crc.h

#define CRCCCITT 0x1021 // polinomul generator

#include "stdio.h"
#include "stdlib.h"

typedef unsigned short int word;
typedef unsigned char byte;

word calculcrc (word, word, word);
word* tabelcrc (word);


crc.c

#include "crc.h"
#include "stdio.h"
#include "string.h"
//
// calculeaza noul rest partial pe baza vechiului rest
// (acum), a unui octet de date (data) si a polinomului
// generator (genpoli)
//

word calculcrc (word data, word genpoli, word acum)
{
int i;
data <<= 8;
for (i=8; i > 0; i--)
{
if ((data^acum) & 0x8000)
acum = (acum << 1) ^ genpoli;
else
acum <<= 1;
data <<= 1;
}
return acum;
}

/*
Functia "calculcrc" determina efectul aplicarii procedeului clasic de calcul CRC asupra unui octet de date. Generatorul polinomial (genpoly) si continutul initial al acumulatorului
(accum) sint date ca argumente.

Calculul prin program al secventei de control sugereaza posibilitatea de a trata problema nu la nivelul fiecarui bit al unui mesaj, ci la nivelul octetilor. Ideea este de a gasi o modalitate mai simpla prin care, dat fiind un octet de date si continutul vechi al acumulatorului (registrul de deplasare) sa se calculeze noua valoare a acumulatorului. Facind o simulare a operatiilor, se poate constata ca octetul de date se combina doar cu bitii mai semnificativi ai acumulatorului, noua valoare a acumulatorului fiind suma (modulo 2 a) secventei de control corespunzatoare acestei valori combinate si a octetului mai putin semnificativ al acumulatorului. Deoarece valoarea combinata ocupa 8 biti, ea poate avea 256 de valori diferite, secventele de control pentru toate aceste valori putind fi calculate si pastrate intr-un tablou. In acest mod calculul noului acumulator se poate face foarte simplu, prin insumarea modulo 2 a octetului inferior al acumulatorului cu o valoare precalculata, din cea totala.

Functia tabelcrc construieste acest tablou; ea are ca parametri:
generatorul polinomial si un pointer la o functie CRC (de ex. calculcrc) si intoarce (unsigned short * ) un pointer in tabela.
*/

//
// calculeaza tabelul codurilor CRC
// alcatuieste tabelul codurilor CRC pentru un anumit
// polinom generator (poli); apeleaza "calculcrc" pentru
// toate cele 256 combinatii posibile ale octetului de date
// intoarce un pointer la tabelul de coduri, alocat dinamic
//

word* tabelcrc (word poli )
{
word* ptabelcrc;
int i;
if ((ptabelcrc = (word*) malloc (256 * sizeof (word))) == NULL)
return NULL;
for (i=0; i < 256; i++)
ptabelcrc [i] = calculcrc (i, poli, 0);
return ptabelcrc;
}

// calculeaza CRC partial (acum) corespunzator unui octet
// (data) prin utilizarea tabelului codurilor CRC (tabelcrc)

void crctabel (word data, word* acum, word* tabelcrc)
{
word valcomb;
valcomb = ((*acum >> 8) ^ data) & 0x00FF;
*acum = ((*acum & 0x00FF) << 8) ^ tabelcrc [valcomb];
}

//
// calculeaza CRC pentru un fisier al carui nume este dat de utilizator; pentru verificare, dupa calculul CRC corespunzator fisierului, se continua calculul considerind si valoarea CRC gasita;
// rezultatul (acumulator) dupa adaugarea CRC este nul

int main ()
{
char s [] = "stuff this in your pipe";
word acum = 0, *tabel = tabelcrc(CRCCCITT); // CRCCCITT este generatorul de polinoame
int i;
for(i=0; i < strlen(s); i++)
crctabel(s[i], &acum, tabel); // pt toate car din string
printf("%d\n",acum);

word ac = acum;
crctabel(ac>>8, &acum, tabel);
crctabel(ac& 0x00FF, &acum, tabel);

printf("%d\n",acum);
return 0;

}