3.10 Codul Hamming
Cel mai comun cod de bloc sistematic liniar este codul Hamming. Acesta include coduri cu distanța minimă de cod dmin = 3, capabil să corecteze singurele erori.
Atunci când un cuvânt de cod este transmis pe un canal de comunicație, o singură eroare poate apărea în oricare dintre elementele sale. Numărul de astfel de situații. Astfel, în scopul de a determina unde a apărut eroarea, numărul de combinații de elemente de testare 2r nu trebuie să fie mai mic decât numărul de posibile situații de eroare în codul plus situația în care nu se produce eroarea, adică. E. Inegalitatea
Din această inegalitate urmează paritatea minimă a bitilor de verificare și de informare necesare pentru a corecta singurele erori
Pentru a calcula parametrii de bază ai codului Hamming, puteți seta numărul elementelor de verificare r. atunci lungimea cuvintelor de cod n≤2r-1 și numărul de elemente de informație kk = n -r. Relația dintre r. n și k sunt prezentate în tabelul următor (Tabelul 3.3).
O caracteristică caracteristică a matricei de verificare a codului cu dmin = 3 este aceea că coloanele sale sunt diferite combinații non-zero ale lungimii r.
Hamming a propus plasarea coloanelor matricei de verificare astfel încât coloana i a matricei și numărul de cod al combinației de coduri să corespundă reprezentării binare a numărului i. Apoi, sindromul de corectare a erorii unice este o reprezentare binară a numărului de biți în care a apărut eroarea. Pentru aceasta, biții de testare nu ar trebui să fie în partea dreaptă a cuvântului cod, ci în pozițiile ale căror numere sunt o putere de două, adică 20. 21. 22. ..., 2r-1.
De exemplu, pentru r = 3, matricea de verificare a codului Hamming are forma
Matricea de testare a codului Hamming (k, n) este compusă din rânduri și coloane n = 2r-1 și reprezintă combinații binare ale numărului i. unde i este numărul coloanei matricei de verificare (bit al combinației de cod).
De exemplu, pentru r = 2. 3. 4 matricele de verificare ale codului Hamming au forma
Sindromul care determină sistemul de ecuații de verificare a codului se găsește din ecuația u '= 0.
De exemplu, pentru r = 3, sistemul de ecuații de testare va fi după cum urmează:
Prin urmare, biții de test (sumele de control) sunt ambele
Pentru a codifica soobscheniem în kachestveui, o putere de 2. gdeine luate biți mesaj adecvat și verificarea biți cu indicii de grad 2 sunt preluate din sistemul de cod de verificare ecuații. În fiecare ecuație a sistemului există o singură sumă de control.
Exemplul 1 Codificăm mesajul m = (0 1 1 1) (4, 7) - cod Hamming.
Din sistemul de ecuații de verificare găsim sumele de control:
Astfel, cuvântul cod este secvența (0001111).
Decodarea codului Hamming are loc în conformitate cu următoarea schemă. Sindromul secvenței acceptate S = y ', unde este matricea codului de control transpus, y este vectorul recepționat este determinat. Dacă sindromul este egal cu vectorul zero, atunci se consideră că cuvântul este transmis fără erori, altfel valoarea sindromului corespunde reprezentării binare a cifrei cifrei în care a apărut eroarea. În acest caz, trebuie să modificați valoarea într-o cifră eronată, numărați cifrele de la stânga la dreapta, începând cu 1.
Exemplul 2 Mesajul este codificat (4, 7) prin codul Hamming. Se acceptă secvența y = (0011111). Decodați vectorul primit.
Determinăm sindromul vectorului adoptat:
eroarea a avut loc pe locul trei.
Corectarea erorii prin modificarea valorii în cel de-al treilea bit
(00111111) ® (0001111).
Mesajul transmis este decodificat ca
Generarea unei matrice (k, n) -Code este Hamming matricea (k x n), în care coloanele numerotate nu grade 2 formă de unitate de submatrice, iar coloanele rămase corespund codului de verificare ecuații. O astfel de matrice, în codificare, va copia biții de mesaje în poziții care nu sunt de gradul 2 și va umple alte poziții ale codului conform sistemului de calcul al cifrei de control.
Exemplul 3 Un sistem de ecuații de verificare a codului Hamming (4, 7) este după cum urmează:
În consecință, matricea generatoare a acestui cod are forma
1 Ce coduri se referă la anti-zgomot. Care sunt caracteristicile comune ale acestora?
2 De ce este introdusă redundanța în codurile anti-zgomot?
3 Care sunt clasele de coduri imunitar-zgomot?
4 Ce coduri se referă la blocarea codurilor anti-zgomot. Când ar trebui folosite?
5 Cum sunt definite operațiile adunării și multiplicării în câmpul simbolurilor binare GF (2) (operațiuni de adunare și multiplicare modulo 2)?
6 Ce coduri se numesc coduri de bloc liniar. Ce coduri au proprietatea sistematicității.
7 Ce este codificarea cu verificarea parității. Care este redundanța acestui cod? Care sunt avantajele și dezavantajele acestui cod?
8 Ce canal de transfer de informații este descris de modelul canal binar simetric.
9 Care este procedura de detectare și corectare a erorilor cu un cod iterativ. Care sunt avantajele și dezavantajele acestui cod?
10 Care sunt modalitățile de a specifica codurile blocului liniar. Care sunt părțile principale ale cuvântului de cod pentru codul sistematic liniar?
11 Care este sistemul de verificare a codului de bloc liniar?
12 Care este matricea generatoare a codului de bloc liniar? Care sunt proprietățile sale? Care este structura matricei de generatoare?
13 Cum, folosind matricea de generare, se construiește un sistem de verificare a ecuațiilor pentru un cod de bloc liniar?
14 Ce este o matrice de verificare a codului de blocare liniară? Care sunt proprietățile sale?
15 Care este structura matricei de verificare a codului blocului linear? Ce parte din matricea de verificare corespunde simbolurilor de informații și care parte este cea de verificare?
16 Cum, folosind o matrice de verificare, se construiește un sistem de ecuații de verificare a parității pentru un cod de bloc liniar?
17 Cum este descris vectorul de eroare din canalul binar? Care este sarcina de a decoda cuvântul de cod transmis?
18 Ce este un sindrom de bloc de cod? Cum este determinată?
19 Ce proprietate se caracterizează prin sindromul vectorului adoptat? În ce cazuri sindromul de cod nu detectează erori în secvența transmisă?
20 Cum detectează blocul de cod și corectează erorile cu un cod de bloc?
21 Cum se determină greutatea și distanța Hamming pentru secvențele binare?
22 Care este distanța minimă de cod a unui cod de blocare liniar Hamming? Cum este determinată?
23 Care este condiția necesară și suficientă pentru detectarea erorilor unei multiplicități dată de un cod de bloc liniar?
24 Care este condiția necesară și suficientă pentru corectarea unei erori de cod de bloc liniar a unei multiplicități date?
25 Care sunt condițiile necesare și suficiente pentru existența unui cod rezistent la zgomot?
26 Cum este definit numărul minim de simboluri de paritate pentru un cod de bloc liniar cu caracteristici specificate?
27 Cum se construiește o matrice de generare a unui cod de bloc liniar cu caracteristici date?
28 Ce coduri de bloc liniar sunt numite coduri Hamming?
29 Cum se determină numărul de simboluri de informație și paritate pentru codul Hamming.
30 Cum se generează cuvinte cod pentru codul Hamming.
31 Cum este compilată matricea de verificare a codului binar Hamming.
32 Care este semnificația sindromului când utilizați codul Hamming?
33 Cum decodează codul Hamming?
34 Cum este construit generatorul de coduri de generare Hamming?
[1] Shannon K. Lucrează pe teoria informării și a ciberneticii. - Editura M. de literatură străină, 1963.
[2] Jaglom A. Jaglom I. Probabilitate și informații - M. Nauka, 1973.
Articole similare
Trimiteți-le prietenilor: