Хемингов код

У телекомуникацијама, Хемингови кодови су породица линеарних грешака и исправљених кодова, који се генералишу као Хемингов (7,4)-код, а који је измислио Ричард Хеминг 1950. године. Хемингови кодови могу да детектују и до две-битне грешке или да исправе једно-битне грешке без откривања неисправљених грешака. Насупрот томе, једноставни парни код не може да исправи грешке, и може да открије само непаран број битова у грешци. Хемингови кодови су савршени кодови, то јест, они достижу највишу могућу брзину за кодове са својом блок дужином и минималном дистанцом од 3.

Бинарни Хемингови кодови
Хемингов(7,4)-код (са $r=3$)
Именован по	Ричард Хеминг
Classification
Type	Линеарни блок код
Параметери
Дужина блока	$2^{r}-1$ где $r\geq 2$
Дужина поруке	$2^{r}-r-1$
Стопа	$1-r/(2^{r}-1)$
Растојање	$3$
Величина алфабета	2
Нотација	$\left[2^{r}-1,2^{r}-r-1,3\right]_{2}$
Својства
перфектан код

Математички, Хеминг кодови су класа бинарних линеарних кодова. За сваки цео број $r\geq 2$ постоји код блок дужине $n=2^{r}-1$ и дужином поруке $k=2^{r}-r-1$. Отуда је брзина Хеминг кодова $R=k/n=1-r/(2^{r}-1)$, што је највише могуће за кодове са дистанцом $3$ и блок дужином $2^{r}-1$. Матрица парне провере Хеминговог кода је конструисана тако да су наведене све колоне дужине $r$ које нису нуле, што значи да је двоструки Хемингов код пробушени Хадамардов код. Матрица парне провере има својство да су било које две удвојене колоне линеарно независне.

Због ограничења сувишног додавања Хемингових кодова у подацима, они могу само да открију и исправе грешке када је вредност грешке ниска. То је случај у меморији рачунара (ECC меморија), где су битне грешке изузетно ретке и Хемингови кодови су у широкој употреби. У том контексту, проширени Хемингов код, који има један екстра парни бит, често се користи. Проширени Хемингови кодови постижу Хемингову дистанцу од $4$, чиме се омогућава декодеру да направи разлику када се јави највише једна битна грешка и када се јаве две битне грешке. У том смислу, проширени Хемингови кодови за исправљање једно грешке и детектовање дупле грешке скраћено су названи SECDED.

Историја

Хеминг је радио у Bell лабораторијама 1940. године на Bel Model V рачунару, машини базираној на електромеханичком релеју са временским циклусом у секунди. Улаз је храњен на бушеним картицама, које би неминовно прочитале грешке. Током дана у недељи, посебан код би пронашао грешке и флеш светла тако да су оператери могли да решавају проблем. Током после-часовних периода и викендом, када није било оператора, машина је једноставно прелрелазила на следећи посао.

Кодови који су претходили Хеминговом коду

Један број једноставних кодова за детекцију грешке били су коришћени пре Хемингових кодова, али ниједан није био ефикасан као Хемингови кодови за исти горенаведени простор.

Парност

Парност додаје један бит који показује да ли је број од 1 битова у претходним подацима био паран или непаран. Ако се непаран број битова мења у преносу, порука ће променити парност и грешка може бити откривена у овом тренутку. (Треба имати на уму да бит који се мења може сам да буде паран!) Најчешћа конвенција је да парност вредности 1 указује да постоји непаран број у подацима, а парност вредности 0 указује да постоји паран број. Ако се још мења број битова, проверени бит ће ће важити и грешка неће бити откривена. Штавише, парност не означава који бит ће садржавати грешку, чак и када може да се детектује. Подаци морају бити у потпуности одбачени и поново емитовани од нуле. На бучним преносним медијима, успешан пренос може да траје дуго или се никада неће јавити. Међутим, иако је квалитет провере парности лош, јер се користи само један бит, овај метод резултује у најмању руку у горенаведеном делу. Осим тога, провера парности дозвољава обнову погрешног бита када је његов положај познат.

Два-из-пет код

Два-из-пет код је шема кодирања која користи пет дигита, који се састоје од тачно три 0 и две 1. Ово обезбеђује десет могућих комбинација, довољно за представљање бројева од 0 до 9. Ова шема може да открије све појединачне грешке бита и све непарне нумерисане грешке бита. Међутим, то још увек не може да води исправци ове грешке.

