Cod Hamming

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 martie 2021; verificările necesită 12 modificări .

Cod binar Hamming
Cod Hamming cu $(7,4)$ $r=3$
Numit după	Richard Hamming
Tip de	cod de bloc liniar
Lungimea blocului	$2^{r}-1$
Lungimea mesajului	$2^{r}-r-1$
acțiune	$1-{\frac {2}{2^{r}-1))$
Distanţă	3
Dimensiunea alfabetului	2
Desemnare	$[2^{r}-1,2^{r}-r-1,3]_{2}$
Fișiere media la Wikimedia Commons

Codul Hamming este un cod de auto-verificare și auto-corectare . Construit cu referire la sistemul de numere binar .

Vă permite să corectați o singură eroare (o eroare într-un bit dintr-un cuvânt) și să găsiți un dublu [1] .

Numit după matematicianul american Richard Hamming care a propus codul.

Istorie

La mijlocul anilor 1940, mașina de calcul Bell Model V a fost creată la Bell Laboratories . Era o mașină electromecanică care folosea blocuri de relee, a căror viteză era foarte mică: o operație în câteva secunde. Datele au fost introduse în mașină folosind carduri perforate cu dispozitive de citire nesigure, așa că au apărut adesea erori în timpul procesului de citire. În zilele lucrătoare, se foloseau coduri speciale pentru detectarea și corectarea erorilor găsite, în timp ce operatorul afla despre eroare prin strălucirea luminilor, corecta și repornește mașina. În weekendurile în care nu existau operatori, dacă apare o eroare, mașina ieșea automat din program și începea altul.

Hamming a lucrat adesea în weekend și a devenit din ce în ce mai enervat deoarece a trebuit să-și reîncarce programul din cauza lipsei de încredere a cititorului de carduri perforate. De câțiva ani a căutat un algoritm eficient de corectare a erorilor. În 1950, a publicat o metodă de codificare cunoscută sub numele de codul Hamming.

Coduri sistematice

Codurile sistematice formează un grup mare de coduri bloc, separabile (în care toate simbolurile unui cuvânt pot fi împărțite în verificare și informații). O caracteristică a codurilor sistematice este că simbolurile de verificare sunt formate ca rezultat al operațiilor logice liniare asupra simbolurilor informaționale. În plus, orice cuvânt de cod permis poate fi obținut ca rezultat al operațiilor liniare pe un set de cuvinte de cod liniar independente.

Coduri de autoverificare

Codurile Hamming sunt coduri de auto-monitorizare, adică coduri care detectează automat erorile în transmiterea datelor. Pentru a le construi, este suficient să atribuiți câte o cifră binară suplimentară (de control) fiecărui cuvânt și să alegeți cifra acestei cifre, astfel încât numărul total de unități din imaginea oricărui număr să fie, de exemplu, impar. O singură eroare în orice cifră a cuvântului transmis (inclusiv, poate, în cifra de verificare) va schimba paritatea numărului total de unități. Contoarele Modulo 2, care numără numărul celor care sunt conținute printre cifrele binare ale unui număr, dau un semnal despre prezența erorilor. În acest caz, este imposibil de știut în ce poziție a cuvântului a apărut eroarea și, prin urmare, nu există nicio modalitate de a o corecta. Erorile care apar simultan în două, patru etc. - într-un număr par de cifre rămân și ele neobservate. Se presupune că erori duble și cu atât mai mult mai multe sunt puțin probabile.

Coduri auto-corecte

Codurile în care este posibilă corectarea automată a erorilor se numesc auto-corectare. Pentru a construi un cod de auto-corecție conceput pentru a corecta erori individuale, o cifră de verificare nu este suficientă. După cum se poate observa din cele ce urmează, numărul de biți de control trebuie ales astfel încât inegalitatea sau să fie satisfăcută , unde este numărul de biți binari de informații ai cuvântului de cod. Valorile minime ale lui k pentru valorile date ale lui m, găsite în conformitate cu această inegalitate, sunt date în tabel. $k$ $2^k \geq k+m+1$ $k \geq \log_2(k+m+1)$ $m$

Raza m	kmin _
unu	2
2-4	3
5-11	patru
12-26	5
27-57	6

De cel mai mare interes sunt codurile de corectare a blocurilor binare . Când se utilizează astfel de coduri, informațiile sunt transmise sub formă de blocuri de aceeași lungime, iar fiecare bloc este codificat și decodat independent de celălalt. În aproape toate codurile de bloc, simbolurile pot fi împărțite în informații și verificare sau control. Astfel, toate cuvintele sunt împărțite în permise (pentru care raportul dintre informații și caractere de verificare este posibil) și interzise.

Principalele caracteristici ale codurilor de auto-corecție:

Numărul de combinații permise și interzise. Dacă - numărul de caractere din bloc, - numărul de caractere de verificare din bloc, - numărul de caractere informative, atunci - numărul de combinații de coduri posibile, - numărul de combinații de coduri permise, - numărul de combinații interzise . $n$ $r$ $k$ $2^{n}$ $2^k$ $2^{n}-2^{k)$
Redundanța codului. Valoarea se numește redundanța codului de corecție. ${\tfrac {r}{n)}$
Distanța minimă de cod. Distanța minimă de cod este numărul minim de simboluri distorsionate necesare pentru a trece de la o combinație permisă la alta. $d$
Numărul de erori detectate și corectate. Dacă este numărul de erori pe care codul le poate remedia, atunci este necesar și suficient $g$ $d\geq 2g+1$
Codurile corective.

Limita Plotkin oferă o limită superioară a distanței codului:

d\leqslant {\tfrac {n\cdot 2^{k-1}}{2^{k}-1)),

r\geq 2\cdot (d-1)-\log _{2}d

n\geq 2\cdot d-1.

Limita Hamming stabilește numărul maxim posibil de combinații de coduri permise:

2^{k}\leq {2^{n}}/\sum _{i=0}^{\tfrac {d-1}{2}}C_{n}^{i},

unde este numărul de combinații de elemente pe elemente. De aici puteți obține o expresie pentru estimarea numărului de simboluri de cec:

C_n^i

n

i

r\geq \log _{2}\left(\sum _{i=0}^{(d-1)/2}C_{n}^{i}\right).

Pentru valorile , diferența dintre limita Hamming și limita Plotkin este mică. $(d/n)\leq 0{,}3$

Limita Varshamov-Gilbert pentru n mare definește o limită inferioară a numărului de simboluri de verificare:

r\geq \log _{2}\left(\sum _{i=0}^{d-2}C_{n-1}^{i}\right).

Toate estimările de mai sus oferă o idee despre limita superioară la fix și /sau o estimare inferioară a numărului de simboluri de cec. $d$ $n$ $k$

Cod Hamming

Construcția codurilor Hamming se bazează pe principiul verificării numărului de caractere individuale pentru paritate: un astfel de element este adăugat secvenței astfel încât numărul de caractere individuale din secvența rezultată să fie egal:

r_{1}=i_{1}\oplus i_{2}\oplus ...\oplus i_{k}.

Semnul aici înseamnă adăugare modulo 2 : $\oplus$

S=i_{1}\oplus i_{2}\oplus ...\oplus i_{n}\oplus r_{1}.

Dacă - atunci nu există nicio eroare, dacă - atunci o singură eroare. $S=0$ $S=1$

Un astfel de cod se numește sau . Primul număr este numărul de elemente de secvență, al doilea este numărul de simboluri de informații. $(k+1,\k)$ $(n,\n-1)$

Pentru fiecare număr de simboluri de cec , există un cod Hamming clasic cu marcaje: $r=3,\ 4,\ 5\ ...$

(n,k)=(2^{r}-1,2^{r}-1-r),

adică - .

(7,4),(15,11),(31,26)

Cu alte valori , se obține așa-numitul cod trunchiat, de exemplu, codul telegrafic internațional MTK-2, care are . Este nevoie de un cod Hamming, care este o versiune trunchiată a clasicului $k$ $k = 5$ $(9,\ 5),$ $(15,\11).$

De exemplu, luați în considerare codul Hamming clasic . Să grupăm simbolurile de verificare după cum urmează: $(7,\ 4)$

r_{1}=i_{1}\oplus i_{2}\oplus i_{3},

r_{2}=i_{2}\oplus i_{3}\oplus i_{4},

r_{3}=i_{1}\oplus i_{2}\oplus i_{4}.

Obținerea cuvântului cod arată astfel:

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & \\ \end{pmatrix}

\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix}

= .

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \\ \end{pmatrix}

Intrarea decodorului primește un cuvânt de cod , unde simbolurile sunt marcate cu o contur, care poate fi distorsionată ca urmare a interferenței. În decodor în modul de corectare a erorilor, este construită o secvență de sindroame: $V=(i_{1}',\i_{2}',\i_{3}',\i_{4}',\r_{1}',\r_{2}',\r_{ 3}')$

S_{1}=r_{1}\oplus i_{1}\oplus i_{2}\oplus i_{3},

S_{2}=r_{2}\oplus i_{2}\oplus i_{3}\oplus i_{4},

S_{3}=r_{3}\oplus i_{1}\oplus i_{2}\oplus i_{4}.

$S=(S_{1},\S_{2},\S_{3})$ numit sindromul secvenței.

Obținerea sindromului arată astfel:

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \\ \end{pmatrix}

\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}

= .

{\begin{pmatrix}S_{1}&S_{2}&S_{3}\\\end{pmatrix}}

