Hammingův kód

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. března 2021; kontroly vyžadují 12 úprav .

Binární Hammingův kód
Hammingův kód s $(7,4)$ $r=3$
Pojmenoval podle	Richard Hamming
Typ	lineární blokový kód
Délka bloku	$2^{r}-1$
Délka zprávy	$2^{r}-r-1$
podíl	$1-{\frac {2}{2^{r}-1))$
Vzdálenost	3
Velikost abecedy	2
Označení	${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2))$
Mediální soubory na Wikimedia Commons

Hammingův kód je samokontrolující a samoopravující kód . Postaveno s odkazem na binární číselný systém .

Umožňuje opravit jednu chybu (chybu v jednom bitu slova) a najít dvojitou [1] .

Pojmenován po americkém matematikovi Richardu Hammingovi , který kód navrhl.

Historie

V polovině 40. let 20. století byl v Bellových laboratořích vytvořen počítací stroj Bell Model V. Byl to elektromechanický stroj využívající reléové bloky, jehož rychlost byla velmi nízká: jedna operace za pár sekund. Data byla do stroje zadávána pomocí děrných štítků s nespolehlivými čtecími zařízeními, takže během procesu čtení často docházelo k chybám. V pracovní dny byly k detekci a opravě nalezených chyb používány speciální kódy, přičemž obsluha se o chybě dozvěděla podle svitu kontrolek, opravila a restartovala stroj. O víkendech, kdy nebyli žádní operátoři, pokud došlo k chybě, stroj automaticky ukončí program a spustí jiný.

Hamming často pracoval o víkendech a byl čím dál tím otrávenější, když musel znovu načíst svůj program kvůli nespolehlivosti čtečky děrných štítků. Několik let hledal účinný algoritmus opravy chyb. V roce 1950 publikoval metodu kódování známou jako Hammingův kód.

Systematické kódy

Systematické kódy tvoří velkou skupinu blokových, oddělitelných kódů (ve kterých lze všechny symboly slova rozdělit na ověřovací a informační). Charakteristickým rysem systematických kódů je, že kontrolní symboly se tvoří jako výsledek lineárních logických operací s informačními symboly. Kromě toho může být jakékoli povolené kódové slovo získáno jako výsledek lineárních operací na sadě lineárně nezávislých kódových slov.

Samokontrolní kódy

Hammingovy kódy jsou samokontrolující kódy, tedy kódy, které automaticky detekují chyby při přenosu dat. K jejich sestavení stačí ke každému slovu přiřadit jednu další (řídicí) dvojkovou číslici a zvolit číslici této číslice tak, aby celkový počet jednotek v obrázku libovolného čísla byl např. lichý. Jediná chyba v libovolné číslici přenášeného slova (možná včetně kontrolní číslice) změní paritu celkového počtu jednotek. Čítače Modulo 2, počítající počet jedniček, které jsou obsaženy mezi binárními číslicemi čísla, dávají signál o přítomnosti chyb. V tomto případě není možné zjistit, na jaké pozici slova se chyba vyskytla, a proto neexistuje způsob, jak ji opravit. Chyby, které se vyskytují současně ve dvou, čtyřech atd. - v sudém počtu číslic, také zůstávají bez povšimnutí. Předpokládá se, že dvojité a ještě více vícenásobné chyby jsou nepravděpodobné.

Samoopravné kódy

Kódy, ve kterých je možná automatická oprava chyb, se nazývají samoopravné. K vytvoření samoopravného kódu určeného k opravě jednotlivých chyb nestačí jedna kontrolní číslice. Jak je patrné z následujícího, počet řídicích bitů musí být zvolen tak, aby byla splněna nerovnost nebo , kde je počet informačních binárních bitů kódového slova. Minimální hodnoty k pro dané hodnoty m, nalezené v souladu s touto nerovností, jsou uvedeny v tabulce. $k$ $2^k \geq k+m+1$ $k \geq \log_2(k+m+1)$ $m$

