Hamming (7,4) - Hamming(7,4)

Hammingův (7,4) -kód
Pojmenoval podle	Richard W. Hamming
Klasifikace
Typ	Lineární kód bloku
Délka bloku	7
Délka zprávy	4
Hodnotit	4/7 ~ 0.571
Vzdálenost	3
Velikost abecedy	2
Zápis	[7,4,3]2-kód
Vlastnosti
	perfektní kód

Grafické znázornění 4 datových bitů d₁ na d₄ a 3 paritní bity str₁ na str₃ a které paritní bity se vztahují na které datové bity

v teorie kódování, Hamming (7,4) je lineární kód pro opravu chyb který kóduje čtyři bity dat do sedmi bitů přidáním tří paritní bity. Je členem větší rodiny Hammingovy kódy, ale termín Hammingův kód často odkazuje na tento konkrétní kód, který Richard W. Hamming představen v roce 1950. V té době pracoval Hamming v Bell Telephone Laboratories a byl frustrován náchylností k chybám děrný štítek čtenář, a proto začal pracovat na kódech opravujících chyby.^[1]

Hammingův kód přidává tři další kontrolní bity na každé čtyři datové bity zprávy. Hammingova (7,4) algoritmus může opravit jakoukoli jednobitovou chybu nebo detekovat všechny jednobitové a dvoubitové chyby. Jinými slovy, minimální Hammingova vzdálenost mezi libovolnými dvěma správnými kódovými slovy je 3 a přijatá slova lze správně dekódovat, pokud jsou ve vzdálenosti nejvýše jednoho od kódového slova, které bylo odesláno odesílatelem. To znamená, že pro situace přenosového média, kde chyby série nedochází, Hammingův (7,4) kód je efektivní (protože médium by muselo být extrémně hlučné, aby bylo možné převrátit dva ze sedmi bitů).

v kvantová informace, Hamming (7,4) se používá jako základ pro Steane kód, typ Kód CSS používá kvantová korekce chyb.

Fotbalová branka

Cílem Hammingových kódů je vytvořit sadu paritní bity které se překrývají, takže jednobitová chyba v datovém bitu nebo paritní bit lze detekovat a opravit. I když lze vytvořit více přesahů, obecná metoda je uvedena v Hammingovy kódy.

Bit #	1	2	3	4	5	6	7
Přenesený bit	${ displaystyle p_ {1}}$	${ displaystyle p_ {2}}$	${ displaystyle d_ {1}}$	${ displaystyle p_ {3}}$	${ displaystyle d_ {2}}$	${ displaystyle d_ {3}}$	${ displaystyle d_ {4}}$
${ displaystyle p_ {1}}$	Ano	Ne	Ano	Ne	Ano	Ne	Ano
${ displaystyle p_ {2}}$	Ne	Ano	Ano	Ne	Ne	Ano	Ano
${ displaystyle p_ {3}}$	Ne	Ne	Ne	Ano	Ano	Ano	Ano

Tato tabulka popisuje, které paritní bity pokrývají, které přenášely bity v kódovaném slově. Například, str₂ poskytuje sudou paritu pro bity 2, 3, 6 a 7. Rovněž podrobně čte sloupec, který přenášený bit pokrývá, který paritní bit je pokryt. Například, d₁ je pokryto str₁ a str₂ ale ne str₃ Tato tabulka bude nápadně podobná matici kontroly parity (H) v další části.

Dále, pokud byly odstraněny sloupce parity ve výše uvedené tabulce

	${ displaystyle d_ {1}}$	${ displaystyle d_ {2}}$	${ displaystyle d_ {3}}$	${ displaystyle d_ {4}}$
${ displaystyle p_ {1}}$	Ano	Ano	Ne	Ano
${ displaystyle p_ {2}}$	Ano	Ne	Ano	Ano
${ displaystyle p_ {3}}$	Ne	Ano	Ano	Ano

pak podobnost s řádky 1, 2 a 4 matice generátoru kódu (G) níže bude také evidentní.

Správným výběrem paritního bitového pokrytí tedy lze detekovat a opravit všechny chyby s Hammingovou vzdáleností 1, což je důvod použití Hammingova kódu.

Hammingovy matice

Hammingovy kódy lze vypočítat v lineární algebra podmínky prostřednictvím matice protože Hammingovy kódy jsou lineární kódy. Pro účely Hammingových kódů dva Hammingovy matice lze definovat: kód matice generátoru G a matice kontroly parity H:

{ displaystyle mathbf {G ^ {T}}: = { begin {pmatrix} 1 & 1 & 0 & 1 1 & 0 & 1 & 1 1 & 0 & 0 & 0 0 & 1 & 1 & 1 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 1 end {pmatrix}}, mathbf {H}: = { begin {pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 0 & 1 & 1 & 0 & 0 & 1 & 1 0 & 0 & 0 & 1 & 1 & 1 & 1 end {pmatrix}}.}

Bitová pozice datových a paritních bitů

Jak bylo uvedeno výše, řádky 1, 2 a 4 G měli by vypadat povědomě, když mapují datové bity na své paritní bity:

str₁ kryty d₁, d₂, d₄
str₂ kryty d₁, d₃, d₄
str₃ kryty d₂, d₃, d₄

Zbývající řádky (3, 5, 6, 7) mapují data na jejich pozici v kódované podobě a v tomto řádku je pouze 1, takže se jedná o identickou kopii. Ve skutečnosti tyto čtyři řádky jsou lineárně nezávislé a tvoří matice identity (záměrně, ne náhodou).

Jak již bylo zmíněno výše, tři řady H by měl být známý. Tyto řádky se používají k výpočtu vektor syndromu na přijímajícím konci a pokud je vektorem syndromu nulový vektor (všechny nuly), pak je přijaté slovo bezchybné; pokud nenulová, pak hodnota označuje, který bit byl převrácen.

Čtyři datové bity - sestavené jako vektor str - je předem vynásoben G (tj., Gp) a vzít modulo 2, čímž se získá kódovaná hodnota, která se přenáší. Původní 4 datové bity jsou převedeny na sedm bitů (odtud název „Hamming (7,4)“) se třemi přidanými paritními bity, aby byla zajištěna rovnoměrná parita pomocí výše uvedených datových bitových pokrytí. První tabulka výše ukazuje mapování mezi každým datovým a paritním bitem do jeho konečné bitové pozice (1 až 7), ale toto může být také prezentováno v Vennův diagram. První diagram v tomto článku ukazuje tři kruhy (jeden pro každý paritní bit) a uzavírá datové bity, které každý paritní bit pokrývá. Druhý diagram (zobrazený vpravo) je identický, ale místo toho jsou bitové pozice označeny.

Pro zbytek této sekce budou jako běžící příklad použity následující 4 bity (zobrazené jako vektor sloupce):

{ displaystyle mathbf {p} = { begin {pmatrix} d_ {1} d_ {2} d_ {3} d_ {4} end {pmatrix}} = { begin { pmatrix} 1 0 1 1 konec {pmatrix}}}

Kódování kanálu

Mapování v příkladu X. Parita červeného, zeleného a modrého kruhu je rovnoměrná.

Předpokládejme, že chceme předat tato data (1011) přes hlučný komunikační kanál. Konkrétně a binární symetrický kanál což znamená, že poškození chyb neupřednostňuje ani nulu, ani jednu (způsobuje chyby symetricky). Dále se předpokládá, že všechny zdrojové vektory jsou rovnocenné. Bereme produkt G a str, se vstupy modulo 2, k určení přenášeného kódového slova X:

{ displaystyle mathbf {x} = mathbf {G} mathbf {p} = { begin {pmatrix} 1 & 1 & 0 & 1 1 & 0 & 1 & 1 1 & 0 & 0 & 0 0 & 1 & 1 & 1 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 0 a 0 pmatrix}} { begin {pmatrix} 1 0 1 1 end {pmatrix}} = { begin {pmatrix} 2 3 1 2 0 1 1 end {pmatrix}} = { begin {pmatrix} 0 1 1 0 0 1 1 end {pmatrix}}}

Tohle znamená tamto 0110011 bude vysílán místo vysílání 1011.

Programátoři, kteří se zajímají o násobení, by měli pozorovat, že každý řádek výsledku je nejméně významným bitem Počet obyvatel nastavených bitů vyplývajících z řádků a sloupců Bitové ANDed spíše než násobit.

V sousedním diagramu je sedm bitů kódovaného slova vloženo do příslušných umístění; z inspekce je zřejmé, že parita červených, zelených a modrých kruhů je sudá:

červený kruh má dvě jedničky
zelený kruh má dvě jedničky
modrý kruh má čtyři 1

Krátce se zobrazí, že pokud se během přenosu bit převrátí, bude parita dvou nebo všech tří kruhů nesprávná a chybný bit lze určit (i když jeden z paritních bitů) s vědomím, že parita všechny tři z těchto kruhů by měly být sudé.

Kontrola parity

Pokud během přenosu nedojde k žádné chybě, pak přijaté kódové slovo r je totožný s přenášeným kódovým slovem X:

{ displaystyle mathbf {r} = mathbf {x}}

Přijímač se znásobí H a r získat syndrom vektor z, který označuje, zda došlo k chybě, a pokud ano, pro který bit kódového slova. Provedení tohoto násobení (opět vstupy modulo 2):

{ displaystyle mathbf {z} = mathbf {H} mathbf {r} = { begin {pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 0 & 1 & 1 & 0 & 0 & 1 & 1 0 & 0 & 0 & 1 & 1 & 1 & 1 konec {pmatrix}} { začátek {pmatrix} 1 1 0 0 1 1 end {pmatrix}} = { begin {pmatrix} 2 4 2 end {pmatrix}} = { begin {pmatrix} 0 0 0 end {pmatrix}}}

Od syndromu z je nulový vektor, může přijímač dojít k závěru, že nedošlo k žádné chybě. Tento závěr je založen na pozorování, že když je datový vektor vynásoben G, dojde ke změně základu do vektorového podprostoru, kterým je jádro z H. Pokud se během přenosu nic neděje, r zůstane v jádře H a násobení získá nulový vektor.

Oprava chyb

Jinak předpokládejme, že singl došlo k bitové chybě. Matematicky můžeme psát

{ displaystyle mathbf {r} = mathbf {x} + mathbf {e} _ {i}}

modulo 2, kde E_i je ${ displaystyle i_ {th}}$ jednotkový vektor, tj. nulový vektor s 1 v ${ displaystyle i ^ {th}}$ , počítáno od 1.

{ displaystyle mathbf {e} _ {2} = { začátek {pmatrix} 0 1 0 0 0 0 0 konec {pmatrix}}}

Výše uvedený výraz tedy znamená jedinou bitovou chybu v ${ displaystyle i ^ {th}}$ místo.

Pokud tento vektor vynásobíme H:

{ displaystyle mathbf {Hr} = mathbf {H} left ( mathbf {x} + mathbf {e} _ {i} right) = mathbf {Hx} + mathbf {He} _ {i }}

Od té doby X jsou přenášená data, jsou bez chyb a výsledkem je produkt H a X je nula. Tím pádem

{ displaystyle mathbf {Hx} + mathbf {He} _ {i} = mathbf {0} + mathbf {He} _ {i} = mathbf {He} _ {i}}

Nyní produkt H s ${ displaystyle i ^ {th}}$ vektor standardní báze vybere tento sloupec H, víme, že k chybě dochází v místě, kde je tento sloupec H dojde.

Předpokládejme například, že jsme na bit # 5 zavedli bitovou chybu

{ displaystyle mathbf {r} = mathbf {x} + mathbf {e} _ {5} = { begin {pmatrix} 0 1 1 0 0 1 1 end {pmatrix}} + { begin {pmatrix} 0 0 0 0 1 0 0 end {pmatrix}} = { begin {pmatrix} 0 1 1 0 1 1 1 konec {pmatrix}}}

Bitová chyba na bitu 5 způsobí špatnou paritu v červených a zelených kruzích

Diagram vpravo ukazuje bitovou chybu (zobrazenou modrým textem) a vytvořenou špatnou paritu (zobrazenou červeným textem) v červených a zelených kruzích. Bitovou chybu lze zjistit výpočtem parity červených, zelených a modrých kruhů. Pokud je detekována špatná parita, pak se datový bit překrývá pouze špatná parita kruhy je bit s chybou. Ve výše uvedeném příkladu mají červené a zelené kruhy špatnou paritu, takže bit odpovídající průniku červené a zelené, ale ne modré, označuje chybný bit.

Nyní,

{ displaystyle mathbf {z} = mathbf {Hr} = { begin {pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 0 & 1 & 1 & 0 & 0 & 1 & 1 0 & 0 & 0 & 1 & 1 & 1 & 1 end {pmatrix}} { begin {pmatrix} 0 1 0 1 1 1 end {pmatrix}} = { begin {pmatrix} 3 4 3 end {pmatrix}} = { begin {pmatrix} 1 0 1 end {pmatrix}}}

což odpovídá pátému sloupci H. Použitý obecný algoritmus (vidět Hammingův kód # Obecný algoritmus ) byl ve své konstrukci záměrný, takže syndrom 101 odpovídá binární hodnotě 5, což znamená, že byl poškozený pátý bit. V bitu 5 byla tedy detekována chyba a lze ji opravit (jednoduše převrátit nebo vyvrátit jeho hodnotu):

{ displaystyle mathbf {r} _ { text {opraveno}} = { begin {pmatrix} 0 1 1 0 { overline {1}} 1 1 konec {pmatrix}} = { begin {pmatrix} 0 1 1 0 0 1 1 end {pmatrix}}}

Tato opravená přijatá hodnota skutečně nyní odpovídá vysílané hodnotě X shora.

Dekódování

Jakmile bylo zjištěno, že přijímaný vektor je bezchybný nebo opravený, pokud došlo k chybě (za předpokladu, že jsou možné pouze nulové nebo jednobitové chyby), je třeba přijímaná data dekódovat zpět do původních čtyř bitů.

Nejprve definujte matici R:

{ displaystyle mathbf {R} = { begin {pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 1 & 0 & 0 0 & 0 & 0 & 0 & 0 & 1 & 0 0 & 0 & 0 & 0 & 0 & 0 & 1 end {pmatrix}}}

Pak přijatá hodnota, str_r, je rovný Rr. Pomocí běžícího příkladu shora

} 0 0 1 1 end {pmatrix}} = { begin {pmatrix} 1 0 1 1 end {pmatrix}}}

Více bitových chyb

Bitová chyba na bitech 4 a 5 je zavedena (zobrazena modře) se špatnou paritou pouze v zeleném kruhu (zobrazena červeně)

Není obtížné ukázat, že pomocí tohoto schématu lze opravit pouze jednobitové chyby. Alternativně lze Hammingovy kódy použít k detekci jednobitových a dvojbitových chyb, pouze tím, že si všimneme, že je výsledkem H je nenulová, kdykoli došlo k chybě. V sousedním diagramu byly převráceny bity 4 a 5. Tím se získá pouze jeden kruh (zelený) s neplatnou paritou, ale chyby nelze obnovit.

Hammingovy kódy (7,4) a podobné Hammingovy kódy však nemohou rozlišovat mezi jednobitovými chybami a dvoubitovými chybami. To znamená, že dvoubitové chyby se zobrazují stejně jako jednobitové chyby. Pokud je oprava chyby provedena u dvoubitové chyby, bude výsledek nesprávný.

Podobně Hammingovy kódy nemohou detekovat ani se zotavit z libovolné tříbitové chyby; Zvažte diagram: pokud by bit v zeleném kruhu (barevně červeně) byl 1, kontrola parity vrátí nulový vektor, což naznačuje, že v kódovém slovu není žádná chyba.

Všechna kódová slova

Protože zdroj má pouze 4 bity, existuje pouze 16 možných přenášených slov. Zahrnuta je osmibitová hodnota, pokud je použit další paritní bit (vidět Hammingův (7,4) kód s dalším paritním bitem ). (Datové bity jsou zobrazeny modře; paritní bity jsou zobrazeny červeně; a extra paritní bit zobrazeny žlutě.)

Data ${ displaystyle ({ color {blue} d_ {1}}, { color {blue} d_ {2}}, { color {blue} d_ {3}}, { color {blue} d_ {4} })}$	Hamming (7,4)		Hamming (7,4) s bitem extra parity (Hamming (8,4))
	Přeneseno ${ displaystyle ({ color {red} p_ {1}}, { color {red} p_ {2}}, { color {blue} d_ {1}}, { color {red} p_ {3} }, { color {blue} d_ {2}}, { color {blue} d_ {3}}, { color {blue} d_ {4}})}$	Diagram	Přeneseno ${ displaystyle ({ color {red} p_ {1}}, { color {red} p_ {2}}, { color {blue} d_ {1}}, { color {red} p_ {3} }, { color {blue} d_ {2}}, { color {blue} d_ {3}}, { color {blue} d_ {4}}, { color {green} p_ {4}}) }$	Diagram
0000	0000000		00000000
1000	1110000		11100001
0100	1001100		10011001
1100	0111100		01111000
0010	0101010		01010101
1010	1011010		10110100
0110	1100110		11001100
1110	0010110		00101101
0001	1101001		11010010
1001	0011001		00110011
0101	0100101		01001011
1101	1010101		10101010
0011	1000011		10000111
1011	0110011		01100110
0111	0001111		00011110
1111	1111111		11111111

E₇ mříž

Hammingův (7,4) kód úzce souvisí s E₇ mříž a ve skutečnosti jej lze použít k jeho konstrukci, nebo přesněji k jeho dvojí mřížce E₇^∗ (podobná konstrukce pro E₇ používá duální kód [7,3,4]₂). Zejména převzetí množiny všech vektorů X v Z⁷ s X shodné (modulo 2) s kódovým slovem Hamminga (7,4) a změna měřítka o 1 /√2, dává mřížku E₇^∗

{ displaystyle E_ {7} ^ {*} = { tfrac {1} { sqrt {2}}} left {x in mathbb {Z} ^ {7}: x , { bmod { ,}} 2 v [7,4,3] _ {2} vpravo }.}

Toto je konkrétní případ obecnějšího vztahu mezi mřížemi a kódy. Například rozšířený (8,4) -Hammingův kód, který vzniká přidáním paritního bitu, souvisí také s E₈ mříž. ^[2]

Reference

^ "Historie Hammingových kódů". Archivovány od originál dne 25.10.2007. Citováno 2008-04-03.
^ Conway, John H.; Sloane, Neil J. A. (1998). Balení koule, mřížky a skupiny (3. vyd.). New York: Springer-Verlag. ISBN 0-387-98585-9.

externí odkazy

Programovací problém týkající se Hammingova kódu (7,4)

[1] "Historie Hammingových kódů". Archivovány od originál dne 25.10.2007. Citováno 2008-04-03.

[Conway-2] Conway, John H.; Sloane, Neil J. A. (1998). Balení koule, mřížky a skupiny (3. vyd.). New York: Springer-Verlag. ISBN 0-387-98585-9.

[1]

[2]