$i_1$	$i_2$	$i_3$	$i_4$	$r_{1}$	$r_{2}$	$r_3$	$i_1$	$i_2$	$i_3$	$i_4$	$r_{1}$	$r_{2}$	$r_3$
0	0	0	0	0	0	0	unu	0	0	0	unu	0	unu
0	0	0	unu	0	unu	unu	unu	0	0	unu	unu	unu	0
0	0	unu	0	unu	unu	0	unu	0	unu	0	0	unu	unu
0	0	unu	unu	unu	0	unu	unu	0	unu	unu	0	0	0
0	unu	0	0	unu	unu	unu	unu	unu	0	0	0	unu	0
0	unu	0	unu	unu	0	0	unu	unu	0	unu	0	0	unu
0	unu	unu	0	0	0	unu	unu	unu	unu	0	unu	0	0
0	unu	unu	unu	0	unu	0	unu	unu	unu	unu	unu	unu	unu

Cuvintele cod ale codului Hamming sunt date în tabel. $(7,\ 4)$

Sindromul indică faptul că nu există nicio distorsiune în secvență. Fiecare sindrom non-zero corespunde unui anumit tipar de eroare, care este corectat în etapa de decodificare. $(0,0,0)$

Sindromul	001	010	011	100	101	110	111
Configurare eroare	0000001	0000010	0001000	0000100	1000000	0010000	0100000
Eroare de simbol	$r_3$	$r_{2}$	$i_4$	$r_{1}$	$i_1$	$i_3$	$i_2$

Pentru codul din tabelul din dreapta, sunt indicate sindroamele non-zero și configurațiile lor de eroare corespunzătoare (pentru forma: ). $(7,4)$ $i_1$ $i_2$ $i_3$ $i_4$ $r_{1}$ $r_{2}$ $r_3$

Algoritm de codificare

Să presupunem că trebuie să generăm un cod Hamming pentru un cuvânt de cod informațional. Să luăm ca exemplu un cuvânt de cod de 15 biți, deși algoritmul este potrivit pentru cuvinte de cod de orice lungime. În tabelul de mai jos, prima linie oferă numerele de poziție în cuvântul de cod, a doua linie oferă desemnarea biților, iar a treia linie oferă valorile biților. $x_{1}\dots \ x_{15},$

unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece
x 1	x2 _	x 3	x4 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	x 12	x 13	x 14	x 15
unu	0	0	unu	0	0	unu	0	unu	unu	unu	0	0	0	unu

Să inserăm biți de control în cuvântul de informații în așa fel încât numerele lor de poziție să fie puteri întregi de două: 1, 2, 4, 8, 16 ... Obținem un cuvânt de 20 de biți cu 15 informații și 5 biți de control. Inițial, biții de control sunt setați la zero. În figură, biții de control sunt evidențiați cu roz. $r_{0}\dots \r_{4)$

unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece	16	17	optsprezece	19	douăzeci
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
0	0	unu	0	0	0	unu	0	0	0	unu	0	unu	unu	unu	0	0	0	0	unu

În general, numărul de biți de control dintr-un cuvânt de cod este egal cu logaritmul binar al unui număr unu mai mare decât numărul de biți din cuvântul de cod (inclusiv biții de control); logaritmul este rotunjit. De exemplu, un cuvânt de informații de 1 biți necesită doi biți de verificare, un cuvânt de informații de 2, 3 sau 4 biți necesită trei, un cuvânt de informații de 5...11 biți necesită patru, un cuvânt de informații de 12...26 cuvântul de informare biți necesită cinci și așa mai departe.

Să adăugăm 5 rânduri la tabel (în funcție de numărul de biți de control), în care vom plasa matricea de transformare. Fiecare rând va corespunde unui bit de control (bitul de control zero este linia de sus, al patrulea este cea de jos), fiecare coloană va corespunde unui bit al cuvântului codificat. În fiecare coloană a matricei de transformare, plasăm numărul binar al acestei coloane, iar ordinea biților va fi inversată - bitul cel mai puțin semnificativ va fi plasat în linia de sus, cel mai semnificativ - în partea de jos. De exemplu, a treia coloană a matricei va conține numerele 11000, care corespund reprezentării binare a numărului trei: 00011.

unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece	16	17	optsprezece	19	douăzeci
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
0	0	unu	0	0	0	unu	0	0	0	unu	0	unu	unu	unu	0	0	0	0	unu
unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	r0 _
0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	r1 _
0	0	0	unu	unu	unu	unu	0	0	0	0	unu	unu	unu	unu	0	0	0	0	unu	r2 _
0	0	0	0	0	0	0	unu	unu	unu	unu	unu	unu	unu	unu	0	0	0	0	0	r3 _
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	unu	unu	unu	unu	unu	r4 _