Rozsah m	km _
jeden	2
2-4	3
5-11	čtyři
12-26	5
27-57	6

Největší zájem je o binární blokové korekční kódy . Při použití takových kódů jsou informace přenášeny ve formě bloků stejné délky a každý blok je zakódován a dekódován nezávisle na druhém. Téměř ve všech blokových kódech lze symboly rozdělit na informační a kontrolní nebo kontrolní. Všechna slova jsou tedy rozdělena na povolená (u kterých je poměr informačních a kontrolních znaků možný) a zakázaná.

Hlavní vlastnosti samoopravných kódů:

Počet povolených a zakázaných kombinací. Pokud - počet znaků v bloku, - počet kontrolních znaků v bloku, - počet informačních znaků, pak - počet možných kombinací kódů, - počet povolených kombinací kódů, - počet zakázaných kombinací . $n$ $r$ $k$ $2^{n}$ $2^k$ ${\displaystyle 2^{n}-2^{k))$
Redundance kódu. Hodnota se nazývá redundance korekčního kódu. ${\tfrac {r}{n))$
Minimální vzdálenost kódu. Minimální kódová vzdálenost je minimální počet zdeformovaných symbolů potřebný k přechodu z jedné povolené kombinace do druhé. $d$
Počet zjištěných a opravených chyb. Pokud je počet chyb, které je kód schopen opravit, pak je to nutné a dostatečné $G$ $d\geq 2g+1$
Opravné kódy.

Plotkinova hranice udává horní hranici vzdálenosti kódu:

d\leqslant {\tfrac {n\cdot 2^{k-1}}{2^{k}-1)),

nebo:

r\geq 2\cdot (d-1)-\log _{2}d

n\geq 2\cdot d-1.

Hammingův limit nastavuje maximální možný počet povolených kombinací kódů:

2^{k}\leq {2^{n}}/\sum _{i=0}^{\tfrac {d-1}{2}}C_{n}^{i},

kde je počet kombinací prvků podle prvků. Odtud můžete získat výraz pro odhad počtu kontrolních symbolů:

C_n^i

n

i

r\geq \log _{2}\left(\sum _{i=0}^{(d-1)/2}C_{n}^{i}\right).

U hodnot je rozdíl mezi Hammingovou a Plotkinovou hranicí malý. $(d/n)\leq 0{,}3$

Varshamov-Gilbertova mez pro velké n definuje dolní mez počtu kontrolních symbolů:

r\geq \log _{2}\left(\sum _{i=0}^{d-2}C_{n-1}^{i}\right).

Všechny výše uvedené odhady poskytují představu o horní hranici při pevném a nebo dolním odhadu počtu kontrolních symbolů. $d$ $n$ $k$

Hammingův kód

Konstrukce Hammingových kódů je založena na principu kontroly počtu jednotlivých znaků na paritu: takový prvek je přidán do sekvence tak, aby počet jednotlivých znaků ve výsledné sekvenci byl sudý:

r_{1}=i_{1}\oplus i_{2}\oplus ...\oplus i_{k}.

Znaménko zde znamená přidání modulu 2 : $\oplus$

S=i_{1}\oplus i_{2}\oplus ...\oplus i_{n}\oplus r_{1}.

Pokud - pak není žádná chyba, pokud - pak jediná chyba. $S=0$ $S=1$

Takový kód se nazývá nebo . První číslo je počet prvků sekvence, druhé je počet informačních znaků. $(k+1,\ k)$ $(n,\ n-1)$

Pro každý počet kontrolních symbolů existuje klasický Hammingův kód se značkami: $r=3,\ 4,\ 5\ ...$

(n,k)=(2^{r}-1,2^{r}-1-r),

to je - .

(7,4),(15,11),(31,26)

