Codul Hamming este un cod (n, k) specificat de matricea de verificare H (n, k). având rânduri și coloane, în care coloanele H (n, k) sunt toate diferite secvențe binare nenul de lungime m (m - bit numere binare de la 1 la).
Lungimea combinației de cod a codului Hamming este.
Numărul de elemente de informații este definit ca.
Deci, codul Hamming este specificat complet de numărul m - numărul elementelor de verificare din combinația de coduri.
Cunoașterea formei matricei H (n, k). este posibil să se determine proprietățile corective ale codului Hamming (n, k). Deoarece toate coloanele matricei de verificare sunt diferite, nu există două coloane H (n, k) dependente liniar. În același timp, pentru orice număr m se pot specifica întotdeauna trei coloane ale matricei H (n, k). care sunt liniar dependente, de exemplu, coloane, care corespund numerelor 1, 2, 3. Astfel, pentru orice (n, k) - cod Hamming, dmin = 3.
Codul Hamming este unul dintre puținele exemple de cod perfect.
Într-adevăr, deoarece (n, k) - codul Hamming corectează toate erorile unice, atunci toate eșantioanele erorilor unice (și există un număr total de variante) ar trebui plasate în diferite clase adiacente, numărul cărora este de asemenea egal. Prin urmare, în plus față de clasele adiacente care conțin mostre de erori unice, nu există alții în tabela de decodificare, ceea ce confirmă perfecțiunea codului Hamming.
Pentru un număr fix, puteți construi un cod Hamming de orice lungime () prin scurtarea codului (n, k). Reducerea nu reduce distanța minimă a codului. Datorită faptului că pentru orice număr n există un cod Hamming, orice cod de grup cu corectarea unor singure erori este denumit de obicei un cod Hamming.
Exemplul 5.13. Definim parametrii codurilor Hamming de lungime naturală pentru diferite valori ale lui m. Rezultatele sunt prezentate sub forma unui tabel.
Evident, lungimea minimă a codului Hamming având o valoare practică este 3. Odată cu creșterea n, raportul crește și tinde la 1.
Exemplul 5.14. Luați în considerare codul Hamming (7.4). Matricea verificărilor acestui cod este formată din 7 numere binare de trei cifre de la 1 la 7:
Dintr-o analiză a acestei matrice arată că numărul minim de coloane dependente liniar este egal cu 3 (de exemplu 1, 2 și 3) și, prin urmare, dmin = 3.
În cazul în care coloanele matricei H (n, k) - cod Hamming este o înregistrare ordonată de m - numere binare de biți, decodificarea este efectuată mod original. Ca urmare a calculării relației de verificare pentru o combinație de cod având o singură eroare, sindromul este exact egal cu numărul elementului în care a apărut eroarea.
Într-adevăr, dacă ei conține o singură unitate în descărcarea corespunzătoare elementului de eroare, atunci înmulțind prin matricea H toate rândurile matricei H T corespunzătoare cu zero în ei. sunt convertite la zero și numai șirul corespunzător "1" în ei își păstrează forma (adică numărul de serie al elementului din înregistrarea binară) în răspuns.
Exemplul 5.15. Permiteți receptorului sistemului RCD al sistemului de transmisie de date să înregistreze combinația. Calculul sindromului dă
și anume eroarea din al patrulea element și combinația de cod a codului (7.4), care a fost transmisă, arată ca:
Prin transformări simple din codul Hamming (n, k) cu dmin = 3, se poate obține codul Hamming (n +1, k) cu dmin = 4.
Pentru a face acest lucru, un element redundant este introdus în combinația de coduri, care este rezultatul unei verificări a parității pe toate elementele combinației de coduri. Numărul de elemente de informații rămâne același.
Matricea de verificare pentru codul Hamming (n +1, k) cu dmin = 4 este obținută din matricea de verificare a codului (n, k) cu dmin = 3 prin introducerea unei linii suplimentare din unitatea (n +1).
Întrucât dimensiunea matricei de verificări ale codului cu dmin = 4 ar trebui să fie egală cu fiecare linie a matricei de verificări de cod cu dmin = 3, trebuie adăugat un element zero pentru a nu încălca verificările introduse mai devreme. Matricea de verificare pentru (n +1, k) - codul dmin = 4 are forma:
Procedura care a condus la prelungirea combinației de coduri cu o cifră cu creșterea dmin cu 1 unitate a fost numită extensia de cod (1-extensie). Alte coduri, de exemplu, codurile Reed-Solomon, pot fi supuse la stingere.
Exemplul 5.16. Construiți codul Hamming (8.4) cu dmin = 4 pe baza matricei de verificări de cod (7.4).
Prin forma matricei, putem concluziona că în codul (7.4) se efectuează 3 verificări de paritate independente.
Fiecare dintre linii definește elementele combinației de cod acoperite de un test.
Astfel, următorul sistem de relații de verificare corespunde matricei:
Pentru a obține codul (8,4) cu dmin = 4, introducem o altă verificare a tuturor elementelor combinației de cod, iar rezultatul acestei verificări este scris sub forma unui al 8-lea element suplimentar:
Această verificare corespunde unui rând suplimentar (al patrulea) din matricea H (8.4). alcătuită din opt unități. Pentru a nu perturba trei testul anterior în locul celui de al optulea element în primele trei rânduri ale matricei H (8,4), în locul celui de al optulea element, este zero aplicate. Astfel, matricea verificărilor de cod (8.4) se obține sub forma:
Definim codul dmin (8.4) într-un mod cunoscut. Din considerarea coloanelor a căror sumă a dat coloana zero în (7.4) - codul, este evident că, odată cu adăugarea rândului 4, ei au încetat să fie liniar dependenți. Acum, numărul de coloane dependente liniar ar trebui să fie echilibrat și un minim de 4, de exemplu, primele 3 coloane și ultimul. Astfel, pentru codul Hamming (8.4) obținut, dmin = 4.
Până în prezent, nu am împărțit încă elementele combinației de coduri în cele informaționale și de verificare. Cel mai rațional, aparent, se poate face după cum urmează. Este de dorit ca fiecare relație de testare să determine în mod unic elementul de verificare ca rezultat al verificării parității unui set de elemente de informație. În acest caz, vom putea determina valoarea elementului de verificare în cel mai simplu mod - soluția unei ecuații liniare cu una necunoscută. Pentru a face acest lucru, atunci când ordonați coloanele matricei H (n, k) conform ordinului, este necesar să luați elemente cu numerele 2 i. unde i variază de la 0 la m -1, deoarece aceste coloane conțin doar o unitate. Acesta din urmă mărturisește că elementele cu numerele 2 i introduc doar o singură verificare și, prin urmare, ele pot fi considerate ca verificare.
Exemplul 5.17. Determinați locația elementelor de testare pentru codul Hamming (7.4).
Prin forma matricei date în exemplul anterior, ca elemente de verificare, selectăm elementele care corespund coloanelor care conțin doar o unitate, adică prima, a doua și a patra. Prin urmare, 4 elemente de informație ale codului (7.4) ar trebui să ocupe locurile 3, 5, 6 și 7. Sistemul de relații de verificare prezentat în exemplul anterior permite determinarea valorii fiecăruia dintre elementele de verificare prin valorile elementelor de informație, adică prin valoarea elementelor de cod simplu, care trebuie codificate cu codul Hamming
Cunoscând locurile elementelor de verificare, este ușor să aducem matricea codului Hamming H (n, k) în forma canonică.
Pentru a face acest lucru, aveți nevoie de coloane cu numerele 2 i. unde, la comanda coloanelor, mutați primele coloane m în locurile în ordine descrescătoare a numerelor. În general, o astfel de permutare a coloanelor din matricea H (n, k) duce la codul echivalent (n, k). În cazul codurilor Hamming de lungime naturală, codul nu este nici măcar echivalent, dar exact același cu codul sursă.
Exemplul 5.18. Transformați matricea în forma canonică.
Vom rearanja coloanele: a 4-a în locul celui de-al 1-lea, locul 1 în locul celui de-al treilea și al treilea în locul celui de-al patrulea:
Aceasta este forma canonică a matricei. Comparând-o cu matricea originală arată că coloanele cu numerele 3, 5, 6, 7 corespund cu locurile elementelor de informație în forma canonică, iar coloanele 4, 2, 1 corespund locurilor elementelor de verificare.
În acest sens, legăturile dintre informație și elementele redundante au fost păstrate în ceea ce privește rearanjarea lor:
Matricea generatoare G (n, k) pentru codul Hamming poate fi obținută din matricea H (n, k). folosind Teorema 5.3:
Dispozitivele de codificare și decodare pentru această clasă de coduri vor fi luate în considerare în studiul codurilor ciclice.
Apreciem eficacitatea codurilor Hamming.
a) Codurile Hamming cu dmin = 3
Aceste coduri sunt folosite fie pentru a corecta eroarea multiplicității t = 1, fie pentru a garanta detectarea erorilor de multiplicitate S = 2. În consecință, probabilitatea de eroare pentru aceste cazuri într-un canal cu gruparea de erori este:
Câștigul pentru fiabilitate în comparație cu codurile simple de aceeași lungime este:
Pentru astfel de coduri sunt posibile două moduri - corectarea erorilor unice și detectarea erorilor și numai detectarea erorilor. Probabilitatea de eroare pentru aceste moduri în cazul grupării de erori este:
Câștigul pentru fiabilitate în comparație cu un cod simplu de aceeași lungime este:
Pe baza codurilor (n, n-1) cu dmin = 2 sau a codurilor Hamming cu dmin = 3 și dmin = 4, pot fi construite coduri cu proprietăți corective mai mari. În acest scop, împreună cu protecția fiecărei combinații transmise în maniera descrisă mai sus, se efectuează codificarea care protejează zgomotul de biți asemănători ai grupurilor de combinații transmise. Procesul de codificare poate fi explicat folosind Fig. 5.6.
Combinațiile de cod simplu care trebuie transmise prin sistemul de comunicații sunt înregistrate sub forma unei tabele - fiecare combinație constituie o linie separată a acestui tabel (simboluri de informare). Apoi codarea este efectuată de rânduri și coloane. În general, pot fi folosite diferite coduri pentru a codifica siruri de caractere și pentru a codifica coloanele. Elementele excesive sunt adăugate la fiecare rând (verificați pe rânduri) și la fiecare coloană (verificați pe coloane). Verificările de verificare sunt efectuate prin codificarea coloanelor compuse din elemente de șir redundante sau prin codarea șirurilor compuse din verificări ale coloanelor. Introducerea ulterioară a redundanței este efectuată pentru a proteja blocurile de informații prezentate în Fig. 5.6. Procesul de codificare este explicat în Fig. 5.7. Din blocurile de informații protejate de două verificări, se formează un paralelipiped. Bitii redundanți ai celui de-al treilea test formează un paralelipiped, separat printr-o linie îngroșată.
5 e. combinație
Ca urmare a codării iterative, se obțin coduri de grup care au următoarea proprietate importantă.
TEOREMUL 5.3. Distanța minimă de cod a codului iterativ este egală cu produsul distanțelor minime de cod, codurile care îl compun.
Într-adevăr, dacă în cazul a două verificări greutatea minimă a unui cod este egală cu cealaltă, atunci vectorul codului iterativ are cel puțin câte unul în fiecare rând și elemente din fiecare coloană și, prin urmare, nu mai puțin de unul.
Un raționament similar poate fi continuat în cazul mai multor inspecții.
Matricea generatoare a codului iterativ poate fi construită după cum urmează.
Fie GA matricea generatoare a codului folosit pentru verificarea prin rânduri, iar GB matricea generatoare a codului utilizat pentru verificarea prin coloane, atunci matricea generatoare a codului iterativ (GAB) are forma:
Înregistrarea înseamnă că matricea "G" este scrisă în matricea "GA" în matricea GA. și în loc de "0" scriem o matrice cu un zer ale cărui dimensiuni sunt egale cu dimensiunile lui GB. De exemplu, dacă utilizați (6, 5) - un cod cu verificarea parității pentru verificarea prin rânduri și coloane, atunci
Articole similare
Trimiteți-le prietenilor: