Cod Hamming (7.4)
Această intrare sau secțiune despre subiecte de matematică și telecomunicații nu menționează sursele necesare sau cei prezenți sunt insuficienți . |
Codul Hamming (7,4) este un cod Hamming care codifică 4 biți de date în 7 biți, adăugând 3 biți de paritate .
Astăzi, codul Hamming se referă la un cod specific (7,4) creat de Richard W. Hamming în 1950 în timp ce lucra ca teoretician la laboratoarele Bell Telephone din anii 1940. Hamming a inventat codul în 1950 pentru a permite corectarea erorilor în timpul transmisiilor și reduce raportul dintre resursele de calcul / timpul pierdut [1] .
Codul Hamming adaugă trei biți de control suplimentari la fiecare patru biți de mesaj. Algoritmul Hamming (7,4) poate corecta orice erori de un singur bit sau poate detecta toate erorile de un singur bit și de doi biți, dar nu le poate corecta. Aceasta înseamnă că, în situațiile în care canalul de transmisie în care erorile nu sunt în rafală (grupuri învecinate), codul Hamming (7,4) este eficient (deoarece canalul trebuie să fie foarte zgomotos pentru a avea un zgomot care schimbă 2 biți pe 7) . Cu alte cuvinte, distanța Hamming între cuvintele transmise și primite nu trebuie să fie mai mare decât una pentru a fi corectată.
Domeniul de aplicare
Scopul codului Hamming este de a crea un set de biți de paritate care se intersectează astfel încât o eroare pe un singur bit de date sau pe un singur bit de paritate să poată fi detectată și corectată.
Acest tabel descrie ce biți de paritate acoperă ce biți transmiși în mesajul codificat. De exemplu protejează biții 2, 3, 6 și 7. Este, de asemenea, ilustrat prin ce bit de paritate este acoperit un bit transmis. De exemplu este protejat de Și dar nu . Acest tabel este foarte similar cu matricea de verificare a parității ( ) în secțiunea următoare.
De asemenea, dacă coloanele bitului de paritate sunt eliminate în tabelul de mai sus
dacă luăm în considerare doar rândurile 1, 2 și 4 din matricea generatoare de cod ( ) sub similitudinea este încă evidentă.
Astfel, protejând în mod corespunzător biții, toate erorile cu distanța de Hamming 1 pot fi detectate și corectate, ceea ce este scopul codului Hamming.
Matrici Hamming
Codurile Hamming pot fi calculate în termeni de algebră liniară prin matrice, deoarece codurile Hamming sunt coduri liniare . Două matrice Hamming sunt definite pentru codurile Hamming: matricea generatoare de cod și matricea de verificare a parității :
Și
După cum sa menționat anterior, rândurile 1, 2 și 4 ale matricei sunt familiarizați prin faptul că mapează biții de date în biții lor de paritate:
- protejează , ,
- protejează , ,
- protejează , ,
Liniile rămase (3, 5, 6, 7) mapează datele la pozițiile lor în mesajul codificat și nu sunt altceva decât matricea de identitate. În realitate, aceste patru linii sunt liniar independente și formează matricea identității (prin construcție).
De asemenea, încă trei linii de sunt familiarizați. Aceste linii sunt folosite pentru a calcula vectorul sindrom la recepție și dacă vectorul sindrom este vectorul nul (toate zero-urile) atunci cuvântul primit este fără erori; dacă este diferit de zero, atunci valoarea sa indică ce bit a fost inversat.
Cei 4 biți de date - sortați într-un vector - sunt înmulțite cu (adică ) și se ia modulul 2. Cele patru biți de date originali sunt apoi convertiți în 7 biți (de unde și numele „Hamming (7,4)”) cu adăugarea a 3 biți de paritate.
Primul tabel de mai sus arată corespondența dintre fiecare biți de date și paritate și pozițiile lor finale, dar aceasta poate fi reprezentată cu o diagramă Venn . Prima diagramă arată trei cercuri (unul pentru fiecare bit de paritate) care conțin biții de date și protecția fiecărui bit de paritate. A doua diagramă (dreapta) este identică, dar poziția biților este marcată. Pentru restul articolului vom folosi biții de probă:
Codificare
Să presupunem că doriți să transmiteți aceste date pe un canal zgomotos . Să presupunem că probabilitatea ca un bit 0 să se schimbe la 1 este aceeași cu aceea că un bit 1 se schimbă la 0 (zgomot simetric). Luăm produsul lui G și p și facem modulul 2 din ele, pentru a determina mesajul care trebuie transmis x :
Apoi vom trimite 0110011
produs de mesajul original 1011
.
În diagrama din dreapta, cei 7 biți ai cuvântului codat sunt introduși în pozițiile lor respective; din observație este clar că paritatea cercurilor roșii, verzi și albastre este egală:
- cercul roșu are două 1s
- cercul verde are două 1s
- cercul albastru are patru 1s
Dacă în timpul transmisiei un bit este inversat atunci paritatea a 2 din cele 3 cercuri va fi incorectă și bitul greșit poate fi determinat (chiar dacă este un bit de paritate) folosind faptul că paritatea tuturor celor trei cercuri trebuie să fie egală.
Verificare paritate
Dacă nu apar erori în timpul transmisiei, cuvântul de cod primit este identic cu cel transmis :
Receptorul se înmulțește Și pentru a obține purtătorul sindromului , care indică dacă a apărut o eroare și dacă da pentru ce bit. Efectuând această multiplicare pentru exemplul nostru și luând modulul 2:
De la sindrom este vectorul nul, receptorul poate concluziona că nu au apărut erori. Această afirmație se bazează pe observația că atunci când un vector de date este înmulțit cu , are loc o schimbare de bază care face ca mesajul codificat să aparțină nucleului din . Dacă nu se întâmplă nimic în timpul difuzării, atunci va rămâne în nucleul iar multiplicarea va da vectorul nul.
Corectarea erorilor
În schimb, să presupunem că a apărut o eroare pe un singur bit. Matematic, poate fi scris
modulul 2, unde este al i -lea vector unitate , adică un vector nul cu un 1 în poziția i , numărând de la 1.
Deci expresia de mai sus înseamnă că a apărut o singură eroare în poziția i .
Dacă înmulțim acest vector cu :
Atâta timp cât sunt datele transmise, sunt fără erori și, prin urmare, rezultatul produsului Și este zero. Prin urmare
Produsul cu vectorul th j- a bazei extractelor din coloana de th j- . De exemplu, să presupunem că ați introdus o eroare la numărul de biți 5
Diagrama din dreapta arată cum bitul greșit (afișat în albastru) provoacă o paritate greșită (afișată cu roșu) în cercurile roșii și verzi. Bitul greșit poate fi recunoscut prin calcularea parității cercurilor roșii, verzi și albastre. Dacă se găsește o paritate greșită, bitul care se suprapune cercurilor singurului bit de paritate greșit este bitul cu eroarea. În exemplu, cercurile roșii și verzi au o paritate greșită, astfel încât bitul corespunzător intersecției cercului roșu și verde, dar nu albastru, indică bitul greșit.
Acum,
care corespunde celei de-a cincea coloane a . Mai mult, datorită construcției algoritmului, sindromul 101, care corespunde valorii 5, indică poziția în care a apărut eroarea. Deci eroarea poate fi corectată (prin negarea valorii bitului):
Această valoare primită este acum aceeași cu cea transmisă .
Decodare
Odată ce orice eroare a fost eliminată din operatorul primit, mesajul primit trebuie decodat în cei 4 biți originali.
Matricea este definită :
Valoarea primită Și
și folosind exemplul de mai sus
Erori multiple
Nu este dificil să se arate că numai erorile cu un singur bit pot fi corectate folosind această schemă. Alternativ, codul poate fi utilizat pentru a detecta o eroare simplă sau dublă, observând pur și simplu că produsul H este diferit de zero atunci când apar aceste erori. În diagrama din dreapta, biții 4 și 5 sunt inversați. Acest lucru provoacă o singură eroare de paritate în cercul verde, dar eroarea nu poate fi corectată.
De asemenea, codul Hamming (7,4) nu poate distinge între erorile pe un singur bit și erorile pe doi biți.
Toate codurile
Deoarece sursa constă din doar 4 biți, există doar 2 4 = 16 cuvinte posibile care pot fi transmise. Un al optulea bit poate fi, de asemenea, inclus pentru verificarea parității suplimentare, care permite în plus detectarea erorilor duble, dar nu corectate. (Biții de date sunt în albastru; biții de paritate sunt în roșu; bitul de paritate suplimentar în verde.)
Notă
- ^ Istoria codurilor Hamming , pe biobio.loc.edu . Adus 03-04-2008 (arhivat din original la 25 octombrie 2007) .