Cod Hamming: detectarea erorilor și corectarea cu exemple

Ce este o eroare?

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

Erorile de date pot duce la pierderea de date importante sau sigure. Majoritatea transferului de date în sistemele digitale se va face sub formă de „transfer de biți”. Chiar și o mică schimbare poate afecta performanța întregului sistem. Într-o secvență de date, dacă 1 este schimbat la 0 sau 0 este schimbat la 1, se numește „Eroare de bit”.

Tipuri de erori

Există în principal trei tipuri de eroare de biți care apar în transmisia de date de la emițător la receptor.

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

Erori pe un singur bit

Modificarea făcută într-un bit în întreaga secvență de date este cunoscută sub numele de „Eroare pe un singur bit”. Cu toate acestea, apariția unei erori pe un singur bit nu este atât de comună. Mai mult, această eroare apare doar într-un sistem de comunicații paralel, deoarece datele sunt transferate pe biți pe o singură linie. Prin urmare, există mai multe șanse ca o singură linie să fie zgomotoasă.

Erori de biți multipli

În secvența de date, dacă există o schimbare în doi sau mai mulți biți dintr-o secvență de date de la un emițător la receptor, aceasta este cunoscută sub numele de „Erori de biți multipli”.

Acest tip de eroare apare în principal atât în ​​rețelele de comunicații de date de tip serie, cât și în paralel.

Erori de explozie

Schimbarea setului de biți în secvența de date este cunoscută sub numele de „Eroare de explozie”. Acest tip de eroare de date este calculată de la schimbarea primului bit până la ultima modificare a bitului.

Ce este detectarea erorilor și corectarea erorilor?

În sistemul de comunicații digitale, eroarea va fi transferată de la un sistem de comunicații în altul. Dacă aceste erori nu sunt detectate și corectate, atunci datele se vor pierde. Pentru o comunicare eficientă, datele sistemului ar trebui să fie transferate cu o precizie ridicată. Acest lucru se va face prin identificarea mai întâi a erorilor și corectarea acestora.

Detectarea erorilor este o metodă de detectare a erorilor care sunt prezente în datele transmise de la un emițător la receptor într-un sistem de comunicație de date.

Aici, puteți folosi coduri de redundanță pentru a găsi aceste erori, adăugând la date atunci când sunt transmise de la sursă. Aceste coduri se numesc „Coduri de detectare a erorilor”.

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.
• Are un mecanism rentabil pentru detectarea erorilor.
• În această tehnică, bitul redundant este cunoscut ca bit de paritate. Este atașat pentru fiecare unitate de date. Numărul total de 1 din unitate ar trebui să devină par, ceea ce este cunoscut ca bit de paritate.

Verificarea redundanței longitudinale

În această tehnică de detectare a erorilor, un bloc de biți este organizat în format tabelar. Metoda LRC vă ajută să calculați bitul de paritate pentru fiecare coloană. Setul acestei parități este de asemenea trimis împreună cu datele originale. Blocul de paritate vă ajută să verificați redundanța.

Verificare redundanță ciclică

Verificarea redundanței ciclice este o secvență de redundanță care trebuie atașată la sfârșitul unității. De aceea, unitatea de date rezultată ar trebui să devină divizibilă cu un al doilea număr binar predeterminat.

La destinație, datele primite trebuie împărțite la același număr. În cazul în care nu există rest, atunci unitatea de date se presupune a fi corectă și este acceptată. În caz contrar, indică faptul că unitatea de date este deteriorată în timpul transmisiei și, prin urmare, trebuie respinsă.

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

Istoria codului Hamming

• Codul Hamming este o tehnică construită de RWHamming pentru a detecta erorile.
• Codul Hamming ar trebui aplicat la unitățile de date de orice lungime și utilizează relația dintre date și biții de redundanță.
• A lucrat la problema metodei de corectare a erorilor și a dezvoltat o gamă din ce în ce mai puternică de algoritmi numită cod Hamming.
• În 1950, a publicat Codul Hamming, utilizat pe scară largă astăzi în aplicații precum memoria ECC.

Aplicarea codului Hamming

Iată câteva aplicații comune de utilizare a codului Hamming:

• Sateliții
• Memorie computer
• modemurile
• PlasmaCAM
• Deschideți conectori
• Sârmă de ecranare
• Procesor încorporat

Avantajele codului Hamming

• Metoda codului Hamming este eficientă pe rețelele în care fluxurile de date sunt date pentru erorile pe un singur bit.
• Codul Hamming nu numai că oferă detectarea unei erori de biți, dar vă ajută și să indentați eroarea care conține biți, astfel încât să poată fi corectată.
• Ușurința de utilizare a codurilor de haming le face cel mai potrivite pentru utilizarea în memoria computerului și corectarea unei singure erori.

Dezavantajele codului Hamming

• Cod de detectare și corectare a erorilor pe un singur bit. Cu toate acestea, dacă există o eroare fondată pe mai mulți biți, atunci rezultatul poate avea ca rezultat un alt bit care ar trebui să fie corect modificat. Acest lucru poate duce la erori suplimentare ale datelor.
• Algoritmul de cod Hamming poate rezolva problemele cu un singur biți.

