3.10 Codul Hamming
Cel mai comun cod de bloc sistematic liniar este codul Hamming. Acesta include coduri cu o distanță 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 ≤ 2 r-1. și numărul de elemente de informație k = 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 coloane de poziționare propuse ale matricei de verificare astfel încât coloana i -lea a matricei și numărul de rang îndeplinesc reprezentarea cuvintelor de cod binar a i. Apoi, sindromul de corectare a erorii unice va fi o reprezentare binară a numărului de biți în care a apărut eroarea. Pentru acest nivel screening-ul nu ar trebui să fie în partea dreaptă a cuvântului de cod, precum și pozițiile de numere care sunt o putere de două, t. E. 20. 21. 22. ..., 2r-1.
De exemplu, pentru r = 3, matricea de verificare a codului Hamming are forma
Matricea de verificare a codului Hamming (k, n) este compusă din n = 2r-1 rânduri și coloane r și reprezintă combinații binare ale numărului i. unde i este numărul coloanei matricei de verificare (bit al combinației de cod).
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 mesajul m. ca ui, unde i nu este egal cu puterea 2. Se iau biții corespunzători ai mesajului, iar biții de testare cu indici de gradul 2 se găsesc din sistemul de verificare a codului. În fiecare ecuație a sistemului există o singură sumă de control.
Exemplul 1 Codificăm mesajul m = (0 1 1 1) (4, 7) -codul 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 este determinat, unde este matricea codului de control transpusă; y este vectorul primit. Dacă sindromul este vectorul de zero, se consideră că cuvântul transmis fără erori, altfel valoarea sindromului corespunde reprezentării binare a numărului categoria î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
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 codificarea biților de mesaje pentru a fi copiate într-o poziție de putere de 2 și de umplere alt sistem de calcul poziția codului conform cu biții de verificare.
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
Ce coduri se referă la anti-zgomot. Care sunt caracteristicile comune ale acestora?
De ce introduceți redundanța în codurile anti-zgomot?
Care sunt clasele de coduri imunitar-zgomot?
Ce coduri se referă la blocarea codurilor anti-zgomot. Când ar trebui folosite?
Cum sunt definite operațiile adunării și multiplicării în câmpul simbolurilor binare GF (2) (operații de adunare și multiplicare modulo 2)?
Ce coduri se numesc coduri de bloc liniar. Ce coduri au proprietatea sistematicității.
Ce este codificarea cu verificarea parității. Care este redundanța acestui cod? Care sunt avantajele și dezavantajele acestui cod?
Ce canal de transfer de informații este descris de modelul canal binar simetric.
Care este procedura de detectare și corectare a erorilor cu un cod iterativ. Care sunt avantajele și dezavantajele acestui cod?
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?
Ce este un sistem de ecuații de verificare a parității pentru codul blocului linear?
Care este matricea generatoare a codului blocului linear? Care sunt proprietățile sale? Care este structura matricei de generatoare?
Cum, folosind o matrice generatoare, să construim un sistem de ecuații de verificare pentru un cod de bloc liniar?
Ce este o matrice de verificare a codului de blocare liniară? Care sunt proprietățile sale?
Care este structura matricei de verificare a codului de bloc liniar? Ce parte din matricea de verificare corespunde simbolurilor de informații și care parte este cea de verificare?
Cum, folosind matricea de verificare, se construiește un sistem de ecuații de verificare a codului de bloc liniar?
Cum este descris vectorul de eroare din canalul binar? Care este sarcina de a decoda cuvântul de cod transmis?
Care este sindromul blocului de cod? Cum este determinată?
Ce proprietate se caracterizează prin sindromul vectorului adoptat? În ce cazuri sindromul de cod nu detectează erori în secvența transmisă?
Cum se detectează și se corectează erorile folosind codul de blocare liniar folosind sindromul de cod?
Cum se determină greutatea Hamming și distanța pentru secvențele binare?
Care este distanța de cod minimă a codului de blocare liniar Hamming? Cum este determinată?
Care este condiția necesară și suficientă pentru detectarea erorilor unei multiplicități dată de un cod de bloc liniar?
Care este condiția necesară și suficientă pentru corectarea unei erori de cod blocare liniară a unei multiplicități date?
Care sunt condițiile necesare și suficiente pentru existența unui cod rezistent la zgomot?
Cum este definit numărul minim de simboluri de paritate pentru un cod de bloc liniar cu caracteristici specificate?
Cum se construiește o matrice de generare a unui cod de bloc liniar cu caracteristici date?
Ce coduri de bloc liniar sunt numite coduri Hamming?
Cum se determină numărul de informații și simbolurile de verificare pentru codul Hamming.
Cum sunt construite codurile codului Hamming.
Cum se compilează matricea de verificare a codului binar Hamming.
Care este semnificația sindromului când utilizați codul Hamming?
Cum este decodarea codului Hamming?
Cum este construit generatorul de coduri Hamming generatoare?
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.
Trimiteți-le prietenilor: