Acest articol nu are suficiente informații.
Codurile Hamming sunt cele mai faimoase și, probabil, primele coduri de auto-verificare și autocorecție. Acestea sunt construite cu referire la un sistem de numere binare.
1. Istorie
La mijlocul anilor 1940, Richard Hamming a lucrat la celebrul Bell Labs pe masina de numărare Bell model V. A fost o mașină electromecanic folosind unități de relee, care a fost rata este foarte scăzută: o tură în câteva secunde. Datele au fost introduse în mașină folosind cartele perforate și, prin urmare, s-au produs greșeli adesea în timpul procesului de lectură. În zilele de lucru coduri speciale utilizate pentru a detecta și corecta eventualele erori constatate, operatorul a recunoscut eroarea lămpilor incandescente, corectate și rula mașina. În weekend, când nu au existat operatori, atunci când a apărut o eroare, mașina a părăsit automat programul și a pornit altul.
2. Coduri sistematice
Codurile sistematice formează un grup mare printre blocurile, codurile separabile (în care toate simbolurile pot fi împărțite în test și informații). O caracteristică a codurilor sistematice este aceea că simbolurile de testare sunt formate ca urmare a operațiilor liniare pe simbolurile informaționale. În plus, orice combinație de cod permisă poate fi obținută ca rezultat al operațiilor liniare pe un set de cuvinte cheie de codare independente liniar.
3. Codurile de auto-monitorizare
Codurile Hamming sunt coduri de auto-monitorizare, adică coduri care detectează automat erori în transmiterea datelor. Pentru construcția lor, este suficient să se atribuie fiecărui cuvânt un bit suplimentar (control) și să se selecteze cifra acestui bit astfel încât numărul total de unități din imaginea oricărui număr să fie, de exemplu, egal. O singură eroare în orice deversare a cuvântului transmis (inclusiv, probabil, în categoria de control) va schimba paritatea numărului total de unități. Contoarele modulo 2, numărarea numărului de unități care sunt cuprinse între cifrele binare ale numărului, pot semnala prezența erorilor.
Nu este posibil să se știe în ce categorie exactă a apărut eroarea și, prin urmare, nu există nicio modalitate de ao corecta. Erori care apar simultan în două, patru sau chiar un număr par de biți rămân neobservate. Cu toate acestea, dublu, iar greșelile de mai mult de patru ori sunt considerate puțin probabile.
4. Coduri de auto-corectare
Codurile în care este posibilă corectarea automată a erorilor se numesc autocorecție. Pentru a construi un cod de autocorecție destinat să stabilească singurele erori, nu este suficientă o singură cifră de verificare. După cum se poate observa din cele ce urmează, numărul de cifre de control k ar trebui ales astfel încât inegalitatea să fie satisfăcută sau, în cazul în care m este numărul de biți de bază ai cuvântului de cod. Valorile minime ale lui k pentru valorile date de m, găsite în conformitate cu această inegalitate, sunt prezentate în tabel.
În prezent, codurile binare de corecție a blocurilor sunt de maxim interes. Atunci când se utilizează astfel de coduri, informația este transmisă sub formă de blocuri de aceeași lungime și fiecare bloc este codat și decodificat independent una de cealaltă. Aproape în toate codurile de bloc, simbolurile pot fi împărțite în informații și verificări. Astfel, toate combinațiile de coduri sunt împărțite în permis (pentru care raportul dintre simbolurile de informare și verificare este posibil) și interzis.
Principalele caracteristici ale codurilor de autocorecție sunt:
- Numărul de combinații permise și interzise. Dacă n este numărul de caractere din bloc, r este numărul de simboluri de paritate din bloc, k este numărul de simboluri de informație, apoi numărul de cuvinte de cod posibile, numărul de cuvinte de cod admise și numărul de combinații interzise.
- Redundanța codului. Valoarea se numește redundanța codului corectiv.
- Distanța minimă de cod. Distanta minima a codului d este numarul minim de simboluri distorsionate necesare pentru a trece o combinatie permisa pe alta.
- Numărul de erori detectabile și corectabile. Dacă g este numărul de erori pe care codul le poate corecta, atunci este necesar și suficient
- Capacitățile corective ale codurilor.
Frontiera Plotkin dă limita superioară a distanței de cod sau
Limita Hamming stabilește numărul maxim posibil de cuvinte cheie admise unde este numărul de combinații de elemente n de elemente i. De aici se poate obține o expresie pentru estimarea numărului de simboluri de paritate: Pentru valori, diferența dintre limita Hamming și limita Plotkin este mică.
Limita Varshamov-Hilbert pentru n mare definește limita inferioară a numărului de simboluri de paritate Toate estimările de mai sus dau o idee a limitei superioare d pentru fix n și k sau estimarea inferioară a numărului de simboluri de paritate
5. Literatură
- Peterson W. Weldon E. Coduri de corectare a erorilor: Trans. cu engleza. M. Mir, 1976, 600 c.
- Clark D. Kane D. Codificare cu corecție de eroare în sistemele de comunicații digitale: Per. cu engleza. M. Radio și comunicare, 1987, 300 p.
Codul Hamming
Construcția codurilor Hamming se bazează pe principiul verificării parității numărului de simboluri unice: un element este adăugat la secvență, astfel încât numărul de simboluri unice din secvența rezultată este egal. Semnul aici înseamnă adăugarea modulului 2
. - nu există nici o eroare, o singură eroare. Acest cod este numit sau. Primul număr este numărul de elemente din secvență, al doilea este numărul de simboluri de paritate. Pentru fiecare număr de simboluri de paritate există un cod Hamming clasic cu un marcaj adică. -. Pentru alte valori ale lui k, așa-numitul cod trunchiat este obținut, de exemplu, codul telegrafic internațional MTK-2, pentru care. Este nevoie de codul Hamming, care este trunchiat de la cel clasic. De exemplu, luați în considerare codul clasic Hamming. Grupăm simbolurile testului după cum urmează:
Semnul aici înseamnă adăugarea modulului 2.
Obținerea cuvântului de cod arată astfel:
La introducerea decodorului apare cuvântul de cod în care simbolurile sunt marcate cu un accident vascular cerebral, care poate fi distorsionată ca urmare a interferenței. În decodor, în modul de corectare a erorilor, se construiește o secvență de sindroame:
se numește sindrom de secvență.
Aflarea sindromului arată astfel:
=
Cuvinte cheie pentru codul Hamming