Doğrusal Kodlar

$\mathbb{F}_{q}$ sonlu cismi üzerindeki $n$ uzunluklu bir doğrusal kod $\mathbb{F}_{q}^{n}$ uzayının bir alt uzayından başka bir şey değildir. Doğrusal kodlar birer vektör uzayı olduğundan, üzerlerindeki cebirsel yapı sayesinde tanımlanmaları ve kullanılmaları doğrusal olmayan kodlara nazaran daha kolay olmaktadır.

Sonlu Cisimler Üzerindeki Vektör Uzayları

Tanım 4.1: Vektör Uzayı

$(V,+)$ bir toplamsal Abelyan grup olsun. $\mathbb{F}_{q}$ cisminin elemanları ile $V$'nin elemanları arasında skalerle çarpma adı verilen ve aşağıdaki özellikleri sağlayan bir çarpma işlemi varsa, $V$'ye, $\mathbb{F}_{q}$ üzerinde bir vektör uzayı veya kısaca bir $\mathbb{F}_{q}$-uzayı denir:

Her $u,v\in V$ ve $\lambda,\mu\in\mathbb{F}_{q}$ için

$\lambda v\in V$
$\lambda(u+v)=\lambda u+\lambda v$ ve $(\lambda+\mu)v=\lambda v+\mu v$
$(\lambda\mu)v=\lambda(\mu v)$
$1_{\mathbb{F}_{q}}v=v$

$V$ bir $\mathbb{F}_{q}$ uzayı olsun. Her $\lambda\in\mathbb{F}_{q}$ ve $u\in V$ için $$\begin{align*} 0_{\mathbb{F}_{q}}u & =0_{V}\\ \lambda0_{V} & =0_{V} \end{align*}$$

olur.

$\mathbb{F}_{q}^{n}$ ile girişleri $\mathbb{F}_{q}$ cisminden olan $n$ uzunluklu vektörlerin kümesini göstereceğiz: $$\mathbb{F}_{q}^{n}=\{(v_{1},\ldots,v_{n}):v_{i}\in\mathbb{F}_{q}\}$$

Toplama ve skalerle çarpma işlemleri bileşensel olarak tanımlanır:

v $+$ w $=(v_{1}+w_{1},\ldots,v_{n}+w_{n})$
$\lambda$v $=(\lambda v_{1},\ldots,\lambda v_{n})$

Örnek 4.22: Vektör Uzayı Örnekleri

Aşağıdaki kümeler $\mathbb{F}_{q}$ üzerinde birer vektör uzayıdır:

$C_{1}=\{(\lambda,\ldots,\lambda):\lambda\in\mathbb{F}_{q}\}$
$C_{2}=\{(0,0,0,0),(1,0,1,0),(0,1,0,1),(1,1,1,1)\}$ ($q=2$)
$C_{3}=\{(0,0,0),(0,1,2),(0,2,1)\}$ ($q=3$)

Not 4.1

Herhangi bir karışıklığa neden olmadığı sürece $(v_{1},\ldots,v_{n})$ vektörünü $v_{1}\ldots v_{n}$ şeklinde göstereceğiz.

Tanım 4.2: Alt Uzay

$V$ bir vektör uzayı ve $C$, $V$'nin boş olmayan bir altkümesi olsun. Eğer $C$, $V$ üzerindeki toplama ve skalerle çarpma işlemi ile bir vektör uzayı oluyor ise $C$'ye $V$'nin bir alt uzayı denir.

Örnek 4.23

$\{\vek0\}$ her uzayın altuzayıdır.
$\mathcal{C}_{2}=\{(0,0,0,0),(1,0,1,0),(0,1,0,1),(1,1,1,1)\}$, $\mathbb{F}_{2}^{4}$'ün bir altuzayıdır.
$\mathcal{C}_{3}=\{(0,0,0),(0,1,2),(0,2,1)\}$, $\mathbb{F}_{3}^{3}$'ün bir altuzayıdır.

Teorem 4.1: Alt Uzay Kriteri

$V$ bir vektör uzayı ve $C$, $V$'nin boş olmayan bir alt kümesi olsun. $C$, $V$'nin bir alt uzayıdır ancak ve ancak her $\lambda,\mu\in\mathbb{F}_{q}$ ve x, y $\in C$ için $\lambda$x$+\mu$y $\in C$ dir.

Not 4.2: İkili Kodlar İçin

$\mathbb{F}_{2}$ cisminin sıfırdan farklı tek elemanı $1$ olduğundan, $\mathbb{F}_{2}$ üzerindeki bir vektör uzayının bütün alt uzayları, toplamsal kapalı altkümelerinden ibaret olur. Yani $C$'nin alt uzay olabilmesi için gerek ve yeter koşul her x, y $\in C$ için x$+$y $\in C$ olmasıdır.

Tanım 4.3: Doğrusal Kombinasyon ve Bağımsızlık

$V$ bir $\mathbb{F}_{q}$-uzayı ve v$_{1}$, v$_{2}$, $\ldots$, v$_{r}\in V$ olsun.

$\lambda_{1},\lambda_{2},\ldots,\lambda_{r}\in\mathbb{F}_{q}$ olmak üzere $V$'nin $\lambda_{1}$v$_{1}+\lambda_{2}$v$_{2}+\cdots+\lambda_{r}$v$_{r}$ şeklindeki bir elemanına doğrusal kombinasyon denir.
Her $\lambda_{1},\ldots,\lambda_{r}\in\mathbb{F}_{q}$ için
$$\lambda_{1}\mathbf{v}_{1}+\lambda_{2}\mathbf{v}_{2}+\cdots+\lambda_{r}\mathbf{v}_{r}=0 \Rightarrow \lambda_{1}=\lambda_{2}=\cdots=\lambda_{r}=0$$
ise $\{\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{r}\}$ kümesine doğrusal bağımsız denir.

Örnek 4.24

$\vek0$'ı içeren her küme doğrusal bağımlıdır.
Herhangi bir $q$ için $\{0001,0010,0100\}$ kümesi $\mathbb{F}_{q}^{4}$'ün doğrusal bağımsız bir altkümesidir.
Herhangi bir $q$ için $\{0001,1000,1001\}$ kümesi $\mathbb{F}_{q}^{4}$'ün doğrusal bağımlı bir altkümesidir.

Önerme 4.2

$V$ bir $\mathbb{F}_{q}$-uzayı ve $S=\{\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{k}\}$, $V$'nin bir altkümesi olsun. $$\left\langle S\right\rangle =\{\lambda_{1}\mathbf{v}_{1}+\lambda_{2}\mathbf{v}_{2}+\cdots+\lambda_{k}\mathbf{v}_{k}:\lambda_{1},\ldots,\lambda_{k}\in\mathbb{F}_{q}\}$$

şeklinde tanımlanan küme $V$'nin bir altuzayıdır. Aslında $\left\langle S\right\rangle $, $S$ kümesini içeren $V$'nin en küçük altuzayıdır.

Tanım 4.4

Yukarıdaki önermede görülen $\left\langle S\right\rangle$ altuzayına $V$'nin $S$ tarafıdan üretilen (veya gerilen) altuzayı denir. Eğer $S=\emptyset$ ise $\left\langle S\right\rangle=\{\vek0\}$ olarak tanımlanır.
$V$'nin bir $C$ altuzayı için $C=\left\langle S\right\rangle$ olacak şekilde $V$'nin bir $S$ altkümesi varsa, yani $C$ bir $S$ kümesi tarafından üretilirse, $S$ kümesine $C$'nin bir üreteç kümesi denir.

Not 4.3

Eğer $S$, $V$'nin bir altuzayı ise bu durumda $\left\langle S\right\rangle =S$ olur.

Örnek 4.25

$q=2$ olsun. $S=\{0001,0010,0100\}$ ise $\left\langle S\right\rangle=\{0000,0001,0010,0100,0011,0101,0110,0111\}$ olur.
$q=2$ ve $S=\{0001,1000,1001\}$ ise $\left\langle S\right\rangle=\{0000,0001,1000,1001\}$ olur.
$q=3$ ve $S=\{0001,1000,1001\}$ ise $\left\langle S\right\rangle=\{0000,0001,0002,2000,1001,1002,2001,2002\}$ olur.

Tanım 4.5: Vektör Uzayının Bazı

$V$ bir $\mathbb{F}_{q}$-uzayı olsun. $V=\langle B\rangle$ olacak şekilde $V$'nin doğrusal bağımsız bir $B$ altkümesi varsa bu $B$ kümesine $V$'nin bir bazı denir.

Not 4.4

$V$ bir vektör uzayı ve $\mathscr{B}=\{\mathbf{v}_{1},\ldots,\mathbf{v}_{k}\}$, $V$'nin bir bazı ise $V$'nin her elemanı, $\mathscr{B}$'nin elemanlarının bir tek doğrusal kombinasyonu şeklinde yazılabilir. Yani $\vek v\in V$ ise $\vek v=\lambda_{1}\mathbf{v}_{1}+\cdots+\lambda_{k}\mathbf{v}_{k}$ olacak şekilde tek türlü belirli $\lambda_{1},\ldots,\lambda_{k}\in\mathbb{F}_{q}$ elemanları bulunabilir.
Her vektör uzayının en az bir bazı vardır. Bir vektör uzayının çok sayıda bazı bulunabilir.
Bir vektör uzayının tüm bazları aynı sayıda eleman içerir. Herhangi bir bazın eleman sayısına o vektör uzayının boyutu diyeceğiz ve $k$ boyutlu bir $V$ vektör uzayı için $\text{boy}_{\mathbb{F}_{q}}(V)=k$ şeklinde yazacağız.

Teorem 4.3: Boyut ve Eleman Sayısı

$V$ bir $\mathbb{F}_{q}$-uzayı ve $\text{boy}_{\mathbb{F}_{q}}(V)=k$ olsun. Buna göre:

$V$, $q^{k}$ tane eleman içerir.
$V$'nin $\dfrac{1}{k!}\prod_{i=0}^{k-1}(q^{k}-q^{i})$ tane farklı bazı vardır.

Tanım 4.6: Nokta Çarpımı ve Diklik

$\vek v=(v_{1},\ldots,v_{n})$, $\vek w=(w_{1},\ldots,w_{n})\in\mathbb{F}_{q}^{n}$ olsun.

$\vek v\cdot\vek w=v_{1}w_{1}+\cdots+v_{n}w_{n}$ şeklinde tanımlanan işleme nokta çarpımı (veya Öklid iç çarpımı) adı verilir.
$\vek v\cdot\vek w=0$ ise $\vek v$ ve $\vek w$ vektörleri için dik vektörler denir ve $\vek v\perp\vek w$ yazılır.
$S$, $\mathbb{F}_{q}^{n}$'nin boş olmayan bir altkümesi ise $S$'nin her elemanına dik olan $\mathbb{F}_{q}^{n}$'nin elemanlarından oluşan kümeye $S$ kümesinin dik tümleyeni (orthogonal complement) denir.

Not 4.5

Kolayca görülebilir ki boş olmayan her $S\subseteq\mathbb{F}_{q}^{n}$ altkümesi için $S^{\perp}$ kümesi $\mathbb{F}_{q}^{n}$'nin bir altuzayıdır ve $\left\langle S\right\rangle^{\perp}=S^{\perp}$.
Nokta çarpımı $\mathbb{F}_{q}^{n}$ üzerinde bir iç çarpımdır. Yani her ${bf}u{/bf},{bf}v{/bf},{bf}w{/bf}\in\mathbb{F}_{q}^{n}$ ve $\lambda\in\mathbb{F}_{q}$ için aşağıdakiler sağlanır:
- $\vek u\cdot\vek v=\vek v\cdot\vek u$,
- $(\lambda\vek u)\cdot\vek v=\vek u\cdot(\lambda\vek v)=\lambda(\vek u\cdot\vek v)$,
- $(\vek u+\vek v)\cdot\vek w=\vek u\cdot\vek w+\vek v\cdot\vek w$,
- $\vek u\cdot(\vek v+\vek w)=\vek u\cdot\vek v+\vek u\cdot\vek w$,
- her $\vek x\in\mathbb{F}_{q }^{n }$ için $\vek x\cdot\vek v=0$ $\iff$ $\vek v=\vek0$.

Örnek 4.26

$q=2$ ve $n=4$ olsun. $\vek u={1111}$, $\vek v=1110$ ve $\vek w=1001$ ise $\vek u\cdot\vek v=1$, $\vek u\cdot\vek w=0$ ve $\vek v\cdot\vek w=1$ bulunur. Buna göre $\vek u$ ve $\vek w$ diktir.
$q=2$ ve $S=\{0100,0101\}$ olsun. Buna göre $S^{\perp}=\{0000,0010,1000,1010\}$ olur.

Teorem 4.4: Dik Tümleyenin Boyutu