Понављање

Још један код је у употреби у време понављања сваког бит податка неколико пута, како би се осигурао његов пробој. На пример, ако је битни податак за слање 1, n = 3 код понављања ће послати "111". Ако три примљена бита нису идентична, дошло је до грешке. Ако је канал довољно чист, у највећем делу времена ће се само један бит променити у сваки троструки. Дакле, 001, 010, 100 и сваки одговара на 0 бит, док 110, 101, 011 и одговарају на 1 бит, као да су битови рачунати као "гласови" у односу на оригиналан бит. Код са овом способношћу реконструкције оригиналне поруке у присуству грешака је познат као код за исправљање грешака. Овај троструко понављајући код је заправо најједноставнији Хаммингов код са $m=2$, јер постоје 2 парна бита и $2^{2}-2-1=1$ бит података.

Такви кодови не могу коректно да поправе све грешке. У нашем примеру, ако канал преврне два бита и пријемник добије "001", систем ће детектовати грешку, али ће закључити да је оригинални бит био 0, што је нетачно. Ако се повећа број пута, дуплира се сваки бит на четири, и могу се открити све две-битне грешке, али не могу да се исправе (гласови "кравата"); у пет, могу да се исправе све две-битне грешке, али не и све три-битне грешке.

Осим тога, код понављања је изузетно неефикасан, смањује проток по три пута у односу на оригиналан случај, а ефикасност опада драстично како се повећа број пута сваки бит се дуплира у циљу откривања и исправљања више грешака.

Хемингови кодови

Ако се више битова за исправљање грешака укључе у поруци, и ако се ови битови могу организовати тако да различити погрешни битови дају различите резултате грешака, онда лош бит може да се идентификује. У 7-битној поруци, постоји седам могућих једно битних грешака, па три бита за контролу грешака могу потенцијално да прецизирају, не само појаву грешке, него и бит који је изазвао грешку.

Хеминг је проучавао постојеће шеме кодирања, укључујући и две од пет и генерализовао је њихов концепт. За почетак, он је развио номенклатуру за опис система, укључујући и број битних података и битова за исправљање грешке у блоку. На пример, парност садржи један бит за било коју реч података, па под претпоставком ASCII речи са 7-бита, Хеминг је ово описао као (8,7) код, са осам битова укупно, од којих су 7 подаци. Пример понављања би био (3,1), који следи исту логику. Код вредности кода други број се дели са првим, у нашем примеру понављања, 1/3.

Хеминг је такође уочио проблеме са окретањем два или више бита, и описао је то као "растојање" (после њега назавна Хемингова дистанца). Парност има дистанцу 2, и како се било која два бита окрену они ће бити невидљиви. Понављање (3,1) има дистанцу 3, како три бита треба да буду окренута у истој трострукости да би се добио неки други код без видљивих грешака. Понављање (4,1) (сваки бит се понавља четири пута) има дистанцу 4, тако да се превртања два бита може открити, али не и исправити. Када се три бита окрену у истој групи не може да се догоди ситуација у којој код исправља према погрешној кодној речи.

Хеминг је био заинтересован за два проблема одједном; повећање дистанце што је више могуће, и у исто време повећање кодне вредности што је више могуће. Током 1940-их је развио неколико шема кодирања које су драматично побољшане на постојећим кодовима. Кључ његових система је да имају преклопљене парне битове, тако да они успевају да провере један другог, као и податаке.

Општи алгоритам

Следећи општи алгоритам генерише код за исправљање једне грешке (SEC) за било који број битова.

1. Број бита почиње од 1: бит 1, 2, 3, 4, 5, итд
2. Бројеве бита се пишу бинарно: 1, 10, 11, 100, 101, итд
3. Све битне позиције које су јачине два (имају само један 1 бит у бинарном облику њиховог положаја) јесу парни битови: 1, 2, 4, 8, itd (1, 10, 100, 1000)
4. Све остале бит позиције, са два или више бита 1 у бинарном облику њихових положаја, су бит подаци.
5. Сваки бит података је укључен у јединствени скуп од 2 или више парних битова, како је одређено бинарним обликом њихове позиције.
   1. Бит парности 1 покрива све битне позиције које имају најмање значајан битни скуп: бит 1 (парност бита сама по себи), 3, 5, 7, 9, итд
   2. Бит парности 2 покрива све битне позиције које имају други најмање значајан битни скуп: бит 2 (парност бита сама по себи), 3, 6, 7, 10, 11, итд
   3. Бит парности 4 покрива све битне позиције које имају трећи најмање значајан битни скуп: битови 4-7, 12-15, 20-23, итд
   4. Бит парности 8 покрива све битне положаје који имају четврти најмање значајан битни скуп: битови 8-15, 24-31, 40-47, итд
   5. У принципу сваки бит парности покрива све битове где је бит над битовима И у позицији парности и позиције бита нису нула.

