1. Semnificația codului Hamming.
3. Principiul construirii codurilor Hamming.
1. Semnificația codului Hamming
Codul Hamming este un cod sistematic, care constă în simboluri informative și corective dispuse de-a lungul unui sistem strict definit, având aceeași lungime și ocupând întotdeauna locuri strict definite în combinații de coduri.
Metodele regulate propuse de Hamming pentru construirea codurilor de corectare a erorilor sunt de o importanță fundamentală. Acestea demonstrează inginerilor posibilitatea practică de a atinge limitele indicate de legile teoriei informației. Aceste coduri au găsit aplicații practice în crearea sistemelor informatice. Lucrarea lui Hamming a dus la rezolvarea problemei ambalării mai densă a câmpurilor finite. El a introdus în uz științific cele mai importante concepte de codificare teorie - distanța Hamming între codewords într-un spațiu vectorial definit pentru codurile binare ca numărul de poziții ale acestor combinații cu diferite simboluri si Hamming legat pentru corectarea capacității codurilor corectoare de erori de bloc. Limita Hamming pentru codurile binare se calculează după următoarea formulă:
În această expresie, numărul de erori e poate fi corectat printr-un cod de blocare de corecție a lungimii N cu combinații de coduri M (C j N este coeficientul binomial).
Activitatea lui Hamming a jucat un rol cheie în dezvoltarea ulterioară a teoriei codării și a stimulat cercetările extinse desfășurate în anii următori.
Codurile Hamming permit nu numai să detecteze prezența unei erori, ci și locația locației sale și, prin urmare, să ofere posibilitatea de ao repara.
2. Codurile Hamming.
Codurile Hamming sunt coduri de auto-monitorizare, adică coduri care detectează automat cele mai grave 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.
În acest caz, desigur, nu primim nici o indicație cu privire la categoria exactă în care a apărut eroarea și, prin urmare, nu o putem corecta. Erori care apar simultan în două, patru sau chiar un număr par de biți rămân neobservate. Cu toate acestea, dublul, și greșelile de mai mult de patru ori sunt considerate puțin probabile.
Codurile în care este posibilă corectarea automată a erorilor se numesc autocorecție. Pentru a construi un cod de autocorecție destinat să corecteze singurele erori, nu este suficientă o singură cifră de verificare. După cum se vede din cele ce urmează, numărul de biți de control k ar trebui să fie ales astfel încât inegalitatea sau este îndeplinită. unde m este numărul de biți de bază ai cuvântului de cod. Valorile minime ale lui k pentru valori date de m, găsite în conformitate cu această inegalitate, sunt prezentate în tabelul nr. 1
Având cifre m + k, codul de autocorecție poate fi construit după cum urmează.
Atribuiți fiecăruia dintre cifre numărul - de la 1 la m + k; vom scrie aceste numere în sistemul binar. Deoarece 2 k> m + k, fiecare număr poate fi reprezentat, evident, de un număr binar k-bit.
Să presupunem în plus că toate cifrele m + k ale codului sunt împărțite în grupuri de control care se suprapun parțial și astfel încât unitățile din reprezentarea binară a cifrei bitului indică apartenența la anumite grupuri de control. De exemplu: bitul 5 aparține grupurilor de control 1 și 3, deoarece în reprezentarea binară a numărului său 510 = ... 0001012 - prima și a treia cifră conțin una.
Dintre biții m + k ai codului, există cifre k, dintre care fiecare aparține unui singur grup de control:
Numărul de rang 1: 110 = ... 0000012 aparține numai grupului 1 de control.
Numărul 2: 210 = ... 0000102 aparține doar celui de-al doilea grup de control.
Numărul de rang 4: 410 = ... 0001002 aparține numai celui de-al treilea grup de control.
Numărul de clasare 2 k-1 aparține numai grupului k de control.
Acești biți k vom lua în considerare controlul. Restul de biți m, fiecare dintre care aparține cel puțin două grupuri de control, vor fi biți de date.
În fiecare dintre grupurile de control k vom avea o descărcare de control. În fiecare dintre biții de control, puneți o astfel de cifră (0 sau 1), astfel încât numărul total de unități din grupul său de control să fie egal.
De exemplu, codul lui Heming cu m = 7 și k = 4 este destul de comun.
Lăsați cuvântul original (cuvânt de cod fără biți de control) să fie 01101012.
Fie Pi un bit de control al lui Ni; și bitul Di - informație Noi, unde i = 1,2,3,
Concluzie. eroare a apărut în a cincea cifră. 1 0 0 0 1 1 0 0 1 0 1 Cuvânt de cod greșit. 1 0 1 0 1 0 0 0 1 0 1 Cuvântul corectat. 1 0 1 0 0 0 0 0 1 0 1 Rezultatul este chiar mai îndepărtat de cel corect decât cel primit. Corectarea codului de regula generală nu numai că nu sa îmbunătățit, ci și ar agrava problema.
Este posibil să se construiască și un astfel de cod care să dezvăluie dubluri și corecte singulare. Pentru aceasta, o altă cifră de control (biți de control dublu) trebuie să fie atribuită unui cod de auto-corectare proiectat să corecteze singurele erori. Numărul total de biți de cod în acest caz este m + k + 1. Cifra din biți de control dublu este setată astfel încât numărul total de unități din toate m + k + 1 biți de cod să fie egal. Această categorie nu este inclusă în numerotarea generală și nu este inclusă în nici un grup de control.
De exemplu, codul Heming cu m = 7 și k = 4 Lăsați cuvântul codului informativ - 0110101
Odată ce suma rezultantă nu este zero și bitul de control indică o eroare de transmisie, găsim o eroare dublă. Corecția de dublă eroare aici, desigur, este imposibilă.
Prin creșterea numărului de cipuri de verificare, ar fi posibilă construirea de coduri menite să corecteze erorile duble și să detecteze triplu etc. Cu toate acestea, metodele de construire a acestor coduri nu sunt pe deplin dezvoltate.
3. Principiul construirii codurilor Hamming.
Construcția codurilor Hamming se bazează pe principiul verificării greutății lui W (numărul de simboluri unice) în grupul de informații al blocului de coduri. Să explicăm ideea de verificare a parității cu exemplul celui mai simplu cod corespunzător, numit cod de verificare sau cod de verificare a parității (egalității). În acest cod, un bit suplimentar (un simbol de verificare a parității, numit verificare sau verificare) este adăugat la combinațiile de codare ale codului binar k-bit primar ne-redundant. Dacă numărul de caractere 1 Odd original, nume de cod-ing, descărcarea în forma de simbol pilot suplimentar număr 0, 1 simboluri Aesli este impar, cifra din simbolul formă suplimentară 1. Ca urmare, numărul total de simboluri în orice cuvânt de cod un forehand-Du- întotdeauna va fi chiar. Astfel, regula pentru formarea unui simbol de verificare este următoarea: r1 = i1 ⊕ i2 ⊕. ⊕ ik, unde i este simbolul de informare corespunzător (0 sau 1); k - numărul total al operațiunii și sub „⊕“ în continuare se referă la pomod plus 2. Este evident că adăugarea de creștere suplimentară a descărcării, un număr total de combinații posibile de două ori codul său original chislomkombinatsy primar, iar combinația razdelyaetvse condiție de paritate pe rezolvate și nerezolvate. Codul de verificare vă permite să detectați o singură eroare când primiți o combinație de coduri, deoarece o astfel de eroare încalcă condiția de paritate prin comutarea combinației admise într-o combinație interzisă. Criteriul corectitudinii combinației primite este egalitatea rezultatului sumării peste mod 2 a tuturor simbolurilor n din cod, inclusiv simbolul de verificare r1. În prezența unei singure erori, S presupune o valoare de 1: S = r1 ⊕ i1 ⊕ i2 ⊕. ⊕ ik = # 63730; 0 - fără eroare, # 63730; 1 este o eroare unică. n Acest cod este (k +1, k) -code sau (n, n-1) -code. Distanța minimă a codului este de două (dmin = 2) și, prin urmare, nici o eroare nu poate fi corectată. Un simplu cod de verificare a parității poate fi folosit numai pentru a detecta (dar nu corect) erorile unice. Creșterea numărului de biți de paritate suplimentare și forma Rui în conformitate cu anumite reguli simbolurilor de verificare R, egal cu 0 sau 1, poate fi îmbunătățită prin ajustarea proprietățile codului, astfel încât OAPC-Lyal nu numai detecta, dar, de asemenea, să corecteze erorile. Aceasta este baza pentru construirea codurilor Hamming. Codurile Hamming vă permit să corectați o singură eroare utilizând descrierea imediată. Pentru fiecare număr de verificare simvolovr = 3, 4, 5 ... există codul Hamming clasic marcat (n, k) = (2r-1, 2r-1 - r). (3.20), adică, e. (7.4) (15.11) (31.26) ... Pentru alte valori ale numărului de simboluri de informații k semi-chayut așa-numitele trunchiată (scurtate) coduri Hemminga.Tak pentru Codul International Telegraph MTC-2. (9,5), care este trunchiat din codul clasic Hemming (15,11), deoarece numărul de caractere din acest cod scade (este scurtat) cu 6.
Codul Hamming este folosit în unele programe de aplicații din zona de stocare a datelor, în special în RAID 2; În plus, metoda Hamming a fost folosită de mult timp în memoria de tip ECC și permite corecția on-the-fly a erorilor și a erorilor duble.
Toate materialele din secțiunea "Informatică"
Articole similare
Trimiteți-le prietenilor: