Hamming CodeDetectarea și corectarea erorilor cu exemple

Ce este o eroare?

TransmitDatele comunicate pot fi corupte în timpul comunicării. Este probabil să fie afectate de zgomot extern sau de alte defecțiuni fizice. Într-o astfel de situație, datele de intrare nu pot fi identice cu datele de ieșire. Această nepotrivire este cunoscută sub numele de „Eroare”.

Erorile de date pot cauza pierderea datelor importante sau securizate. Cea mai mare parte a transferului de date în sistemele digitale ia forma „transferului de biți” și chiar și o mică modificare a unui singur bit poate afecta performanța întregului sistem. Într-o secvență de date, dacă un 1 este schimbat în 0 sau un 0 este schimbat în 1, aceasta se numește „eroare de bit”.

Tipuri de erori

Există în principal trei tipuri de erori de bit care apar atunci când datele sunt transmitde la emițător la receptor. Diagrama de mai jos ilustrează modul în care fiecare tip afectează o secvență de date:

• Erori pe un singur bit
• Erori de biți multipli
• Erori de explozie

Erori pe un singur bit

O modificare adusă unui bit în întreaga secvență de date este cunoscută sub numele de „eroare pe un singur bit”. Apariția unei erori pe un singur bit nu este atât de frecventă. Se întâmplă mai ales într-un sistem de comunicații paralel, deoarece datele sunt transferate pe biți pe linii separate, astfel încât există o șansă mai mare ca o linie să devină zgomotoasă în timp ce celelalte rămân curate.

Erori de biți multipli

Când doi sau mai mulți biți ai unei secvențe de date se schimbă între transmitter și receptor, aceasta este cunoscută sub numele de „eroare pe mai mulți biți”.

Acest tip de eroare apare atât în ​​rețelele de comunicații de date seriale, cât și în cele paralele.

Erori de explozie

O modificare a unui set de biți consecutivi dintr-o secvență de date este cunoscută sub numele de „eroare în rafale”. Lungimea unei erori în rafale se măsoară de la primul bit modificat până la ultimul bit modificat.

Ce este detectarea și corectarea erorilor?

Într-un sistem de comunicații digitale, pot apărea erori pe măsură ce datele se transferă de la un dispozitiv la altul. Dacă aceste erori nu sunt detectate și corectate, datele se pierd. Pentru o comunicare eficientă, datele trebuie transferate cu o precizie ridicată, ceea ce se realizează prin identificarea mai întâi a erorilor și apoi corectarea acestora.

Eroare detectata este o metodă de identificare a erorilor prezente în date transmitluat de la un transmitter către un receptor într-un comunicare de date sistemului.

Codurile de redundanță sunt folosite pentru a găsi aceste erori prin adăugarea de biți suplimentari la date atunci când acestea sunt transmitde la sursă. Acești biți suplimentari se numesc „coduri de detectare a erorilor”. Cele mai comune trei tipuri de coduri de detectare a erorilor sunt:

• Verificarea parității
• Controlul redundanței ciclice (CRC)
• Verificarea redundanței longitudinale (LRC)

Verificarea parității

• Este cunoscut și ca verificare de paritate.
• Oferă un mecanism eficient din punct de vedere al costurilor pentru detectarea erorilor.
• În această tehnică, bitul redundant adăugat fiecărei unități de date este cunoscut sub numele de bit de paritate. Acesta este setat astfel încât numărul total de 1-uri din unitate să devină par (paritate pară) sau impar (paritate impară).

Verificarea redundanței longitudinale

În această tehnică de detectare a erorilor, un bloc de biți este organizat într-un tabel. Metoda LRC calculează un bit de paritate pentru fiecare coloană, iar acest set de biți de paritate este trimis împreună cu datele originale. Blocul de biți de paritate ajută receptorul să verifice redundanța și să detecteze erorile.

Verificare redundanță ciclică

Verificarea redundanței ciclice adaugă o secvență de biți redundanți la sfârșitul unității de date, astfel încât unitatea de date rezultată să devină exact divizibilă cu un al doilea număr binar predeterminat.

La destinație, datele primite sunt împărțite la același număr. Dacă nu există rest, unitatea de date este considerată corectă și este acceptată. În caz contrar, indică faptul că unitatea de date a fost deteriorată în timpul transmisiei și trebuie respinsă.

Ce este un Hamming Code?

Codul Hamming este un cod liniar util pentru detectarea a până la două erori imediate pe bit și corectarea erorilor pe un singur bit. Corecția erorilor de acest tip operează de obicei la nivelul legăturii de date, încadrând datele și verificând integritatea acestora între nodurile adiacente.

În codul Hamming, sursa codifică mesajul prin adăugarea de biți redundanți. Acești biți redundanți sunt inserați și generați în poziții specifice din mesaj pentru a efectua procesul de detectare și corectare a erorilor.

Istoria lui Hamming Code

• Codul Hamming este o tehnică dezvoltată de RW Hamming pentru detectarea și corectarea erorilor.
• Poate fi aplicat unităților de date de orice lungime și utilizează relația dintre biții de date și biții de redundanță.
• Hamming a lucrat la problema corecției erorilor și a dezvoltat o gamă din ce în ce mai puternică de algoritmi.
• În 1950, a publicat codul Hamming, care este încă utilizat pe scară largă astăzi în aplicații precum memoria ECC.

Aplicații ale lui Hamming Code

Iată câteva aplicații comune ale codului Hamming:

