Ako vypočítať Hammingovu vzdialenosť

Dnes takmer každý aspekt moderného života zahŕňa prenos digitálnych informácií, buď medzi jednotlivými ľuďmi, alebo medzi jednotlivými servermi alebo systémami. Keď spravujete svoje bankové účty online, aktualizujte svoje stránky sociálnych médií alebo si dokonca prehrajte DVD s pripojeným DVD prehrávačom do vašej televízie sa informácie pohybujú z jedného miesta na druhé digitálne, a to buď káblom, alebo bezdrôtovým pripojením signál. Aby tieto informácie mohli prechádzať z jedného miesta na druhé, je potrebné ich preniesť prostredníctvom počítačového kódu. V tomto „jazyku“ sa informácie pohybujú kombináciou 1 a 0, známych ako binárny kód. Chyba v prechode binárneho kódu z jedného systému do druhého môže znamenať, že informácie nie sú prenášané správne, čo by mohlo spôsobiť veľa problémov používateľovi počítača. Hammingova vzdialenosť je spôsob pochopenia toho, ako sa kódy líšia. To sa potom dá použiť na opravu chýb.

TL; DR (príliš dlhý; Nečítali)

Hammingova vzdialenosť sa týka počtu bodov, v ktorých sa líšia dva riadky binárneho kódu, určený jednoduchým spočítaním počtu miest, kde sa líšia dva riadky kódu. Napríklad vzdialenosť medzi dvoma kódovými slovami 10101010 a 01011010 je štyri: aj keď to bez kontextu nemusí veľa znamenať, mohlo by to znamenať, že v štyroch bodoch chyby v kóde spôsobili, že sa zvukový súbor neprehral správne, obraz v televízii sa zobrazoval nesprávne alebo sa vyskytla kritická funkcia počítača nesprávne interpretované.

Hammingova vzdialenosť dvoch daných riadkov kódu je počet bodov, v ktorých sú hodnoty binárneho kódu riadkov odlišné (za predpokladu, že dva riadky kódu majú rovnakú dĺžku). To môže byť pri prvom prechode trochu mätúce, takže zvážte tento jednoduchý príklad: Z telefónu A do telefónu B sa posiela jednoslovná textová správa. Keď sa preloží do binárneho kódu, riadok kódu predstavujúci textovú správu v telefóne A znie „101“ a v telefóne B riadok kódu znie „010“. Pri porovnaní týchto riadkov môžete vidieť, že v každom z troch miest sú rôzne symboly. Môže to byť znamenie, že správa nebola odoslaná správne.

V jednoduchých scenároch je výpočet Hammingovej vzdialenosti jednoduchý, je však potrebné pamätať na to, že Hammingovu vzdialenosť je možné vypočítať iba pre čiary rovnakej dĺžky. Jednoducho spočítate počet miest, kde majú riadky rôzne hodnoty. V príklade vyššie by bola Hammingova vzdialenosť tri, pretože čiary majú rôzne hodnoty na troch miestach. Toto zdĺhavé porovnanie je však náročnejšie na čas, čím dlhší je riadok binárneho kódu. Zvážte trochu dlhší príklad s dvoma riadkami kódu: 100110 a 110011. Oba tieto riadky kódu obsahujú šesť informačných bodov. Hodnoty sa líšia v troch z týchto bodov, takže Hammingova vzdialenosť medzi týmito dvoma čiarami je tiež tri. Výpočet Hammingovej vzdialenosti s väčšou množinou údajov sa stáva komplikovanejším a zahŕňa použitie zložitých rovníc a funkcií ako d = min {d (x, y): x, y∈C, x ≠ y}.

Z kontextu sa Hammingova vzdialenosť môže javiť ako ľubovoľná. Pre kódovačov je to však dôležité meranie. Hammingova vzdialenosť môže pomôcť kódovačom napísať kód, ktorý zistí chyby, a dokonca ich sám opraví. Môže tiež pomôcť ľuďom pochopiť, aký je kód náchylný na chyby. Hammingova vzdialenosť je pomenovaná po Richardovi Wesleyovi Hammingovi, ktorý vyvinul meranie koncom 40. rokov minulého storočia, keď pracoval v spoločnosti Bell Telephone Laboratories. Aj keď Hamming bagatelizoval oslavu inovácie, technologický priemysel si toho všimol a pri riešení problémov s kódom ho veľmi efektívne využil. Takmer 50 rokov potom, čo Hamming objavil meranie, mu v roku 1996 udelila Nemecká nadácia Eduarda Rheima cenu Eduarda Rheima za úspech v technológii. Okrem toho I.E.E.E., veľká profesionálna organizácia v technologickom sektore, každoročne vydáva Richard W. Hammingova medaila na jeho počesť.