Hamming kód

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. március 2-án felülvizsgált verziótól ; az ellenőrzések 12 szerkesztést igényelnek .

Bináris Hamming kód
Hamming kóddal $(7,4)$ $r=3$
Valaki után elnevezve	Richard Hamming
Típusú	lineáris blokkkód
Blokk hossza	$2^{r}-1$
Az üzenet hossza	$2^{r}-r-1$
Részvény	$1-{\frac {2}{2^{r}-1))$
Távolság	3
Ábécé mérete	2
Kijelölés	${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2))$
Médiafájlok a Wikimedia Commons oldalon

A Hamming-kód egy önellenőrző és önjavító kód . A kettes számrendszerre való hivatkozással készült .

Lehetővé teszi egyetlen hiba kijavítását (a szó egy bitjében lévő hiba) és a dupla [1] megtalálását .

Richard Hamming amerikai matematikusról nevezték el, aki javasolta a kódot.

Történelem

Az 1940-es évek közepén a Bell Model V számológépet a Bell Laboratories létrehozta . Ez egy reléblokkokat használó elektromechanikus gép volt, melynek sebessége nagyon alacsony volt: egy művelet néhány másodperc alatt. Az adatok lyukkártyákkal , megbízhatatlan leolvasó eszközökkel kerültek a gépbe , így az olvasás során gyakran előfordultak hibák. Munkanapokon speciális kódok segítségével észlelték és javították a talált hibákat, miközben a kezelő a lámpák felvillanásával értesült a hibáról, javította és újraindította a gépet. Hétvégén, amikor nem volt kezelő, hiba esetén a gép automatikusan kilépett a programból és elindított egy másikat.

Hamming gyakran dolgozott hétvégén, és egyre idegesebb lett, mivel a lyukkártya-olvasó megbízhatatlansága miatt újra kellett töltenie a programját. Több éven át keresett egy hatékony hibajavító algoritmust. 1950 - ben kiadta a Hamming-kód néven ismert kódolási módszert.

Szisztematikus kódok

A szisztematikus kódok blokk, szétválasztható kódok nagy csoportját alkotják (amelyben egy szó összes szimbóluma ellenőrzésre és információra osztható). A szisztematikus kódok sajátossága, hogy az ellenőrző szimbólumok információs szimbólumokon végzett lineáris logikai műveletek eredményeként jönnek létre. Ezenkívül bármely engedélyezett kódszó megszerezhető lineárisan független kódszavak halmazán végzett lineáris műveletek eredményeként.

Önellenőrző kódok

A Hamming kódok önellenőrző kódok, vagyis olyan kódok, amelyek automatikusan észlelik az adatátvitel során fellépő hibákat. Felépítésükhöz elegendő minden szóhoz egy további (kontroll) bináris számjegyet rendelni, és ennek a számjegynek a számjegyét kiválasztani úgy, hogy bármely szám képében szereplő egységek összszáma például páratlan legyen. Egyetlen hiba az átvitt szó bármely számjegyében (beleértve az ellenőrző számjegyet is) megváltoztatja az egységek teljes számának paritását. A Modulo 2 számlálók, amelyek egy szám bináris számjegyei között számolják a számjegyek számát, jelzik a hibák jelenlétét. Ebben az esetben nem lehet tudni, hogy a szó melyik pozíciójában fordult elő a hiba, ezért nincs mód a javításra. Azok a hibák, amelyek egyszerre kettőben, négyben stb. - páros számú számjegyben fordulnak elő, szintén észrevétlenek maradnak. Feltételezzük, hogy a kettős, sőt még inkább a többszörös hiba valószínűtlen.

Önjavító kódok

Azokat a kódokat, amelyekben lehetséges az automatikus hibajavítás, önjavítónak nevezzük. Egyetlen hibák kijavítására tervezett önjavító kód felépítéséhez egy ellenőrző számjegy nem elegendő. Amint az alábbiakból látható, a vezérlőbitek számát úgy kell megválasztani, hogy az egyenlőtlenség vagy teljesüljön , ahol a kódszó információs bináris bitjeinek száma. Az ezzel az egyenlőtlenséggel összhangban talált, adott m-értékekhez tartozó k minimális értékeit a táblázat tartalmazza. $k$ $2^k \geq k+m+1$ $k \geq \log_2(k+m+1)$ $m$

Tartomány m	kmmin _
egy	2
2-4	3
5-11	négy
12-26	5
27-57	6

A legérdekesebbek a bináris blokkjavító kódok . Az ilyen kódok használatakor az információ azonos hosszúságú blokkok formájában kerül továbbításra, és mindegyik blokk kódolása és dekódolása egymástól függetlenül történik. Szinte minden blokkkódban a szimbólumok információra és ellenőrzésre vagy vezérlésre oszthatók. Így minden szó fel van osztva engedélyezettre (amelynél lehetséges az információs és ellenőrző karakterek aránya) és tiltottra.

Az önjavító kódok főbb jellemzői:

A megengedett és tiltott kombinációk száma. Ha - a blokkban lévő karakterek száma, - a blokkban lévő ellenőrző karakterek száma, - az információs karakterek száma, akkor - a lehetséges kódkombinációk száma, - a megengedett kódkombinációk száma, - a tiltott kombinációk száma . $n$ $r$ $k$ $2^{n}$ $2^k$ ${\displaystyle 2^{n}-2^{k))$
Kód redundancia. Az értéket a korrekciós kód redundanciájának nevezzük. ${\tfrac {r}{n))$
Minimális kód távolság. A minimális kódtávolság a torz szimbólumok minimális száma, amely az egyik engedélyezett kombinációból a másikba való átmenethez szükséges. $d$
Az észlelt és kijavított hibák száma. Ha az a hibák száma, amelyeket a kód képes kijavítani, akkor ez szükséges és elegendő $g$ $d\geq 2g+1$
Javító kódok.

A Plotkin -korlát megadja a kódtávolság felső korlátját:

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

vagy:

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

nál nél

n\geq 2\cdot d-1.

A Hamming-korlát beállítja a megengedett kódkombinációk maximális számát:

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

ahol az elemek elemenkénti kombinációinak száma . Innen egy kifejezést kaphat az ellenőrző szimbólumok számának becslésére:

C_n^i

n

én

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

Az értékek esetében kicsi a különbség a Hamming- és a Plotkin-korlát között. $(d/n)\leq 0{,}3$

A Varshamov-Gilbert korlát nagy n-re meghatározza az ellenőrző szimbólumok számának alsó korlátját:

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

A fenti becslések mindegyike képet ad az ellenőrző szimbólumok számának felső határáról és / vagy alsó becsléséről . $d$ $n$ $k$

Hamming kód

A Hamming-kódok felépítése azon az elven alapul, hogy az egyes karakterek számát ellenőrizzük a paritás szempontjából: egy ilyen elemet hozzáadunk a sorozathoz, hogy a kapott sorozatban az egyes karakterek száma páros legyen:

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

A jel itt a modulo 2 kiegészítést jelenti : $\oplus$

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

Ha - akkor nincs hiba, ha - akkor egyetlen hiba. $S=0$ $S=1$

Az ilyen kódot vagy hívják . Az első szám a sorozatelemek száma, a második az információs szimbólumok száma. ${\megjelenítési stílus (k+1,\ k)}$ $(n,\ n-1)$

Minden egyes számú ellenőrző szimbólumhoz tartozik egy klasszikus Hamming-kód jelölésekkel: $r=3,\ 4,\ 5\ ...$

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

vagyis - .

{\megjelenítési stílus (7,4),(15,11),(31,26)}

Más értékekkel az úgynevezett csonka kódot kapjuk, például az MTK-2 nemzetközi távírókódot, amely . Hamming kódot igényel, ami a klasszikus csonka változata $k$ $k = 5$ $(9,\ 5),$ $(15,\ 11).$

Vegyük például a klasszikus Hamming-kódot . Csoportosítsuk az ellenőrző jeleket a következőképpen: $(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}.

A kódszó lekérése így néz ki:

\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}

A dekódoló bemenete egy kódszót kap , ahol a szimbólumok egy vonallal vannak jelölve, amelyek az interferencia hatására torzulhatnak. A hibajavító módban a dekóderben szindrómasorozat épül fel: $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})$ szekvencia szindrómának nevezik.

A szindróma kialakulása így néz ki:

\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	egy	0	0	0	egy	0	egy
0	0	0	egy	0	egy	egy	egy	0	0	egy	egy	egy	0
0	0	egy	0	egy	egy	0	egy	0	egy	0	0	egy	egy
0	0	egy	egy	egy	0	egy	egy	0	egy	egy	0	0	0
0	egy	0	0	egy	egy	egy	egy	egy	0	0	0	egy	0
0	egy	0	egy	egy	0	0	egy	egy	0	egy	0	0	egy
0	egy	egy	0	0	0	egy	egy	egy	egy	0	egy	0	0
0	egy	egy	egy	0	egy	0	egy	egy	egy	egy	egy	egy	egy

A Hamming-kód kódszavait a táblázat tartalmazza. $(7,\ 4)$

A szindróma azt jelzi, hogy a sorozatban nincs torzulás. Minden nem nulla szindróma egy bizonyos hibamintának felel meg, amelyet a dekódolási szakaszban korrigálnak. $(0,0,0)$

Szindróma	001	010	011	100	101	110	111
Hiba a konfigurációban	0000001	0000010	0001000	0000100	1000000	0010000	0100000
Szimbólum hiba	$r_3$	$r_{2}$	$i_4$	$r_{1}$	$i_1$	$i_3$	$i_2$

A jobb oldali táblázatban szereplő kódnál a nullától eltérő szindrómák és a hozzájuk tartozó hibakonfigurációk vannak feltüntetve (az űrlaphoz: ). $(7,4)$ $i_1$ $i_2$ $i_3$ $i_4$ $r_{1}$ $r_{2}$ $r_3$

Kódolási algoritmus

Tegyük fel, hogy Hamming-kódot kell generálnunk valamilyen információs kódszóhoz. Vegyünk példának egy 15 bites kódszót, bár az algoritmus bármilyen hosszúságú kódszóra alkalmas. Az alábbi táblázatban az első sor a kódszó pozíciószámait, a második a bitmegnevezést, a harmadik pedig a bitértékeket adja meg. $x_{1}\dots \ x_{15},$

egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt
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
egy	0	0	egy	0	0	egy	0	egy	egy	egy	0	0	0	egy

Szúrjunk be vezérlőbiteket az információs szóba úgy, hogy pozíciószámuk kettő egész hatványa legyen: 1, 2, 4, 8, 16 ... Egy 20 bites szót kapunk 15 információval és 5 vezérlőbittel. Kezdetben a vezérlőbitek nullára vannak állítva. Az ábrán a vezérlőbitek rózsaszínnel vannak kiemelve. ${\displaystyle r_{0}\dots \ r_{4))$

egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt	16	17	tizennyolc	19	húsz
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	egy	0	0	0	egy	0	0	0	egy	0	egy	egy	egy	0	0	0	0	egy

Általában a kódszóban lévő vezérlőbitek száma megegyezik a kódszóban lévő bitek számánál eggyel nagyobb szám bináris logaritmusával (beleértve a vezérlőbiteket is); a logaritmust felfelé kerekítjük. Például egy 1 bites információs szóhoz két ellenőrző bit, egy 2, 3 vagy 4 bites információs szóhoz három, egy 5...11 bites információs szóhoz négy, egy 12...26 bites információs szóhoz például három. bit információs szóhoz öt kell, és így tovább.

Adjunk hozzá 5 sort a táblázathoz (a vezérlőbitek számának megfelelően), amibe elhelyezzük a transzformációs mátrixot. Minden sor egy vezérlőbitnek felel meg (a nulla vezérlőbit a felső sor, a negyedik az alsó), minden oszlop a kódolt szó egy bitjének felel meg. A transzformációs mátrix minden oszlopába ennek az oszlopnak a bináris számát helyezzük el, és a bitek sorrendje megfordul - a legkisebb jelentőségű bit a felső sorba, a legjelentősebb - az alsóba kerül. Például a mátrix harmadik oszlopa az 11000 számokat tartalmazza, ami a hármas szám bináris reprezentációjának felel meg: 00011.

egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt	16	17	tizennyolc	19	húsz
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	egy	0	0	0	egy	0	0	0	egy	0	egy	egy	egy	0	0	0	0	egy
egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	r0 _
0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	r1_ _
0	0	0	egy	egy	egy	egy	0	0	0	0	egy	egy	egy	egy	0	0	0	0	egy	r2_ _
0	0	0	0	0	0	0	egy	egy	egy	egy	egy	egy	egy	egy	0	0	0	0	0	r3 _
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	egy	egy	egy	egy	egy	r4_ _

A táblázat jobb oldalán egy oszlop üresen maradt, melybe a vezérlőbitek számításának eredményeit helyezzük el. A vezérlőbiteket a következőképpen számítjuk ki: vesszük a transzformációs mátrix egyik sorát (például ), és megkeressük annak skaláris szorzatát a kódszóval, azaz megszorozzuk mindkét sor megfelelő bitjeit, és megkeressük a transzformációs mátrix egyik sorát. Termékek. Ha az összeg egynél nagyobbnak bizonyult, akkor megkapjuk 2-vel való osztásának maradékát. Vagyis megszámoljuk, hogy hányszor vannak egységek azonos pozícióban a kódszóban és a mátrix megfelelő sorában, és vegye ezt a számot modulo 2. $r_{0}$

Ha ezt a folyamatot mátrixalgebrával írjuk le, akkor a művelet a transzformációs mátrix szorzata a kódszó mátrixoszlopával, aminek eredményeként a vezérlőbitek mátrixoszlopa jön létre, amit modulo 2-re kell venni.

Például a következő sorhoz : $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.

Az így kapott vezérlőbitek a kódszóba kerülnek a korábban ott lévő nullák helyett. Analógia útján a többi sorokban találjuk az ellenőrző biteket. A Hamming kódolás befejeződött. A kapott kódszó: 11110010001011110001.

egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt	16	17	tizennyolc	19	húsz
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
egy	egy	egy	egy	0	0	egy	0	0	0	egy	0	egy	egy	egy	egy	0	0	0	egy
egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	r0 _	egy
0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	r1_ _	egy
0	0	0	egy	egy	egy	egy	0	0	0	0	egy	egy	egy	egy	0	0	0	0	egy	r2_ _	egy
0	0	0	0	0	0	0	egy	egy	egy	egy	egy	egy	egy	egy	0	0	0	0	0	r3 _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	egy	egy	egy	egy	egy	r4_ _	egy

Dekódoló algoritmus

A Hamming dekódoló algoritmus teljesen azonos a kódoló algoritmussal. A megfelelő dimenzió transzformációs mátrixát megszorozzuk a kódszó oszlopmátrixszal, és a kapott oszlopmátrix minden elemét modulo 2-vel veszik. A kapott oszlopmátrixot "szindrómamátrixnak" nevezik. Könnyen ellenőrizhető, hogy az előző részben leírt algoritmus szerint generált kódszó mindig nulla szindrómamátrixot ad-e.

A szindrómamátrix nem nulla lesz, ha egy hiba következtében (például egy szó zajos kommunikációs vonalon való továbbításakor) az eredeti szó egyik bitje megváltoztatta az értékét. Tegyük fel például, hogy az előző részben kapott kódszóban a hatodik bit értéke nulláról egyre változott (az ábrán pirossal jelölve). Ekkor a következő szindrómák mátrixát kapjuk.

egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt	16	17	tizennyolc	19	húsz
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
egy	egy	egy	egy	0	egy	egy	0	0	0	egy	0	egy	egy	egy	egy	0	0	0	egy
egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	egy	0	s0_ _	0
0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	0	egy	egy	0	s 1	egy
0	0	0	egy	egy	egy	egy	0	0	0	0	egy	egy	egy	egy	0	0	0	0	egy	s2_ _	egy
0	0	0	0	0	0	0	egy	egy	egy	egy	egy	egy	egy	egy	0	0	0	0	0	s3_ _	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	egy	egy	egy	egy	egy	s4_ _	0

Vegye figyelembe, hogy egyetlen hiba esetén a szindrómamátrix mindig annak a pozíciószámnak a bináris rekordja (a legkevésbé jelentős számjegy a felső sorban), amelyben a hiba történt. A fenti példában a szindrómamátrix (01100) a 00110 bináris számnak vagy decimális 6-nak felel meg, ami azt jelenti, hogy a hiba a hatodik bitben történt.

Alkalmazás

Hamming kódot használnak egyes tárolóalkalmazásokban, különösen a RAID 2 -ben . Ezenkívül a Hamming-módszert régóta használják az ECC memóriában , és lehetővé teszi az egyszeri hibák kijavítását és a kettős hibák menet közbeni észlelését.

Lásd még

Jegyzetek

↑ Hamming kódok – "All About Hi-Tech" . all-ht.ru. Hozzáférés dátuma: 2016. január 20. Az eredetiből archiválva : 2016. január 15. (határozatlan)

Irodalom

Peterson W., Weldon E. Hibajavító kódok: Per. angolról. Moszkva: Mir, 1976, 594 p.
Penin P. E., Filippov L. N. Rádiótechnikai információátviteli rendszerek. Moszkva: Rádió és Kommunikáció, 1984, 256 p.
Blahut R. A hibaellenőrző kódok elmélete és gyakorlata. Per. angolról. M.: Mir, 1986, 576 p.