Cum se codifică un mesaj în Hamming Code

Procesul folosit de expeditor pentru a codifica mesajul include următorii trei pași:

• Calculul numărului total de biți redundanți.
• Verificarea poziției biților redundanți.
• În cele din urmă, calcularea valorilor acestor biți redundanți.

Când biții redundanți de mai sus sunt încorporați în mesaj, acesta este trimis utilizatorului.

Pas 1) Calculul numărului total de biți redundanți.

Să presupunem că mesajul conține:

• n– numărul de biți de date
• p – numărul de biți redundanți care îi sunt adăugați astfel încât np să poată indica cel puțin (n + p + 1) stări diferite.

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

Pas 2) Plasarea biților redundanți în poziția lor corectă.

Biții p redundanți ar trebui plasați la poziții de biți cu puteri de 2. De exemplu, 1, 2, 4, 8, 16 etc. Aceștia sunt denumiți ca p₁ (la poziția 1), p₂ (la poziția 2), p₃ (la pozitia 4), etc.

Pas 3) Calculul valorilor bitului redundant.

Biții redundanți ar trebui să fie biți de paritate fac ca numărul de 1 să fie par sau impar.

Cele două tipuri de paritate sunt ?

• Numărul total de biți din mesaj este făcut par se numește paritate pară.
• Numărul total de biți din mesaj devine impar se numește paritate impară.

Aici, tot bitul redundant, p1, trebuie calculat ca paritate. Ar trebui să acopere toate pozițiile biților a căror reprezentare binară ar trebui să includă un 1 în prima poziție, excluzând poziția lui p1.

P1 este bitul de paritate pentru fiecare biți de date din pozițiile a căror reprezentare binară include un 1 în poziția mai puțin importantă, fără a include 1 Like (3, 5, 7, 9, .... )

P2 este bitul de paritate pentru fiecare biți de date din pozițiile a căror reprezentare binară include 1 în poziția 2 din dreapta, fără a include 2 Like (3, 6, 7, 10, 11,...)

P3 este bitul de paritate pentru fiecare bit din pozițiile a căror reprezentare binară include un 1 în poziția 3 din dreapta, nu include 4 Like (5-7, 12-15,... )

Decriptarea unui mesaj în codul Hamming

Destinatorul primește mesaje care necesită să efectueze recalculări pentru a găsi și corecta erorile.

Procesul de recalculare se desfășoară în următorii pași:

• Numărarea numărului de biți redundanți.
• Poziționarea corectă a tuturor biților redundanți.
• Verificare paritate

Pas 1) Numărarea numărului de biți redundanți

Puteți utiliza aceeași formulă pentru codificare, numărul de biți redundanți

2^p ? n + p + 1

Aici, numărul de biți de date și p este numărul de biți redundanți.

Pas 2) Poziționând corect toți biții redundanți

Aici, p este un bit redundant care este situat la pozițiile biților cu puteri de 2, De exemplu, 1, 2, 4, 8 etc.

Pas 3) Verificare paritate

Biții de paritate trebuie să fie calculati pe baza biților de date și a biților redundanți.

p1 = paritate (1, 3, 5, 7, 9, 11...)

p2 = paritate (2, 3, 6, 7, 10, 11… )

p3 = paritate(4-7, 12-15, 20-23… )

Rezumat

• Datele transmise pot fi corupte în timpul comunicării
• Trei tipuri de eroare de biți sunt 1) Erori de un singur bit 2) Eroare de biți multipli 3) Erori de biți de explozie
• Modificarea făcută într-un bit în întreaga secvență de date este cunoscută sub numele de „Eroare pe un singur bit”.
• În secvența de date, dacă există o schimbare în doi sau mai mulți biți dintr-o secvență de date de la un emițător la receptor, aceasta este cunoscută sub numele de „Erori de biți multipli”.
• Schimbarea setului de biți în secvența de date este cunoscută sub numele de „Eroare de explozie”.
• Detectarea erorilor este o metodă de detectare a erorilor care sunt prezente în datele transmise de la un emițător la receptor într-un sistem de comunicație de date.
• Trei tipuri de coduri de detectare a erorilor sunt: ​​1) Verificarea parității 2) Verificarea redundanței ciclice (CRC) 3) Verificarea redundanței longitudinale (LRC)
• Codul Hamming este un cod de liner care este util pentru detectarea erorilor de până la două erori imediate de biți. Este capabil de erori pe un singur bit.
• Codul Hamming este o tehnică construită de RWHamming pentru a detecta erorile.
• Aplicațiile obișnuite de utilizare a codului Hamming sunt memoria computerului prin satelit, modemurile, procesorul încorporat etc.
• Cel mai mare beneficiu al metodei codului hamming este eficient pe rețelele în care fluxurile de date sunt date pentru erorile pe un singur bit.
• Cel mai mare dezavantaj al metodei codului hamming este că poate rezolva doar problemele cu un singur biți.
• Putem efectua procesul de criptare și decodare a mesajului cu ajutorul codului hamming.