Codul Hamming, Coduri detectoare de erori

Codul Hamming

Bitii din cuvantul de cod se numeroteaza de la stanga la dreapta incepand cu bitul 1 de la marginea din stanga. Bitii care sun puteri ale lui 2(1, 2, 4, 8, .) vor fi biti de control, restul de biti ai cuvantului de cod vor fi biti de date propriu-zisi. Fiecare bit de control forteaza ca paritatea unui grup de biti inclusiv el insusi sa fie para sau impara. Un bit poate fi inclus in mai multe calcule de paritate. Pentru a vedea la care biti de control contribuie bitul de date din pozitia k vom scrie k ca o suma de puteri ale lui 2; de exemplu 11=1+2+8, adica vom spune ca bitul 11 este verificat de bitii de control 1, 2 si 8. Cand primeste un cuvant de cod receptorul initializeaza un contor la 0, examineaza apoi fiecare bit de control pentru a vedea daca paritatea este corecta. Daca nu este corecta adauga la contor valoarea k. Daca la sfarsitul examinarii tuturor bitilor de control paritatea a fost corecta atunci contorul va avea valoarea 0. Daca valoarea contorului va fi diferita de 0 ea va reprezenta chiar numarul bitului incorect. Astfel daca bitii de control 1, 2 si 8 sunt eronati inseamna ca bitul care a fost inversat este bitul 11. Sa presupunem ca avem caracterul ASCII H: 1001000; atunci codul Hamming al acestui caracter va fi:

00110010000

1 2 34 5 67 8 910 11

3 = 1+2

7 = 1+2+4

Coduri detectoare de erori

Cele mai folosite coduri detectoare de erori sunt codurile polonomiale. Denumirea acestora este CRC (Cycle Redundancy Check). Codurile polinomiale se bazeaza pe tratarea sirului de biti ce trebuie transmis prin reprezentarea lui sau asocierea lui cu un polinom ai carui coeficienti vor fi 0 si 1. Astfel un cadru avand k biti va fi vazut ca o lista de coeficienti ai unui polinom avand k termeni respectiv de la la . Se spune ca un astfel de polinom este de grad k-1, termenii fiind numerotati de la bitul cel mai nesemnificativ de la stanga spre dreapta. De exemplu sa presupunem ca avem un cadru pe 6 biti 110001 caruia ii asociem polinomul: 1.

Toate calculele care se fac pentru codificarea unui cadru se vor face in aritmetica modulo 2 fara transport la adunare si fara imprumut la scadere. Practic adunarea si scaderea vor fi similare cu operatia Sau Exclusiv cand se utilizeaza metoda polinomiala, emitatorul si receptorul se pun de acord in alegerea asa numitului polinom generator notat cu G(x). Acest polinom este obligatoriu sa aiba cel mai semnificativ bit si respectiv cel mai putin semnificativ bit de valoare 1. Ideea acestei codificari este de a adauga o suma de control la sfarsitul cadrului astfel incat polinomul rezultat prin aceasta concatenare sa fie divizibil cu G(x). Cand receptorul primeste cadrul cu suma de control il asociaza polinomului de gradul respectiv (cat rezultat prin concatenare) si incearca sa-l imparta la G(x). Daca rezultatul impartirii are restul 0 receptorul considera ca transmisia s-a facut fara erori, in caz contrar se va cere retransmiterea cadrului respectiv.

Algoritmul pentru calculul sumei de control este urmatorul:

1.     fie r gradul polinomului G(x). se vor adauga cadrului de transmis r biti de 0 la capatul cel mai putin semnificativ al cadrului asa incat noul cadru va contine m biti de date r biti de 0(biti de control) si va corespunde polinomului:

G(x) - grad r

M(x) - cadru de transmis

- rezultat prin concatenarea cu r biti de 0

2.     se imparte modulo 2 cu polinomul generator G(x)

3.     se scade restul impartirii din sirul corespunzator si se va obtine polinomul care va fi transmis pe linie: T(x) - R(x); R(x) este restul impartirii lui la G(x).

Exemplu

Sa presupunem ca avem de transmis urmatorul cadru: 1101011011.

Alegem G(x): 10011  (1)

Se face concatenarea lui G(x), cadru + 5 biti de 0 (numarul bitilor de 0 este egal cu numarul bitilor lui G(x).

1 10 00 01 0 1 0 1

Sa presupunem ca la transmiterea cadrului apar erori. Atunci la receptie in loc sa ajunga T(x) va ajunge T(x) E(x). Receptorul va incerca sa imparta T(x) E(x) la G(x) adica:

[T(x) + E(x)] / G(x) = T(x) / G(x) + E(x) / G(x)

ca daca E(x) este divizibil cu G(x) aceste erori nu vor fi detectate, in schimb orice alta valoare va fi detectata.

Presupunem ca E(x) - eroare singulara pe bitul I

la receptie vom avea T(x) + . Pentru a se detecta eroarea trebuie ca sa nu fie divizibil cu G(x).

Conditia pentru a detecta erori de 1 bit este ca G(x) sa aiba cel putin 2 termeni.

Sa presupunem ca se produc doua erori singulare de 1 bit:

E(x) + ; i>j

E(x) = (+1)

In practica s-a demonstrat ca exista polinoame generatoare de grad mic care sa asigure protectia unor cadre de lungime mare cum ar fi polinomul 1. Acest polinom nu se divide cu factori de forma 1 pana la o valoare a lui k = 32768.