$S\subseteq\mathbb{F}_{q}^{n}$ olsun. Buna göre $$\text{boy}(\langle S\rangle)+\text{boy}(S^{\perp})=n$$

olur.

Doğrusal Kodlar

Tanım 4.7: Doğrusal Kod

$\mathbb{F}_{q}$ üzerinde, uzunluğu $n$ olan bir doğrusal kod $\mathbb{F}_{q}^{n}$'nin bir alt uzayıdır. $C$ doğrusal kodunun boyutu, $C$'nin $\mathbb{F}_{q}$ üzerindeki vektör uzayı olarak boyutu ile aynıdır.

Örnek 4.27: Doğrusal Kod Örnekleri

Aşağıdakiler birer doğrusal koddur:

$C=\{(\lambda,\ldots,\lambda):\lambda\in\mathbb{F}_{q}\}$ (tekrar kodu)
$C=\{000,001,010,011\}$ ($q=2$)
$C=\{0000,1100,2200,0001,0002,1101,1102,2201,2202\}$ ($q=3$)
$C=\{000,001,010,011,100,101,110,111\}$ ($q=2$)

Tanım 4.8: Dual Kod

$C$, $\mathbb{F}_{q}$ üzerinde uzunluğu $n$ olan bir doğrusal kod olsun. $\mathbb{F}_{q}^{n}$'nin $C^{\perp}$ alt uzayına $C$ kodunun duali denir.

Teorem 4.5: Dual Kod Özellikleri

$C$, $\mathbb{F}_{q}$ üzerinde uzunluğu $n$ olan bir doğrusal kod olsun.

$|C|=q^{\text{boy}(C)}$, yani $\text{boy}(C)=\log_{q}|C|$.
$C^{\perp}$ bir doğrusal koddur ve $\text{boy}(C)+\text{boy}(C^{\perp})=n$.
$(C^{\perp})^{\perp}=C$.

Not 4.6: Gösterim

$\mathbb{F}_{q}$ üzerinde $n$-uzunluklu ve boyutu $k$ olan bir doğrusal kod için genellikle $q$-lu [n,k]-kodu ifadesi kullanılır. Eğer, ek olarak, $C$'nin (minimum) uzaklığı $d$ ise $C$'ye kimi zaman [n,k,d]-doğrusal kodu denir.

Tanım 4.9: Kendisine dik kodlar ve öz-dual kodlar

$C$ bir doğrusal kod olsun.

$C\subseteq C^{\perp}$ ise $C$'ye bir kendisine dik (self-orthogonal) doğrusal kod,
$C=C^{\perp}$ ise $C$'ye bir öz-dual (self-dual) kod denir.

Teorem 4.6: Öz-Dual Kodların Boyutu

$n$-uzunluklu kendisine dik bir kodun boyutu $n/2$ sayısından küçük veya eşittir. $n$-uzunluklu bir öz-dual kodun boyutu $n/2$ sayısına eşittir.

$\vek x=x_1\ldots x_n,\vek y=y_1\ldots y_n\in\ff_2^n$ sözcükleri için $$\vek x\wedge \vek y = z_1\ldots z_n,$$

öyle ki her $1\le i \le n$ için $z_i=x_iy_i\in \ff_2$, işlemi tanımlansın. Aşağıdaki teorem ikili sözcükler için $\wedge$ işlemi ile ağırlık fonksiyonu arasındaki ilişkiyi göstermesi bakımından kullanışlı bir sonuçtur.

Teorem 4.7

$\vek x,\vek y\in\ff_2^n$ iki sözcük olsun. Buna göre aşağıdakiler sağlanır:

$\wt(\vek x + \vek y) = \wt(\vek x) + \wt(\vek y) - 2\wt(\vek x\wedge \vek y)$
$\wt(\vek x \wedge \vek y) \equiv \vek x \cdot\vek y \pmod{2}$.

Teorem 4.8

$\mcc$ bir ikili kod olsun.

$\mcc$ kendisine dik bir kod ve $\mcc$'nin bir üreteç matrisinin satırlarının ağırlıkları 4 ile bölünebilirse, $\mcc$'nin her kod sözcüğünün ağırlığı 4 ile bölünebilir.
Eğer $\mcc$'nin her kod sözcüğünün ağırlığı 4 ile bölünebilirse, o zaman $\mcc$ kendisine diktir.

Kanıt

(i) $G$, satırlarının ağırlıkları 4 ile bölünebilen $\mcc$'nin bir üreteç matrisi olsun. $\vek x$ ve $\vek y$, $G$'nin iki satırı olsun. O zaman

$$\begin{align} \wt(\vek x + \vek y) & = \wt(\vek x) + \wt(\vek y) - 2\wt(\vek x\wedge\vek y)\\ & \equiv 0 + 0 - 2\wt(\vek x\wedge\vek y) \pmod{4}\\ & \equiv 0 \pmod{4} \end{align}$$

ve böylece $\wt(\vek x + \vek y)$, 4 ile bölünebilir. $\mcc$'nin kod sözcükleri $G$'nin satırlarının toplamı şeklinde yazıldığından, tümevarım ile istenilen elde edilir.

(ii) $\vek x,\vek y\in \mcc$ olsun. Kabulden dolayı

$$\begin{align} 2\ (\vek x\cdot\vek y) = 2\wt(\vek x\wedge \vek y) & = 2\wt(\vek x\wedge\vek y) - \wt(\vek x) - \wt(\vek y)\\ & \equiv -\wt(\vek x + \vek y) \equiv 0 \pmod{4} \end{align}$$

olacağından, $\vek x\cdot\vek y\equiv 0 \pmod{2}$ bulunur. Böylece $\mcc$ kodu kendisine diktir.

Hamming Ağırlığı

Tanım 4.10: Hamming Ağırlığı

$\vek x$, $\mathbb{F}_{q}^{n}$ içinde bir sözcük olsun. $\text{wt}(\mathbf{x})$ ile gösterilen ve $\vek x$'in (Hamming) ağırlığı adı verilen sayı, $\vek x$'in sıfırdan farklı koordinatlarının sayısı olarak tanımlanır. Yani $$\text{wt}(\mathbf{x})=d(\mathbf{x},\mathbf{0})$$

Teorem 4.9: Uzaklık ve Ağırlık İlişkisi

$\vek x$, $\vek y$ $\in\mathbb{F}_{q}^{n}$ olsun. Buna göre $$d(\mathbf{x},\mathbf{y})=\text{wt}(\mathbf{x}-\mathbf{y})$$

