Hamming-távolság

A Hamming-távolság alatt két azonos hosszúságú bináris jelsorozat eltérő bitjeinek a számát értjük. A fogalmat kiterjeszthetjük két azonos hosszúságú szöveges (alfanumerikus) karaktersorozatra is.

Értelmezés

Adott két azonos hosszúságú jelsorozat: "01100111010" és "01100110010". A különbség közöttük csak a vastagon megjelölt számjegy. Mivel a két jelsorozat (a továbbiakban szó) összesen egyetlen karakterben tér el egymástól, ezért a két szó Hamming-távolsága 1 (az ilyen kódszavakból álló sorozatot Gray-kódnak nevezzük).

A távolság megállapításakor nem számít, hogy az eltérő karakterhelyen hányféle jel állhat. Vegyünk két decimális szót, vagyis a megszokott tízféle számjegyből álló jelsorozatot: "81770815266072" és "81740815266072". A két szó távolsága 1, annak ellenére, hogy az eltérés helyén még nyolc másik számjegy is állhatna.

Ugyancsak lényegtelen a távolság megállapításakor, hogy a szavak hossza mekkora, az értelmezéshez csak az szükséges, hogy egymással megegyezzen.

Ahogy számjegyekre, úgy betűkre és egyéb karakterekre is használható a fogalom: a "harap" és "harag" szavak távolsága 1, a "drücken" és "drucker" távolsága 2, az "uostb8lpr" és "uortbclpr" távolsága szintén 2, hiszen a technikailag érdektelen, hogy a szavaknak van-e jelentése.

Minimális távolság

Adott négy szó: a: "0001111", b: "0010110", c: "0100101", d: "1001011". Állapítsuk meg a szótár minimális Hamming-távolságának értékét (a jele d). Ehhez a négy szót minden lehetséges variációban össze kell hasonlítani, megállapítani a távolságukat, majd ezek legkisebbike lesz d értéke.

H_ab=3, H_ac=3, H_ad=2, H_bc=4, H_bd=5, H_cd=5. A minimális távolság 2.

Hibavédelem

Ha azonos hosszúságú jelsorozatokból egyesekhez jelentést rendelünk, a többihez nem, akkor megállapítható a jelentéssel bíró szavak – ezeket kódszavaknak nevezik – minimális Hamming-távolsága. Ezeket a kódszavakat tárolni vagy valamilyen adatátviteli csatornán továbbítani kell. Ha a kódszótárnak van két eleme, amelyek távolsága 1, az azt jelenti, hogy ha a párból az egyik tárolt vagy továbbított szónak egyetlen betűje egy hiba miatt elváltozik, akkor lehet, hogy ez pont azzal a betűvel és úgy történik meg, hogy a másik szó lesz belőle. Természetesen ennek a valószínűsége több tényezőtől is függ, és lehet nagyon kicsi is, de az informatika vagy a telekommunikáció területén mindig fel kell készülni a legvalószínűtlenebb "lehet"-re is.

Ha a kódszótár minimális távolsága 2, akkor ha két, egymástól 2 betűnyi távolságra levő kódszó közül az egyik tárolásakor vagy továbbításakor 1 betű elváltozik, úgy mivel nincs olyan kódszó, amely ezzel megegyezik, észrevehető, hogy hiba történt. Például tegyük fel, hogy a kódszótárban nincs olyan szó, amely a "szekrény"-től csak egyetlen betűnyit tér el (azonos hossz mellett). Ekkor ha ebben a szóban bármelyik betűt eltévesztjük (dzekrény, szakrény, szeklény stb.), látható lesz, hogy tévesztés történt, mivel az így kijött szó mindenképpen értelmetlen lesz.

Kódszótár bármilyen célra, bármilyen jelekből létrehozható. A számítógépek gépi kódú utasításszavai azonos hosszúságú bináris számok, kódszótárat alkotnak egy áruház áruinak azonosítására használt betű- és számsorozatok, a repülőterek IATA-betűjelei, de egységesen 11 számjegyből álló "kódszavak" halmazát alkotják a személyi számok – ez esetben a kódok "jelentései" különböző személyek – vagy az autók rendszámai is.

