Hamming távolság

A Hamming-távolság matematikai fogalom, amelyet Richard Hamming határozott meg , és a számítógépeket a jelfeldolgozásban és a távközlésben használta . Fontos szerepet játszik a korrekciós kódok algebrai elméletében . Ez lehetővé teszi a szimbólumok két szekvenciája közötti különbség számszerűsítését. Ez a kifejezés matematikai értelmében vett távolság . Két azonos hosszúságú szimbólum-szekvenciával hozzárendeli azoknak a pozícióknak a számát, ahol a két szekvencia eltér.

A Hamming-súly megfelel a véges mező elemeinek láncában szereplő nem nulla elemek számának .

A koncepció érdeke

Az alkalmazás története és területe

A Hamming-távolság Richard Hammingnek ( 1915 - 1998 ) köszönheti nevét . Ezt a módszert az cikkből a kódot elmélet . A távközlésben arra használják, hogy megszámolja a sérült bitek számát egy adott hosszúságú üzenet továbbításakor. A Hamming-súly a nullától eltérő bitek száma, számos területen alkalmazzák, például információelméletben , kódolási elméletben és kriptográfiában . Azonban a változó hosszúságú szekvenciák vagy a karakterláncok összehasonlításához, amelyek nemcsak helyettesítéseken, hanem beillesztéseken vagy törléseken is áteshetnek, kifinomultabb mutatók, például Levenshtein távolsága megfelelőbb.

Motiváció

A javító kódok forrása az adatátviteli probléma. Néha az adatátvitel megbízhatatlan kommunikációs csatornán történik. A javító kód célja az információ-redundancia biztosítása oly módon, hogy a hiba észlelhető, vagy akár kijavítható legyen.

Egy üzenet tagja egy sor E álló kész lakosztályok levelek közül egy ábécé A . A redundancia hozzájárulása az E inj injektív alkalmazásának eredménye az F készletben, amely szintén A ábécé betűinek véges szekvenciáiból áll . A lakosztályok mindegyike F választjuk eleve hosszabb E . Az φ ( E ) halmazt kódnak hívjuk, és a kód ezen set ( m ) halmazának eleme . Az φ (m) átvitelének előnyét m helyett a jobb oldali ábra szemlélteti.

A redundancia nélküli kód esete az ábra bal oldalán látható. F ekkor egyenlő E-vel és φ az azonosság. Ha egy zöld színű üzenetet továbbítás közben átalakítanak, akkor új, piros színű üzenetet továbbítanak. Nincs információ arra vonatkozóan, hogy hibát követtek volna el.

Ennek az állapotnak a leküzdésére a cél az, hogy a kód szavait, amelyek a zöld pontoktól jobbra látható ábrának megfelelnek, hibákat tartalmazó üzenetekkel vegyék körül. Ezeket az elbocsátásokat a narancssárga rács metszéspontjai szemléltetik. Ha egyetlen hiba lép fel, akkor az átvitt üzenet piros pontnak felel meg. Ha a redundancia ügyesen felépült, csak egy zöld pont van a kapott piros ponthoz közel, a hiba kijavítható.

A Hamming-távolság megfelel az ábrán a rács legkisebb azon szakaszainak számának, amelyeket két pont összekapcsolásához keresztezni kell.

Meghatározás és példák

Definíciók

• Vagy egy ábécé és F a beállított hosszúságú szekvenciák n értékekkel a A . A Hamming-távolsága a két elem egy és b az F a elemeinek száma a beállított képek olyan , amely különbözik a b .

Formálisan, ha d (.,.) A Hamming-távolságot jelöli:

∀nál nél,b∈Fnál nél=(nál nélén)én∈[0,nem-1]etb=(bén)én∈[0,nem-1]d(nál nél,b)=#{én:nál nélén≠bén}{\ displaystyle \ forall a, b \ in F \ quad a = (a_ {i}) _ {i \ in [0, n-1]} \; és \; b = (b_ {i}) _ {i \ itt: [0, n-1]} \ quad d (a, b) = \ # \ {i: a_ {i} \ neq b_ {i} \}}

A jelölési # E jelöli a bíboros a készlet E .

Fontos eset a gyakorlatban a bináris szimbólumoké. Más szavakkal: A = {0,1}, akkor írhatunk, ha ⊕ a kizárólagos vagy .

d(nál nél,b)=∑én=0nem-1(nál nélén⊕bén){\ displaystyle d (a, b) = \ sum _ {i = 0} ^ {n-1} (a_ {i} \ oplus b_ {i})}

Abban a gyakori esetben, amikor az ábécé egy véges mező , az F vektortér- szerkezete n dimenzió . A távolság ekkor egy álnormából származik  :

• Vagy K egy véges mező, és F a beállított hosszúságú szekvenciák n értéke K . A Hamming súlya p ( a ) egy elem egy az F a számossága a készlet nem nulla képek egy .

Az ábécé gyakran F 2 , két elem mezője {0,1}. A Hamming-súly álnorma, mert:

∀nál nél∈F∀λ∈Ko(λ.nál nél)=o(nál nél){\ displaystyle \ forall a \ in F \; \ forall \ lambda \ in \ mathbb {K} \ quad p (\ lambda .a) = p (a)}

Ha azonban az ábécé véges mező, akkor a távolság a Hamming-súlyból származik, sőt:

∀nál nél,b∈Fd(nál nél,b)=o(b-nál nél){\ displaystyle \ all a, b \ in F \ quad d (a, b) = p (ba)}

Példák

Vegye figyelembe a következő bináris szekvenciákat:

nál nél=(0001111)etb=(1101011)nál néllorsd=1+1+0+0+1+0+0=3{\ displaystyle a = {\ kezdés {pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\\ end {pmatrix}} \; és \; b = {\ begin {pmatrix} 1 & 1 & 0 & 1 & 0 & 1 & 1 \\\ end {pmatrix}} \ quad majd \ quad d = 1 + 1 + 0 + 0 + 1 + 0 + 0 = 3}

Közötti távolság a és b értéke 3 , mert 3 bit különböznek.

• A 10 1 1 1 01 és a 10 0 1 0 01 közötti Hamming-távolság 2.
• A 2 14 3 8 96 és a 2 23 3 7 96 közötti Hamming-távolság 3.
• A " r a m e r " és a " c a s e s " közötti Hamming-távolság 3.

Bináris eset

Fontos eset, amikor az ábécé a kétrészes {0,1} mező. Ezután egy levelet kissé hívnak . Széles körben használják az informatikában és a telekommunikációban.

Lehetséges grafikusan szemléltetni a kódot és a különböző szavak közötti távolságokat.

Az esetet, amikor egy szónak három betűje van, a bal oldali ábra szemlélteti. A 010 és 111 közötti távolság egyenlő kettővel, mert a két pont összekapcsolásához két szegmenst kell megtenni. A 100 és 011 pontok összekapcsolásának távolsága három.

A jobb oldali ábra egy négyes méretű bináris hiperkockát szemléltet . A 0110 és 1110 közötti távolság egyenlő, míg a 0100 és 1001 közötti távolság három.

A Hamming súlya egy elem egy megfelel a távolságot a szót nulla amelyek csak nulla koordinátáit és a .

Ingatlan

Távolság

A Hamming-távolság a kifejezés matematikai értelmében vett távolság :

∀nál nél,b∈F:d(nál nél,b)=d(b,nál nél){\ displaystyle \ forall, b \ in F: d (a, b) = d (b, a)}	(szimmetria)
∀nál nél,b∈F:d(nál nél,b)=0⇔nál nél=b{\ displaystyle \ minden a, b \ -ban F: d (a, b) = 0 \ Balra mutató nyíl a = b}	(elválasztás)
∀nál nél,b,vs.∈F:d(nál nél,vs.)≤d(nál nél,b)+d(b,vs.){\ displaystyle \ összes a, b, c \ -ban F: d (a, c) \ leq d (a, b) + d (b, c)}	(háromszög egyenlőtlenség)

A harmadik tulajdonság bizonyult egy indukciós a n .

Korrekciós képesség és minimális távolság

A minimális távolság δ a kód két szava közötti minimális távolság. Ez lehetővé teszi a maximális számú javítható hibák t kell meghatározni. A t értéke valóban a legnagyobb egész szám értéke, szigorúan kisebb, mint δ / 2.

Ha M számát jelöli, szó a kódot, q a betűk száma az ábécé A az F és V t számosságának zárt labdát sugarú t , akkor a következő növekedése igazolt:

M≤qnemVtnál nélvevs.Vt=∑én=0t(nemén)(q-1)én{\ displaystyle M \ leq {\ frac {q ^ {n}} {V_ {t}}} \ quad with \ quad V_ {t} = \ sum _ {i = 0} ^ {t} {n \ select i } (q-1) ^ {i}}

Ez a növekedés Borne de Hamming nevet viseli .

Abban az esetben, egy lineáris kód , és ha k jelöli a hossza a szavak a kódok, van egy másik növekedése, az úgynevezett Singleton kötött:

δ-1≤nem-k{\ displaystyle \ delta -1 \ leq nk \;}

Alkalmazások

Ellenőrző összeg

7 bites adat	paritásos bitdel
0000000	0 0000000
1010001	1 1010001
1101001	0 1101001
1111111	1 1111111

Az ellenőrző összeg egyszerű példa a Hamming-távolság használatára. A kód két szava közötti minimális távolság egyenlő kettővel . Következésképpen, ha egyetlen hiba történik, akkor azt észlelik. Viszonteladás nélkül azonban nem javítható. Valóban, vannak eleve több kódszót távol egyik a hibás üzenet.

A legegyszerűbb példa a paritásbit . Ellenőrző összegnek felel meg abban az esetben, ha a test bináris, vagyis két nulla és egy elemet tartalmaz .

Tegyük fel, hogy a cél hét bit átvitele . A paritásbitet nullának definiáljuk, ha a többi bit összege páros, egy pedig más. A továbbított nyolc bit először az paritásbit, majd az üzenet hét bitje. Megfelel a páros paritásbitnek, vagyis a jobb oldali táblázat második oszlopának. Küldött üzeneteket nyolc bit mindig nulla paritás , így ha hiba történik, a nulla lesz egy , vagy fordítva; a vevő tudja, hogy változás történt. Valójában a bitek összege páratlan lesz, ami átviteli hiba nélkül nem lehetséges.

Hamming-kód

A Hamming-kód valamivel összetettebb példa, mint az előző. A kód két szava közötti minimális távolság három. Ha egy sérülés történik, akkor a fogadott üzenet a parttól egy egyetlen pont a kódot. Így lehetséges egy hiba automatikus kijavítása, ha tudjuk, hogy a hiba egyedi.

Lineáris kód

A lineáris kódok a két előző példát tartalmazó családot alkotnak. Az ábécé véges mező , az E és F halmaz vektorterek, a map térkép pedig lineáris. A Hamming-távolság az álnormából származik: a Hamming-súlyból. Ezt az összefüggést általában az ipar használja.

Ciklikus kód

Ez a kódcsalád a lineáris kód egy adott esetének felel meg. Az E és F struktúrák gyűrűs szerkezettel vannak gazdagítva, amely algebra státuszt ad nekik . Ez a véges mezők kiterjesztéseire vonatkozó polinomelméleten alapuló szerkezet lehetővé teszi a lehető legkisebb távolságok megalkotását.

Számos kód épül erre az elméletre. Úgy tűnik, hogy a Hamming-kód ezek speciális esete. Megemlíthetjük például a kompaktlemezekhez használt BCH vagy Reed-Salamon kódokat is .

Megjegyzések és hivatkozások

1. Richard Hamming hibadetektáló és hibajavító kódok Bell System Technical Journal 29 (2): 147-160, 1950

Lásd is

Kapcsolódó cikk

• Legközelebbi csatorna

Külső linkek

• JP Zanotti, Touloni Egyetem CIRC-korrekciós kódja
• Algebra és hibajavítás : Dany-Jack Mercier, Antilles-Guyane Egyetem
• Lineáris kód : G. Zemor, Bordeaux-i Egyetem
• Kód természetesen Christine Bachoc, Bordeaux I Egyetem
• Javító kód : M. Coste, A. Paugam, R. Quarez, Lille-i Egyetem

Bibliográfia

• (in) Jessie MacWilliams és Neil Sloane , A hibajavító kódok elmélete, Észak-Hollandia , 1977 ( ISBN  978-0-444-85009-6 )
• A. Spătaru, Az információátadás elméletének alapjai , PPUR , 1987 ( ISBN  978-2-88074-133-4 )
• Michel Demazure , Az algebra tanfolyama: elsődlegesség, oszthatóság, kódok [ a kiadások részlete ]
• B. Martin, Kódolás, rejtjelezés és alkalmazások , PPUR, 2004 ( ISBN  978-2-88074-569-1 )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">