olur.

Tanım 4.11: Kodun Asgari Ağırlığı

Bir $C$ kodu için

$$\text{wt}(C)=\min\{\text{wt}(\mathbf{c}):\mathbf{c}\in C,\ \mathbf{c}\neq\mathbf{0}\}$$

sayısına $C$'nin asgari ağırlığı denir.

Teorem 4.10: Doğrusal Kodun Uzaklığı

$C$ bir doğrusal kod ise $d(C)=\text{wt}(C)$ olur.

Kanıt

$C$ doğrusal olduğundan, her x, y $\in C$ için x$-$y $\in C$ olur. Dolayısıyla $$d(C)=\min\{d(\mathbf{x},\mathbf{y}):\mathbf{x},\mathbf{y}\in C,\ \mathbf{x}\neq\mathbf{y}\}$$ $$=\min\{\text{wt}(\mathbf{x}-\mathbf{y}):\mathbf{x},\mathbf{y}\in C,\ \mathbf{x}\neq\mathbf{y}\}$$ $$=\min\{\text{wt}(\mathbf{c}):\mathbf{c}\in C,\ \mathbf{c}\neq\mathbf{0}\}=\text{wt}(C)$$

elde edilir.

Not 4.7: Önemli

Bu teorem, doğrusal bir kodun uzaklığını hesaplarken tüm çiftler yerine sadece sıfırdan farklı kod sözcüklerinin ağırlıklarını kontrol etmenin yeterli olduğunu gösterir. Bu, hesaplama karmaşıklığını önemli ölçüde azaltır.

Üretec ve Eşlik-Denetim Matrisleri

Tanım 4.12: Eşlik-Denetim Matrisi

$C$ bir kod olsun.

Satırları $C$'nin bir bazı olan bir matrise $C$ kodunun bir üretec matrisi denir.
$C^{\perp}$ dual kodunun bir üretec matrisine $C$ kodunun bir eşlik-denetim matrisi denir.

Not 4.8: Üreteç ve Eşlik-Denetim Matrislerinin Boyutları

$C$ bir $[n,k]$-kodu ise $C$'nin her üretec matrisi $k\times n$ boyutlu, her eşlik-denetim matrisi ise $(n-k)\times n$ boyutludur. Bir doğrusal kodun üreteç matrisleri çok çeşitli olabilir. $k\times n$ boyutlu bir $G$ matrisinin bir $C$ kodunun üreteç matrisi olduğunu göstermek için $G$'nin satırlarının $C$'nin kod sözcükleri olduğunu ve bu satırların doğrusal bağımsız olduğunu görmek yeterlidir.

Tanım 4.13: Standart Form

Bir üretec matrisi $G=(I_{k}|A)$ biçiminde ise, burada $I_{k}$ birim matris ve $A$ herhangi bir $k\times(n-k)$ matris olmak üzere, bu üretec matrisine standart formda denir.

Örnek 4.28

$\mathbb{F}_{2}$ üzerindeki $C=\{000,101,110,011\}$ kodunun üreteç matrisleri aşağıdakilerden oluşur: $$\begin{pmatrix}1&0&1\\ 1&1&0\end{pmatrix},\quad\begin{pmatrix}1&1&0\\ 1&0&1\end{pmatrix},\quad\begin{pmatrix}0&1&1\\ 1&1&0\end{pmatrix},\quad\begin{pmatrix}1&1&0\\0&1&1\end{pmatrix}$$ $$\begin{pmatrix}1&0&1\\ 0&1&1\end{pmatrix}\ \text{(standart)},\quad\begin{pmatrix}0&1&1\\1&0&1\end{pmatrix}$$

şeklindedir.

Lemma 4.11: Üretec Matrisi ile Diklik

$C$, $\mathbb{F}_{q}$ üzerinde bir $[n,k]$-kodu ve $G$, $C$'nin bir üreteç matrisi olsun.

Her $\mathbf{v}\in\mathbb{F}_{q}^{n}$ için $\mathbf{v}\in C^{\perp}$ $\iff$ $\mathbf{v}$, $G$'nin her satırına diktir $\iff$ $\mathbf{v}G^{T}=0$.
$(n-k)\times n$ boyutlu bir $H$ matrisi için; $H$, $C$'nin bir eşlik-denetim matrisidir ancak ve ancak $H$'nin satırları doğrusal bağımsızdır ve $HG^{T}=0$ dır.

Lemma 4.12: Eşlik-Denetim Matrisi ile Diklik

$C$, $\mathbb{F}_{q}$ üzerinde bir $[n,k]$-kodu ve $H$, $C$'nin bir eşlik-denetim matrisi olsun.

Her $\mathbf{v}\in\mathbb{F}_{q}^{n}$ için $\mathbf{v}\in C$ $\iff$ $\mathbf{v}$, $H$'nin her satırına diktir $\iff$ $\mathbf{v}H^{T}=0$.
$k\times n$ boyutlu bir $G$ matrisi için; $G$, $C$'nin bir üretec matrisidir ancak ve ancak $G$'nin satırları doğrusal bağımsızdır ve $GH^{T}=0$ dır.

Teorem 4.13: Uzaklık ve Eşlik-Denetim Matrisi

$C$ bir doğrusal kod ve $H$, $C$'nin bir eşlik-denetim matrisi olsun. Buna göre

$d(C)\geq d$ ancak ve ancak $H$'nin herhangi $d-1$ adet sütunu doğrusal bağımsızdır.
$d(C)\leq d$ ancak ve ancak $H$'nin $d$ adet doğrusal bağımlı sütunu vardır.

Sonuç 4.14: Uzaklık Karakterizasyonu

$C$ bir doğrusal kod ve $H$, $C$'nin bir eşlik-denetim matrisi olsun. Buna göre aşağıdakiler denktir:

$d(C)=d$
$H$'nin herhangi $d-1$ adet sütunu doğrusal bağımsız ve $H$'nin $d$ adet doğrusal bağımlı sütunu vardır.

Örnek 4.29: Uzaklık Hesabı

$C$ bir ikili doğrusal kod ve $C$'nin bir eşlik-denetim matrisi $$H=\begin{pmatrix}1&0&1&0&0\\1&1&0&1&0\\0&1&0&0&1\end{pmatrix}$$

olsun. Herhangi bir sütun sıfır olmadığından $d(C)\geq 2$; herhangi iki sütun doğrusal bağımsız olduğundan $d(C)\geq 3$; ancak 1., 2. ve 3. sütunlar doğrusal bağımlı olduğundan $d(C)\leq 3$. O halde $d(C)=3$.

