Hamming Uzaklığı
Eşit uzunluktaki iki karakter dizisi arasındaki Hamming uzaklığı, karşılık gelen konumlarda farklı olan karakterlerin sayısını ifade eder.
Basit bir ifadeyle, Hamming uzaklığı bir diziyi diğerine dönüştürmek için kaç karakterin değiştirilmesi gerektiğini gösterir. Bu nedenle bilgi kuramı, kodlama teorisi, veri iletimi ve hata düzeltme kodları gibi alanlarda yaygın olarak kullanılır.
Uzunluğu \( n \) olan iki dizi \( s \) ve \( t \) verildiğinde, Hamming uzaklığı \( D_H(s, t) \) aşağıdaki formülle tanımlanır:
$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$
Burada \( s_i \) ve \( t_i \), sırasıyla \( s \) ve \( t \) dizilerinin \( i \). konumundaki karakterleri gösterir. \( \delta(s_i, t_i) \) fonksiyonu ise iki karakter farklıysa 1, aynıysa 0 değerini alır.
Hamming uzaklığı yalnızca aynı uzunluktaki diziler için tanımlıdır. Uzunlukları farklı olan diziler arasında doğrudan Hamming uzaklığı hesaplanamaz.
Pratik Bir Örnek
Aşağıdaki iki kelimeyi ele alalım:
$$ s = \text{"karbon"} $$
$$ t = \text{"carbon"} $$
Bu iki kelime yalnızca ilk karakterde farklıdır. Birinde “k”, diğerinde ise “c” bulunur. Dolayısıyla aralarındaki Hamming uzaklığı:
$$ D_H(s,t)=1 $$
olur.
Örnek 2
Şimdi Hamming uzaklığı 2 olan başka bir örneğe bakalım:
$$ s = \text{"thing"} $$
$$ t = \text{"thank"} $$
Bu iki kelime iki farklı konumda ayrılır:
- Üçüncü harfte: “i” ve “a”
- Beşinci harfte: “g” ve “k”
Dolayısıyla:
$$ D_H(s,t)=2 $$
sonucu elde edilir.
Hamming Uzaklığına Dayalı Metrik Topoloji
Hamming uzaklığı yalnızca bir benzerlik ölçüsü değildir. Aynı zamanda matematiksel anlamda bir metrik oluşturur. Bunun nedeni, bir metrikten beklenen temel özelliklerin tamamını sağlamasıdır.
- Negatif Olmama
$$ D_H(x, y) \geq 0 \quad \text{and} \quad D_H(x, y) = 0 \ \text{if and only if} \ x = y $$
Hamming uzaklığı farklı konumların sayısını verdiğinden hiçbir zaman negatif olamaz. Ayrıca uzaklık ancak iki dizi tamamen aynıysa sıfır olur. - Simetri
$$ D_H(x, y) = D_H(y, x) $$
\( x \) ile \( y \) arasındaki uzaklık, \( y \) ile \( x \) arasındaki uzaklığa eşittir. Çünkü hangi dizinin önce yazıldığı sonuca etki etmez. - Üçgen Eşitsizliği
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
Herhangi üç dizi için doğrudan uzaklık, ara uzaklıkların toplamından büyük olamaz. Bu özellik, Hamming uzaklığının gerçek bir metrik olarak kullanılabilmesini sağlar.
Bu özellikler sayesinde Hamming uzaklığı, belirli uzunluktaki tüm diziler kümesi üzerinde bir metrik uzay tanımlar.
Metrik uzaylarda uzaklık kavramından yararlanılarak bir topoloji oluşturulabilir. Bu nedenle Hamming uzaklığı aynı zamanda bir metrik topoloji de belirler.
Uzunluğu \( n \) olan herhangi bir \( x \) dizisi ve \( r \) yarıçapı için, merkezi \( x \) olan açık küre şu şekilde tanımlanır:
$$ B(x, r) = \{y \mid D_H(x, y) < r\}. $$
Bu küme, \( x \)'e olan Hamming uzaklığı \( r \)'den küçük olan tüm dizileri içerir.
Metrik topolojideki açık kümeler, bu tür açık kürelerin birleşimleri alınarak elde edilir. Bu nedenle açık küreler, topolojinin temel yapı taşlarıdır.
Not. Uzunluğu \( n \) olan tüm ikili dizilerden veya belirli bir alfabeyle oluşturulmuş tüm dizilerden oluşan küme sonluysa, Hamming uzaklığının indüklediği topoloji ayrık topoloji olur. Bu durumda her eleman tek başına hem açık hem de kapalı bir küme oluşturur. Bunun nedeni, yeterince küçük bir yarıçap seçilerek her dizinin yalnızca kendisini içeren bir açık küre elde edilebilmesidir.
Dolayısıyla eşit uzunluktaki sonlu diziler üzerinde Hamming uzaklığının oluşturduğu metrik topoloji ayrık topolojidir.
Örnek
Uzunluğu üç olan aşağıdaki ikili diziler kümesini ele alalım:
$$ X = \{000, 001, 011, 110, 111 \} $$
\( r=2 \) yarıçapı için açık küreleri hesaplayalım.
$$ B(x, r) = \{y \mid D_H(x, y) < 2 \} $$
Bu durumda her açık küre, merkezdeki diziden en fazla bir konumda farklı olan dizileri içerir.
- \( 000 \) merkezli açık küre
$$ B(000,2)=\{000,001\} $$ Çünkü yalnızca \( 001 \), \( 000 \)'dan bir konumda farklıdır. - \( 001 \) merkezli açık küre
$$ B(001,2)=\{001,000,011\} $$ Hem \( 000 \) hem de \( 011 \), \( 001 \)'den yalnızca bir konumda farklıdır. - \( 011 \) merkezli açık küre
$$ B(011,2)=\{011,001,111\} $$ Burada \( 001 \) ve \( 111 \), merkez diziden bir konumda farklıdır. - \( 110 \) merkezli açık küre
$$ B(110,2)=\{110,111\} $$ Bu kürede yalnızca \( 111 \), merkez diziden bir konumda farklıdır. - \( 111 \) merkezli açık küre
$$ B(111,2)=\{111,011,110\} $$ Burada \( 011 \) ve \( 110 \), merkez diziden bir konumda farklıdır.
Bu açık küreler, \( r=2 \) yarıçapı için elde edilen topolojinin tabanını oluşturur. Çünkü diğer açık kümeler bu kümelerin birleşimleri alınarak oluşturulabilir.
Not. Açık küre tanımında eşitsizlik sıkıdır. Bu nedenle \( r=2 \) yarıçapı kullanıldığında koşul: $$ B(x,r)=\{y \mid D_H(x,y)<2\} $$ şeklindedir. Kapalı küre tanımlamak istersek eşitsizlik şu hale gelir: $$ C(x,r)=\{y \mid D_H(x,y)\le 2\} $$
Örneğin \( B(000,2) \) ve \( B(110,2) \) kümelerinin birleşimini ele alalım:
$$ B(000,2)\cup B(110,2) $$
Yerine yazarsak:
$$ \{000,001\}\cup\{110,111\} $$
ve sonuç olarak:
$$ B(000,2)\cup B(110,2)=\{000,001,110,111\} $$
elde edilir.
Dolayısıyla \( \{000,001,110,111\} \) kümesi de bu topolojide açık bir kümedir.
Sonuç olarak Hamming uzaklığı, eşit uzunluktaki diziler üzerinde doğal bir metrik oluşturur. Bu metrikten elde edilen açık küreler ise bir metrik topolojinin temelini meydana getirir. Sonlu kümelerde ortaya çıkan topoloji ayrık topoloji olsa da, Hamming uzaklığı daha genel bağlamlarda da kodlama teorisi ve bilgi kuramının temel araçlarından biri olarak önemli bir rol oynar.
