Codul lui Hamming

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În telecomunicații, codul Hamming este un cod de corecție liniar numit după inventatorul său Richard Hamming . Codul Hamming poate detecta și corecta erorile pe un singur bit. Cu alte cuvinte, distanța Hamming între cuvintele de cod transmise și primite trebuie să fie zero sau una pentru o comunicare fiabilă. Alternativ, codul poate dezvălui (dar nu corect) erori duplicate.

Codul Hamming face parte din codurile liniare , iar parametrii săi sunt , unde q este dimensiunea alfabetului folosit (de exemplu 2 dacă este binar) și m este numărul de biți utilizați.

Codul de paritate permite detectarea erorii, dar nu corectarea acesteia. Prin creșterea redundanței în mesaj (adăugarea de biți pentru detectarea și corectarea erorilor) este, de asemenea, posibil să cunoașteți poziția bitului greșit și, astfel, să îl corectați. Codul Hamming oferă această posibilitate.

Dacă un cod conține N informații distincte, reprezentarea în formă binară a fiecăruia dintre ele are loc folosind un cuvânt n- bit, astfel încât să apară: .

De sine, , o eroare în unul sau mai mulți biți duce la o configurație binară diferită care, totuși, corespunde întotdeauna unei date care aparține aceluiași cod: în practică nu este posibil să înțelegem dacă a existat sau nu o eroare.

De exemplu, să presupunem că doriți să codificați cifrele zecimale 0-9 folosind 5 biți. Cu 5 biți sunt posibili configurații diferite din care doar 10 vor fi utilizate. Dacă există o eroare, datele ar putea presupune una dintre celelalte 22 de configurații și, prin urmare, va fi posibil să se dezvăluie o eroare. Rețineți că doar 4 biți ar fi necesari pentru codificarea celor 10 cifre zecimale. Al cincilea bit este redundant . Metoda de codificare rămâne de definit. Un bun criteriu este acela care asociază fiecare cifră zecimală cu o configurație binară în care există întotdeauna două 1s și trei 0s (sau invers) ca în tabelul următor.

Zecimal Codificare
0 11000
1 10100
2 10010
3 10001
4 01100
5 01010
6 01001
7 00110
8 00101
9 00011

Rețineți că, dacă apare o eroare, numărul de 1 din cod este modificat. Acest tip de codificare identifică, de asemenea, prezența, dar nu locația erorii.

Metoda de construcție a codului

Legendă:

  • , numărul de biți ai mesajului original;
  • , numărul de biți de „verificare” (de redundanță) adăugați la mesajul original;
  • , numărul de biți ai mesajului final (adică mesajul după codarea Hamming).
  1. Găsiți o valoare K: ;
  2. Plasați biții K găsiți, în mesajul original, în funcție de puterile lui 2 ( , considerăm puterile pe baza valorii lui K, dacă K este egal cu trei, vom lua în considerare puterile până la );
  3. Găsiți valoarea K:
    • Codurile binare codifică pozițiile biților mesajului final (de exemplu, pentru un mesaj pe 6 biți, pozițiile vor fi numerotate de la primul - 001 la al șaselea - 110);
    • Pozițiile binare ale fiecărui K sunt verificate, acordând atenție la ce poziție ocupă bitul 1 (de exemplu, în poziția 1 ocupă poziția cea mai dreaptă; în poziția 2, pe de altă parte, poziția centrală) și care cifre ale mesajului au o 1 în aceeași poziție;
    • Cifrele găsite sunt luate în considerare și bitul de paritate este găsit (de exemplu cifra1 = 1, cifra2 = 0, cifra3 = 0; bitul de paritate = 1), bitul de paritate va corespunde valorii lui K.

Detectarea și corectarea erorilor

Odată ce mesajul a fost codificat conform lui Hamming, acesta ajunge la receptor care îl verifică înainte de al utiliza, deoarece mesajul poate suferi modificări din cauza zgomotelor de semnal. Presupunând că un mesaj incorect ajunge la receptor, procedați conform regulii descrise mai sus, adică realizând bitul de paritate al biților legați împreună de același K.

Exemplu:

Mesaj corect:

Mesaj original: 10

K. Bit de paritate
K1 (3,5) 1
K2 (3) 1
K3 (5) 0

Astfel se obține mesajul codat: 11 1 0 0

Receptor

Mesaj primit (incorect): 11000

K. Bit de paritate
K1 (3,5) 0
K2 (3) 0
K3 (5) 0

Odată ce valorile K sunt obținute, operația logică XOR se efectuează între K corespunzător al mesajului receptorului și cele ale sursei. Acest lucru va avea ca rezultat o succesiune verticală de numere binare.

Exemplu:

K1 (1) XOR K1r (0) = 1

K2 (1) XOR K2r (0) = 1

K3 (0) XOR K3r (0) = 0

Rezultatele obținute sunt apoi citite de jos în sus, obținând poziția binară a bitului greșit (în cazul nostru obținem 011 (3dec))

Elemente conexe

Alte proiecte

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică