Хемингов код

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

Математички, Хеминговите кодови се класа бинарни линеарни кодови. За секој цел број $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-битна порака постојат 7 можни еднобитни грешки, па 3 бита за контрола на грешка можат потенцијално да прецизираат, не само појаван на грешка туку и битот којшто ја предизвикал грешката.

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

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

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

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

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

Бројот на битови започнува од 1: бит 1, 2, 3, 4, 5, итн
Броевите на битот се запишуваат бинарно: 1, 10, 11, 100, 101, итн
Сите битни позиции кои имаат јачина два (имаат само 1 бит во бинарен облик на нивната положба)се парни битови: 1, 2, 4, 8, итн (1, 10, 100, 1000)
Сите останати бит позиции со два или повеќе бита, во бинарен облик на нивната положба, се бит податоци.
Секој бит на податоци е вклучен во единствен збоир од два или повеќе парни битови како што е одредено во бинарниот облик на нивната позиција.
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. Во принцип секој бит на парност ги покрива сите битови каде што битот е над битовите и во позицијата на парност и позицијата на битот не се нула.

Обликот на парност е неважен. Дури и парноста е едноставна од гледна точка на теоретската математика, но во пракса не постои разлика.

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

Шифриран податок за битот		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Позиција на битот		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
Парност на битна покриеност	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 за податоци), но образецот се продолжува во недоглед. Битна работа во врска со Хеминговите кодови која што може да се види од визуелниот увид е дека било кој даден бит е вклучен во единствен збир на парни битови. За да се проверат грешките треба да се проверат сите парности на битот. Образецот на грешки кој се вика синдром на грешка го идентификува битот во грешка. Ако сите битови во парноста се исправни, нема грешка. Инаку збирот на позиции на погрешни парности на битови го идентификува погрешниот бит. На пример, ако парноста на битот на позиција 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] Хемингов код

Во 1950 година, Хеминг го вовел [7,4] Хемингоиот код. Тој кодира 4 битни податоци во 7 битови со додавање на 3 парни бита. Тој може да открие и исправи едно-битни грешки. Со додавање на вкупната парност на битот, исто така може да се открие (но не и да се исправи) двојна грешка.

Конструкција 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]=[2^m − 1, 2^m−1-m, m]. Матрица за проверка на парност H, на Хеминговиот код е изработена со помош на листинг на сите колони со должина m кои се "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]

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

Кодирање

Пример

Од горе наведената матрица имаме 2 ^k=2⁴=16 кодни зборови. Во кодираните зборови на овој бинарен код можат да се дибијат од ${\vec {x}}={\vec {a}}G$ . Sо ${\vec {a}}=a_{1}a_{2}a_{3}a_{4}$ со $a_{i}$ постои во $F_{2}$ (Во поле со два елементи и тоа 0 и 1).

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

Поради тоа,

(1,0,1,1) се кодира како (1,0,1,1,0,1,0).

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

thumb|300px|Ист [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] кодот.

Конечно, може да се покаже дека минималното растојание (оддалеченост) се зголемува од, со [7,4] кодот, до 4 со [8,4] кодот. Поради тоа, кодот може да се дефинира како [8,4] Хемингов код.

Поврзано

Наводи

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

Литература

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 0-521-64298-1.
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.

Категории:Теорија на кодирање Категории:Детекција на грешки и исправка Категории:Компјутерска аритметика

[1] See Lemma 12 of

[Moon-2] 2,0 ^2,1 Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3). ISBN 978-0-471-64800-0.

[1]

[2]