3.10. Cod Hamming
Unul dintre cele mai comune coduri sistematice este codul Hamming [132].
Acestea includ, de obicei, coduri cu o distanță minimă de cod care corectează toate erorile individuale și coduri cu corectarea distanței toate cele singulare și detectarea tuturor erorilor duble. Hamming lungime cod
(r este numărul de biți de test). Din această inegalitate obținem
Formula (3.29) poate fi redusă la următoarea formă:
unde numărul de biți de informație. Această inegalitate ne permite să determinăm lungimea codului pentru un anumit număr de biți de informații. În tabel. 21 prezintă parametrii unor coduri Hamming.
Tabelul 21 (consultați scanarea)
O caracteristică caracteristică a matricei de verificare a codului c este aceea că coloanele sale sunt diferite combinații diferite de lungime. De exemplu, pentru codul (15,11), matricea de verificare poate avea următoarea formă:
Permițând coloanele care conțin o unitate, această matrice poate fi redusă la formă
Utilizarea unui astfel de cod vă permite să corectați o singură eroare sau să detectați o eroare arbitrară de multiplicitate doi.
Dacă biții de informație și de verificare ai codului sunt numerotați de la stânga la dreapta, atunci în conformitate cu matricea obținem un sistem de ecuații de testare, cu care se calculează biții de testare:
unde "biții de testare; categoriile de informații.
În cazul în care apare o singură eroare în timpul transmiterii cuvântului de cod, acele relații de verificare care includ valoarea descărcării eronate vor fi nerealizate. De exemplu, dacă eroarea a apărut în cea de-a cincea categorie de informații, ecuațiile primei și a patra nu pot fi realizate, adică sindromul este 1001 (coincide cu a cincea coloană a matricei H). Prin urmare, obținem algoritmi pentru determinarea localizării unei singure erori: localizarea coloanei matrice coincide cu sindromul calculat indică localizarea erorii. Este clar că valoarea calculată a sindromului coincide în mod necesar cu una dintre coloanele matricei, deoarece toate numerele posibile binare sunt alese ca coloane.
Hamming a propus utilizarea unui astfel de aranjament al coloanelor matricei de selectare a unui număr de coloană matrice și numărul de rang cuvânt de cod corespunde reprezentării binare a numărului în acest caz, sindromul obținut din ecuațiile paritate de verificare, este un binar combinații cu descărcare reprezentarea numerelor în care sa produs eroarea. Pentru acest nivel screening-ul nu ar trebui să fie în sfârșitul cuvântului de cod, iar numărul de poziție, care poate fi exprimată ca o putere a două astfel încât fiecare dintre ele apare numai într-una din ecuațiile paritate de verificare.
Un exemplu. Pentru următoarele, se poate alege ca o verificare următoarea matrice:
Ca biți de testare, selectăm primul, al doilea și al patrulea. Pentru a codifica mesajul 1101, este necesar să se determine biții de test din combinație. Din matrice avem
Prin urmare, mesajul codificat are forma 1010101. Să presupunem că acest al șaselea simbol primit în eroare, atunci mesajul este primit 1010111. Sindromul în acest caz, are forma. E. Reprezentarea binară a 6.
Un cod binar Hamming cu o distanță de cod este obținut prin adăugarea la codul Hamming de la un bit de testare, care este suma a doi modulo toți biți ai stratului de cod. Lungimea codului cu acest bit, din care sunt testate.
Operația de codare poate fi efectuată în două etape. La prima etapă a matricei folosind codul de cuvânt de cod I corespunzător al doilea - testul de evacuare adăugat la unul în care se înregistrează rezultatul însumare modulo doi biți ai cuvântului cod obținut în prima etapă.
Operația de decodificare constă, de asemenea, din două etape. Primul calculează sindromul corespunzător codului c pe al doilea - este verificată ultima rată de verificare. Rezultatele acestor operațiuni și concluziile corespunzătoare sunt prezentate în tabelul. 22
Tabelul 22 (consultați scanarea)
Matricea de verificare pentru codul c poate avea forma
O relație de verificare suplimentară introdusă pentru a mări distanța minimă a codului Hamming este următoarea: Luând în considerare (3.31), obținem
Sistemul de ecuații (3.31) și ultima relație pentru care ne permite să notăm matricea de verificare a codului (16, 11):
Uneori, în utilizarea practică a codului, problema este obținerea unui cod trunchiat cu o anumită distanță minimă sau 4). În acest caz, o matrice de testare este construită pentru un non-cod cu cea mai mică valoare care îndeplinește următoarele condiții:
În al doilea caz, numărul de biți de paritate ai codului este egal cu Atunci toate coloanele suplimentare ale submatricii sunt aruncate în matricea rezultată
Un exemplu. Construiți o matrice de verificare pentru codul Hamming de la biții de informații care conțin. Cea mai mică valoare care satisface inegalitatea (3.34) este 4.
Lungimea de cod este 16. Matricea pentru acest cod este dat în (3.32), într-o submatrice care cuprinde și evacuările cruce în ultima coloană pentru economii de hardware (de obicei, coloanele sunt eliminate din cele mai mari ediints număr).
Matricea de verificare a codului trunchiat (15, 10) are în acest caz forma
Când utilizați tabelul. 21 este foarte simplu să se determine pentru care din codurile Hammeig nu sunt trunchiate este necesar să se construiască o matrice de verificare pe care este construită matricea de verificare a codului trunchiat. De exemplu, dacă este necesar să se construiască o matrice de verificare pentru cod, adică un cod (63, 57), și apoi să se șterge douăzeci și șapte coloane din submatricul.
Este convenabil să găsim caracteristica de greutate a codului Hamming cu ajutorul unei funcții care ne permite să determinăm numărul de vectori de cod cu greutăți diferite [193].
În formulele (3.35), (3.36), numărul de vectori de cod cu greutatea ω este egal cu valoarea coeficienților polinomului înainte
Un exemplu. Să setăm codul Hamming o Determinați coeficienții de tranziții false. Pentru acest cod, conform formulei (3.35), avem
Prin urmare, acest cod conține un cuvânt de cod O, șapte cuvinte cu greutatea 3, șapte cuvinte cu greutatea 4 și un cuvânt de greutate 7. Aceasta înseamnă că distribuția vectorilor de lucru de-a lungul distanțelor de cod ale acestui cod este următoarea! Coeficienții tranzițiilor false
Prin urmare, al doilea cod detectează toate erorile de una, două, cinci, șase ori, 80% din triple și patru ori.