Jelaskan Contoh dari Jarak Hamming

Simbol pada string dapat berupa karakter, bit, digit desimal, maupun hal-hal lain. Berikut adalah contoh jarak Hamming antara:

"kain"  dan  "kain"  adalah 3.

"krin"  dan  "krin"  adalah 3.

"kin"  dan  "kin"  adalah 4.

10101  dan  10101  adalah 2.

2396  dan  2396  adalah 3.

Untuk panjang n yang tetap, jarak Hamming adalah metrik pada himpunan kata dengan panjang n (juga dikenal sebagai ruang Hamming), karena memenuhi kondisi sifat ketaknegatifan, simetri, bernilai 0 jika dan hanya jika kedua kata identik, dan memenuhi ketaksamaan segitiga: untuk setiap kata a, b, dan c, jika terdapat perbedaan huruf ke-i di a dan huruf ke-i di c, maka setidaknya terdapat perbedaan huruf ke-i di a dan huruf ke-i di b, atau perbedaan huruf ke-i di c dan huruf ke-i di b. Karenanya, jarak Hamming antara a dan c tidak mungkin lebih besar dari jumlah jarak Hamming antara a dan b dan antara b dan c. Jarak Hamming antara kata a dan b juga dapat dipandang sebagai berat Hamming dari a - b -- untuk pemilihan operator (-) yang cocok, mirip seperti selisih nilai antara dua bilangan dapat dipandang sebagai jarak dari 0 pada garis bilangan.

Untuk untai biner a dan b, jarak Hamming sama dengan banyaknya 1 di a XOR b. Ruang metrik dari untai biner dengan panjang n, dan dengan jarak Hamming, dikenal dengan kubus Hamming; hal ini setara dengan ruang metrik jarak antar himpunan titik di graf hiperkubus. String biner dengan panjang n juga dapat dipandang sebagai vektor di dengan menganggap setiap simbol sebagai koordinat. Dengan embedding ini, string membentuk himpunan titik hiperkubus dimensi-n, dan jarak Hamming antar string setara dengan jarak Manhattan antar titik.

Deteksi galat dan koreksi galat

Jarak Hamming minimum digunakan untuk mendefinisikan beberapa notasi penting pada teori kode, seperti kode pendeteksi galat dan kode pengoreksi galat. Secara khusus, suatu kode C dikatakan pendeteksi k-galat, jika dan hanya jika jarak Hamming minimum antara dua katakodenya setidaknya k+1.

Sebagai contoh, jarak Hamming antara katakode "000" dan "111" adalah 3, dan karenanya termasuk pendeteksi 2-galat. Hal ini berarti galat masih dapat terdeteksi jika sebuah atau dua bit berganti tanda. Namun jika tiga bit berganti tanda, "000" akan berubah menjadi "111" dan galat tidak dapat dideteksi.

Suatu kode C dikatakan pengoreksi k-galat bila, untuk setiap kata w di ruang Hamming H yang bersangkutan, terdapat paling banyak satu katakode c (elemen C) sehingga jarak Hamming antara w dan c tidak lebih dari k. Dengan kata lain, sebuah kode disebut pengoreksi k-galat jika dan hanya jika jarak Hamming minimum antara dua katakodenya adalah 2k+1. Hal ini dapat dipahami secara geometris dengan mengamati bola dengan radius k dan berpusat pada setiap katakode tidak dapat beririsan. Dalam konteks ini, bola tersebut juga disebut dengan bola Hamming.

Sebagai contoh, perhatikan kode tiga bit dari katakode "000" dan "111". Ruang Hamming-nya terdiri dari delapan kata 000, 001, 010, 100, 011, 101, 110, dan 111. Kodekata "000" dan kata dengan satu bit galat "001", "010", "100"  memiliki jarak Hamming ke "000" yang tidak lebih dari 1. Dengan alasan yang serupa, katakode  "111" dan kata dengan satu bit galat  "110","101" and "011" memiliki jarak Hamming maksimal 1 dari katakode asli "111". Dalam kode ini setiap galat satu bit selalu memiliki 1 jarak Hamming dengan kodekata aslinya, karenanya kode termasuk pengoreksi 1-galat (yakni dengan k=1). Jarak Hamming minimum antara "000" dan "111" adalah 3, yang memenuhi 2k+1 = 3.

Dengan demikian jarak Hamming minimum d antar katakode dapat mendeteksi paling banyak d-1 galat dan dapat mengoreksi paling banyak ⌊(d-1)/2⌋ galat. Nilai terakhir ini juga disebut dengan radius packing atau kapabilitas pengoreksi galat dari kode.