S jinými hodnotami se získá tzv. zkrácený kód, např. mezinárodní telegrafní kód MTK-2, který má . Vyžaduje Hammingův kód, což je zkrácená verze klasiky $k$ $k = 5$ $(9,\ 5),$ $(15,\ 11).$

Vezměme si například klasický Hammingův kód . Seskupíme kontrolní symboly následovně: $(7,\ 4)$

r_{1}=i_{1}\oplus i_{2}\oplus i_{3},

r_{2}=i_{2}\oplus i_{3}\oplus i_{4},

r_{3}=i_{1}\oplus i_{2}\oplus i_{4}.

Získání kódového slova vypadá takto:

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & \\ \end{pmatrix}

\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix}

= .

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \\ \end{pmatrix}

Vstup dekodéru přijímá kódové slovo , kde jsou symboly označeny čárou, která může být v důsledku interference zkreslená. V dekodéru v režimu opravy chyb je vytvořena sekvence syndromů: $V=(i_{1}',\ i_{2}',\ i_{3}',\ i_{4}',\ r_{1}',\ r_{2}',\ r_{ 3}')$

S_{1}=r_{1}\oplus i_{1}\oplus i_{2}\oplus i_{3},

S_{2}=r_{2}\oplus i_{2}\oplus i_{3}\oplus i_{4},

S_{3}=r_{3}\oplus i_{1}\oplus i_{2}\oplus i_{4}.

$S=(S_{1},\ S_{2},\ S_{3})$ nazývaný sekvenční syndrom.

Získání syndromu vypadá takto:

\begin{pmatrix} i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \\ \end{pmatrix}

\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}

= .

{\begin{pmatrix}S_{1}&S_{2}&S_{3}\\\end{pmatrix}}

$i_1$	$i_2$	$i_3$	$i_4$	$r_{1}$	$r_{2}$	$r_3$	$i_1$	$i_2$	$i_3$	$i_4$	$r_{1}$	$r_{2}$	$r_3$
0	0	0	0	0	0	0	jeden	0	0	0	jeden	0	jeden
0	0	0	jeden	0	jeden	jeden	jeden	0	0	jeden	jeden	jeden	0
0	0	jeden	0	jeden	jeden	0	jeden	0	jeden	0	0	jeden	jeden
0	0	jeden	jeden	jeden	0	jeden	jeden	0	jeden	jeden	0	0	0
0	jeden	0	0	jeden	jeden	jeden	jeden	jeden	0	0	0	jeden	0
0	jeden	0	jeden	jeden	0	0	jeden	jeden	0	jeden	0	0	jeden
0	jeden	jeden	0	0	0	jeden	jeden	jeden	jeden	0	jeden	0	0
0	jeden	jeden	jeden	0	jeden	0	jeden	jeden	jeden	jeden	jeden	jeden	jeden

Kódová slova Hammingova kódu jsou uvedena v tabulce. $(7,\ 4)$

Syndrom naznačuje, že v sekvenci není žádné zkreslení. Každý nenulový syndrom odpovídá určitému chybovému vzoru, který je opraven ve fázi dekódování. $(0,0,0)$

Syndrom	001	010	011	100	101	110	111
Chyba konfigurace	0000001	0000010	0001000	0000100	1000000	0010000	0100000
Chyba symbolu	$r_3$	$r_{2}$	$i_4$	$r_{1}$	$i_1$	$i_3$	$i_2$

U kódu v tabulce vpravo jsou uvedeny nenulové syndromy a jim odpovídající chybové konfigurace (pro tvar: ). $(7,4)$ $i_1$ $i_2$ $i_3$ $i_4$ $r_{1}$ $r_{2}$ $r_3$

Kódovací algoritmus

Předpokládejme, že potřebujeme vygenerovat Hammingův kód pro nějaké informační kódové slovo. Vezměme si jako příklad 15bitové kódové slovo, ačkoliv je algoritmus vhodný pro kódová slova libovolné délky. V níže uvedené tabulce jsou na prvním řádku uvedena čísla pozic v kódovém slově, na druhém řádku je označení bitu a na třetím řádku jsou uvedeny hodnoty bitů. $x_{1}\tečky \ x_{15},$

jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct
x 1	x2 _	x 3	x4 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	x 12	x 13	x 14	x 15
jeden	0	0	jeden	0	0	jeden	0	jeden	jeden	jeden	0	0	0	jeden

Vložme řídicí bity do informačního slova tak, že jejich poziční čísla jsou celočíselné mocniny dvou: 1, 2, 4, 8, 16 ... Získáme 20bitové slovo s 15 informačními a 5 řídicími bity. Zpočátku jsou řídicí bity nastaveny na nulu. Na obrázku jsou kontrolní bity zvýrazněny růžově. ${\displaystyle r_{0}\tečky \ r_{4))$

jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16	17	osmnáct	19	dvacet
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
0	0	jeden	0	0	0	jeden	0	0	0	jeden	0	jeden	jeden	jeden	0	0	0	0	jeden

Obecně je počet řídicích bitů v kódovém slově roven binárnímu logaritmu čísla o jednu větší, než je počet bitů v kódovém slově (včetně řídicích bitů); logaritmus se zaokrouhlí nahoru. Například 1bitové informační slovo vyžaduje dva kontrolní bity, 2-, 3- nebo 4bitové informační slovo vyžaduje tři, 5...11bitové informační slovo vyžaduje čtyři, 12...26- bitové informační slovo vyžaduje pět a tak dále.

Do tabulky přidáme 5 řádků (podle počtu řídicích bitů), do kterých umístíme transformační matici. Každý řádek bude odpovídat jednomu řídicímu bitu (nulový řídicí bit je horní řádek, čtvrtý je dolní), každý sloupec bude odpovídat jednomu bitu kódovaného slova. Do každého sloupce transformační matice umístíme binární číslo tohoto sloupce a pořadí bitů se obrátí - nejméně významný bit bude umístěn v horním řádku, nejvýznamnější - v dolní. Například třetí sloupec matice bude obsahovat čísla 11000, což odpovídá binárnímu vyjádření čísla tři: 00011.

jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16	17	osmnáct	19	dvacet
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
0	0	jeden	0	0	0	jeden	0	0	0	jeden	0	jeden	jeden	jeden	0	0	0	0	jeden
jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	r0 _
0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	r1 _
0	0	0	jeden	jeden	jeden	jeden	0	0	0	0	jeden	jeden	jeden	jeden	0	0	0	0	jeden	r2 _
0	0	0	0	0	0	0	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	0	0	0	0	0	r3 _
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	jeden	jeden	jeden	jeden	jeden	r4 _

V pravé části tabulky zůstal prázdný jeden sloupec, do kterého umístíme výsledky výpočtu kontrolních bitů. Řídicí bity vypočítáme následovně: vezmeme jeden z řádků transformační matice (například ) a najdeme jeho skalární součin s kódovým slovem, to znamená, že vynásobíme odpovídající bity obou řádků a zjistíme součet produkty. Pokud se ukáže, že součet je větší než jedna, zjistíme zbytek jeho dělení 2. Jinými slovy, spočítáme, kolikrát jsou jednotky na stejných pozicích v kódovém slově a odpovídajícím řádku matice a vezměte toto číslo modulo 2. $r_{0}$

Pokud tento proces popíšeme z hlediska maticové algebry, pak operace je vynásobením transformační matice maticovým sloupcem kódového slova, výsledkem je maticový sloupec řídicích bitů, který je třeba vzít modulo 2.

Například pro řádek : $r_{0}$

r_{0}

= (1 0+0 0+1 1+0 0+1 0+0 0+1 1+0 0+1 0+0 0+1 1+0 0+ 1 1+0 1+1 1+0 0+ 1 0+0 0+1 0+0 1) mod 2 = 5 mod 2 = 1.

