Codul lui Hamming
Această intrare sau secțiune despre subiecte de matematică și telecomunicații nu menționează sursele necesare sau cei prezenți sunt insuficienți . |
Î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).
- Găsiți o valoare K: ;
- 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 );
- 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
- Cod Hamming (7.4)
- Distanța de lovire
- Distanța Levenshtein , o generalizare a distanței Hamming
Alte proiecte
- Wikimedia Commons conține imagini sau alte fișiere despre Codul lui Hamming
linkuri externe
- ( EN ) Codul lui Hamming , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.