Teorem 4.15: Standart Form ve Eşlik-Denetim

$C$ bir $[n,k]$-kodu ve $G$, $C$'nin bir üretec matrisi olsun. Eğer $G=[I_{k}|X]$ şeklinde ise $H=[-X^{T}|I_{n-k}]$ matrisi $C$'nin bir eşlik-denetim matrisi olur.

Örnek 4.30: Eşlik-Denetim Matrisi Hesabı

$S=\{11101,10110,01011,11010\}$ olmak üzere $C=\langle S\rangle$ ikili doğrusal kodu için bir eşlik-denetim matrisi bulmak üzere, satırları $S$ kümesinin elemanları olan bir matris oluşturup satır indirgeme yapılır. Standart forma getirildikten sonra $H$ matrisi elde edilir.

Tanım 4.14: Eşlik-Denetim Matrisi için Standart Yapı

Bir eşlik-denetim matrisi $[Y|I_{n-k}]$ yapısında ise bu matris için "standart yapıdadır" denir.

Doğrusal Kodların Denkliği

Tanım 4.15: Denk Kodlar

$\mathbb{F}_{q}$ üzerinde iki adet $(n,M)$-kodundan biri diğerinden aşağıdaki işlemlerin bir dizisi uygulanarak elde edilebiliyorsa bu iki koda denk kodlar denir:

Kod sözcüklerinin koordinatlarının permütasyonu
Sabit bir konumdaki koordinatın sıfırdan farklı bir skaler ile çarpılması

Örnek 4.31: Denklik Örneği

$\mathbb{F}_{3}$ üzerinde $C=\{000,011,001,002,010,020,012,021,022\}$ doğrusal kodunun bir üretec matrisi $$G=\begin{pmatrix}0&1&0\\0&0&1\end{pmatrix}$$

olarak verilir. Sütunları yer değiştirerek (2. ve 3. sütunları 1. ve 2. sıralara getirerek)

$$G'=\begin{pmatrix}1&0&0\\0&1&0\end{pmatrix}$$

standart matris elde edilir. $G'$ matrisi $C$'ye denk olan $C'$ kodunun bir üretec matrisidir.

Teorem 4.16

Her doğrusal kod, standart yapıda üretec matrisine sahip bir doğrusal kod ile denktir.

Doğrusal Kodlar ile Kodlama

$C$ bir $q$-lu $[n,k,d]$-kodu olsun. $C$ kodu ile $q^{k}$ tane bilgi parçası temsil edilebilir. $\{\mathbf{r}_{1},\ldots,\mathbf{r}_{k}\}$, $C$'nin bir bazı ise her kod sözcüğü $\mathbf{v}$, tek türlü belirli $u_{1},\ldots,u_{k}\in\mathbb{F}_{q}$ için $$\mathbf{v}=u_{1}\mathbf{r}_{1}+\cdots+u_{k}\mathbf{r}_{k}$$

doğrusal kombinasyonu şeklinde yazılabilir. $G$, satırları $\mathbf{r}_{1},\ldots,\mathbf{r}_{k}$ olan $k\times n$ matris ve $\mathbf{u}=(u_{1},\ldots,u_{k})$ olsun. O zaman

$$\mathbf{v}=\mathbf{u}G=u_{1}\mathbf{r}_{1}+\cdots+u_{k}\mathbf{r}_{k}$$

olur. Tersine her $\mathbf{u}=(u_{1},\ldots,u_{k})\in\mathbb{F}_{q}^{k}$ için $\mathbf{v}=\mathbf{u}G\in C$ olur. Bu işleme kodlama denir.

Örnek 4.32: Kodlama Örneği

$$G=\begin{pmatrix}1&0&1&1&0\\0&1&0&1&1\\0&0&1&0&1\end{pmatrix}$$

olmak üzere $C$, üretec matrisi $G$ olan bir ikili $[5,3]$-kodu olsun. Buna göre $\mathbf{u}=101$ mesajı,

$$\mathbf{v}=\mathbf{u}G=(1\;0\;1)\cdot\begin{pmatrix}1&0&1&1&0\\0&1&0&1&1\\0&0&1&0&1\end{pmatrix}=10011$$

olarak kodlanır. Dikkat edilirse $5$ bitten yalnız $3$'ü mesajı taşımak için kullanılır. Bu durumda $C$ kodunun bilgi oranı $3/5$ dir.

Not 4.9: Standart Yapıda Kodlama

Standart yapıda üretec matrise sahip kodlar ile kodlama yapmak nispeten daha kolaydır. $G=[I_{k}|X]$ ise $\mathbf{u}G=(\mathbf{u},\mathbf{u}X)$ olur. Yani bir $\mathbf{u}$ mesajı kodlandığında elde edilen kod sözcüğünün ilk $k$ basamağı $\mathbf{u}$'yu verir. Geri kalan $n-k$ basamağa ise kontrol basamakları denir.

Doğrusal Kodların Çözülmesi

Tanım 4.16: Koset

$C$, $\mathbb{F}_{q}$ üzerinde $n$ uzunluklu bir doğrusal kod ve $\mathbf{u}\in\mathbb{F}_{q}^{n}$ herhangi bir sözcük olsun. $$\mathbf{u}+C=\{\mathbf{u}+\mathbf{v}:\;\mathbf{v}\in C\}$$

kümesine $C$'nin $\mathbf{u}$'yu içeren koseti denir.

Örnek 4.33: Koset Örneği

$q=2$ ve $C=\{000,101,010,111\}$ olsun. Buna göre $$\begin{aligned} 000+C&=\{000,101,010,111\}\\ 001+C&=\{001,100,011,110\} \end{aligned}$$

Dikkat edilirse $000+C=010+C=101+C=111+C$ ve $001+C=011+C=100+C=110+C=\mathbb{F}_{2}^{3}\setminus C$ olur.

Teorem 4.17: Koset Özellikleri

$C$, $\mathbb{F}_{q}$ üzerinde bir $[n,k,d]$-kodu olsun.

