Hamming-távolság

A Wikipédiából, a szabad enciklopédiából.

Hamming-távolság alatt két azonos hosszúságú bináris vagy szöveges string eltérő bitjeinek illetve karaktereinek a számát értjük.

Tartalomjegyzék

1 Példák
2 Tulajdonságok
3 Történet és alkalmazások
4 Forrás

[szerkesztés] Példák

a Hamming távolság 1011101 és 1001001 között 2.
a Hamming távolság 2143896 és 2233796 között 3.
a Hamming távolság "keret" és "telep" között 3.

[szerkesztés] Tulajdonságok

Rögzített $n$ mellett a Hamming-távolság metrikát alkott 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.

[szerkesztés] 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 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 egyszeres bithiba szükséges ahhoz, hogy az egyik a másikba alakulhasson.