În partea dreaptă a tabelului, o coloană a rămas goală, în care plasăm rezultatele calculului biților de control. Calculăm biții de control astfel: luăm unul dintre rândurile matricei de transformare (de exemplu, ) și găsim produsul scalar al acestuia cu cuvântul de cod, adică înmulțim biții corespunzători ambelor rânduri și găsim suma produse. Dacă suma s-a dovedit a fi mai mare decât unu, găsim restul împărțirii sale cu 2. Cu alte cuvinte, numărăm de câte ori există unități în aceleași poziții în cuvântul de cod și rândul corespunzător al matricei și luați acest număr modulo 2. $r_{0}$

Dacă descriem acest proces în termeni de algebră matriceală, atunci operația este o multiplicare a matricei de transformare cu coloana-matrice a cuvântului de cod, rezultând o coloană-matrice de biți de control, care trebuie luate modulo 2.

De exemplu, pentru linia : $r_{0}$

r_{0}

= (1 0+0 0+1 1+0 0+1 0+0 0+1 1+0 0+1 0+0 0+1 1+0 0+ 1 1+0 1+1 1+0 0+ 1 0+0 0+1 0+0 1) mod 2 = 5 mod 2 = 1.

Biții de control rezultați sunt inserați în cuvântul de cod în loc de zerourile care erau acolo mai devreme. Prin analogie, găsim biții de verificare în liniile rămase. Codarea Hamming este completă. Cuvântul de cod primit este 11110010001011110001.

unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece	16	17	optsprezece	19	douăzeci
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
unu	unu	unu	unu	0	0	unu	0	0	0	unu	0	unu	unu	unu	unu	0	0	0	unu
unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	r0 _	unu
0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	r1 _	unu
0	0	0	unu	unu	unu	unu	0	0	0	0	unu	unu	unu	unu	0	0	0	0	unu	r2 _	unu
0	0	0	0	0	0	0	unu	unu	unu	unu	unu	unu	unu	unu	0	0	0	0	0	r3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	unu	unu	unu	unu	unu	r4 _	unu

Algoritm de decodare

Algoritmul de decodare Hamming este absolut identic cu algoritmul de codificare. Matricea de transformare a dimensiunii corespunzătoare este înmulțită cu matricea coloanei cuvântului de cod, iar fiecare element al matricei coloanei rezultată este luat modulo 2. Matricea coloanei rezultată se numește „matricea sindromului”. Este ușor de verificat că un cuvânt de cod generat în conformitate cu algoritmul descris în secțiunea anterioară oferă întotdeauna o matrice de sindrom zero.

Matricea sindromului devine diferită de zero dacă, ca urmare a unei erori (de exemplu, la transmiterea unui cuvânt pe o linie de comunicație zgomotoasă), unul dintre biții cuvântului original și-a schimbat valoarea. De exemplu, să presupunem că în cuvântul de cod obținut în secțiunea anterioară, al șaselea bit și-a schimbat valoarea de la zero la unu (indicat cu roșu în figură). Apoi obținem următoarea matrice de sindroame.

unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece	16	17	optsprezece	19	douăzeci
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
unu	unu	unu	unu	0	unu	unu	0	0	0	unu	0	unu	unu	unu	unu	0	0	0	unu
unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	unu	0	s0 _	0
0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	0	unu	unu	0	s 1	unu
0	0	0	unu	unu	unu	unu	0	0	0	0	unu	unu	unu	unu	0	0	0	0	unu	s2 _	unu
0	0	0	0	0	0	0	unu	unu	unu	unu	unu	unu	unu	unu	0	0	0	0	0	s3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	unu	unu	unu	unu	unu	s4 _	0

Rețineți că, cu o singură eroare, matricea sindromului este întotdeauna o înregistrare binară (cea mai puțin semnificativă cifră din rândul de sus) a numărului de poziție în care a apărut eroarea. În exemplul de mai sus, matricea sindromului (01100) corespunde numărului binar 00110 sau zecimal 6, ceea ce implică faptul că eroarea a apărut în al șaselea bit.

Aplicație

Codul Hamming este folosit în unele aplicații de stocare, în special RAID 2 . În plus, metoda Hamming a fost folosită mult timp în memoria ECC și vă permite să corectați erorile individuale și să detectați erorile duble din mers.

Vezi și

Note

↑ Hamming Codes - „Totul despre Hi-Tech” . all-ht.ru. Data accesului: 20 ianuarie 2016. Arhivat din original la 15 ianuarie 2016. (nedefinit)

Literatură

Peterson W., Weldon E. Coduri de corectare a erorilor: Per. din engleza. Moscova: Mir, 1976, 594 p.
Penin P. E., Filippov L. N. Sisteme de transmitere a informațiilor de inginerie radio. Moscova: Radio și Comunicare, 1984, 256 p.
Blahut R. Teoria și practica codurilor de control al erorilor. Pe. din engleza. M.: Mir, 1986, 576 p.