$\mathbb{F}_{q}^{n}$'deki her vektör $C$'nin bir koseti tarafından içerilir.
Her $\mathbf{u}\in\mathbb{F}_{q}^{n}$ için $|\mathbf{u}+C|=|C|=q^{k}$.
Her $\mathbf{u},\mathbf{v}\in\mathbb{F}_{q}^{n}$ için $\mathbf{u}\in\mathbf{v}+C$ ise $\mathbf{u}+C=\mathbf{v}+C$.
İki koset ya eşittir ya da ayrıktır.
$C$'nin toplam $q^{n-k}$ tane koseti vardır.
Her $\mathbf{u},\mathbf{v}\in\mathbb{F}_{q}^{n}$ için $\mathbf{u}-\mathbf{v}\in C$ ancak ve ancak $\mathbf{u}$ ve $\mathbf{v}$ aynı koset içindedir.

Örnek 4.34: Kosetlerin Listesi

$C=\{0000,1011,0101,1110\}$ ikili kodunu ele alalım. $C$'nin tüm kosetleri $$\begin{aligned} 0000+C&=\{0000,1011,0101,1110\}\\ 0001+C&=\{0001,1010,0100,1111\}\\ 0010+C&=\{0010,1001,0111,1100\}\\ 1000+C&=\{1000,0011,1101,0110\} \end{aligned}$$

olarak bulunur.

Tanım 4.17: Koset Öncüsü ve Koset Ağırlığı

Bir kosetteki ağırlığı en küçük olan elemanların her birine o kosetin öncüsü denir. Bir koset öncüsünün ağırlığına ise o kosetin ağırlığı denir.

Örnek 4.35: Koset Öncüleri

$C=\{0000,1011,0101,1110\}$ ikili kodu için tüm kosetler ve öncüleri: $$\begin{aligned} 0000+C&=\{{\color{red}0000},1011,0101,1110\}\\ 0001+C&=\{{\color{red}0001},1010,{\color{red}0100},1111\}\\ 0010+C&=\{{\color{red}0010},1001,0111,1100\}\\ 1000+C&=\{{\color{red}1000},0011,1101,0110\} \end{aligned}$$

$C$ bir doğrusal kod olsun. Kabul edelim ki bir $\mathbf{v}$ kod sözcüğü gönderilmiş ve $\mathbf{w}$ sözcüğü alınmış olsun. $\mathbf{e}=\mathbf{w}-\mathbf{v}\in\mathbf{w}+C$ şeklinde tanımlı $\mathbf{e}$ vektörüne hata dizgesi diyeceğiz.

$\mathbf{w}-\mathbf{e}=\mathbf{v}\in C$
$\mathbf{w}$ ile $\mathbf{e}$ hata dizgesi aynı koset içinde bulunur
$d(\mathbf{v},\mathbf{w})=\text{wt}(\mathbf{w}-\mathbf{v})=\text{wt}(\mathbf{e})$
Asgari uzaklık kod çözme kuralına göre $\mathbf{w}$, $\mathbf{v}$ şeklinde çözülürse $\mathbf{e}$, $\mathbf{w}+C$ kosetinin bir öncüsüdür

[index:coset_weight:Koset Ağırlığı]

Sendrom ile Kod Çözme

Tanım 4.18: Sendrom

$C$, $\mathbb{F}_{q}$ üzerinde bir $[n,k]$-kodu ve $H$, $C$'nin bir eşlik-denetim matrisi olsun. $\mathbf{w}\in\mathbb{F}_{q}^{n}$ için $S_{H}(\mathbf{w})=\mathbf{w}H^{T}\in\mathbb{F}_{q}^{n-k}$ sözcüğüne $\mathbf{w}$'nun $H$'ye bağlı sendromu denir.

Teorem 4.18: Sendrom Özellikleri

$C$, bir $[n,k]$-kodu ve $H$, $C$'nin bir eşlik-denetim matrisi olsun. $\mathbf{u},\mathbf{v}\in\mathbb{F}_{q}^{n}$ için

$S(\mathbf{u}+\mathbf{v})=S(\mathbf{u})+S(\mathbf{v})$
$S(\mathbf{u})=0$ ancak ve ancak $\mathbf{u}\in C$
$S(\mathbf{u})=S(\mathbf{v})$ ancak ve ancak $\mathbf{u}$ ve $\mathbf{v}$, $C$'nin aynı koseti içindedir

Not 4.10: Koset ve Sendrom İlişkisi

Bir koset, aynı sendroma sahip sözcüklerin kümesidir. Bir $C$ $[n,k]$-kodu için kosetler ile $\mathbb{F}_{q}^{n-k}$ arasında birebir bir eşleme vardır.

Tanım 4.19: Sendrom Tablosu

Koset öncüleri ile bunların sendromlarını karşılık getiren bir tabloya sendrom tablosu denir.

Önerme 4.19: Tek Öncü Koşulu

$C$ bir doğrusal kod ve $d(C)=d$ olsun. Bir $\mathbf{e}\in\mathbb{F}_{q}^{n}$ için $$\text{wt}(\mathbf{e})\leq\left\lfloor\frac{d-1}{2}\right\rfloor$$

ise $\mathbf{e}$, $C$'nin kendisini içeren kosetinin tek öncü elemanıdır.

Sendrom ile kod çözme işlemi:

Alınan $\mathbf{w}$ sözcüğü için $S(\mathbf{w})$ sendromunu hesaplarız.
Sendrom tablosundan $S(\mathbf{u})=S(\mathbf{w})$ olacak şekildeki $\mathbf{u}$ koset öncüsünü buluruz.
$\mathbf{w}$ sözcüğünü $\mathbf{v}=\mathbf{w}-\mathbf{u}$ olarak çözeriz.

Örnek 4.36: Sendrom ile Kod Çözme

$C$, bir eşlik denetim matrisi $$H=\left(\begin{array}{ccccc}1&0&1&0&0\\1&1&0&1&0\\0&1&0&0&1\end{array}\right)$$

olan bir $[5,2,3]$-kodu olsun. Buna göre $C$'nin sendrom tablosu aşağıdaki gibidir:

koset öncüsü	sendrom
00000	000
00001	001
00010	010
00100	100
01000	011
10000	110
?	101
?	111

koset öncüsü	sendrom
00000	000
00001	001
00010	010
00100	100
01000	011
10000	110
11000, 00101	101
?	111

koset öncüsü	sendrom
00000	000
00001	001
00010	010
00100	100
01000	011
10000	110
11000, 00101	101
10001, 01100	111

1 / 3

Hamming Kodları

