Хамингов код

Из Википедије, слободне енциклопедије
Бинарни Хамингови кодови
Hamming(7,4).svg
Хамингов(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
Својства
перфектан код

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

Математички, Хаминг кодови су класа бинарних линеарних кодова. За сваки цео број r \ge 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}, је све нулта матрица.[2]

После је [7,4,3]=[n,k,d]=[2m − 1, 2m−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]

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

Кодирање[уреди]

Пример

Из горе наведене матрице имамо 2k=24=16 кодних речи. У кодне речи овог бинарног кода могу се добити од \vec{x}=\vec{a}G . Sa \vec{a}=a_1a_2a_3a_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] Хамингов код.

Види још[уреди]

Референце[уреди]

  1. ^ See Lemma 12 of
  2. ^ а б Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3). ISBN 978-0-471-64800-0.

Литература[уреди]