Облик парности је ирелевантан. Чак је парност једноставнија са становишта теоријске математике, али у пракси не постоји разлика.

Ово опште правило може да се визуелно прикаже на следећи начин:

Позиција бита		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
Шифровани подаци бита		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Парност битне покривености	p1	X		X		X		X		X		X		X		X		X		X
	p2		X	X			X	X			X	X			X	X			X	X
	p4				X	X	X	X					X	X	X	X					X
	p8								X	X	X	X	X	X	X	X
	p16																X	X	X	X	X

Приказано је само 20 кодираних битова (5 парност, 15 података), али образац се наставља унедоглед. Кључна ствар у вези Хемингових кодова, која може да се види из визуелног увида, јесте да је било који дати бит укључен u јединствени скуп парних битова. Да би се провериле грешке, треба да се провере све парности бита. Образац грешака, који се зове синдром грешке, идентификује бит у грешки. Ако су сви битови парности исправни, нема грешке. Иначе, збир позиција погрешних парности битова идентификује погрешан бит. На пример, ако парност бита на позицијама 1, 2 и 8 указује на грешку, тада је бит 1 +2 +8 = 11 у грешки. Ако само једна парност бита указује на грешку, парност самог бита је у грешки.

Као што може видети, ако постоји $m$ парних битова, он може да покрије битове од 1 до $2^{m}-1$. Ако одузмемо парност бита, остаје $2^{m}-m-1$ бита који могу да се користе за податке. Како $m$ варира, тако се добијају сви могуће Хемингови кодови:

Битови парности	Укупан број битова	Битови података	Име	Брзина
2	3	1	Хеминг(3,1) (Троструко понављање кода)	1/3 ≈ 0.333
3	7	4	Хеминг(7,4)	4/7 ≈ 0.571
4	15	11	Хеминг(15,11)	11/15 ≈ 0.733
5	31	26	Хеминг(31,26)	26/31 ≈ 0.839
...
$m$	$2^{m}-1$	$2^{m}-m-1$	Hamming$(2^{m}-1,2^{m}-m-1)$	$(2^{m}-m-1)/(2^{m}-1)$

Ако је, додатно, укључена укупна парност бита (бит 0), код може да открије (али не и исправи) било коју двобитну грешку, правећи SECDED код. Укупна парност показује да ли је укупан број грешака паран или непаран. Ако основни Хемингов код детектује грешку, а укупна парност покаже да постоји још већи број грешака, јавља се неисправљена 2-битна грешка.

Хемингови кодови са додатном парношћу (SECDED)

Хемингови кодови имају минималну дистанцу од 3, што значи да декодер може да открије и исправи једну грешку, али он не може да разликује двоструку битну грешку неке кодне речи из једно битне грешке другачије кодне речи. Дакле, они могу да открију дупле-битне грешке само ако се није покушало са корекцијом.

Као лек за овај недостатак, Хемингови кодови могу да се продуже помоћу екстра парног бита. На овај начин, могуће је повећати минималну дистанцу Хеминговог кода на 4, који омогућава да декодер направи разлику између једно-битних грешака и двобитних грешака. Тако декодер може да открије и исправи једну грешку и истовремено открије (али не и исправи) дуплу грешку. Ако декодер не покушава да исправи грешке, тада он може да детектује до 3 грешке.

Овако проширен Хемингов код је популаран у рачунарским меморијским системима, где је познат као SECDED ("single error correction, double error detection" – "корекција једне грешке, детекција дупле грешке"). Посебно је популаран (72,64) код, скраћени (127,120) Хемингов код плус додатних парни бит, који има исти простор као горњи (9,8) парни код.

[7,4] Хемингов код

Графички приказ 4 битних података и 3 парног бита и који парни битови с епримењују у битовима података

Године 1950, Хеминг је увео [7,4] Хемингов код. Он кодира 4 битних података у 7 битова додавањем три парна бита. Он може да открије и исправи једнобитне грешке. Са додатком укупне парности бита, такође може да открије (али не исправи) двоструке битне грешке.

