Yeni Kodların İnşası
Bu kısımda, verilen bir koddan yeni kodlar oluşturmak için kullanılan bazı yöntemleri tanımlayacağız. Bu yöntemler, delme, genişletme, kısaltma, dik toplam ve (u | u+v) inşası gibi teknikleri içerir. Ayrıca, Reed-Muller kodları gibi özel kod sınıflarını da inceleyeceğiz.
Delme Yöntemi
Teorem 5.1: Delme Teoremi
Eğer $d\geq 2$ ise $\mathcal{C}^{(i)}$ bir $[n-1,k,d^{(i)}]$-doğrusal kodudur ve $d-1\leq d^{(i)}\leq d$ eşitsizliği sağlanır. Daha açık bir ifade ile eğer $\mcc$'nin minimum ağırlığa sahip bir kod sözcüğünün $i$-yinci koordinatı sıfırdan farklı ise $d^{(i)}=d-1$, aksi takdirde $d^{(i)}=d$'dir.
Eğer $d=1$ ise $\mathcal{C}^{(i)}$ bir $[n-1,k^{(i)},d^{(i)}]$-doğrusal kodudur ve $k-1\leq k^{(i)}\leq k$ eşitsizliği sağlanır. Daha açık bir ifade ile eğer $\mcc$'nin ağırlığı $1$ olan bir kod sözcüğünün $i$-inci koordinatı sıfırdan farklı ise $k^{(i)}=k-1$, aksi takdirde $k^{(i)}=k$'dır.
Not 5.1
Bir kodu art arda birkaç koordinattan delerek kodu istenilen uzunluğa kadar kısaltabiliriz. Bu ardışık delme işlemini tek bir hamlede de yapabiliriz. $\mathcal{C}$, $\mathbb{F}_{q}$ üzerinde bir $[n,k,d]$-kodu olsun ve $T$, $t$ tane koordinattan oluşan herhangi bir küme olsun. $\mathcal{C}$ kodunun tüm kod sözcüklerinde $T$'deki koordinatların silinmesiyle elde edilen ve uzunluğu $n-t$ olan koda $T$ üzerinde delinmiş kod denir ve $\mathcal{C}^{T}$ ile gösterilir. Bu durumda eğer $T=\{i_{1},i_{2},\ldots,i_{t}\}$ ise $\mathcal{C}^{T}=(\cdots((\mathcal{C}^{(i_{1})})^{(i_{2})})\cdots)^{(i_{t})}$ olur.
Genişletme Yöntemi
Yukarıdaki yöntemin aksine, bir koda yeni bir koordinat ekleyerek daha uzun kodlar elde edebiliriz. Bir kodu genişletmenin birçok yolu vardır; en yaygın yaklaşım, yeni kodun yalnızca çift benzeri (even-like) vektörlerden oluşmasını sağlamaktır.
$\mathcal{C}$, $\mathbb{F}_{q}$ üzerinde bir $[n,k,d]$-kodu olsun. Buna göre $\widehat{\mathcal{C}}$ ile gösterilen genişletilmiş kod şu şekilde tanımlanır: $$\widehat{\mathcal{C}}=\{x_{1}x_{2}\cdots x_{n+1}\in \mathbb{F}_{q}^{n+1}\mid x_{1}x_{2}\cdots x_{n}\in \mathcal{C}\ \text{ve}\ x_{1}+x_{2}+\cdots+x_{n+1}=0\}.$$ $\widehat{\mathcal{C}}$ kodunun doğrusal olduğu kolayca görülebilir.Teorem 5.2: Genişletme Teoremi
Ayrıca, $\widehat{\mathcal{C}}$ kodu için bir eşlik denetim matrisi aşağıdaki şeklide seçilebilir:
$$\widehat{H}=\begin{pmatrix} 1 & \cdots & 1 & 1\\ & H & & 0\\ \end{pmatrix}.$$Kanıt
Yukarıdaki gibi tanımlanan bir $\widehat{G}$ matrisinin satırlarının doğrusal bağımsız olduğu açıktır. Öte yandan $\widehat{C}$ kodunun eleman sayısı değişmediğinden, boyutu hala $k$ olacaktır. Buna göre $\widehat{G}$ matrisi $\widehat{C}$ kodunun bir üretec matrisidir. Öte yandan $\widehat{H}$ matrisinin satırlarının $\widehat{G}$ matrisinin satırlarına dik olduğu kolayca doğrulanabilir. Ayrıca $H$'nin satırları doğrusal bağımsız olduğundan, $\widehat{H}$ matrisinin de satırları doğrusal bağımsız olur. Böylece $\widehat{H}$ matrisi $\widehat{C}$ kodunun bir eşlik denetim matrisidir. Genişletilmiş kodun uzaklığının en fazla 1 artacağı da kolayca görülebilir. Böylece kanıt tamamlanır.
Örnek 5.11: Genişletilmiş Hamming Kodu
Bir Hamming kodunu genişleterek genişletilmiş Hamming kodu elde ederiz. Örneğin 7-uzunluklu $\mathcal{H}_{2,3}$ kodunu genişleterek 8-uzunluklu $\widehat{\mathcal{H}_{2,3}}$ kodunu elde ederiz. Bu genişletilmiş kodun bir eşlik denetim matrisini Teorem 5.2 gereğince aşağıdaki gibi alabiliriz:
$$\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix}$$Kısaltma Yöntemi
ile gösterelim. $\mathcal{C}(T)$, $\mathcal{C}$'nin bir alt kodudur.
$\mathcal{C}(T)$ kodunun $T$ koordinatlarından delinmesiyle elde edilen ve uzunluğu $n-t$ olan koda $T$ üzerinde kısaltılmış kod denir ve $\mathcal{C}_{T}$ ile gösterilir.Örnek 5.12
olan bir ikili $[7,3,3]$-doğrusal kodu olsun ve $T=\{4,5\}$ alınsın.
Bu durumda
$$\mathcal{C}_{T}=\{00000,010111,10111,11100\}$$olur; yani kısaltılan kod bir ikili $[5,2,3]$-kodudur.
Teorem 5.3: Kısaltma-Delme ve Dual İlişkisi
- $(\mathcal{C}^{\perp})_{T}=(\mathcal{C}^{T})^{\perp}$ ve $(\mathcal{C}^{\perp})^{T}=(\mathcal{C}_{T})^{\perp}$.
Eğer $t<d$ ise $\mathcal{C}^{T}$ ve $(\mathcal{C}^{\perp})_{T}$ kodlarının boyutları sırasıyla $k$ ve $n-t-k$ olur.
Eğer $t=d$ ve $T$, minimum ağırlıklı bir kod sözcüğünün sıfırdan farklı olduğu koordinatların kümesi ise $\mathcal{C}^{T}$ ve $(\mathcal{C}^{\perp})_{T}$ kodlarının boyutları sırasıyla $k-1$ ve $n-d-k+1$ olur.
Kanıt
Önce (i)'yi gösterelim. $(\mathcal{C}^{\perp})_{T}$ içinden bir kod sözcüğü alalım. Bu sözcük, $\mathcal{C}^{\perp}$ içinde $T$ koordinatlarında sıfır olan bir sözcüğün $T$ üzerinden delinmiş hâlidir. $\mathcal{C}$ içinden herhangi bir $\mathbf{x}$ için $\mathbf{x}$'in $T$ üzerinde delinmiş hâlini $\mathbf{x}^{*}$ ile gösterirsek, ortogonallik ilişkisi korunur ve bu da $(\mathcal{C}^{\perp})_{T}\subseteq(\mathcal{C}^{T})^{\perp}$ verir. Ters kapsama için $(\mathcal{C}^{T})^{\perp}$ içindeki bir vektör, $T$ konumlarına $0$ eklenerek bir vektöre genişletilir; bu genişletilmiş vektör $\mathcal{C}$'nin her sözcüğüne diktir, dolayısıyla $\mathcal{C}^{\perp}$ içindedir ve $T$ üzerinde sıfırdır. Böylece $(\mathcal{C}^{\perp})_{T}=(\mathcal{C}^{T})^{\perp}$ elde edilir. $\mathcal{C}$ yerine $\mathcal{C}^{\perp}$ yazarak ikinci eşitlik de bulunur.
(ii) için $t<d$ olduğunu varsayalım. Bu durumda herhangi bir $n-t$ koordinat kümesi $\mathcal{C}$ kodunda sıfırdan farklı bir iz düşüme sahiptir. Dolayısıyla $\mathcal{C}^{T}$ kodunun boyutu düşmez ve $k$ olarak kalır. (i)'den
$$\dim((\mathcal{C}^{\perp})_{T})=\dim((\mathcal{C}^{T})^{\perp})=(n-t)-k$$sonucu elde edilir.
(iii) için $t=d$ olsun ve $T$, minimum ağırlıklı bir kod sözcüğünün desteği olsun. $T$'den bir koordinat çıkarıp $|S|=d-1$ olacak şekilde $S\subset T$ seçelim. (ii)'ye göre $\mathcal{C}^{S}$ kodunun boyutu $k$'dır. Ayrıca $\mathcal{C}^{S}$ içinde ağırlığı $1$ olan bir sözcük bulunduğundan, $\mathcal{C}^{T}$ kodu $\mathcal{C}^{S}$'in bu koordinattan delinmesiyle elde edilir ve boyut $1$ azalır; yani $\dim(\mathcal{C}^{T})=k-1$. Yine (i)'yi kullanarak
$$\dim((\mathcal{C}^{\perp})_{T})=(n-d)-\dim(\mathcal{C}^{T})=(n-d)-(k-1)=n-d-k+1$$bulunur.
Dik Toplam İnşası
Teorem 5.4: Dik Toplam
matrisi de $C_{1}\oplus C_{2}$ kodunun bir üretec matrisidir.
Kanıt
matrisi $C_{1}\oplus C_{2}$ kodunun bir üretec matrisidir.
Örnek 5.13
Bir ikili $[3,2,2]$-doğrusal kodu olan $C_{1}=\{000,110,101,011\}$ ile ikili $[4,1,4]$-doğrusal kodu olan $C_{2}=\{0000,1111\}$ kodu alınırsa
$$C_{1}\oplus C_{2}=\{0000000,1100000,1010000,0110000,0001111,1101111,1011111,0111111\}$$kodu bir ikili $[7,3,2]$-doğrusal kodu olur.
(u | u+v) İnşası
Teorem 5.5
matrisi $(u,u+v)$-inşası ile elde edilen $C$ kodunun bir üretec matrisidir.
Kanıt
Örnek 5.14
bir ikili $[6,3,3]$-doğrusal kodudur.
Sonuç 5.6: Özel Bir Durum
bir ikili $[2n,k+1,\min\{n,2d\}]$-doğrusal kodudur.
Kanıt
Reed-Muller Kodları
Tanım 5.1: Reed-Muller Kodları
Her $m\geq 1$ tamsayısı için aşağıdaki gibi özyineli (recursive) olarak tanımlanan ve $\mathcal{R}(1,m)$ ile gösterilen kodlara (birinci derece) Reed-Muller kodları denir:
- $\mathcal{R}(1,1)=\mathbb{F}_{2}^{2}$
- $m\geq 1$ için $$\mathcal{R}(1,m+1)=\{(\mathbf{u},\mathbf{u}):\mathbf{u}\in\mathcal{R}(1,m)\}\cup\{(\mathbf{u},\mathbf{u}+\mathbf{1}):\mathbf{u}\in\mathcal{R}(1,m)\}$$
Örnek 5.15: Reed-Muller Kodu Örneği
Teorem 5.7: Reed-Muller Kod Parametreleri
Teorem 5.8: Reed-Muller Üretec Matrisleri
- $\mathcal{R}(1,1)$ kodunun bir üretec matrisi
$$\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix}$$
olarak alınabilir.
- $G_{m}$, $\mathcal{R}(1,m)$ kodunun bir üretec matrisi ise $\mathcal{R}(1,m+1)$ kodunun bir üretec matrisi
$$G_{m+1}=\begin{pmatrix}G_{m} & G_{m}\\0\cdots 0 & 1\cdots 1\end{pmatrix}$$
olarak alınabilir.
Örnek 5.16: Üretec Matris Hesabı
üretec matrisini kullanarak
$$G_{3}=\begin{pmatrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\end{pmatrix}$$elde ederiz.
Örnek 5.17
📖 Detaya Git'da ele alınan $\widehat{\mathcal{H}_{23}}$ genişletilmiş Hamming kodunun eşlik denetim matrisinin sütunlarını aşağıdaki gibi yeniden sıralayarak $\mathcal{R}(1,3)$ kodunun bir üreteç matrisini elde ederiz. $$\begin{array}{c} {\color{red}\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{matrix}} \\[2pt] \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \end{array} \quad \longrightarrow \quad \begin{array}{c} {\color{red}\begin{matrix} 8 & 4 & 2 & 6 & 1 & 5 & 3 & 7 \end{matrix}} \\[2pt] \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} \end{array}$$
Dolayısıyla $\mathcal{R}(1,3)^{\perp}$ ile $\widehat{\mathcal{H}_{23}}$ birbirine denktir. Bu durum $m=3$ yerine herhangi bir $m\ge 2$ için doğrudur.
Teorem 5.9: Reed-Muller ve Hamming İlişkisi
Tanım 5.2: Genel Reed-Muller Kodları
- $2^{m}$ uzunluklu $\{\mathbf{0},\mathbf{1}\}$ koduna bir sıfırıncı mertebeden Reed-Muller kodu denir ve $\mathcal{R}(0,m)$ ile gösterilir.
Birinci mertebeden Reed-Muller kodları yukarıda verildiği gibidir.
- $r\geq 2$ olmak üzere her $m\geq r-1$ için
$$\mathcal{R}(r,m+1)=\begin{cases}\mathbb{F}_{2}^{2^{r}}, & m=r-1\\\{(\mathbf{u},\mathbf{u}+\mathbf{v}):\mathbf{u}\in\mathcal{R}(r,m),\mathbf{v}\in\mathcal{R}(r-1,m)\}, & m>r-1\end{cases}$$
kuralıyla özyineli olarak tanımlanan koda $r$-inci mertebeden Reed-Muller kodu denir.
Not 5.2: Uygulamalar
Reed-Muller kodları, NASA'nın Mars keşif araçlarında (Mariner 9) kullanılmıştır. Bu kodlar, düşük sinyal-gürültü oranlarında bile güvenilir iletişim sağlayabilmektedir.
Teorem 5.10: Genel Reed-Muller Kod Özellikleri
Her $0\leq i\leq j\leq m$ için $\mathcal{R}(i,m)\subseteq\mathcal{R}(j,m)$ olur.
- $\mathcal{R}(r,m)$ kodunun boyutu
$$\binom{m}{0}+\binom{m}{1}+\cdots+\binom{m}{r}$$
eşittir.
- $\mathcal{R}(r,m)$ kodunun minimum ağırlığı $2^{m-r}$'dir.
- $\mathcal{R}(m,m)^{\perp}=\{\mathbf{0}\}$'dır ve eğer $0\leq r<m$ ise $\mathcal{R}(r,m)^{\perp}=\mathcal{R}(m-r-1,m)$ olur.
Kanıt
(i) $m$ üzerine tümevarım uygulayalım. $m=1$ için doğruluğu açıktır. Ayrıca $j=m$ için de $\mathcal{R}(m,m)=\mathbb{F}_{2}^{2^{m}}$ olduğundan durum açıktır. Kabul edelim ki her $0\leq k\leq \ell<m$ için $\mathcal{R}(k,m-1)\subseteq\mathcal{R}(\ell,m-1)$ olsun. $0<i\leq j<m$ olsun. Buna göre, tanımdan,
$$\mathcal{R}(i,m)=\{(\mathbf{u},\mathbf{u}+\mathbf{v})\mid \mathbf{u}\in\mathcal{R}(i,m-1),\ \mathbf{v}\in\mathcal{R}(i-1,m-1)\}$$ $$\subseteq \{(\mathbf{u},\mathbf{u}+\mathbf{v})\mid \mathbf{u}\in\mathcal{R}(j,m-1),\ \mathbf{v}\in\mathcal{R}(j-1,m-1)\}=\mathcal{R}(j,m)$$olur. Dolayısıyla $i > 0$ için tümevarım hipotezimiz gereği (i) sağlanır.
Eğer $i=0$ ise $2^{m}$ uzunluğundaki $\one$'in (tüm-birler vektörünün) $j<m$ için $\mathcal{R}(j,m)$'de olduğunu göstermek yeterlidir. Tümevarımla $2^{m-1}$ uzunluğundaki $\one$'in $\mathcal{R}(j,m-1)$'de olduğunu kabul edelim. Bu durumda tanıma göre $\mathbf{u}=\one$ ve $\mathbf{v}=\zero$ seçimiyle $2^{m}$ uzunluğundaki tüm-birler vektörünün $\mathcal{R}(j,m)$'de olduğu görülür.
(ii) $r=m$ durumu, $\mathcal{R}(m,m)=\mathbb{F}_{2}^{2^{m}}$ olduğundan ve
$$\binom{m}{0}+\binom{m}{1}+\cdots+\binom{m}{m}=2^{m}$$eşitliğinden dolayı doğrudur. $m=1$ durumunu da kolayca doğrulayabiliriz. Şimdi her $0\leq i<m$ için $\mathcal{R}(i,m-1)$ kodunun boyutunun
$$\binom{m-1}{0}+\binom{m-1}{1}+\cdots+\binom{m-1}{i}$$olduğunu kabul edelim. $\mathcal{R}(r,m)$ kodunun boyutu, $\mathcal{R}(r,m-1)$ ve $\mathcal{R}(r-1,m-1)$ kodlarının boyutlarının toplamıdır; yani
$$\binom{m-1}{0}+\binom{m-1}{1}+\cdots+\binom{m-1}{r}+\binom{m-1}{0}+\binom{m-1}{1}+\cdots+\binom{m-1}{r-1}.$$İstenilen sonucu, binom katsayılarının temel özellikleri olan
$$\binom{m-1}{0}=\binom{m}{0}\quad\text{ve}\quad\binom{m-1}{i-1}+\binom{m-1}{i}=\binom{m}{i}$$eşitliklerinden elde edebiliriz.
(iii) Kolayca görülebilir ki iddia $m=1$, $r=0$ ve $r=m$ durumlarının herbiri için doğrudur; çünkü $\mathcal{R}(0,m)$ uzunluğu $2^{m}$ olan ikili tekrar kodudur ve $\mathcal{R}(m,m)=\mathbb{F}_{2}^{2^{m}}$'dir. Kabul edelim ki $0\leq i<m$ için $\mathcal{R}(i,m-1)$ kodunun minimum ağırlığı $2^{m-1-i}$ olsun. Buna göre $0<r<m$ için $\mathcal{R}(r,m)$ kodunun minimum ağırlığı $\min\{2\cdot 2^{m-1-r},\, 2^{m-1-(r-1)}\}=2^{m-r}$ olur.
(iv) Öncelikle $\mathcal{R}(m,m)=\mathbb{F}_{2}^{2^{m}}$ olduğundan $\mathcal{R}(m,m)^{\perp}=\{\mathbf{0}\}$ olur. $m=1$ durumunda $r=0$ olabilir. Bu durumda $\mathcal{R}(0,1)^{\perp}=\mathcal{R}(0,1)$ olduğundan iddia $m=1$ için doğrulanır. Şimdi $m>1$ ve $0\leq i<m-1$ ise $\mathcal{R}(i,m-1)^{\perp}=\mathcal{R}((m-1)-i-1,m-1)$ olduğunu kabul edelim.