Хемингови кодови — семејство на линеарни грешки и исправени кодови во телекомуникациите кои се воопштуваат како Хемингов (7,4)-код, а кои ги измислил Ричард Хеминг во 1950 г. Хеминговите кодови можат да пронаоѓаат двобитни грешки или да исправат едно-битни грешки без откривање на неисправените грешки. Наспроти тоа, едноставниот парен код не може да исправа грешки, а може да открие само непарен број битови во грешката. Хеминговите кодови се совршени кодови, т.е. тие достигнуваат највисока можна брзина за кодови со своја блокова должина и минимално растојание од 3.See Lemma 12 of
Математички, Хеминговите кодови се класа двоични линеарни кодови. За секој цел број постои код блок со должина и должина на пораката . Одтука брзината на Хеминговите кодови е , што е најголема можна за кодови со растојание и должина на блокот . Матрицата за парна проверка на Хеминговиот код е конструирана така што се наведени сите колони со должина кој не се нула, што значи дека двојниот Хемингов код е пробиен Хадамардов код. Матрицата за парна проверка има својство да било кои две удвоени колони се линеарно независни.
Поради ограничувањата на дополнително додадени Хемингови кодови во податоците, тие можат само да откријат и исправат грешки кога вредноста на грешката е многу мала. Тоа е случај во меморијијата на сметачите (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, 2, 3, 4, 5, итн Броевите на битот се запишуваат двоично: 1, 10, 11, 100, 101, итн Сите битни позиции кои имаат јачина два (имаат само 1 бит во двоичен облик на нивната положба)се парни битови: 1, 2, 4, 8, итн (1, 10, 100, 1000) Сите останати бит позиции со два или повеќе бита, во двоичен облик на нивната положба, се бит податоци. Секој бит на податоци е вклучен во единствен збоир од два или повеќе парни битови како што е одредено во двоичниот облик на нивната положба. Бит со парност 1 ги покрива сите битни позиции кои имаат најмалку значаен битен збир: бит 1 (парност на битот сама по себе), 3, 5, 7, 9, итн Бит со парност 2 ги покрива сите битни позиции кои имаат втор најмалку значаен битен збир: бит 2 (парност на битот сама по себе), 3, 6, 7, 10, 11, итн Бит со парност 4 ги покрива сите битни позиции кои имаат трет најмалку значаен битен збир: битови 4-7, 12-15, 20-23, итн Бит со парност 8 ги покрива сите битни позиции кои имаат четврт најмалку значаен битен збир: битови 8-15, 24-31, 40-47, итн Во принцип секој бит на парност ги покрива сите битови каде што битот е над битовите и во положбата на парност и положбата на битот не се нула.
Обликот на парност е неважен. Дури и парноста е едноставна од гледна точка на теоретската математика, но во пракса не постои разлика.
Ова опшсто правило може визуелно да се прикаже на следниов начин:
{| class="wikitable" style="text-align:center;" |- !colspan="2"| Положба на битот ! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16 !! 17 !! 18 !! 19 !! 20 |rowspan="7"| ... |- !colspan="2"| Шифриран податок за битот !style="background-color: #90FF90;"| p1 !style="background-color: #90FF90;"| p2 !! d1 !style="background-color: #90FF90;"| p4 !! d2 !! d3 !! d4 !style="background-color: #90FF90;"| p8 !! d5 !! d6 !! d7 !! d8 !! d9 !! d10 !! d11 !style="background-color: #90FF90;"| p16 !! d12 !! d13 !! d14 !! d15 |- !rowspan="5"|Парност на битнапокриеност !style="background-color: #90FF90;"| p1 | X || || X || || X || || X || || X || || X || || X || || X || || X || || X || |- !style="background-color: #90FF90;"| p2 | || X || X || || || X || X || || || X || X || || || X || X || || || X || X || |- !style="background-color: #90FF90;"| p4 | || || || X || X || X || X || || || || || X || X || X || X || || || || || X |- !style="background-color: #90FF90;"| p8 | || || || || || || || X || X || X || X || X || X || X || X || || || || || |- !style="background-color: #90FF90;"| 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)