Конструкција G и H

Матрица $\mathbf {G} :={\begin{pmatrix}I_{k}|-A^{T}\\\end{pmatrix}}$ се зове (Канонична) генератор матрица линеарног (n, к) кода,

и $\mathbf {H} :={\begin{pmatrix}A|I_{n-k}\\\end{pmatrix}}$ се зове матрица за проверу парности.

Ово је конструкција G i H у стандардном (или систематском) облику. Без обзира на форму, G i H за линеарне блок кодове морају да задовоље.

$\mathbf {H} \,\mathbf {G} ^{T}=\mathbf {0}$, је све нулта матрица.

После је [7,4,3]=[n,k,d]=[2^m − 1, 2^m−1-m, m]. Матрица провере парности H, Хеминговог кода је израђена помоћу листинга свих колона дужине м које су "pair-wise" независне.

Тако H је матрица чија је лева страна у свему не нулта н-торка где редослед н-торке у колонама матрице није битна. Десна страна је само (n-k) - матрица идентитета.

Тако G се може добити из H узимајући транспоновање леве стране H са идентитетом матрице к-идентитета на левој страни G.

Код генераторске матрице $\mathbf {G}$ и матрица провере парности $\mathbf {H}$ су:

$\mathbf {G} :={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}_{4,7}$

и

$\mathbf {H} :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}_{3,7}.$

Коначно, ове матрице могу да мутирају у еквивалентне несистематске кодове помоћу следећих операција:

• Пермутације колона (замене колона)
• Елементгарни ред операција (замена реда са линеарном комбинацијом редова)

Кодирање

Пример

Из горенаведене матрице имамо 2^k=2⁴=16 кодних речи. У кодне речи овог бинарног кода могу се добити од ${\vec {x}}={\vec {a}}G$. Sa ${\vec {a}}=a_{1}a_{2}a_{3}a_{4}$ са $a_{i}$ постоји у $F_{2}$ (A поље са два елемента и то 0 и 1).

Тако су кодне речи све 4-торке (К-торке).

Због тога,

(1,0,1,1) бива кодиран као (1,0,1,1,0,1,0).

[7,4] Хеминг код са додатним парним битом

Исти [7,4] горњи пример са екстра парним битом. Дијаграм са овим примером не одговара Х матрици.

[7,4] Хемингов код може се лако проширити на [8,4] код додавањем екстра парног бита на врху (7,4) кодиране речи (видети Хеминг (7,4)). Ово се може сумирати са ревидираним матрицама:

$\mathbf {G} :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}$

и

$\mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}.$

Примећује се да H није у стандардном облику. За добијање G, елементарне редне операције могу да се користе да би се добила еквивалентна матрица за H у систематском облику:

$\mathbf {H} =\left(\left.{\begin{array}{cccc}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{array}}\right|{\begin{array}{cccc}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{array}}\right)_{4,8}.$

На пример, први ред ове матрице је збир другог и трећег реда H у не-систематском облику. Када се користи систематска изградња за Хемингове горње кодове, матрица А је очигледна и систематски облик G је написан као:

$\mathbf {G} =\left(\left.{\begin{array}{cccc}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{array}}\right|{\begin{array}{cccc}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{array}}\right)_{4,8}.$

Несистематски облик G може да буде редуковани ред (коришћењем основних редних операција) да би одговарао овај матрици.

Додавањем четвртог реда ефикасно се израчунава збир свих кодних речи бита (подаци и парност) као и четврти парни бит.

На пример, 1011 је кодиран у 01100110 где су плаве цифре подаци, црвене цифре су парност из [7,4] Хеминговог кода, и зелена цифра је парност додата са [8,4] кодом. Зелена цифра чини парност у [7,4] кода.

Коначно, може се показати да се минимална дистанца (удаљеност) повећава са 3, са [7,4] кодом, до 4 са [8,4] кодом. Због тога, код се може дефинисати као [8,4] Хемингов код.

Види још

• Хемингово растојање
• Хемингов код (7,4)

Литература

• Moon, Todd K. (2005). Error Correction Coding. New Jersey: John Wiley & Sons. ISBN 978-0-471-64800-0. 
• MacKay, David J.C. (2003). Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press. ISBN 978-0-521-64298-9. 
• D.K. Bhattacharryya, S. Nandi. „An efficient class of SEC-DED-AUED codes”. 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97). стр. 410—415. doi:10.1109/ISPAN.1997.645128.