Хамингов код

Од Википедија — слободната енциклопедија
Прејди на прегледникот Прејди на пребарувањето

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

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

Поради ограничувањата на дополнително додадени Хамингови кодови во податоците, тие можат само да откријат и исправат грешки кога вредноста на грешката е многу мала. Тоа е случај во меморијијата на компјутерите (ECC меморија), каде што битните се исклучително ретки и Хаминговите кодови се во широка употреба. Во тој контекст, проширениот Хамингов код, кој има едан екстра парни бит, често се користи. Проширените Хамингови кодови постигнуваат Хамингово расстојание од , со што се овозможува на декодерот да направи разлика кога ќе се јави најмногу една битна грешка и кога ќе се јави дво битна грешка. Во таа смисла, проширените Хамингови кодови за исправување едно грешка и детектирвање двојна грешка скратено се нареченит 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 бит, овие битови да се сметаат како "гласови" во однос на оригиналниот бит. Код со оваа способност за реконструкција на оригиналната порака во присуство на грешка е познат како код за исправање на грешка. Овај тројно повторувачки код воедно е наједноставниот Хамингов код со , затоа што постоат 2 парни бита и бит податоци.

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

Како што може да се види, ако постојат парни битови, тој може да покрива битови од 1 до . Ако ја одземеме парноста на битот, останува на битот кој можат да се користат за податоци. Како што варира , така се добиваат сите Хамингови кодови:

Битови на парност Вкупен број битови Бидови податоци Име Брзина
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
...
Hamming

Ако е, дополнително, вклучена вкупна парност на битот (бит 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[уреди | уреди извор]

Матрица се вика (Канонична) генератор матрица на линеарниот (n, к) код,

и се вика матрица за проверка на парност.

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

, е цела нулта матрица. [2]

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

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

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

Кај генераторска матрица и матрица за проверка на парност се:

и

Конечно, овие матрици можат да мутираат во еквивалентни несистематски кодови со помош на следните операции:[2]

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

Кодирање[уреди | уреди извор]

Пример

Од горе наведената матрица имаме 2 k=24=16 кодни зборови. Во кодираните зборови на овој бинарен код можат да се дибијат од . Sо со постои во (Во поле со два елементи и тоа 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)). Ово може да се сумира со проверена матрица:

и

Се приметува дека H не е во стандарден облик. За да се добие G, елементарните редни операции можат да се користат за да се добие еквивалентна матрица за H во систематски облик:

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

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

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

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

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

Види повеќе[уреди | уреди извор]

Референци[уреди | уреди извор]

  1. See Lemma 12 of
  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.

Литература[уреди | уреди извор]

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