Örnek 4.36'den de görülebileceği gibi, minimal uzaklığı $d$ olan bir kodun sendrom tablosu yapılırken, öncelikle, ağırlığı en fazla $\lfloor \frac{d-1}{2}\rfloor$ olan sözcüklerle başlanırsa, sendrom tablosunun ilk satırları, bulundukları kosetlerin tek öncü elemanları ile dolar. Dikkat edilirse ağırlığı 1 olan sözcüklerin bulunduğu kosetlere karşılık gelen sendromlar, eşlik denetim matrisinin sütunlarıdır. Bunlardan sonra ağırlığı 2 olan sözcükler gelir ki onlar da eşlik denetim matrisinin sütunlarının ikişerli doğrusal kombinasyonlarıdır.

Ağırlığı en fazla 1 olan sözcüklerin, koset öncüleri olarak sendrom tablosunu doldurduğu bir durumu göz önüne alalım. Başka bir değişle ağırlığı en fazla 1 olan sözcüklerin tüm sendromları karşılayabildiği özel bir durumu ele alıyoruz. Kolaylık olması açısından başlangıçta ikili kodları düşünelim. $n$ uzunluklu bir ikili kod için toplam $n+1$ tane ağırlığı $0$ veya $1$ olan sözcük vardır. Tüm sendromların sayısı ise ikinin bir kuvveti şeklinde olacaktır. Buna göre $n+1$ sayısı ikinin bir kuvveti olacak şekilde seçilmelidir.

Örneğin $n+1 = 8$, yani $n=7$ olsun. O zaman eşlik denetim matrisi

$$H= \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}$$

olan ikili $[7,4]$-kodu için sendrom tablosu yandaki gibidir.

Yandaki sendrom tablosundan görülebileceği gibi tüm sendromlar, koset öncüsü tek olan kosetler ile tamamen eşlenmiş durumdadır. Buna göre 1 bitlik hataların tamamı düzeltilebilir. Başka bir deyişle, bir eşlik denetim matrisi $H$ olan ikili doğrusal kodun minimum uzaklığı 3 veya 4'tür. Aslında $H$ matrisinin herhangi iki sütunu doğrusal bağımsız olduğundan $d\geq 3$ olur. Ancak doğrusal bağımlı üç sütununu bulmak mümkün olduğundan $d=3$ olur, yani bu kod bir $[7,4,3]$-kodudur.

Daha genel olarak, her $r\geq 2$ için, bir eşlik denetim matrisi $\ff_2^r$'nin tüm sıfırdan farklı vektörlerinin sütunlara yazılmasıyla elde edilebilen $n=2^{r}-1$ uzunluğunda ikili doğrusal kodun minimum uzaklığı yine 3 olur. Bu kodlara ikili Hamming kodları diyeceğiz ve herhangi birini $\mathcal{H}_{2,r}$ ile göstereceğiz.

Koset Öncüsü	Sendrom
0000000	000
1000000	001
0100000	010
0010000	011
0001000	100
0000100	101
0000010	110
0000001	111

Teorem 4.20: Hamming Kodları

$r\geq 2$ için, herhangi iki $\mathcal{H}_{2,r}$ Hamming kodu birbirine denktir ve her biri $[2^{r}-1,2^{r}-1-r,3]$-kodudur.

Örnek 4.37: $\mathcal{H}_{2,4}$

Bir $\mathcal{H}_{2,4}$ Hamming kodu için eşilk denetim matrisi

$$H= \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}$$

olarak düzenlenebilir. Hem bu matrisin hem de bir önceki sayfada verilen $H$ matrisinin sütunları $\ff_2^r$'nin tüm sıfırdan farklı vektörlerinin 1'den $2^r-1$'e kadar olan sayıların ikilik düzendeki gösterimleri olduğunu görebiliriz. Başka bir sıralama seçimek de mümkündür. Örneğin $H$'nin ilk dört sütunu $0001$, $0010$, $0100$ ve $1000$'i verecek şekilde düzenlenebilir. O zaman $H$'nin geri kalan 11 sütunu da sırasıyla $0011$, $0101$, $0110$, $1001$, $1010$, $1100$, $0111$, $1011$, $1101$, $1110$ ve $1111$'i verecek şekilde düzenlenebilir. Fakat nasıl düzenlenirse düzenlensin, elde edilen kod $\mathcal{H}_{2,4}$ ile gösterdiğimiz bir Hamming kodu olacaktır ve yukarıdaki gibi seçilen eşilk denetim matrisine sahip Hamming kodu ile birbirlerine denk olacaklardır.

Not 4.11

Yukarıdaki örnekte de bahsedildiği gibi bir Hamming kodunun eşlik denetim matrisini yazarken seçilen sütun sıralaması kodun yapısını değiştirmese de kod çözme işleminde fark yaratabilir. Bu fark genelde daha hızlı işlem yapmaya olanak tanır.

İkili Hamming Kodları ile Kod Çözme

Örnek 4.37'teki $H$ matrisi üzerinden sendrom ile kod çözmeyi kullanırsak, alınan bir sözcüğün senderomu, bir $t$ doğal sayısının ikilik düzendeki temsili olarak $H$'nin sütunları arasındadır ve Örnek 4.37'te seçilen sütun sıralamasına göre bu sütun aslında $t$-yinci sütundan başkası değildir.

Örneğin $\vek w = 100010100010101$ sözcüğü için sendrom $S(\vek w) = 1010$ olur. Bu ise $10$ sayısının ikilik düzendeki temsili olduğundan $\vek w$ sözcüğü 10. sütunun verdiği koset öncüsü olan $000000000100000$ ile aynı kosette bulunur. Başka bir deyişle hata 10. koordinattadır. O zaman $\vek w$ sözcüğü $\vek w - 000000000100000 = 100010100{\color{red}1}10101$ sözcüğü şeklinde çözülebilir.

Yukarıdaki gibi özel sütun sıralaması ile oluşturulan eşlik denetim matrisi üzerinden, Hamming kodları için aşağıdaki gibi bir kod çözme algoritması verebiliriz:

Adım 1. Alınan sözcüğün sendromunu hesapla.
Adım 2. Sendromuun ikilik düzende temsil ettiği doğal sayıyı belirle.
Adım 3. İkinci adımda bulunan sayı t ise alınan sözcükten $\vek e_t$ vektörünü çıkararak kod sözcüğünü elde et.

Tanım 4.20: Genel Hamming Kodları

$r\ge 2$ için, $\ff_q$ üzerindeki $\mcc$ kodunun bir eşlik denetim matrisi, $\ff_q^r$'nin sıfırdan farklı 1-boyutlu her alt uzayından birer eleman seçilerek sütunlara yazılmasıyla elde edilebiliyorsa bu $\mcc$ koduna bir $q$-lu Hamming kodu denir. Bu şekildeki bir $q$-lu Hamming kodunu $\mathcal{H}_{q,r}$ ile göstereceğiz.