Výsledné řídicí bity jsou vloženy do kódového slova namísto nul, které tam byly dříve. Analogicky najdeme kontrolní bity ve zbývajících řádcích. Hammingovo kódování je dokončeno. Přijaté kódové slovo je 11110010001011110001.

jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16	17	osmnáct	19	dvacet
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
jeden	jeden	jeden	jeden	0	0	jeden	0	0	0	jeden	0	jeden	jeden	jeden	jeden	0	0	0	jeden
jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	r0 _	jeden
0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	r1 _	jeden
0	0	0	jeden	jeden	jeden	jeden	0	0	0	0	jeden	jeden	jeden	jeden	0	0	0	0	jeden	r2 _	jeden
0	0	0	0	0	0	0	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	0	0	0	0	0	r3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	jeden	jeden	jeden	jeden	jeden	r4 _	jeden

Dekódovací algoritmus

Hammingův dekódovací algoritmus je naprosto identický s kódovacím algoritmem. Transformační matice odpovídajícího rozměru se vynásobí sloupcovou maticí kódového slova a každý prvek výsledné sloupcové matice se vezme modulo 2. Výsledná sloupcová matice se nazývá „matice syndromu“. Je snadné ověřit, že kódové slovo generované v souladu s algoritmem popsaným v předchozí části vždy poskytuje matici nulového syndromu.

Matice syndromu se stane nenulovou, pokud v důsledku chyby (například při přenosu slova po zašuměné komunikační lince) jeden z bitů původního slova změnil svou hodnotu. Předpokládejme například, že v kódovém slově získaném v předchozí části šestý bit změnil svou hodnotu z nuly na jednu (na obrázku je označena červeně). Pak dostaneme následující matici syndromů.

jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16	17	osmnáct	19	dvacet
r0 _	r1 _	x 1	r2 _	x2 _	x 3	x4 _	r3 _	x5 _	x6 _	x 7	x 8	x9 _	x 10	x 11	r4 _	x 12	x 13	x 14	x 15
jeden	jeden	jeden	jeden	0	jeden	jeden	0	0	0	jeden	0	jeden	jeden	jeden	jeden	0	0	0	jeden
jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	jeden	0	s0 _	0
0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	0	jeden	jeden	0	s 1	jeden
0	0	0	jeden	jeden	jeden	jeden	0	0	0	0	jeden	jeden	jeden	jeden	0	0	0	0	jeden	s2 _	jeden
0	0	0	0	0	0	0	jeden	jeden	jeden	jeden	jeden	jeden	jeden	jeden	0	0	0	0	0	s3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	jeden	jeden	jeden	jeden	jeden	s4 _	0

Všimněte si, že s jedinou chybou je matice syndromu vždy binárním záznamem (nejméně významná číslice v horním řádku) čísla pozice, ve které k chybě došlo. Ve výše uvedeném příkladu matice syndromu (01100) odpovídá binárnímu číslu 00110 nebo desítkové 6, což znamená, že k chybě došlo v šestém bitu.

Aplikace

Hammingův kód se používá v některých úložných aplikacích, zejména RAID 2 . Kromě toho se Hammingova metoda již dlouho používá v paměti ECC a umožňuje opravit jednotlivé chyby a detekovat dvojité chyby za chodu.

Viz také

Poznámky

↑ Hammingovy kódy – „Vše o Hi-Tech“ . all-ht.ru. Datum přístupu: 20. ledna 2016. Archivováno z originálu 15. ledna 2016. (neurčitý)

Literatura

Peterson W., Weldon E. Kódy pro opravu chyb: Per. z angličtiny. Moskva: Mir, 1976, 594 s.
Penin P. E., Filippov L. N. Radiotechnické systémy přenosu informací. Moskva: Rádio a komunikace, 1984, 256 s.
Blahut R. Teorie a praxe chybových kontrolních kódů. Za. z angličtiny. M.: Mir, 1986, 576 s.