Hata Tespiti, Hata Düzeltme ve Kod Çözme
İletişim Kanalları
Tanım 2.1: Kod Alfabesi ve Sözcükler
- $\omega_{1},\ldots,\omega_{n}\in A$ olmak üzere $\vek w=w_{1}w_{2}\ldots w_{n}$ şeklindeki bir diziye $n$-uzunluklu bir $q$-lu sözcük denir. $\vek w$ aynı zamanda $(w_{1},w_{2},\ldots,w_{n})$ vektörü ile eşdeğer şekilde de düşünülebilir.
Aynı $n$ uzunluğuna sahip $q$-lu sözcüklerin boş olmayan bir $C$ kümesine $q$-lu öbek kodu ($q$-ary block code) veya kısaca $q$-lu kod denir. $C$ kümesinin her elemanına ise kod-sözcüğü adı verilir. $C$ içindeki kod-sözcüklerinin sayısına $C$'nin büyüklüğü denir ve $|C|$ ile gösterilir.
Uzunluğu $n$ olan bir $C$ kodunun (bilgi) oranı $(\log_{q}|C|)/n$ sayısı ile tanımlanmaktadır.
Uzunluğu $n$ olan $M$ büyüklüğünde bir kod için (n,M)-kodu ifadesini kullanacağız.
Not 2.1: Önemli
Uygulamada ve dersimizde kod alfabesi olarak sıklıkla bir sonlu cisim, genellikle de mertebesi $q$ olan sonlu cisim ($\mathbb{F}_{q}$), kullanılmaktadır.
Örnek 2.5: İkili Kod Örnekleri
- $C_{1}=\{00,01,10,11\}$ bir $(2,4)$-kodudur.
- $C_{2}=\{000,010,110,111\}$ bir $(3,4)$-kodudur.
- $C_{3}=\{0101,1100,0011,1010,1001,0110\}$ bir $(4,6)$-kodudur.
Benzer şekilde, üçlü ve dörtlü kodlar, kod alfabeleri sırasıyla $\mathbb{F}_{3}=\{0,1,2\}$ ve $\mathbb{F}_{4}$ ($4$ elemanlı sonlu cisim) olan kodlara denilmektedir. Ancak bazen kod alfabesi $\mathbb{Z}_{4}=\{0,1,2,3\}$ halkası olan kodlara da dörtlü kod denilebilmektedir. Buradan, kod alfabelerinin cebirsel yapılarının kodlar üzerinde etkili olduğu bir kuramı tanıtacağımızı anlamak mümkündür.
Tanım 2.2: İletişim Kanalı
Bir iletişim kanalı sonlu bir $A=\{a_{1},\ldots,a_{q}\}$ kanal alfabesi ile (ileri yönlü) kanal olasılıklarının bir $\{\mathcal{P}(a_{j}|a_{i}):1\leq i,j\leq q\}$ kümesinden oluşur. Burada $\mathcal{P}(a_{j}|a_{i})$; aynı zamanda $\mathcal{P}(a_{j}$ alınır $|$ $a_{i}$ gönderilir$)$ biçiminde de gösterilebilen, $a_{i}$ gönderilmesi halinde $a_{j}$ alınması (koşullu) olasılığını temsil etmektedir.
İleri yönlü kanal olasılıkları her $1\leq i\leq q$ için
$$\sum_{j=1}^{q}\mathcal{P}(a_{j}|a_{i})=1$$eşitliğini sağlamalıdır. Bunun anlamı ise; her $i$ için, $a_{i}$ gönderildiğinde $A$'nın bir elemanının mutlaka alınacağının güvence altında olduğudur.
Tanım 2.3: Belleksiz Kanal
Bir iletişim kanalında gerçekleşen bir iletimin sonucu, daha önce gerçekleşen iletimlerin sonucundan bağımsız ise bu kanala belleksiz kanal denir. Yani, bir belleksiz kanalda, $n$ uzunluklu $\vek c=c_{1}\ldots c_{n}$ ve $\vek x=x_{1}\ldots x_{n}$ gibi iki sözcük için
$$\mathcal{P}(\vek x|\vek c)=\prod_{i=1}^{n}\mathcal{P}(x_{i}|c_{i})$$olur.
Tanım 2.4: Simetrik Kanal
Eğer $q$ büyüklüğünde alfabeye sahip bir belleksiz kanalda
aktarılan her bir simgenin hata ile alınmış olması olasılığı aynı ve $1/2$'den az,
bir simge hata ile alındığında $q-1$ adet muhtemel hatanın her biri eşdeğer oranda muhtemel
ise bu kanala bir $q$-lu simetrik kanal denir.
Özel olarak, ikili simetrik kanal (İSK), alfabesi $\{0,1\}$ kümesi ve kanal olasılıkları
$$\begin{array}{l} \mathcal{P}(1|0)=\mathcal{P}(0|1)=p \\ \mathcal{P}(0|0)=\mathcal{P}(1|1)=1-p \end{array}$$biçiminde olan bir belleksiz kanaldır. Buna göre bir İSK'da bir bit hata olasılığı $p$'dir. Bu olasılığa İSK'ın çapraz olasılığı denir.
Örnek 2.6: İSK Örneği
İkinci olasılığın birinciden daha büyük olması nedeniyle gönderilmiş olması daha muhtemel olan sözcüğün $111$ olduğu sonucuna varabiliriz.
Kod Çözme
Kodlamalı bir iletişim kanalında, yalnızca kod sözcükleri iletilir. Eğer bir iletimde geçerli bir kod sözcüğü alınırsa bu durumda iletimde bir hata olmadığını düşünmek olasıdır. Ancak, tersi bir durumda, iletimde hatalar meydana geldiğini biliriz. Böyle bir durumda, gönderilmiş olması en muhtemel kod sözcüğünü belirlemek üzere bir kurala ihtiyacımız olur. Böyle bir kurala kod çözme kuralı adı verilir. Bu bölümde şimdilik iki genel kuralı tanıtmakla yetineceğiz:
1. Azami Olasılık (Kod-Çözme) Kuralı
Kabul edelim ki bir $C$ kodunun kod sözcükleri bir iletişim kanalı üzerinden gönderiliyor olsun. Bir $\vek x$ sözcüğü alınırsa, her $\vek c\in C$ için
$$\mathcal{P}(\mathbf{x}|\mathbf{c})$$kanal olasılıklarını hesaplayabiliriz. Azami olasılık kod-çözme kuralı'na göre, eğer $\vek c_{\mathbf{x}}$ sözcüğü için bu kanal olasılıkları azami değer alıyor ise, yani
$$\mathcal{P}(\mathbf{x}|\mathbf{c}_{\mathbf{x}})=\underset{\mathbf{c}\in C}{\text{maks}}\mathcal{P}(\mathbf{x}|\mathbf{c})$$ise o zaman $\vek c_{\mathbf{x}}$, gönderilmiş olması en muhtemel kod sözcüğüdür.
Azami olasılık kuralı tam ve tam olmayan şeklinde ikiye ayrılır. Tam azami olasılık kuralında kanal olasılıklarının azami olduğu birden fazla kod sözcüğü olması halinde bu sözcükler arasında rastgele bir seçim yapılır. Tam olmayan azami olasılık kuralında ise böyle bir durumda sözcüğün yeniden gönderilmesi istenir.
2. Asgari Uzaklık (Kod-Çözme) Kuralı
Kabul edelim ki bir $C$ kodunun kod sözcükleri, çapraz olasılığı $p$ ($<1/2$) olan bir İSK üzerinden gönderiliyor olsun. Eğer bir $n$-uzunluklu bir $\vek x$ sözcüğü alınır ise bu durumda herhangi bir ($n$-uzunluklu) $\vek c \in C$ için ileri yönlü kanal olasılığı
$$\mathcal{P}(\mathbf{x}|\mathbf{c})=p^{e}(1-p)^{n-e}$$şeklindedir. Burada $e$, $\vek x$ ile $\vek c$ sözcüklerinin birbirlerinden farklı oldukları (veya ayrıldıkları) basamakların sayısını temsil etmektedir. $p<1/2$ olduğundan $1-p>p$ olur. Böylece bu olasılığın değeri $n-e$ değeri büyüdükçe, başka bir deyişle de $e$ değeri küçüldükçe, artar. Buna göre, bu olasılık, $e$'nin mümkün olduğunca küçük tutulabildiği bir $\vek c$ sözcüğü için azami değere sahiptir. Burada sözü edilen $e$ sayısı, bizi, aşağıdaki tanımda olduğu gibi verilen bir uzaklık kavramını ortaya atmaya itmektedir:
Hamming Uzaklığı
Tanım 2.5: Hamming Uzaklığı
Bir $A$ alfabesi üzerinde $n$-uzunluklu $\vek x$ ve $\vek y$ gibi iki sözcük alalım. $\vek x$ ve $\vek y$ arasındaki uzaklık (ya da Hamming uzaklığı), $\vek x$ ve $\vek y$'nin birbirinden ayrıldığı basamakların sayısı olarak tanımlanır ve $d(\vek x,\vek y)$ şeklinde gösterilir. Buna göre $\vek x =x_{1}\ldots x_{n}$, $\vek y =y_{1}\ldots y_{n}$ ve $x_{i}$ ile $y_{i}$ simgelerini $1$-uzunluklu sözcükler olarak düşünmek suretiyle
$$d(x_{i},y_{i})=\left\{\begin{array}{cc} 1, & x_{i}\neq y_{i} \\ 0, & x_{i}=y_{i} \end{array}\right.$$dersek,
$$d(\mathbf{x},\mathbf{y})=d(x_{1},y_{1})+\cdots +d(x_{n},y_{n})$$olarak yazılabilir.
Örnek 2.7: Uzaklık Hesabı
elde edilir.
Teorem 2.1: Uzaklık Özellikleri
- $0\leq d(\vek x,\vek y)\leq n$.
- $d(\vek x,\vek y)=0\iff \vek x=\vek y$.
- $d(\vek x,\vek y)=d(\vek y,\vek x)$
[Üçgen eşitsizliği] $d(\vek x,\vek z)\leq d(\vek x,\vek y)+d(\vek y,\vek z)$.
📝 Ödev 2.1 (MTK698-2026) | ⏰ Son Teslim: 05.03.2026 00:00
ÖDEV I
Yukarıdaki teoremi ispatlayınız.
Kabul edelim ki bir $C$ kodunun kod sözcükleri bir iletişim kanalı üzerinden gönderiliyor olsun. Asgari uzaklık kod çözme kuralına göre, eğer $\vek c_{\mathbf{x}}$ sözcüğü için
$$d(\mathbf{x}|\mathbf{c}), \quad c\in C$$uzaklıkları asgari değer alıyor ise, yani
$$d(\mathbf{x}|\mathbf{c}_{\mathbf{x}})=\underset{\mathbf{c}\in C}{\min}d(\mathbf{x}|\mathbf{c})$$ise o zaman $\vek x$ sözcüğü $\vek c_{\mathbf{x}}$ olarak çözülür. Azami olasılık kuralında olduğu gibi asgari uzaklık kuralı da tam ve tam olmayan olmak üzere iki çeşittir.
Teorem 2.2: Kuralların Denkliği
Bir İSK için azami olasılık kuralı ile asgari uzaklık kuralı denktir.
Kanıt
Simetrik kanalın çapraz olasılığı $p<1/2$ olsun. Kullanılan kodu $C$ ile, aktarımda alınan $n$-uzunluklu bir sözcüğü de $\vek x$ ile gösterelim. $n$-uzunluklu herhangi bir $\vek c$ kod sözcüğü için
$$d(\vek x|\vek c)=i \iff \mathcal{P}(\vek x|\vek c)=p^{i}(1-p)^{n-i}$$olur. $p<1/2$ olduğundan
$$p^{0}(1-p)^{n}>p^{1}(1-p)^{n-1}>p^{2}(1-p)^{n-2}>\cdots >p^{n}(1-p)^{0}$$yazabiliriz. Tanıma göre azami olasılık kuralı, $\vek x$ sözcüğünü $\mathcal{P}(\vek x|\vek c)$ değerini en büyük, yani $d(\vek x|\vek c)$ değerini en küçük yapan bir $\vek c$ kod sözcüğü olarak çözer ve dolayısıyla da asgari uzaklık kuralı ile aynı işi yapmış olur.
Örnek 2.8: Asgari Uzaklık Örneği 1
Örnek 2.9: Asgari Uzaklık Örneği 2
| alınan $\vek x$ | $d(\vek x,000)$ | $d(\vek x,011)$ | çözülen |
|---|---|---|---|
| $000$ | $0$ | $2$ | $000$ |
| $100$ | $1$ | $3$ | $000$ |
| $010$ | $1$ | $1$ | -- |
| $001$ | $1$ | $1$ | -- |
| $110$ | $2$ | $2$ | -- |
| $101$ | $2$ | $2$ | -- |
| $011$ | $2$ | $0$ | $011$ |
| $111$ | $3$ | $1$ | $011$ |
Bir Kodun Uzaklığı
Uzunluk ve büyüklük gibi iki özellikten sonra bir kod için önemli başka bir özellik te o kodun uzaklığıdır.
Tanım 2.6: Kodun Uzaklığı
En az iki sözcük içeren bir $C$ kodu için, $C$'nin (asgari) uzaklığı
$$d(C)=\min \{d(\mathbf{x},\mathbf{y}):\mathbf{x},\mathbf{y}\in C,\ \mathbf{x}\neq \mathbf{y}\}$$olarak tanımlanır.
Uzunluğu $n$, büyüklüğü $M$ ve uzaklığı $d$ olan bir kod için (n,M,d)-kodu ifadesi kullanılır. $n$, $M$ ve $d$ sayılarına kodun parametreleri denir.
Örnek 2.10: Kod Uzaklığı Örneği 1
Buna göre $C$ bir $(5,3,2)$-ikili kodudur.
Örnek 2.11: Kod Uzaklığı Örneği 2
Tanım 2.7: Hata Sezici Kod
Örnek 2.12: Hata Sezici Kod Örneği
Aslında $C$ bir tam-$1$-hata sezici koddur. Çünkü $00000$ sözcüğünün ilk iki hanesini değiştirerek geçerli bir kod sözcüğü olan $11000$ elde ediliyor.
$C=\{000000,111000,111222\}$ üçlü kodu ise bir tam-$2$-hata sezici koddur.Teorem 2.3: Hata Sezme Teoremi
Bir $C$ kodu $u$-hata sezicidir ancak ve ancak $d(C)\geq u+1$. Başka bir deyişle uzaklığı $d$ olan bir kod tam-$(d-1)$-hata sezici koddur.
📝 Ödev 2.2 (MTK698-2026) | ⏰ Son Teslim: 05.03.2026 00:00
ÖDEV I
Yukarıdaki teoremi ispatlayınız.
Tanım 2.8: Hata Düzeltici Kod
Örnek 2.13: Hata Düzeltici Kod Örneği
- $000$ gönderilir ve yalnız bir hata meydana gelirse, $100$, $010$ veya $001$ olarak alınan kod sözcüğü, $000$ olarak çözülür.
- $111$ gönderilir ve yalnız bir hata meydana gelirse, $011$, $101$ veya $110$ olarak alınan kod sözcüğü, $111$ olarak çözülür.
Dolayısıyla, $C$ kodu bir $1$-hata düzeltici koddur. Asgari uzaklık kuralı, $C$ kodunun sözcükleri üzerinde meydana gelebilecek iki adet hata sonucu oluşacak sözcükleri yanlış çözeceğinden $C$ kodu tam-$1$-hata düzeltici kod olur.
Teorem 2.4: Hata Düzeltme Teoremi
Bir $C$ kodu $v$-hata düzelticidir ancak ve ancak $d(C)\geq 2v+1$. Başka bir deyişle uzaklığı $d$ olan bir kod tam-$\lfloor (d-1)/2\rfloor$-hata düzeltici koddur. Burada $\lfloor x\rfloor$, $x$'den büyük olmayan en büyük tamsayıdır.
📝 Ödev 2.3 (MTK698-2026) | ⏰ Son Teslim: 05.03.2026 00:00
ÖDEV I
Yukarıdaki teoremi ispatlayınız.
Neler Öğrendik?
Kısa sınav
⚠️ Quiz cevaplamak için giriş yapmalısınız. Giriş Yap.