Aşağıdaki teoremi verebiliriz:

Teorem 4.21

Aynı uzunluğa sahip her $q$-lu Hamming kodu birbirine denktir ve her biri birer $[n,n-r,3]$-kodu olur. Burada $n=(q^{r}-1)/(q-1)$ dir.

Kanıt

$\mcc$ bir $q$-lu Hamming kodu olsun. $\mcc$'nin bir eşlik denetim matrisi $H$'nin sütunları $\ff_q^r$'nin sıfırdan farklı 1-boyutlu alt uzaylarından birer eleman seçilerek oluşturulmuş olsun. Bu seçimden dolayı $H$'nin herhangi iki sütunu doğrusal bağımsız olacağından $d(\mcc)\geq 3$ olur. Ancak $H$'nin üç doğrusal bağımlı sütunu vardır. Bunu görmek için $H$'nin $u$ ve $v$ şeklinde iki farklı sütununu alalım. $u$ ve $v$ doğrusal bağımsız olduğundan, $\langle u + v \rangle \neq \langle u \rangle$ ve $\langle u + v \rangle \neq \langle v \rangle$ olur. Buna göre $H$'nin $u+v$'nin bir skaler katına eşit olan bir sütunu vardır ve bu sütun $u$ ve $v$ sütunları ile birlikte doğrusal bağımlı bir küme oluşturur. O zaman $d(\mcc)=3$ olur.

$H$'nin herhangi iki sütunu doğrusal bağımsız olduğundan $H$'nin herhangi iki sütunu birbirine benzer değildir. O zaman $H$'nin sütunları $\ff_q^r$'nin sıfırdan farklı 1-boyutlu alt uzaylarının tümünü verir. $\ff_q^r$'nin sıfırdan farklı 1-boyutlu alt uzaylarından sıfır vektörünü çıkarırsak bunlar ikişerli olarak ayrık kümelere dönüşür ve birleşimleri de $\ff_q^r\setminus\{\vek0\}$ kümesidir. Her 1-boyutlu alt uzaysa $q$ tane eleman olacağından $\ff_q^r$'nin 1-boyutlu alt uzaylarının sayısı $(q^{r}-1)/(q-1)$ olur. Buna göre $H$'nin sütun sayısı, ve ayrıca, $\mcc$'nin uzunluğu da $(q^{r}-1)/(q-1)$ olur. O zaman bir $\mcc$, $[n,n-r,3]$-kodu olur. $n$-uzunluklu herhangi iki $q$-lu Hamming kodunun yukarıdaki gibi yazılan eşlik denetim matrisleri birbirinden bir sütun permütasyonu ve/veya sütunların sıfırdan farklı skalerler ile çarpıması ile ayrılır. Dolayısıyla $n$-uzunluklu her $q$-lu Hamming kodu birbirine denktir.

Not 4.12

Yukarıdaki tanımda tarif edilen eşlik denetim matrisi oluşturma işleminin takibi önemli bir zorluk doğrabileceğinden belli bir prosedür üzerinden sütunların yazılması bu konuda ortaya çıkabilecek aksaklıkların da önlenmesinde faydalı olacaktır. Bunun için bir önerimiz var: $H$ matrisinin sütunlarını yazarken $m$ uzunluklu vektörler kullanıyoruz. Bu vektörlerden soldan sağa ilk sıfırdan farklı kooridnatı 1'e eşit olan tüm sözcükler $\ff_q^r$'nin tüm birbirinden ve sıfırdan farklı 1-boyutlu uzaylarlarını gererler. O nedenle $H$'nin sütunlarına bu vektörleri yazmak yeterlidir. Aşağıdaki örneği inceleyiniz.

Örnek 4.38

$q=3$ ve $m=3$ için $$H=\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 2 & 1 & 1 & 2 & 2 & 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 0 & 0 & 1 & 2 & 1 & 2 & 0 & 1 & 2 & 1 \end{pmatrix}$$

matrisi bir üçlü Hamming kodunun eşlik denetim matrisidir.

q-lu Hamming Kodları ile Kod Çözme

Örnek 4.38'daki gibi tanımlanan $H$ matrisine göre sendrom hesaplarsak, elde edilen üçlü sözcük, soldan sağa sıfırdan farklı ilk koordinatı 1 olan bir sözcüğün bir skaler (1 veya 2) katıdır. Yani, hesaplanan sendrom $c\cdot\vek u$ olacak şekilde sıfırdan farklı bir $c\in\ff_3$ ve soldan sağa ilk koordinatı 1'e eşit olan bir $u\in\ff_3^3$ vardır. Dikkat edilirse $u$, $H$'nin sütunlarından biridir. Diyelim ki $u$, $H$'nin t-yinci sütununda bulunuyor. O zaman hata t koordinatındadır ve hata dizgesi de $e=c\cdot\vek e_t$ olur. O zaman alınan sözcüğü $e$ kadar değiştirerek kod sözcüğünü elde ederiz.

Örneğin, Örnek 4.38'daki gibi tanımlanan $H$ matrisine göre $\vek w = 1010000002002$ sözcüğünün sendromu $S(\vek w) = 221$ olur. Bu ise $2\cdot 112$ olduğundan $\vek w$ sözcüğü 7. sütunun verdiği koset öncüsü olan $2\cdot\vek e_7$ ile aynı kosette bulunur. Başka bir deyişle hata 7. koordinattadır ve hata dizgesi $e=2\cdot\vek e_7$ olur. O zaman $\vek w$ sözcüğü $\vek w - 2\cdot\vek e_7 = 101000{\color{red}1}002002$ sözcüğü şeklinde çözülebilir.

Yukarıdaki gibi özel sütun sıralaması ile oluşturulan eşlik denetim matrisi üzerinden, $q$-lu Hamming kodları için aşağıdaki gibi bir kod çözme algoritması verebiliriz:

Adım 1. Alınan sözcüğün sendromunu hesapla.
Adım 2. Birinci adımda bulunan sendromu, sıfırdan farklı ilk koordinatı 1 olan bir $\vek u$ sözcüğünün bir skaler $c$ katı olarak yaz.
Adım 3. İkinci adımda bulunan $\vek u$'nun $H$'nin hangi sütunu olduğunu belirle.
Adım 4. Üçüncü adımda bulunan sütun t ise alınan sözcükten $c\cdot\vek e_t$ vektörünü çıkararak kod sözcüğünü elde et.