• Sateliții
• Memoria computerului (ECC RAM)
• modemurile
• PlasmaCAM
• Deschideți conectori
• Sârmă ecranată
• Procesoare încorporate

Avantajele Hamming Code

• Codul Hamming este eficient în rețelele în care fluxurile de date sunt expuse la erori pe un singur bit.
• Nu numai că detectează o eroare de bit, dar vă ajută și să identificați bitul care conține eroarea, astfel încât aceasta să poată fi corectată.
• Ușurința în utilizare a codurilor Hamming le face potrivite pentru memoria computerului și corectarea erorilor singulare.

Dezavantaje ale lui Hamming Code

• Este un cod de detectare și corectare a erorilor pe un singur bit. Dacă se constată că mai mulți biți sunt eronați, rezultatul poate inversa un alt bit care era de fapt corect, corupând și mai mult datele.
• Algoritmul codului Hamming poate rezolva doar probleme pe un singur bit.

Cum se codifică un mesaj în Hamming Code

Procesul pe care expeditorul îl folosește pentru a codifica mesajul implică următorii trei pași:

• Calculați numărul total de biți redundanți.
• Determinați poziția biților redundanți.
• Calculați valoarea fiecărui bit redundant.

Când biții redundanți sunt încorporați în mesaj, cuvântul de cod complet este trimis receptorului.

Pasul 1) Calculați numărul total de biți redundanți.

Presupunem că mesajul conține n biți de date și p biți redundanți, adăugați astfel încât 2^p poate indica cel puțin (n + p + 1) stări diferite.

Aici, (n + p) reprezintă locația unei erori în fiecare dintre pozițiile biților (n + p), iar o stare suplimentară indică lipsa unei erori. Deoarece p biți de paritate pot indica 2^p state, 2^p trebuie să fie cel puțin egal cu (n + p + 1).

Pasul 2) Plasați biții redundanți în pozițiile lor corecte.

Cei p biți redundanți sunt plasați la poziții de biți care sunt puteri ale lui 2 - de exemplu, 1, 2, 4, 8 și 16. Aceștia sunt denumiți p₁ (la poziția 1), p₂ (la poziția 2), p₃ (la poziția 4) și așa mai departe.

Pasul 3) Calculați valoarea fiecărui bit redundant.

Fiecare bit redundant este un bit de paritate care face ca numărul de 1-uri din grupul său să fie par sau impar. Cele două tipuri de paritate sunt:

• Paritate uniformă: Numărul total de 1-uri din pozițiile acoperite este par.
• Paritate impară: Numărul total de 1-uri din pozițiile acoperite este făcut impar.

Fiecare bit de paritate acoperă un set specific de poziții, determinat de reprezentarea binară a numerelor de poziție:

• p₁ verifică fiecare poziție a cărei valoare binară are un 1 în bitul cel mai puțin semnificativ - pozițiile 1, 3, 5, 7, 9, 11 și așa mai departe.
• p₂ verifică fiecare poziție a cărei valoare binară are un 1 în al doilea bit de la dreapta — pozițiile 2, 3, 6, 7, 10, 11 și așa mai departe.
• p₃ verifică fiecare poziție a cărei valoare binară are un 1 în al treilea bit de la dreapta — pozițiile 4 la 7, 12 la 15 și așa mai departe.

Exemplu lucrat (7,4): Luați în considerare cei patru biți de date 1011Sunt necesari trei biți de paritate (2³ = 8 ≥ 4 + 3 + 1), rezultând un cuvânt de cod pe șapte biți, prezentat ca p₁ p₂ d₁ p₃ d₂ d₃ d₄Plasarea datelor plasează pozițiile 3, 5, 6, 7 = 1, 0, 1, 1. Folosind paritatea pară: p₁ acoperă pozițiile 1, 3, 5, 7 (biții 1, 0, 1 → p₁ = 0); p₂ acoperă 2, 3, 6, 7 (biții 1, 1, 1 → p₂ = 1); p₃ acoperă 4, 5, 6, 7 (biții 0, 1, 1 → p₃ = 0). Cel/Cea/Cei/Cele transmitPrin urmare, cuvântul de cod Ted este 0110011.

Cum să decodezi un mesaj în Hamming Code

Destinatarul preia mesajul primit și efectuează recalculări pentru a găsi și corecta erorile. Procesul de recalculare utilizează următorii pași:

• Numărați numărul de biți redundanți.
• Poziționați corect toți biții redundanți.
• Efectuați verificarea parității.

Pasul 1) Numărați numărul de biți redundanți. Folosește aceeași formulă ca pentru codificare: 2^p ≥ n + p + 1, unde n este numărul de biți de date, iar p este numărul de biți redundanți.

Pasul 2) Poziționați corect toți biții redundanți. Fiecare bit redundant se află la o poziție de bit care este o putere a lui 2 - de exemplu, 1, 2, 4 și 8.

Pasul 3) Efectuați verificarea parității. Biții de paritate sunt recalculați din biții de date și biții redundanți recepționați:

• p₁ = paritate(1, 3, 5, 7, 9, 11, …)
• p₂ = paritate(2, 3, 6, 7, 10, 11, …)
• p₃ = paritate(4–7, 12–15, 20–23, …)

Biții de paritate recalculați formează împreună un număr binar. Dacă acel număr este zero, nu există nicio eroare; în caz contrar, valoarea sa indică poziția exactă a bitului unic corupt, care este apoi inversat pentru a corecta mesajul.

Întrebări frecvente