A fenti példákból a személyi számok rendszerének kidolgozói gondoskodtak arról, hogy a szótár minimális távolsága 1-nél nagyobb legyen, a rendszámok esetében ez már nem így történt. Ezért előfordulhat, hogy egy balesetet okozó autó rendszáma például HCY-822, de ha a szemtanú ehelyett a HGY-822 rendszámot adja meg, akkor a rendőrök egy másik, vétlen autóst vesznek őrizetbe. Ám ha a szótár szavait meghosszabbítjuk még egy jellel, az autó színével, akkor máris csökken a tévedés esélye, mert a tévedéshez itt már a két autó színének is egyeznie kell.

Szintén a tévedés valószínűségét csökkentik azzal, hogy egy új gyógyszernek nem adható olyan fantázianév, amely egyetlen betűnyit tér el egy már létező névtől, azaz a minimális távolságot 1-nél nagyobb értéken tartják. Valójában mi is a kódszavak Hamming-távolságát növeljük azzal, amikor telefonban a "hétszáz" helyett "hetesszáz"-at mondunk, és "kettőszáz"-at a "kétszáz" helyett.

Az adatsorok véletlen hibából történő, félreértést okozó eltévesztésének valószínűségét csökkenti az az eljárás, amikor számsorokhoz információt nem hordozó, csakis a Hamming-távolság növelésével a tévesztést észrevétető ellenőrzőösszeget illesztenek.

Tulajdonságok

• Rögzített $n$ mellett a Hamming-távolság metrikát alkot az $n$ hosszúságú szavak halmazán.
• Bináris sztringek esetében a Hamming-távolság megegyezik az $a$ XOR $b$ sztringben szereplő egyesek számával.

Történet és alkalmazások

Richard Hamming vezette be ezt a távolságfüggvényt a hibajelző és hibajavító kódokról szóló alapvető cikkében 1950-ben.

Az elektromos hálózatban keletkező áramlökések és egyéb okok miatt a számítógépek memóriái néha hibáznak. Ezeknek a hibáknak a kiszűrésére bizonyos memóriák hibafelismerő vagy hibajavító kódot alkalmaznak. Ezek használata esetén minden memóriabeli szót kiegészítenek speciális bitekkel. Egy szó kiolvasása során ezeket a kiegészítő biteket ellenőrzik, hogy a hiba kiderüljön.

Tegyük fel, hogy egy memóriabeli szó m adatbitből áll, ehhez adunk még r redundáns vagy más néven ellenőrző bitet. A teljes hossz legyen n (vagyis n = m + r). Egy n bites, m adatbitet, és r ellenőrző bitet tartalmazó egységet gyakran n bites kódszónak neveznek.

Ha adott két szó, mondjuk 10001001 és 10110001, akkor megállapíthatjuk, hogy hány bitpozíción térnek el. Az eltérő bitpozíciók számának megállapításához egy egyszerű logikai 'kizáró vagy' (jele EOR vagy XOR) műveletet kell végezni a két kódszón, majd megszámolni az eredmény 1-es bitjeit. A módszernek az a jelentősége, hogy ha 2 kódszó távolsága d, akkor d darab egyszeres bithibának kell előfordulnia, ahhoz hogy az egyik kódszó a másikba alakulhasson. Például az 11110001 és a 00110000 Hamming távolsága 3, mert 3 bitet kell megváltoztatni ahhoz, hogy az egyik a másikba alakulhasson. Mivel egyidejűleg több hiba bekövetkezésére kisebb az esély, ezért a nagyobb Hamming-távolság növeli az adat biztonságát.

Források

• Andrew S. Tanenbaum: Számítógép-architektúrák (ISBN 963-545-282-9)