Devirli Kodlar
Bu bölümde doğrusal kodların en önemli alt sınıflarından biri olan devirli kodları tanımlayacağız ve bu kodların temel özelliklerini inceleyeceğiz. Devirli kodlar, kod sözcüklerinin belirli bir düzen içinde birbirlerine dönüştürülebildiği kodlardır ve bu özellikleri sayesinde birçok uygulamada tercih edilirler. Devirli kodların analizini yaparken, sözcükleri polinomlara dönüştürerek çalışacağız. Bu nedenle devirli kodları çalışırken, $n$ uzunluklu bir sözcüğün koordinatlarını 0,1,$\ldots$, $n-1$ olarak numaralandırmak oldukça kullanışlı olacaktır. Böylece $(a_{0},a_{1},\ldots,a_{n-1})$ sözcüğünü $a_{0}+a_{1}x+\cdots+a_{n-1}x^{n-1}$ polinomuyla ilişkilendirebiliriz. Devirli kodların tanımında ve özelliklerinde bu polinom temelli gösterimi daha çok kullanacağız.
Temel Tanımlar
Tanım 7.1: Devirli Kod
Örnek 7.26: Devirli Kod Örnekleri
Aşağıdaki kodlar birer devirli koddur:
- $\{\mathbf{0}\}$, $\{\lambda\cdot\mathbf{1}:\lambda\in\mathbb{F}_{q}\}$ ve $\mathbb{F}_{q}^{n}$
- $\{000,110,101,011\}$ ikili $[3,2,2]$-doğrusal kodu
- $S(3,2)=\{0000000,1011100,0101110,0010111,1110010,0111001,1001011,1100101\}$ ikili simpleks kodu
Kolayca görülebilir ki aşağıdaki dönüşüm $\mathbb{F}_{q}$ üzerindeki vektör uzaylarının bir izomorfizmasıdır:
$$\pi:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}[x]/(x^{n}-1), \quad (a_{0},a_{1},\ldots,a_{n-1})\mapsto a_{0}+a_{1}x+\cdots+a_{n-1}x^{n-1}$$Buna göre gerektiğinde $\mathbb{F}_{q}^{n}$ uzayını $\mathbb{F}_{q}[x]/(x^{n}-1)$ ile, $(a_{0},a_{1},\ldots,a_{n-1})$ elemanını ise $a_{0}+a_{1}x+\cdots+a_{n-1}x^{n-1}$ ile özdeş tutabiliriz.
Örnek 7.27
olarak verilir.
Benzer şekilde $S(3,2)=\{0000000,1011100,0101110,0010111,1110010,0111001,1001011,1100101\}$ ikili simpleks kodunun $\pi$ dönüşümüyle elde edilen kümesi
$$\pi(S(3,2))=\{0,1+x+x^{2}+x^{4},1+x^{2}+x^{3}+x^{4},1+x+x^{3}+x^{4},1+x+x^{2}+x^{3},1+x^{2}+x^{4},1+x+x^{2}+x^{4},1+x+x^{2}+x^{3}+x^{4}\}$$olarak elde edilir.
Üretec Polinomları
Tanım 7.2: Temel İdeal
olacak şekilde bir $g\in I$ varsa $I$ idealine bir esas ideal denir. Buradaki $g$ elemanına $I$ idealinin bir üreteci denir.
Teorem 7.1
Kanıt
olacak şekilde $q(x),r(x)\in\mathbb{F}_{q}[x]$ polinomları vardır. Tüm dereceler $n$'den küçük olacağı için bu eşitlik $\ff_q[x]/(x^n-1)$ halkası içinde de doğrudur. $f(x),g(x)\in I$ olduğundan, $q(x)g(x)\in I$ ve dolayısıyla, $r(x)=f(x)-q(x)g(x)\in I$ olduğunu görürüz. $r(x)\neq 0$ olsun. Uygun bir $\lambda\in\ff_q$ skaleri için $\lambda r(x)\in I$, derecesi $g(x)$'in derecesinden küçük bir monik polinom olurdu ki bu da $g(x)$'in derecesinin en küçük olduğu varsayımımızla çelişir. O halde $r(x)=0$ olmalıdır ve böylece $f(x)=q(x)g(x)$ olur. Bu da $g(x)$'in $I$ idealinin bir üreteci olduğunu gösterir. Ayrıca, eğer başka bir polinom olan $h(x)$ de $I$'nın sıfırdan farklı en küçük dereceli monik elemanı olsaydı, o zaman $\deg(h(x))=\deg(g(x))$ ve dolayısıyla $h(x)-g(x)$ polinomu $I$ idealinin sıfırdan farklı ve derecesi $g(x)$'in derecesinden daha küçük olan bir elemanı olurdu ki bu da bir çelişkidir. Böylece $g(x)$ tektir.
olacak şekilde $q(x),r(x)\in\mathbb{F}_{q}[x]$ polinomları vardır. Buna göre
$$q(x)g(x) + r(x) \equiv 0 \pmod{x^{n}-1}$$olur. Buna göre $g(x)\in I$ olduğundan $\ff_q[x]/(x^n-1) halkası içinde $r(x)=-q(x)g(x)\in I$ olur. Eğer $r(x)\neq 0$ olursa, uygun bir $\lambda\in\ff_q$ skaleri için $\lambda r(x)\in I$ derecesi $g(x)$'in derecesinden küçük bir monik polinom olurdu ki bu da $g(x)$'in seçimi ile çelişir. O halde $r(x)=0$ olmalıdır ve böylece $xn-1=q(x)g(x)$ olur.
Tanım 7.3: Üretec Polinomu
Örnek 7.28
- $\{000,110,011,101\}$ devirli kodunun üretec polinomu $1+x$ olur.
- $S(3,2)$ simpleks kodunun üretec polinomu $1+x^{2}+x^{3}+x^{4}$ olur.
Teorem 7.2
ise $\mathbb{F}_{q}$ üzerinde $n$-uzunluklu $\prod_{i=1}^{r}(e_{i}+1)$ adet devirli kod vardır.
Kanıt
📖 Detaya Git'den bu eşleme örtendir. Diğer taraftan, $g(x)$ ve $g'(x)$, $x^n-1$ polinomunun iki monik böleni olmak üzere $\langle g(x)\rangle=\langle g'(x)\rangle$ olduğunu varsayalım. Eğer $\langle g(x)\rangle=\langle g'(x)\rangle=0$ ise $g(x)=x^n-1=g'(x)$ olur. Dolayısıyla, $\langle g(x)\rangle=\langle g'(x)\rangle\neq0$ olsun. $g(x)\in\langle g'(x)\rangle$ ve $g'(x)\in\langle g(x)\rangle$ olacağından, uygun $t(x),t'(x)\in\ff_q[x]/(x^n-1)$ elemanları için $g(x)=t(x) g'(x)$ ve $g'(x)=t'(x) g(x)$ olur. Buna göre $$t(x)g'(x)=(x^n-1)P(x) + g(x) \quad\text{ve}\quad t'(x)g(x)=(x^n-1)P'(x)+g'(x)$$
olacak şekilde $P(x),P'(x)\in\ff_q[x]$ polinomları vardır. Bu eşitliklerden, $g'(x)\mid g(x)$ ve $g(x)\mid g'(x)$ olduğunu görürüz. $g(x)$ ve $g'(x)$ polinomları monik olduğundan, $g(x)=g'(x)$ olur. Böylece eşleme birebir olur.
Teoremin ikinci kısmı için, $x^{n}-1$ polinomunun monik bölenleri $p_1(x),\ldots,p_r(x)$ ve bu bölenlerin sırasıyla $e_1,\ldots,e_r$ kez bölündüğü varsayılsın. $g(x)=\prod_{i=1}^{r}p_{i}^{f_{i}}(x)$ olsun. Burada $0\leq f_i \leq e_i$'dir. Böylece $g(x)$'in $x^n-1$'in bir böleni olması için her $f_i$'nin $e_i$'den küçük veya ona eşit olması gerekir. Her $f_i$ için $e_i+1$ farklı değer alabileceğinden, toplamda $\prod_{i=1}^{r}(e_{i}+1)$ farklı devirli kod vardır.
Örnek 7.29: 6-Uzunluklu İkili Devirli Kodlar
- $1$, $1+x$, $1+x+x^{2}$
- $(1+x)^{2}$, $(1+x)(1+x+x^{2})$, $(1+x)^{2}(1+x+x^{2})$
- $(1+x+x^{2})^{2}$, $(1+x)(1+x+x^{2})^{2}$, $1+x^{6}$
Buna göre $6$-uzunluklu 9 adet ikili devirli kod bulunmaktadır.
Not 7.1
Sözcüklerle, onların polinom karşılıkları özdeş tutulduğundan, $\pi(\mcc)=\langle g(x) \rangle$ şeklinde bir ifade, kavramsal olarak gerçeği yansıtmasa da $\mcc$ kodu ile ona karşılık gelen $\langle g(x) \rangle$ idealini birbirlerinin yerine kullanmak, amaçlarımız bakımından bir soruna neden olmadığı gibi basitliğin hatırı için tercih edeceğimiz bir yazım şeklidir. Bu nedenle çoğu zaman bir $\mcc$ devirli kodu için $\mcc$'nin üreteç polinomu $g(x)$ ise bu durumu kısaca $\mcc = \langle g(x) \rangle$ şeklinde yazarak belirteceğiz. Hatta, bir çok defa kod sözcüklerini de polinpm karşılıkları şeklinde yazacağız. Bu tür bir yazım tercihi genellikle bir devirli kod ile çalışırken, polinomlar arası cebirsel işlemlerin kullanımını mümkün kılmak ve bu işlemlerin kod sözcüklerine yansımasını daha kolay görebilmek amacıyla yapılır.
Teorem 7.3
Ek olarak, eğer $g(x)=\sum_{i=0}^{n-k} g_i x^i$ ise,
$$\begin{align*} G & = \begin{pmatrix}g_{0} & g_{1} & \cdots & \cdots & g_{n-k} & 0 & \cdots & \cdots & 0\\0 & g_{0} & g_{1} & \cdots & \cdots & g_{n-k} & \cdots & \cdots & 0\\\vdots & & & & & & & & \vdots\\0 & \cdots & \cdots & 0 & g_{0} & g_{1} & \cdots & \cdots & g_{n-k}\end{pmatrix} \\ & = \begin{pmatrix}g(x) \\ xg(x) \\ \vdots \\ x^{k-1}g(x) \end{pmatrix} \end{align*}$$ $\mcc$'nin bir üreteç matrisidir.Kanıt
Öte yandan, $\mcc = \langle g(x) \rangle$ olduğundan, $\mcc$'deki her kod sözcüğü $f(x)g(x)$ şeklinde yazılabilir. O zaman $\mcc\subseteq \{f(x)g(x) : f(x)\in \ff_q[x]\}$ olur. $g(x)$'nin derecesinin $n-k$ olduğunu kabul ettiğimizden, $f(x)g(x)$'nin derecesi $n-k+\deg(f(x))$ olur. O zaman $f(x)g(x)$'nin derecesi $n-1$'den küçük veya ona eşit olması için $\deg(f(x))$'nin $k-1$'den küçük veya ona eşit olması gerekir. Kabul edelim ki $f(x)=\sum_{j=0}^{k-1} f_j x^j$ olsun. Bu durumda,
$$f(x)g(x) = \sum_{j=0}^{k-1} f_j x^jg(x)$$olacağından, $\mcc$, $\{g(x), xg(x), x^2g(x), \ldots, x^{k-1}g(x)\}$ kümesi tarafından gerilir. $\{g(x), xg(x), x^2g(x), \ldots, x^{k-1}g(x)\}$ kümesinin $\mcc$'nin bir bazını oluşturduğunu göstermek için, bu kümenin doğrusal bağımsız olduğunu göstermek yeterlidir. Fakat bu da her $0\le i < k$ için $x^ig(x)$'nin derecesinin en fazla $n-1$ olması nedeniyle, $x^ig(x)$'lerin birbirinden farklı derecelere sahip olduğunu kullanarak kolayca gösterilebilir. Böylece $\{g(x), xg(x), x^2g(x), \ldots, x^{k-1}g(x)\}$ kümesi doğrusal bağımsız olur ve dolayısıyla da $\mcc$'nin bir bazını oluşturur.
Teoremin kalan kısmı da, $\{g(x), xg(x), x^2g(x), \ldots, x^{k-1}g(x)\}$ kümesinin $\mcc$'nin bir bazını oluşturduğunu gösterdiğimiz için, bu kümenin elemanları ile oluşturulan $G$ matrisi de $\mcc$ için bir üreteç matrisidir. Böylece teoremdeki tüm iddialar doğrulanmış olur.
Not 7.2
matrisi, standart yapıda bir üreteç matrisine indirgenebilir. Böylece sıfırdan farklı her devirli kodun standart yapıda bir üreteç matrisine sahip olduğu görülür.
Örnek 7.30: 7-Uzunluklu İkili Devirli Kodlar
ve
$$\begin{aligned} \langle(1+x)(1+x+x^{3})\rangle&=\{0000000,1011100,0101110,0010111,\\ &\qquad 1001011,1100101,1110010,0111001\} \end{aligned}$$olarak verilir.
Örnek 7.31
olduğundan, toplam 8 tane 9-uzunluklu ikili devirli kod vardır. Bu kodların üreteç polinomları sırasıyla $x^9-1$, $(x-1)(x^2+x+1)(x^6+x^3+1)$, $(x-1)(x^2+x+1)$, $(x-1)(x^6+x^3+1)$, $(x^2+x+1)(x^6+x^3+1)$, $x-1$, $x^2+x+1$ ve $x^6+x^3+1$ olur. Bu kodların boyutları sırasıyla 0, 9, 7, 6, 5, 8, 7 ve 6 olur. Aşağıdaki tabloda bu kodların üreteç polinomları ve boyutları verilmiştir.
$$\begin{array}{c|c} \text{Üreteç Polinomu} & \text{Boyut} \\ \hline x^9-1 & 0 \\ (x^2+x+1)(x^6+x^3+1) & 1 \\ (x-1)(x^6+x^3+1) & 2 \\ x^6+x^3+1 & 3 \\ (x-1)(x^2+x+1) & 6 \\ x^2+x+1 & 7 \\ x-1 & 8 \\ 1 & 9 \end{array}$$Örnek 7.32: En küçük devirli kod bulma
Bu sözcüğün polinom karşılığı $x + x^5 + x^6$ olur. O zaman bu sözcüğü içeren en küçük devirli kodun üreteç polinomunun hem $x^7-1$'i, hem de $x + x^5 + x^6$'yı bölmesi gerektiği görülür. Bir devirli kodun boyutu ile üreteç polinomunun derecesi arasındaki ilişkiyi göz önünde bulundurarak, bu kodun boyutunun mümkün olduğunca küçük olması için üreteç polinomunun derecesinin mümkün olduğunca büyük olması gerektiğini söyleyebiliriz.
$x^7-1$'i ve $x + x^5 + x^6$'yı bölen en büyük dereceli monik bölen, bu iki polinomun en büyük ortak bölenidir. Kolayca görülebilir ki bu polinom $x^3 + x + 1$ polinomudur. Böylece verilen sözcüğü içeren en küçük ikili devirli kodun üreteç polinomun $x^3 + x + 1$ bulunur. O zaman bu kodun boyutunun $7 - 3 = 4$ olduğunu görürüz. Bu kodun üreteç matrisini de Teorem 7.3$\mcc$, $\ff_q$ üzerinde $n$-uzunluklu bir devirli kod olmak üzere $\mcc = \langle g(x) \rangle$ olsun. Kabul edelim ki $\deg(g(x)) = n - k$ olun. O zaman $\mcc$'nin boyutu $k$ ve $$\{g(x), xg(x), x^2g(x), \ldots, x^{k-1}g(x)\}$$ $\mcc$'nin bir bazını oluşturur.Ek olarak, eğer $g(x)=\sum_{i=0}^{n-k} g_i x^i$ ise, $$\begin{align*} G & = \begin{pmatrix}g_{0} & g_{1} & \cdots & \cdots & g_{n-k} & 0 & \cdots & \cdots & 0\\0 & g_{0} & g_{1} & \cdots & \cdots & g_{n-k} & \cdots & \cdots & 0\\\vdots & & & & & & & & \vdots\\0 & \cdots & \cdots & 0 & g_{0} & g_{1} & \cdots & \cdots & g_{n-k}\end{pmatrix} \\ & = \begin{pmatrix}g(x) \\ xg(x) \\ \vdots \\ x^{k-1}g(x) \end{pmatrix} \end{align*}$$ $\mcc$'nin bir üreteç matrisidir.
📖 Detaya Git'deki formülasyonu kullanarak aşağıdaki gibi yazabiliriz: $$G = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}$$
📝 Ödev 7.1 (MTK698-2026) | ⏰ Son Teslim: 19.04.2026 23:59
Eşlik Denetim Polinomları
Teorem 7.4
Bir devirli kodun duali de bir devirli koddur.
Kanıt
olur. Böylece $(y_1,\ldots,y_{n-1},y_0)\in\mcc^\perp$ olur ve $\mcc^\perp$ de bir devirli kod olur.
Tanım 7.4: Karşıt polinom
Örnek 7.33
olur.
$t(x) = x + x^4 + x^7 + x^8$ polinomunun karşıt polinomu ise $$t_K(x) = x^8 t(x^{-1}) = x^8 (x^{-1} + x^{-4} + x^{-7} + x^{-8}) = x^7 + x^4 + x + 1$$olur.
olur.
Lemma 7.5: (M. Solmaz)
olur. Özel olarak $\fring{q,n}$ halkasında $u(x)v(x^{-1})=0$'dır ancak ve ancak $\vek u$ sözcüğü, $\vek v,\sigma(\vek v),\ldots,\sigma^{n-1}(\vek v)$ sözcüklerinin tümüne diktir.
Kanıt
olur.
Kolayca görülebilir ki eğer bir $h(x)$ polinomu $x^n-1$ polinomunu bölerse, o zaman $h_K(x)$ polinomu da $x^n-1$ polinomunu böler.
Teorem 7.6
Kanıt
📖 Detaya Git gereğince $h_K(x)\in\mcc^\perp$ ancak ve ancak $h_K(x)g(1/x)=0$ olur. Dolayısıyla $h_K(x)g(1/x)=0$ olduğunu göstermeliyiz. $g(x)h(x)=0$ olduğundan eşitliğin iki tarafında $x$ yerine $1/x$ yazarak $g(1/x)h(1/x)=0$ elde edilir. Bu eşitliğin iki tarafını $x^k$ ile çarparsak $$0=x^kh(1/x)g(1/x)=h_K(x)g(x)$$ elde edilir. Böylece istenen elde edilmiş olur. Teoremin son kısmı Teorem 7.6$\mcc$, $\ff_q$ üzerinde $n$-uzunluklu bir devirli kod olmak üzere $\mcc = \langle g(x) \rangle$ olsun. O zaman $\mcc^\perp$ de üreteç polinomu $h(x) = \frac{x^n-1}{g(x)}$ için $h_K(x)$ olan bir devirli koddur. Buna göre aşağıdaki matris $\mcc$'nin bir eşlik denetim matrisidir: $$H=\begin{pmatrix} h_k & \ldots & \ldots & h_0 & 0 & \ldots & \ldots & 0 \\ 0 & h_k & \ldots & \ldots & h_0 & 0 & \ldots & 0\\ \vdots & & & & & & & \vdots \end{pmatrix}$$
📖 Detaya Git gereğince açıktır.
📝 Ödev 7.2 (MTK698-2026) | ⏰ Son Teslim: 19.04.2026 23:59
15-uzunluklu ikili devirli kodların kaçı kendisine diktir? Kaçı öz dualdir?
Devirli Kodlar ile Kodlama
Devirli kodların özel yapısı sayesinde klasik kodlamadan farklı olarak, sistemli kodlama algoritmaları ortaya konulabilir. Bu bölümde iki kodlama algoritması üzerinde duracağız.
Kodlama Algoritması I
Bir $\vek m\in\ff_q^k$ mesajı seçip onun polinom karşılığını $m(x)$ ile gösterelim. Buna göre $m(x)$ polinomu ya sıfırdır ya da derecesi en fazla $k-1$ olan bir polinomdur. Kabul edelim ki $m(x)$ sıfır olmasın. O zaman $x^{n-k}m(x)$ polinomunun derecesi en fazla $n-1$'dir ve ilk $n-k$ teriminin katsayısı sıfırdır. Dolayısıyla, mesaj, $x^{n-k}m(x)$ polinomunun $x^{n-k},x^{n-k+1},\ldots,x^{n-1}$ terimleri ile taşınır. Bölme algoritması ile
$$x^{n-k}m(x) = g(x)a(x) + r(x) \quad \text{ve}\quad r(x)=0 \text{ veya }\deg r(x) < n-k$$olacak şekilde $a(x),r(x)\in\ff_q[x]$ polinomları vardır. $c(x) = x^{n-k}m(x) - r(x)$ olsun. Buna göre $c(x)$, $g(x)$'in katı olduğundan $\mcc$ kodunun bir sözcüğüdür. Ayrıca, $r(x) = 0$ veya $\deg r(x) < n-k$ olduğundan $c(x)$ ve xn-km(x) polinomlarının $x^{n-k},x^{n-k+1},\ldots,x^{n-1}$ terimleri tıpa tıp aynıdır. Böylece $c(x)$, $\vek m$ mesajını $k$ tane bileşeni ile taşımış olur.
Kodlama Algoritması II
📖 Detaya Git'deki gibi eşlik denetim matrisi $H$ olsun. Buna göre $\frac{x^n-1}{g(x)}=h_0+h_1x+\cdots+h_kx^k$ olmak üzere $$H=\begin{pmatrix} h_k & \ldots & \ldots & h_0 & 0 & \ldots & \ldots & 0 \\ 0 & h_k & \ldots & \ldots & h_0 & 0 & \ldots & 0\\ \vdots & & & & & & & \vdots \end{pmatrix}$$
olur. Bu matrisin satırlarını $h_0^{-1}$ ile genişleterek
$$H' =\begin{pmatrix} h'_k & \ldots & \ldots & 1 & 0 & \ldots & \ldots & 0 \\ 0 & h'_k & \ldots & \ldots & 1 & 0 & \ldots & 0\\ \vdots & & & & & & & \vdots \end{pmatrix}$$şeklinde bir eşlik denetim matrisi elde edebiliriz.
$(c_0,\ldots,c_{k-1})\in\ff_q^k$ mesajını seçelim. Tek türlü belirli öyle bir $\vek c=(c_0,\ldots,c_{k-1},c_k,\ldots,c_{n-1})\in\ff_q^n$ sözcüğü vardır ki $$H\cdot\vek c^T = 0$$eşitliği sağlanır, yani $\vek c\in \mcc$'dir. Dikkat edilirse önceden belirlenen $c_0,\ldots,c_{k-1}$ bileşenleri ile geri kalan bileşenler, adım adım, her $i=k,k+1,\ldots,n-1$ için
$$c_i = -\sum_{j=0}^{i-1} c_jh'_{i-j}$$eşitlikleri ile elde edilir. Böylece mesajın ilk $k$ adet bileşende taşındığı bir kod sözcüğü elde edilmiş olur.
Eşkare Üreteçler
Tanım 7.5
Bir $R$ halkasında $e^2 = e$ şartını sağlayan $e$ elemanına eşkare (idempotent) eleman denir. Eğer $e, f \in R$ eşkare elemanları için $ef = fe = 0$ ise bu elemanlara dik (ortogonal) eşkareler adı verilir.
Bu alt başlık boyunca $\ebob{n,q}=1$ olduğunu kabul ediyoruz. $n$ ve $q$ aralarında asal olduğundan $x^n-1$ polinomunun $\ff_q$ üzerindeki indirgenemez bölenlerinin cebirsel katılılığı (multiplicty) 1'dir. Buna göre $\fring{q,n}$ bir yarı-basit halka olur. Wedderburn'ün Yapısal Teoremi gereğince her devirli kodun bir eşkare üreteci vardır. Aşağıdaki teorem ile bu eşkare üretecin tek türlü belirli olduğunu göstereceğiz.
Bir $\fring{}$ halkasının bir $\ci$ ideali özel olarak çarpımsal kapalı bir kümedir. Başka bir değişle, $\fring{}$'nin çarpma işlemi aynı zamanda $\ci$ üzerinde de tanımlıdır. $\ci$, üzerindeki çarpma işlemine göre birim elemana sahipse bu elemana $\ci$'nın birimi diyeceğiz. Başka bir deyişle her $a\in\ci$ için $ea=ae=a$ olacak şekilde $e\in \ci$ elemanı varsa bu $e$ elemanına $\ci$ idealinin birimi denir.Teorem 7.7
- $\mcc=\langle e(x)\rangle$ olacak şekilde bir eşkare $e(x)\in\mcc$ vardır.
- $e(x)\in\mcc$ sıfırdan farklı eşkare eleman olmak üzere $\mcc=\langle e(x)\rangle$ ancak ve ancak $e(x)$, $\mcc$'nin birimidir.
Kanıt
Örnek 7.34
Üreteç polinomu $g(x)=1+x+x^3$ olan $7$ uzunluklu devirli kod $\mcc$ olsun. $h(x)=(x^n-1)/g(x)$ olsun. Buna göre
$$h(x)=\frac{x^n-1}{1+x+x^3}=(1+x)(1+x^2+x^3)=1+x+x^2+x^4$$olur. $x(1+x+x^3)+1\cdot(1+x+x^2+x^4)=1$ olduğundan
$$e(x)=x(1+x+x^3)=x+x^2+x^4$$ $\mcc$'nin eşkare üretecidir.Teorem 7.8
Kanıt
Teorem 7.9
matrisi $\mcc$'nin bir üreteç matrisidir.
Kanıt
şeklinde tanımlanan kümenin de bir doğrusa kod olduğunu görmek zor değildir. Bu yeni doğrusal koda $\mcc_1$ ile $\mcc_2$'nin toplamı denir.
Teorem 7.10
- $\mcc_1\cap\mcc_2$, üreteç polinomu $\ekok{g_1(x),g_2(x)}$ ve eşkare üreteci $e_1(x)e_2(x)$ olan bir devirli koddur.
- $\mcc_1+\mcc_2$, üreteç polinomu $\ebob{g_1(x),g_2(x)}$ ve eşkare üreteci $e_1(x)+e_2(x)-e_1(x)e_2(x)$ olan bir devirli koddur.
Kanıt
(ii) Önce iki devirli kodun toplamının da yine bir devirli kod olduğunu görelim. $\mcc_1+\mcc_2$'nin $\ff_q^n$'nin bir alt uzayı olduğu açıktır. Ayrıca $\pi(\mcc_1+\mcc_2)=\pi(\mcc_1)+\pi(\mcc_2)$ ve $\pi(\mcc_i)$, $\fring{q,n}$'in bir ideali olduğundan $\pi(\mcc_1+\mcc_2)$ de $\fring{q,n}$'nin bir ideali olur. $g(x)=\ebob{g_1(x),g_2(x)}$ olsun. Öklid algoritması ile $a(x)g_1(x)+b(x)g_2(x)=g(x)$ olacak şekilde $a(x),b(x)\in\ff_q[x]$ vardır. Özel olarak, $g(x)\in\mcc_1+\mcc_2$ olur. $\mcc_1+\mcc_2$ bir devirli kod olduğundan, $\igen{g(x)}\subseteq \mcc_1+\mcc_2$ olur. Diğer taraftan $g(x)\mid g_1(x)$ ve $g(x)\mid g_2(x)$ olduğundan $\mcc_1\subseteq\igen{g(x)}$ ve $\mcc_2\subseteq\igen{g(x)}$ ve böylece $\mcc_1 + \mcc_2\subseteq\igen{g(x)}$ olur. $g(x)\mid g_1(x)$ ve $g_1(x)\mid x^n-1$ olduğundan $g(x)$, $x^n-1$'in bir monik bölenidir. Dolayısıyla, $g(x)$, $\mcc_1+\mcc_2$'nin üreteç polinomudur. $c_1(x)\in\mcc_1$ ve $c_2(x)\in\mcc_2$ olmak üzere $c(x)=c_1(x)+c_2(x)$ olsun. Buna göre
$$c(x)\left(e_1(x)+e_2(x)-e_1(x)e_2(x)\right)=c_1(x)+c_1(x)e_2(x)-c_1(x)e_2(x)+c_2(x)e_1(x)+c_2(x)-c_2(x)e_1(x)=c(x)$$olur. Öte yandan
\begin{align*} (e_1(x)+e_2(x)-e_1(x)e_2(x))^2 & = (e_1(x)+e_2(x)-e_1(x)e_2(x))(e_1(x)+e_2(x)-e_1(x)e_2(x))\\ & = e_1(x)^2+e_1(x)e_2(x)-e_1(x)^2e_2(x)+e_2(x)e_1(x)+e_2(x)^2-e_1(x)e_2(x)^2-e_1(x)^2e_2(x)-e_1(x)e_2(x)^2+e_1(x)^2e_2(x)^2\\ & = e_1(x)+e_1(x)e_2(x)-e_1(x)e_2(x)+e_1(x)e_2(x)+e_2(x)-e_1(x)e_2(x)-e_1(x)e_2(x)-e_1(x)e_2(x)+e_1(x)e_2(x)\\ & = e_1(x) + e_2(x) - e_1(x)e_2(x) \end{align*}olduğundan $e_1(x)+e_2(x)-e_1(x)e_2(x)$ bir eşkaredir. Böylece $e_1(x)+e_2(x)-e_1(x)e_2(x)$, $\mcc$'nin eşkare üretecidir.
📝 Ödev 7.3 (MTK698-2026) | ⏰ Son Teslim: 22.04.2026 23:59
İlkel Eşkareler
olsun.
Bir $\mathcal{R}$ halkasındaki sıfırdan farklı bir $\ci$ ideali ile sıfır ideali arasında başka bir ideal yoksa bu $ci$ idealine $\mathcal{R}$ halkasının bir minimal ideali denir. Başka bir deyişle, her $(0)\subset \mathcal{J}\subset \ci$ olacak şekilde bir $\mathcal{J}$ ideali yoksa $\ci$ idealine bir minimal ideal denir.Tanım 7.6
Teorem 7.11
- $\igen{\hat{f}_1(x)},\ldots,\igen{\hat{f}_s(x)}$ idealleri $\fring{q,n}$'nin tüm minimal idealleridir.
- $\ff_q$ uzayı olarak $$\fring{q,n}=\bigoplus_{i=1}^{s}\igen{\hat{f}_i(x)}.$$
- $i\neq j$ ise $\hat{e}_i(x)\hat{e}_j(x)=0.$
- $\sum_{i=1}^s \hat{e}_i(x) = 1.$
- $\igen{\hat{f}_i(x)}$ içindeki tüm eşkareler $0$ ve $\hat{e}_i(x)$'dir.
- $e(x)$, $\fring{q,n}$'in sıfırdan farklı bir eşkare elemanı olsun. O zaman $\{1,2,\ldots, s\}$ kümesinin uygun bir $T$ alt kümesi için $e(x)=\sum_{i\in T}\hat{e}_i(x)$ ve $\igen{e(x)}=\sum_{i\in T}\igen{\hat{f}_i(x)}$ olur.
Kanıt
(i) Önce her $1\le i\le s$ için $\langle \hat{f}_i(x)\rangle$ idealinin bir minimal ideal olduğunu gösterelimm. $0\subset \cj \subseteq \langle \hat{f}_i(x)\rangle$ olacak şekilde $\fring{q,n}$'nin bir $\cj$ ideali alalım. $\cj$'nin $x^n-1$'i bölen monik üreteci $g(x)$ olsun. O halde $g(x)=\hat{f}_{j_1}\ldots\hat{f}_{j_t}$ olacak şekilde $1\le j_1<\ldots<j_t\le s$ sayıları vardır. $g(x)\neq0$ olduğundan, $t<s$ ve $\{j_1,\ldots,j_t\}\subsetneq\{1,\ldots,s\}$ olur. $j\in\{1,\ldots,s\}\setminus\{j_1,\ldots,j_t\}$ olsun. $\hat{f}_i(x)\mid g(x)$ olduğundan $g(x)=\hat{f}_i(x)u(x)$ olacak şekilde $u(x)\in\fring{q,n}$ vardır. Eğer $j\neq i$ ise $f_j(x)\mid \hat{f}_i(x)$ olacağından $f_i(x)\mid g(x)$ olur --ki bu da $j$'nin seçimiyle çelişir. Dolayısıyla $\{1,\ldots,s\}\setminus\{j_1,\ldots,j_t\}=\{i\}$ ve böylece $g(x)=\hat{f}_i(x)$ olur. Böylece $\cj=\langle \hat{f}_i(x)\rangle$ olur. Dolayısıyla, $\langle \hat{f}_i(x)\rangle$, $\fring{q,n}$'nin bir minimal idealidir.
Şimdi $\ci$, $\fring{q,n}$'nin bir minimal ideali olsun. $\ci$'nın $x^n-1$'i bölen monik üreteci $g(x)$ olsun. $g(x)\neq0$ olduğundan $f_i(x)\not\mid g(x)$ olacak şekilde bir $1\le i\le s$ vardır. Bu durumda $g(x)\mid\hat{f}_i(x)$ ve böylece $0\neq\langle \hat{f}_i(x)\rangle\subseteq \ci$ olur. $\ci$ minimal olduğundan $\ci=\langle \hat{f}_i(x)\rangle$ bulunur. Böylece (i) kanıtlanmış olur.(ii) $\hat{f}_1(x),\ldots,\hat{f}_s(x)$ aralarında asal olduğundan, Öklid algoritması ile
$$\hat{f}_1(x)a_1(x)+\cdots+\hat{f}_s(x)a_s(x)=1$$olacak şekilde $a_1(x),\ldots,a_s(x)\ff_q[x]$ vardır. Buna göre her $f(x)\in\fring{q,n}$ için
$$f(x)=\hat{f}_1(x)a_1(x)f(x)+\cdots+\hat{f}_s(x)a_s(x)f(x)\in\sum_{i=1}^s \langle \hat{f}_i(x)\rangle$$olacağından
$$\fring{q,n} = \sum_{i=1}^s \langle \hat{f}_i(x)\rangle$$elde edilir. Diğer taraftan bir $1\le j\le s$ için
$$f(x)\in \langle \hat{f}_j(x)\rangle\cap\sum_{\substack{i=1\\ i\neq j}}\langle \hat{f}_i(x)\rangle$$seçersek, her $1\le i\le s$ için $i\neq j$ ise $f_j(x)\mid fi(x)$ olacağından $f_j(x)\mid f(x)$ olur. Fakat aynı zamanda $\hat{f}_i(x)\mid f(x)$ olduğundan $\fring{q,n}$'de $f(x)=0$ elde edilir. Böylece $\sum_{i=1}^s\langle \hat{f}_i(x)\rangle$ toplamı diktir. Yani
$$\fring{q,n}=\bigoplus_{i=1}^s \langle \hat{f}_i(x)\rangle$$elde edilir.
(iii)Teorem 7.7$\mcc$, $\ff_q^n$ içinde bir devirli kod olsun. O zaman
• $\mcc=\langle e(x)\rangle$ olacak şekilde bir eşkare $e(x)\in\mcc$ vardır.
• $e(x)\in\mcc$ sıfırdan farklı eşkare eleman olmak üzere $\mcc=\langle e(x)\rangle$ ancak ve ancak $e(x)$, $\mcc$'nin birimidir.
📖 Detaya Git'in kanıtında olduğu gibi $\hat{f}_i(x)c_i(x)+f_i(x)d_i(x)=1$ olacak şekildeki $c_i(x),d_i(x)\in\ff_q[x]$ polinomları için $\hat{e}_i(x)=\hat{f}_i(x)c_i(x)$ alabiliriz. Buna göre birbirinden farklı $i$ ve $j$ için
olur çünkü $x^n-1\mid \hat{f}_i(x)\hat{f}_j(x)$'dir.
(iv) (ii)'nin kanıtında olduğu gibi $\hat{f}_1(x),\ldots,\hat{f}_s(x)$ aralarında asal olduğundan, Öklid algoritması ile
$$\hat{f}_1(x)a_1(x)+\cdots+\hat{f}_s(x)a_s(x)=1\tag{1}$$olacak şekilde $a_1(x),\ldots,a_s(x)\ff_q[x]$ bulabiliriz. Aynı eşitliği $\fring{q,n}$ halkası içinde de yazabiliriz.
Her $1\le i\le s$ için $\hat{e}_i(x)\hat{f}_i(x)=\hat{f}_i(x)$ olduğunu biliyoruz. Diğer taraftan, $i\neq j$ ise $\hat{e}_i(x)\hat{f}_j(x)=\hat{e}_i(x)\hat{e}_j(x)\hat{f}_j(x)=0$ olur. Dolayısıyla (1) eşitliğinin iki tarafını $\hat{e}_i(x)$ ile çarparsak,
$$\hat{e}_i(x)=\hat{f}_i(x)a_i(x)$$eşitliğini elde ederiz Böylece $\hat{e}_1(x)+\cdots+\hat{e}_s(x)=1$ olur.
(v) $e(x)\in\igen{\hat{f}_i(x)}$ sıfırdan farklı bir eşkare olsun. $\igen{\hat{f}_i(x)}$ bir minimal ideal olduğundan $\igen{\hat{f}_i(x)}=\igen{e(x)}$ olur. Teorem 7.7$\mcc$, $\ff_q^n$ içinde bir devirli kod olsun. O zaman
• $\mcc=\langle e(x)\rangle$ olacak şekilde bir eşkare $e(x)\in\mcc$ vardır.
• $e(x)\in\mcc$ sıfırdan farklı eşkare eleman olmak üzere $\mcc=\langle e(x)\rangle$ ancak ve ancak $e(x)$, $\mcc$'nin birimidir.
📖 Detaya Git (ii)'den $e(x)$, $\igen{\hat{f}_i(x)}$'in birimi olacağından $e(x)=\hat{e}_i(x)$ olmak zorundadır.
(vi) $e(x)\fring{q,n}$ bir eşkare eleman olsun. Her $1\le i \le s$ için $e(x)\hat{e}_i(x)$, $\igen{\hat{f}_i(x)}$ içinde bir eşkare olduğundan, (v) gereğince, $e(x)\hat{e}_i(x)=0$ veya $e(x)\hat{e}_i(x)=\hat{e}_i(x)$ olur. $\hat{e}_1(x)+\cdots+\hat{e}_s(x)=1$ eşitliğinin iki tarafını $e(x)$ ile çarparsak, eşitliğin bir tarafı $e(x)$, diğer tarafı
$$\sum_{e(x)\hat{e_i(x)}\neq 0}\hat{e}_i(x)$$olur. $T=\{i:1\le i \le s,\ e(x)\hat{e}_i(x)\neq0\}$ olsun. Buna göre
$$e(x)\in\sum_{t\in T}\igen{\hat{f}_t(x)}$$olur. Diğer taraftan her $t\in T$ için $\hat{e}_t(x)=e(x)\hat{e}_t(x)\in \igen{e(x)}$ olduğundan
$$\sum_{t\in T}\igen{\hat{f}_t(x)}\subseteq\igen{e(x)}$$elde edilir. Böylece
$$\igen{e(x)}=\sum_{t\in T}\igen{\hat{f}_t(x)}$$bulunur.
Önerme 7.12
Kanıt
Teorem 7.13
olur.
Kanıt
Çarpanlar ve Devirli Kodların Denkliği
Bu kısımda, iki devirli kodun ne zaman permütasyon-denk olduğunu araştıracağız. İki kodun permütasyon-denk olması, kodların birinden diğerine koordinatlar üzerinde bir permütasyon ile geçilebilmesi demektir. Daha açık olarak, aynı $n$ uzunluğunda ve aynı kod alfabesi üzerinde tanımlı aynı büyüklükte iki $\mcc_1$ ve $\mcc_2$ kodu için eğer bir $\sigma\in\mathcal{S}_n$ varsa öyle ki her $\vek x=(x_1,\ldots,x_n)\in\mcc_1$ için $\vek x^{\sigma}=(x_{\sigma(1)},\ldots,x_{\sigma(n)})\in\mcc_2$, o zaman $\mcc_1$ ve $\mcc_2$ kodları birbirine permütasyon-denk diyeceğiz.
Çarpan
şeklinde tanımlı bir fonksiyon olsun. $(a,n)=1$ olduğundan $\mu_a$, $\{1,\ldots,n-1\}$ kümesi üzerinde bir permütasyondur. Buna göre $\mu_a\in\mathcal{S}_n$ olur. $\{1,\ldots,n-1\}$ kümesi üzerinde bu şekilde tanımlanan $\mu_a$ permütasyonuna bir çarpan denir.
şeklinde tanımlı etkiyi de $\mu_a$ ile göstereceğiz. Dikkat edilirse, $a>0$ olduğu zaman her $f(x)\in\fring{q,n}$ için
$$\mu_af(x)\equiv f(x^a)\pmod{x^n-1}\tag{2}$$olur. Öte yandan bir $a<0$ tam sayısı için $x^a$ kuvvetini
$$\mu_ax\equiv x^{\mu_a(1)}\pmod{x^n-1},$$yani $x^a=x^{(a\mod{n})}$ şeklinde tanımlayarak (2) eşitliğini negatif $a$ tamsayıları için genişletebiliriz.
Teorem 7.14
- $b\equiv a\pmod{n}$ ise $\mu_a=\mu_b$'dir.
- $\mu_a:\fring{q,n}\rightarrow\fring{q,n}$ bir halka otomorfizmasıdır.
- $e(x)\in\fring{q,n}$ bir eşkare eleman ise $\mu_ae(x)$ de bir eşkaredir.
- $\mu_q$ permütasyonunun $\sym{n}$ simetrik grubu içindeki yörüngeleri $q$'nun $n$ modülüne göre dairesel kosetleridir. Buna göre $\mu_q$'nun $\sym{n}$ içindeki mertebesi $q$'nun $(\zz_n^{*},\cdot)$ çarpımsal grubu içindeki mertebesine eşittir.
📝 Ödev 7.4 (MTK698-2026)
Not 7.3
Not 7.4
elde edilir.
Teorem 7.15
- $\mu_a\mcc$, eşkare üreteci $\mu_ae(x)$ olan bir devirli koddur;
- $\mu_qe(x)=e(x)$ ve $\mu_q\in\paut{\mcc}$.
Kanıt
- $\mu_a:\fring{q,n}\rightarrow\fring{q,n}$ bir halka otomorfizması olduğundan
$$\mu_a\mcc=\{\mu_a(e(x)f(x)):f(x)\in\fring{q,n}\}=\{(\mu_ae(x))(\mu_af(x)):f(x)\in\fring{q,n}\}=\{\mu_ae(x)h(x):h(x)\in\fring{q,n}\}=\igen{\mu_ae(x)}$$
elde edilir. Böylece (i) kanılanmış olur.
Yukarıdaki notu dikkate alırsak, $\mu_qe(x)=e(x^q)=e(x)^q$ elde edilir. Fakat $e(x)^2=e(x)$ olduğundan, tümevarım ile, $e(x)^q=e(x)$ eşitliği de yazılabilir. Böylece $\mu_qe(x)=e(x)$ bulunur. Yukarıdaki (i) şıkkından dolayı, $\mu_q\mcc=\mcc$ olacağından $\mu_q\in \paut(\mcc)$ olur.
Sonuç 7.16
Eğer $i$ ve $j$, $q$'nun $n$ modülüne göre aynı dairesel koseti içindeyse $e_i = e_j$ olur. Buna göre $q$'nun $n$ modülüne göre bir tam temsilci kümesi $T$ ise
$$e(x)=\sum_{i\in T}e_i\sum_{j\in C_i}x^j$$olacak şekilde $\{a_j\in\ff_q:j\in T\}\subseteq\ff_q$ vardır.
Eğer $q = 2$ ise,
-
$$e(x) = \sum_{i \in I} \sum_{j \in C_i} x^j$$
olacak şekilde $2$'nin $n$ modülüne göre dairesel kosetlerin temsilcilerinin bir $I$ alt kümesi vardır,
- $2$'nin $n$ modülüne göre temsilcilerinin her $I$ alt kümesi için $\mathcal{R}_n$ halkasının
$$\sum_{i \in I} \sum_{j \in C_i} x^j$$
formundaki her elemanı $\mathcal{R}_n$'nin bir eşkare elemanıdır.
-
$$e(x) = \sum_{i \in I} \sum_{j \in C_i} x^j$$
Kanıt
- $0\le i\le n-1$ olsun. Teorem 7.15 (i)'den $e(x)=\mu_qe(x)=e(x^q)=\sum_{i=0}^{n-1}e_ix^{(iq \mod{n})}$ ve böylece $j\equiv iq \pmod{n}$ ise $e_i=e_j$ olur. Şimdi $i$ yerine $j$'yi alarak aynı düşünce ile $e_j=e_{(jq\mod{n})}=e_{(iq^2\mod{n})}$ elde edilir. Bu şekilde devam edilirse, tümevarım ile, her $j\in C_i$ için $e_i=e_j$ elde edilir. Böylece $e(x)$'in yazımındaki $\{x^j:j\in C_i\}$ terimlerini gruplayarak $e_i$ ortak parantezinde yazabiliriz. Böylece
$$e(x)=\sum_{i\in T}e_j\sum_{j\in C_i}x^j$$
yazabiliriz.
(a) şıkkı yukarıdaki maddenin doğrudan sonucudur. (b) şıkkı için $I$, $2$'nin $n$ modülüne göre dairesel kosetlerinin temsilcilerininin bir alt kümesi olmak üzere
$$e(x)=\sum_{i\in I}\sum_{j\in C_i}x^j$$olsun. O zaman
$$e(x)^2=\sum_{i\in I}\sum_{j\in C_i}x^{2j}=\sum_{i\in I}\sum_{j\in C_i}x^j=e(x)$$elde edilir.
Bir Devirli Kodun Sıfırları
• $r=\frac{q^{m}-1}{n}$ diyelim.
• $\alpha\in\mathbb{F}_{q^{m}}$ bir ilkel eleman,
• $\alpha^{i}$'nin $\mathbb{F}_{q}$ üzerindeki minimal polinomu $\mathcal{M}^{(i)}(x)$,
• $\{s_{1},\ldots,s_{t}\}$, $q$'nun $n$ modülüne göre dairesel kosetlerinin bir tam temsilci kümesi olsun.
Buna göre $$x^{n}-1=\prod_{i=1}^{t}\mathcal{M}^{(rs_{i})}(x)$$ olur.
📖 Detaya Git gereğince $x^n-1$ polinomu $\ff_{q^m}$ üzerinde indirgenemez çarpanlarına ayrılabilir. (Aslında $\ff_{q^m}$, $x^n-1$ polinomunun $\ff_q$ üzerindeki parçalanış cismidir.) Eğer $r=\frac{q^m-1}{n}$ denirse, $\ff_{q^m}$'nin herhangi bir $\beta$ ilkel elemanı için $\beta^r$, birimin $n$-yinci dereceden bir ilkel kökü olur.
$\beta\in\ff_{q^m}$ bir ilkel eleman olmak üzere $\alpha=\beta^r$ olsun.
📖 Detaya Git ve Teorem 3.17$n>0$ bir tamsayı ve $(n,q)=1$ olsun. Kabul edelim ki $m>0$ tamsayısı için $n\mid q^{m}-1$ olsun.
• $r=\frac{q^{m}-1}{n}$ diyelim.
• $\alpha\in\mathbb{F}_{q^{m}}$ bir ilkel eleman,
• $\alpha^{i}$'nin $\mathbb{F}_{q}$ üzerindeki minimal polinomu $\mathcal{M}^{(i)}(x)$,
• $\{s_{1},\ldots,s_{t}\}$, $q$'nun $n$ modülüne göre dairesel kosetlerinin bir tam temsilci kümesi olsun.
Buna göre $$x^{n}-1=\prod_{i=1}^{t}\mathcal{M}^{(rs_{i})}(x)$$ olur.
📖 Detaya Git gereğince, $g(x) = \prod_s M_{\alpha^s}(x) = \prod_s \prod_{i \in C_s}(x - \alpha^i)$ şeklindedir. Burada $C_s$, $q$'nun $n$ modülüne göre $s$'yi içeren dairesel kosetidir ve $s$, bu kosetlerin temsilcilerinin belirli bir alt kümesi üzerinden değişmektedir.) Bu dairesel kosetlerin birleşimi $T = \bigcup_s C_s$ kümesi olsun. Birimin köklerinin $\mathcal{Z} = \{\alpha^i \mid i \in T\}$ kümesine $\mathcal{C}$ devirli kodunun sıfırları (zeros) ve $\{\alpha^i \mid i \notin T\}$ kümesine ise $\mathcal{C}$'nin sıfır olmayanları (nonzeros) denir. $T$ kümesine $\mathcal{C}$'nin tanımlayacı kümesi (defining set) ya da kısaca tanımlayıcısı adı verilir. (Birimin ilkel $n$-inci kökünü değiştirirsek $T$ kümesinin de değişeceğine dikkat ediniz; bu nedenle $T$, sabitlenmiş bir ilkel köke göre hesaplanır.) Dikkat edilirse, her $c(x)\in\fring{q,n}$ için $c(x)$ polinomunun $\mathcal{C}$'ye ait olması için gerek ve yeter şart, her $i \in T$ için $c(\alpha^i) = 0$ olmasıdır. Öte yandan $T$'nin (ve dolayısıyla sıfırlar kümesinin veya sıfır olmayanlar kümesinin) $g(x)$ üreteç polinomunu tamamen belirlediğine dikkat ediniz. $|T|$ değeri $g(x)$'in derecesi olduğundan, $\mathcal{C}$'nin boyutu $n - |T|$ olur.
Örnek 7.35
Aşağıdaki tablo 7 uzunluklu ikili devirli kodların üreteç polinomlarını, eşkare üreteçlerini ve tanımlayıcı kümelerini göstermektedir:
| $i$ | dim | $g_i(x)$ | $e_i(x)$ | Tanımlayıcı Küme |
|---|---|---|---|---|
| 0 | 0 | $1 + x^7$ | 0 | $\{0, 1, 2, 3, 4, 5, 6\}$ |
| 1 | 1 | $1 + x + x^2 + \dots + x^6$ | $1 + x + x^2 + \dots + x^6$ | $\{1, 2, 3, 4, 5, 6\}$ |
| 2 | 3 | $1 + x^2 + x^3 + x^4$ | $1 + x^3 + x^5 + x^6$ | $\{0, 1, 2, 4\}$ |
| 3 | 3 | $1 + x + x^2 + x^4$ | $1 + x + x^2 + x^4$ | $\{0, 3, 5, 6\}$ |
| 4 | 4 | $1 + x + x^3$ | $x + x^2 + x^4$ | $\{1, 2, 4\}$ |
| 5 | 4 | $1 + x^2 + x^3$ | $x^3 + x^5 + x^6$ | $\{3, 5, 6\}$ |
| 6 | 6 | $1 + x$ | $x + x^2 + \dots + x^6$ | $\{0\}$ |
| 7 | 7 | 1 | 1 | $\emptyset$ |
Teorem 7.17
Bu durumda, $\mathbf{c} \in \mathcal{C}$ olması için gerek ve yeter koşul $L\mathbf{c}^\mathrm{T} = \mathbf{0}$ olmasıdır. $\mathbb{F}_{q^m}$ uzayının $\mathbb{F}_q$ üzerindeki bir bazını seçerek, $\mathbb{F}_{q^m}$'nin her bir elemanını $\mathbb{F}_q$ üzerinde birer $m \times 1$ boyutlu sütun vektörü olarak temsil edebiliriz. $L$ matrisinin her bir bileşenini buna karşılık gelen sütun vektörüyle değiştirerek, $\mathbb{F}_q$ üzerinde $\mathbf{c} \in \mathcal{C} \iff H\mathbf{c}^\mathrm{T} = \mathbf{0}$ özelliğine sahip $mw \times n$ boyutlu bir $H$ matrisi elde ederiz. Özel olarak, $k \ge n - mw$ olur.
Kanıt
📖 Detaya Git gereğince her $1 \le j \le w$ için $c(\alpha^{i_j}) = 0$ olmasına denktir. Açıkça görüleceği üzere bu durum, katsayıları $\alpha$'nın kuvvetleri olan homojen bir doğrusal denklem sistemi olan $L\mathbf{c}^\mathrm{T} = \mathbf{0}$ eşitliğine denktir. $\alpha$'nın bu kuvvetlerinin her birini, $\mathbb{F}_{q^m}$'nin $\mathbb{F}_q$ üzerindeki seçilen bazına göre açmak, denk olan $H\mathbf{c}^\mathrm{T} = \mathbf{0}$ sistemini verir. $H$ matrisinin satırları doğrusal bağımlı olabileceğinden, $k \ge n - tw$ elde edilir.
Teorem 7.18
- $\mathcal{C} = \langle v(x) \rangle$ olması için gerek ve yeter koşul, $\text{ebob}(v(x), x^n - 1) = g(x)$ olmasıdır.
- $v(x)$'in $\mathcal{C}$'yi üretmesi için gerek ve yeter koşul, $v(x)$'in sıfırları olan birimin $n$-inci köklerinin tam olarak $\mathcal{C}$'nin sıfırları olmasıdır.
Kanıt
İlk olarak $\text{ebob}(v(x), x^n - 1) = g(x)$ olduğunu varsayalım. $g(x) \mid v(x)$ olduğundan, $\mathcal{R}_{q,n}$ içinde $v(x)$'in katları $g(x)$'in de katlarıdır ve dolayısıyla $\langle v(x) \rangle \subseteq \mathcal{C}$ olur. Öklid Algoritması uyarınca, $\mathbb{F}_q[x]$ içinde $g(x) = a(x)v(x) + b(x)(x^n - 1)$ olacak şekilde $a(x)$ ve $b(x)$ polinomları mevcuttur. Buradan $\mathcal{R}_{q,n}$ içinde $g(x) = a(x)v(x)$ elde edilir; böylece $\mathcal{R}_{q,n}$ içinde $g(x)$'in katları $v(x)$'in de katları olur, bu da $\langle v(x) \rangle \supseteq \mathcal{C}$ anlamına gelir. Dolayısıyla $\mathcal{C} = \langle v(x) \rangle$ elde edilir. Tersine, $\mathcal{C} = \langle v(x) \rangle$ olduğunu varsayalım. $d(x) = \text{ebob}(v(x), x^n - 1)$ olsun. $g(x) \mid v(x)$ ve $g(x) \mid (x^n - 1)$ olduğundan, $g(x) \mid d(x)$ olur. $g(x) \in \mathcal{C} = \langle v(x) \rangle$ olduğundan, $\mathcal{R}_{q,n}$ içinde $g(x) = a(x)v(x)$ olacak şekilde bir $a(x)$ polinomu vardır. O halde $\mathbb{F}_q[x]$ içinde $g(x) = a(x)v(x) + b(x)(x^n - 1)$ olacak şekilde bir $b(x)$ polinomu mevcuttur. Böylece, $d(x) \mid g(x)$ olur. Hem $d(x)$ hem de $g(x)$ monik polinomlar olduklarından ve birbirlerini böldüklerinden, $d(x) = g(x)$ olur ve (i) şıkkı sağlanır. Hem $g(x)$ hem de $x^n - 1$ polinomlarının ortak tek kökleri birimin $n$-inci kökleri olduğundan, $g(x) = \text{ebob}(v(x), x^n - 1)$ olması için gerek ve yeter koşul, $v(x)$'in sıfırları olan birimin $n$-inci köklerinin tam olarak $g(x)$'in sıfırları olmasıdır; bunlar da $\mathcal{C}$'nin sıfırlarıdır.
Sonuç 7.19
Kanıt
• $\mu_a\mcc$, eşkare üreteci $\mu_ae(x)$ olan bir devirli koddur;
• $\mu_qe(x)=e(x)$ ve $\mu_q\in\paut{\mcc}$.
📖 Detaya Git uyarınca, $\mu_a\mcc $ devirli kodunun eşkare üreteci $\mu_ae(x)$ olur. Yukarıdaki teorem gereğince, $\mathcal{C}$ ve $\mu_a\mcc$ kodlarının sıfırları, sırasıyla $e(x)$ ve $e'(x) = \mu_ae(x)$ polinomlarının da kökleri olan birimin $n$-inci kökleridir. $e'(x) = \mu_a e(x) \equiv e(x^a) \pmod{x^n - 1}$ olduğundan, $\mathbb{F}_q[x]$ içinde $e'(x) = e(x^a) + b(x)(x^n - 1)$ yazılabilir. Birimin $n$-inci kökü olan $\alpha^j$'nin $e'(x)$'in bir kökü olması için gerek ve yeter şartın $\alpha^{aj}$'nin $e(x)$'in bir kökü olması gerçeğinden hareketle istenilen elde edilir.
Eğer $\mathcal{C}$, $\mathbb{F}_q$ üzerinde uzunluğu $n$ olan bir kod ise, o zaman $\mathcal{C}$'nin tümleyeni (complement), $\mathcal{C} + \mathcal{C}^c = \mathbb{F}_q^n$ ve $\mathcal{C} \cap \mathcal{C}^c = \{\mathbf{0}\}$ koşullarını sağlayan bir $\mathcal{C}^c$ kodudur. Genel olarak, tümleyen tek türlü belirli değildir. Ancak, Teorem 7.11$\fring{q,n}$'de aşağıdakiler sağlanır.
• $\igen{\hat{f}_1(x)},\ldots,\igen{\hat{f}_s(x)}$ idealleri $\fring{q,n}$'nin tüm minimal idealleridir.
• $\ff_q$ uzayı olarak
$$\fring{q,n}=\bigoplus_{i=1}^{s}\igen{\hat{f}_i(x)}.$$
• $i\neq j$ ise $\hat{e}_i(x)\hat{e}_j(x)=0.$
• $\sum_{i=1}^s \hat{e}_i(x) = 1.$
• $\igen{\hat{f}_i(x)}$ içindeki tüm eşkareler $0$ ve $\hat{e}_i(x)$'dir.
• $e(x)$, $\fring{q,n}$'in sıfırdan farklı bir eşkare elemanı olsun. O zaman $\{1,2,\ldots, s\}$ kümesinin uygun bir $T$ alt kümesi için $e(x)=\sum_{i\in T}\hat{e}_i(x)$ ve $\igen{e(x)}=\sum_{i\in T}\igen{\hat{f}_i(x)}$ olur.
📖 Detaya Git, eğer $\mathcal{C}$ devirli bir kod ise, o zaman $\mathcal{C}$'nin yine devirli olan tek bir tümleyeni olduğunu göstermektedir. Bu koda $\mathcal{C}$'nin devirli tümleyeni (cyclic complement) diyoruz. Aşağıdaki teoremde, devirli tümleyenin üreteç polinomunu ve eşkare üretecini veriyoruz.
Teorem 7.20
- $h(x) = (x^n - 1) / g(x)$, $\mathcal{C}^c$ için üreteç polinomudur ve $1 - e(x)$ onun eşkare üretecidir.
- $\mathcal{C}^c$, $\mathcal{R}_n$'nin $\mathcal{C}$'de bulunmayan minimal ideallerinin toplamıdır.
Eğer $\mathcal{N} = \{0, 1, \dots, n - 1\}$ ise, o zaman $\mathcal{N} \setminus T$, $\mathcal{C}^c$'nin tanımlayıcı kümesidir.
Teorem 7.21
- $\mathcal{C}^\perp = \mu_{-1}(\mathcal{C}^c)$'dir.
- $\mathcal{C}^\perp$'nin eşkare üreteci $\mu_{-1}(1 - e(x))$'dir.
Eğer $\beta_1, \dots, \beta_k$, $\mathcal{C}$'nin sıfırları ise, o zaman $\beta_1^{-1}, \dots, \beta_k^{-1}$, $\mathcal{C}^\perp$'nin sıfır olmayanlarıdır.
Eğer $\mathcal{N} = \{0, 1, \dots, n - 1\}$ ise, o zaman $\mathcal{N} \setminus (-1)T \pmod n$, $\mathcal{C}^\perp$'nin tanımlayıcı kümesidir.
Devirli Kodların Minimum Uzaklığı
Herhangi bir kodda, hata düzeltme yeteneğini belirlemek için minimum uzaklığı belirleyebilmek önemlidir. Bu nedenle, özellikle alt sınırlar olmak üzere, minimum mesafe üzerindeki sınırları bilmenin büyük faydası vardır. Bir devirli kodun minimum uzaklığı için bilinen birkaç alt sınır vardır. Bunların en eskisi, genellikle BCH Sınırı olarak adlandırılan ve BCH kodlarının tanımı için temel olan Bose–Ray-ChaudhuriR. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes,” Inform. and Control 3 (1960), 68–79.–HocquenghemA. Hocquenghem, “Codes correcteurs d’erreurs,” Chiffres (Paris) 2 (1959), 147–156. Sınırı'dır. Bu sınırın iyileştirmeleri Hartmann ve TzengC. R. P. Hartmann and K. K. Tzeng, “Generalizations of the BCH bound,” Inform. and Control 20 (1972), 489–498. ve daha sonra van Lint ve WilsonJ. H. van Lint and R. M. Wilson, “On the minimum distance of cyclic codes,” IEEE Trans. Inform. Theory IT–32 (1986), 23–40. tarafından elde edilmiştir. Bu kısımda BCH Sınırı ile van Lint ve Wilson'a ait bir sınırlandırma tekniği sunulmaktadır.
Bu bölümde $\mathcal{C}$'nin $\mathbb{F}_q$ üzerinde $n$ uzunluğunda bir devirli (cyclic) kod olduğunu ve $\alpha$'nın $\mathbb{F}_{q^m}$ içinde bir ilkel (primitive) $n$. birim kökü olduğunu varsayacağız; burada $m = \text{ord}_n(q)$. $\mathcal{C}$'nin sıfırlarının $\{\alpha^i \mid i \in T\}$ olması durumunda $T$'nin $\mathcal{C}$ için bir tanımlayıcı küme olduğunu hatırlayınız. Dolayısıyla $T$, $q$'nun $n$ modülüne göre dairesel kosetlerinin bir birleşimi olmalıdır. Eğer $\{b, b + 1, \dots, b + s - 1\}$ şeklinde $s$ ardışık tam sayıdan oluşan bir küme için,
$$\{b, b + 1, \dots, b + s - 1\} \pmod n = S \subseteq T$$şartı sağlanıyorsa, $T$'nin $s$ ardışık elemandan oluşan bir $S$ kümesi içerdiğini söyleriz. Örneğin tanımlayıcı kümesi $T = \{0,3,6,5\}$ olan, 7 uzunluğundaki ikili devirli $\mathcal{C}$ kodu için $T$, üç ardışık elemandan oluşan $S = \{5, 6, 0\}$ kümesine sahiptir.
Teorem 7.22: BCH Sınırı
Kanıt
Varsayım gereği, $\mathcal{C}$ kodunun sıfırları $\alpha^b, \alpha^{b+1}, \dots, \alpha^{b+\delta-2}$ elemanlarını içerir. $c(x)$, $\mathcal{C}$ içinde $w$ ağırlığına sahip sıfırdan farklı bir kod sözcüğü olsun ve
$$c(x) = \sum_{j=1}^{w} c_{i_j} x^{i_j}$$şeklinde tanımlansın.
Kabul edelim ki $w < \delta$ olsun. $b \le i \le b+\delta-2$ için $c(\alpha^i) = 0$ olduğundan,
$$M = \begin{bmatrix} \alpha^{i_1 b} & \alpha^{i_2 b} & \dots & \alpha^{i_w b} \\ \alpha^{i_1(b+1)} & \alpha^{i_2(b+1)} & \dots & \alpha^{i_w(b+1)} \\ & & \vdots & \\ \alpha^{i_1(b+w-1)} & \alpha^{i_2(b+w-1)} & \dots & \alpha^{i_w(b+w-1)} \end{bmatrix}$$ve $\mathbf{u} = [c_{i_1}, c_{i_2}, \dots, c_{i_w}]$ olmak üzere $M\mathbf{u}^{\text{T}} = \mathbf{0}$ elde edilir. $\mathbf{u} \neq \mathbf{0}$ olduğundan, $M$ tekil bir matristir, yani $\det M = 0$ olur. Öte yandan $\det M = \alpha^{(i_1+i_2+\dots+i_w)b} \det V$ eşitliği sağlanır; burada $V$ aşağıdaki Vandermonde matrisidir:
$$V = \begin{bmatrix} 1 & 1 & \dots & 1 \\ \alpha^{i_1} & \alpha^{i_2} & \dots & \alpha^{i_w} \\ & & \vdots & \\ \alpha^{i_1(w-1)} & \alpha^{i_2(w-1)} & \dots & \alpha^{i_w(w-1)} \end{bmatrix}$$ $\alpha^{i_j}$ elemanları birbirinden farklı olduğundan, $\det V \neq 0$ olur ki bu durum $\det M = 0$ olmasıyla çelişir. Dolayısıyla $w\ge \delta$ ve böylece $d(\mcc)\ge \delta$ elde edilir.📝 Ödev 7.5 (MTK698-2026)
Üç hata düzelten $[15, 5]$ ikili devirli kodunun üreteç polinomunu ve üreteç matrisini bulunuz.
van Lint ve Wilson 1986'da, bir devirli kodun minimum ağırlığı üzerinde alt sınırlar üretmek için kullanılabilecek teknikler sunmuştur. Burada bunlardan yalnızca van Lint–Wilson Sınırlama Tekniği olarak adlandıracağımız bir tekniği sunuyoruz. van Lint–Wilson Sınırlama Tekniği, hem BCH hem de Hartmann–Tzeng Sınırlarını ispatlamak için kullanılabilir. van Lint–Wilson Sınırlama Tekniği'ni ortaya koymak için, bir kodun tanımlayıcı kümesiyle ilişkili olan ve $n$ modülüne göre tam sayıların alt kümelerinden oluşan bir küme dizisi inşa etmeliyiz. Bunu aşağıda tarif edilen özel bir biçimde yapacağız:
$\mathcal{N} = \{0, 1, \dots, n - 1\}$ ve $S \subseteq \mathcal{N}$ olsun. $\mathcal{N}$'nin alt kümelerinden oluşan bir $I_0, I_1, I_2, \dots$ dizisi, aşağıdaki şartlar sağlandığı takdirde $S$'ye göre bağımsız bir dizi olur:- $I_0 = \emptyset$,
- $i > 0$ ise, ya $I_j \subseteq S$ ve $a \in \mathcal{N} \setminus S$ olacak şekilde bir $0 \le j < i$ için $I_i = I_j \cup \{a\}$'dır ya da bir $0 \le j < i$ ve $b \neq 0$ için $I_i = \{b\} + I_j$'dir.
Teorem 7.23: van Lint–Wilson Sınırlama Tekniği
Kanıt
İlk olarak, $I_j \subseteq S$ ve $a \in \mathcal{N} \setminus S$ olacak şekilde bir $0 \le j < i$ için $I_i = I_j \cup \{a\}$ olduğunu varsayalım. Tümevarım varsayımı gereği, $V(I_j)$ doğrusal bağımsızdır. $k \in I_j$ için
$$0 = f(\alpha^k) = c_1 \alpha^{k i_1} + c_2 \alpha^{k i_2} + \cdots + c_w \alpha^{k i_w}$$olduğundan, $\mathbf{c} = (c_1, c_2, \dots, c_w)$ vektörü $V(I_j)$ kümesine diktir. Eğer $V(I_i)$ doğrusal bağımlı ise, o zaman $(\alpha^{a i_1}, \alpha^{a i_2}, \dots, \alpha^{a i_w})$ vektörü $V(I_j)$'nin gerdiği alt uzayda yer alır ve bu nedenle $(c_1, c_2, \dots, c_w)$ vektörüne diktir. Buradan $0 = c_1 \alpha^{a i_1} + c_2 \alpha^{a i_2} + \dots + c_w \alpha^{a i_w} = f(\alpha^a)$ elde edilir ki bu durum $a \notin S$ olmasıyla çelişir.
Şimdi, $b \neq 0$ olmak üzere bir $0 \le j < i$ için $I_i = \{b\} + I_j$ olduğunu varsayalım. Bu durumda $V(I_i) = \{(\alpha^{(b+k)i_1}, \alpha^{(b+k)i_2}, \dots, \alpha^{(b+k)i_w}) \mid k \in I_j\} = \alpha^bV(I_j)$ olur. $V(I_j)$ bağımsız olduğundan, $V(I_i)$ de bağımsızdır. □
Sonuç 7.24
Kanıt
Örnek 7.36
📝 Ödev 7.6 (MTK698-2026)
📝 Ödev 7.7 (MTK698-2026)
Modulo 41 ikili devirli eşkümelerini ($2$-cyclotomic cosets) bulunuz.
- $f(x)$ sıfırdan farklı bir kod sözcüğü ve $S = \{i \in \mathcal{N} \mid f(\alpha^i) = 0\}$ olsun. Eğer $1 \in S$ ise, $f(x)$'in ya $\mathbf{0}$ ya da $1 + x + \dots + x^{40}$ olduğunu gösteriniz.
- $1 \notin S$ olduğunu varsayalım. $S = T$ veya $S = T \cup \{0\}$ olduğunu gösteriniz.
Şimdi $f(x)$'in ağırlığının 8 veya daha az olduğunu varsayalım. Bağımsız diziler inşa etme kurallarını uygulayarak, aşağıdaki kümelerin $S$'ye göre bağımsız bir dizinin parçası olduğunu gösteriniz: $\{28\}$, $\{12, 17\}$, $\{19, 22, 27\}$, $\{3, 6, 11, 30\}$, $\{11, 12, 14, 19, 38\}$, $\{6, 12, 26, 27, 29, 34\}$, $\{6, 7, 13, 27, 28, 30, 35\}$ ve $\{1, 6, 7, 13, 27, 28, 30, 35\}$.
(d) şıkkından yararlanarak $\text{wt}(f(x)) \ge 8$ olduğunu gösteriniz.
Eğer $\text{wt}(f(x)) = 8$ ise, $\{0, 14, 15, 17, 22, 29, 34, 35\}$ ve $\{0, 1, 14, 15, 17, 22, 29, 34, 35\}$ kümelerinin $S$'ye göre bağımsız olduğunu gösteriniz.
- $d \ge 9$ olduğunu gösteriniz. Aslında, $d=9$ olduğu gösterilmiştir.J. H. van Lint and R. M. Wilson, “On the minimum distance of cyclic codes,” IEEE Trans.
Inform. Theory IT–32 (1986), 23–40.
Devirli Kodlar ile Kod Çözme
Bu bölümde, Meggitt kod çözmesi olarak bilinen devirli kodlar ile kod çözme tekniğinden bahsedeceğiz. Meggitt kod çözmenin pek çok varyasyonu bulunmaktadır. Burada bunların sadece ikisi yer almaktadır.
Birinci Versiyon: $y(x)$ en fazla $n$ kez kaydırılarak listedeki ilgili hata vektörü $e(x)$ bulunur ve tüm hatalar tek seferde düzeltilir.
İkinci Versiyon: $y(x)$, $n-1$. koordinatta bir hata görünene kadar kaydırılır. Sadece bu koordinattaki hata düzeltildikten sonra, ardışık kaydırmalarla sırasıyla $n-2, n-3, \dots, 1, 0$. koordinatlardaki hatalar giderilir.
Herhangi bir $v(x) \in \mathbb{F}_q[x]$ polinomu için $R_{g(x)}(v(x))$, Bölme Algoritması uyarınca $v(x)$'in $g(x)$ ile bölümünden elde edilen kalanı göstersin. Yani; $r(x) = 0$ veya $\deg r(x) < n-k$ olmak üzere, $v(x) = g(x)f(x) + r(x)$ eşitliğini sağlayan bir tek $r(x)$ polinomu için $R_{g(x)}(v(x)) = r(x)$ şeklinde tanımlansın. Buna göre aşağıdaki özellikler sağlanır:
| Madde | Özellik |
|---|---|
| (i) | Her $v(x), v'(x) \in \mathbb{F}_q[x]$ ve $a, b \in \mathbb{F}_q$ için $R_{g(x)}(av(x) + bv'(x)) = a R_{g(x)}(v(x)) + b R_{g(x)}(v'(x))$ |
| (ii) | $R_{g(x)}(v(x) + a(x)(x^n - 1)) = R_{g(x)}(v(x))$ - Dolayısıyla $R_{g(x)}$ hem $\ff_q[x]$ hem de $\fring{q,n}$ üzerinde aynı biçimde tanımlanabilir. |
| (iii) | $R_{g(x)}(v(x)) = 0 \iff v(x) \pmod{x^n - 1} \in \mathcal{C}$ |
| (iv) | Eğer $c(x) \in \mathcal{C}$ ise, $R_{g(x)}(c(x) + e(x)) = R_{g(x)}(e(x))$ |
| (v) | Her birinin ağırlığı en fazla $t$ olan $e(x)$ ve $e'(x)$ hata vektörleri için; $R_{g(x)}(e(x)) = R_{g(x)}(e'(x)) \implies e(x) = e'(x)$ |
| (vi) | Eğer $\deg v(x) < n - k$ ise, $R_{g(x)}(v(x)) = v(x)$ |
Not: İspatlar alıştırma olarak bırakılmıştır.
Teorem 7.25
olur; burada $s_{n-k-1}$, $s(x)$ içindeki $x^{n-k-1}$ teriminin katsayısıdır.
Kanıt
Tanım gereği, $s(x) = \sum_{i=0}^{n-k-1} s_i x^i$ olmak üzere $v(x) = g(x)f(x) + s(x)$ yazılabilir. Buradan $s'(x) = R_{g(x)}(x s(x))$ olmak üzere
$$x v(x) = x g(x)f(x) + x s(x) = x g(x)f(x) + g(x)f_1(x) + s'(x)$$elde edilir. Ayrıca $x v(x) \pmod{x^n - 1} = x v(x) - (x^n - 1)v_{n-1}$ eşitliği sağlanır. Dolayısıyla, $g(x)h(x) = x^n - 1$ olmak üzere
$$\begin{aligned} x v(x) \pmod{x^n - 1} &= x g(x)f(x) + g(x)f_1(x) + s'(x) - (x^n - 1)v_{n-1} \\ &= (x f(x) + f_1(x) - h(x)v_{n-1})g(x) + s'(x) \end{aligned}$$elde edilir. $\deg s'(x) < n - k$ olduğundan, $R_{g(x)}(x v(x) \pmod{x^n - 1}) = s'(x) = R_{g(x)}(x s(x))$ olur. $g(x)$, $n - k$ dereceli monik bir polinom ve $x s(x) = \sum_{i=0}^{n-k-1} s_i x^{i+1}$ olduğundan, $x s(x)$'in $g(x)$ ile bölümünden kalan $x s(x) - g(x) s_{n-k-1}$ olarak bulunur.
Meggitt - 1. versiyon
Şimdi Meggitt Kod Çözme Algoritması'nın ilk versiyonunu verelim: Herhangi bir $v(x)$ polinomunun sendrom polinomu $S(v(x))$, aşağıdaki gibi tanımlanır:
$$S(v(x)) = R_{g(x)}(x^{n-k} v(x)).$$(iii) $R_{g(x)}(v(x)) = 0 \iff v(x) \pmod{x^n - 1} \in \mathcal{C}$ gereği, $v(x) \in \mathcal{R}_n$ için $S(v(x)) = 0$ olması için gerek ve yeter şart $v(x) \in \mathcal{C}$ olmasıdır.
Adım I. Bu adım tek seferlik bir ön hesaplamadır. $\text{wt}(e(x)) \le t$ ve $e_{n-1} \neq 0$ koşullarını sağlayan tüm $e(x) = \sum_{i=0}^{n-1} e_i x^i$ hata örüntülerinin $S(e(x))$ sendrom polinomlarını bulunuz.
- Adım II. $w(x)$'in alınan vektör olduğunu varsayalım. $S(w(x)) = R_{g(x)}(x^{n-k} w(x))$ sendrom polinomunu hesaplayınız. (iv)Eğer $c(x) \in \mathcal{C}$ ise, $R_{g(x)}(c(x) + e(x)) = R_{g(x)}(e(x))$ gereği, $c(x) \in \mathcal{C}$ olmak üzere $w(x) = c(x) + e(x)$ iken $S(w(x)) = S(e(x))$ olur.
Adım III. Eğer $S(w(x))$ sendromu Adım I'de hesaplanan listede yer alıyorsa, $e(x)$ hata polinomu biliniyor demektir ve $c(x)$ kod sözcüğünü elde etmek için bu hata polinomu $w(x)$'den çıkarılabilir. Eğer $S(w(x))$ listede yoksa Adım IV'e geçiniz.
Adım IV. Sendrom polinomu Adım I'deki listede yer alana kadar sırasıyla $x w(x), x^2 w(x), \dots$ polinomlarının sendromlarını hesaplayınız. Eğer $S(x^i w(x))$ bu listede yer alıyorsa ve $e'(x)$ hata polinomu ile ilişkiliyse, alınan vektör $w(x) - x^{n-i} e'(x)$ olarak çözülür (decoded).
Adım IV'teki hesaplama en kolay Teorem 7.25 kullanılarak gerçekleştirilir. $R_{g(x)}(x^{n-k} w(x)) = S(w(x)) = \sum_{i=0}^{n-k-1} s_i x^i$ olmak üzere;
$$\begin{aligned} S(x w(x)) &= R_{g(x)}(x^{n-k} x w(x)) = R_{g(x)}(x(x^{n-k} w(x))) = R_{g(x)}(x S(w(x))) \\ &= x S(w(x)) - s_{n-k-1} g(x) \end{aligned}$$eşitliği elde edilir. $x w(x)$'in sendromundan $x^2 w(x)$'in sendromunu elde etmek için de aynı yöntemle işlemlere devam edilir.
Örnek 7.37
Örnek Uygulama: Meggitt Algoritması ile Adım Adım Kod Çözme
Meggitt Kod Çözme Algoritması'nın adımlarını somutlaştırmak adına, tanımlayıcı kümesi $T = \{1, 2, 3, 4, 6, 8, 9, 12\}$ olan $\mathbb{F}_2$ üzerindeki $[15, 7, 5]$ ikili devirli $\mathcal{C}$ kodunu ele alalım. Burada $\alpha$, $\mathbb{F}_{16}$ içinde bir ilkel 15. birim köküdür.
Kodun üreteç polinomu $g(x) = 1 + x^4 + x^6 + x^7 + x^8$ olarak verilmiştir. Bir $e(x)$ hata polinomunun sendromu ise $S(e(x)) = R_{g(x)}(x^8 e(x))$ formülüyle hesaplanır.
Adım I. 🛠️ Ön Hesaplama ve Sendrom Tablosunun Oluşturulması:
Algoritmanın ilk aşaması olarak, $\text{wt}(e(x)) \le t$ (burada $t=2$) ve en yüksek dereceli terimi içeren ($e_{14} \neq 0$) hata örüntüleri için sendrom polinomları önceden hesaplanır. Sendromun özelliklerini kullanarak aşağıdaki tabloyu verebiliriz:
| Hata Örüntüsü $e(x)$ | Sendrom Polinomu $S(e(x))$ | Hata Örüntüsü $e(x)$ | Sendrom Polinomu $S(e(x))$ |
|---|---|---|---|
| $x^{14}$ | $x^7$ | $x^6 + x^{14}$ | $x^3 + x^5 + x^6$ |
| $x^{13} + x^{14}$ | $x^6 + x^7$ | $x^5 + x^{14}$ | $x^2 + x^4 + x^5 + x^6 + x^7$ |
| $x^{12} + x^{14}$ | $x^5 + x^7$ | $x^4 + x^{14}$ | $x + x^3 + x^4 + x^5 + x^7$ |
| $x^{11} + x^{14}$ | $x^4 + x^7$ | $x^3 + x^{14}$ | $1 + x^2 + x^3 + x^4 + x^7$ |
| $x^{10} + x^{14}$ | $x^3 + x^7$ | $x^2 + x^{14}$ | $x + x^2 + x^5 + x^6$ |
| $x^9 + x^{14}$ | $x^2 + x^7$ | $x + x^{14}$ | $1 + x + x^4 + x^5 + x^6 + x^7$ |
| $x^8 + x^{14}$ | $x + x^7$ | $1 + x^{14}$ | $1 + x^4 + x^6$ |
| $x^7 + x^{14}$ | $1 + x^7$ |
Hesaplama Notu: Örneğin $1 + x^{14}$ için sendromu bulurken önce $R_{g(x)}(x^8) = 1 + x^4 + x^6 + x^7$ olduğunu belirleyip, ardından doğrusallık özelliğini kullanarak:
$$S(1 + x^{14}) = R_{g(x)}(x^8(1 + x^{14})) = R_{g(x)}(x^8) + R_{g(x)}(x^7) = 1 + x^4 + x^6$$elde edebiliriz. Diğer değerler de benzer adımlarla üretilebilir.
Adım II. 📡 Alınan Vektör ve İlk Sendromun Hesaplanması:
Kanal üzerinden bize ulaşan sinyal (alınan vektör) şu şekilde olsun:
$$w(x) = 1 + x^4 + x^7 + x^9 + x^{10} + x^{12}$$Bu polinomun sendromunu hesapladığımızda ilk çıktımız elde edilir:
$$S(w(x)) = x + x^2 + x^6 + x^7$$Adım III. 🔍 Tablo Kontrolü (Arama - 1) Elde ettiğimiz $S(w(x)) = x + x^2 + x^6 + x^7$ polinomunu alıp Adım I'deki tablomuzda aratıyoruz. Tabloyu dikkatlice incelediğimizde bu sendromun listede yer almadığını görüyoruz. Dolayısıyla mevcut hata konfigürasyonu doğrudan çözülemez; bir sonraki aşamaya geçmemiz gerekir.
Adım IV. 🔄 Çevrimsel Kaydırma ve Kod Çözme (Döngü):
Mevcut sendrom listede olmadığı için alınan vektörü simbolik olarak kaydırıp (yani $x$ ile çarparak) yeni sendromları (4.8) formülü uyarınca dinamik olarak hesaplamaya başlıyoruz:
-
İlk Kaydırma ($x \cdot w(x)$):
$S(w(x))$ polinomunda $x^7$ teriminin katsayısı $s_7 = 1$'dir. (4.8) formülü uygulanırsa: $$\begin{aligned} S(x w(x)) &= x \cdot S(w(x)) - 1 \cdot g(x) \\ &= x(x + x^2 + x^6 + x^7) - (1 + x^4 + x^6 + x^7 + x^8) \\ &= 1 + x^2 + x^3 + x^4 + x^6 \end{aligned}$$Bu polinom da Adım I'deki referans listemizde mevcut değil. Kaydırmaya devam ediyoruz.
-
İkinci Kaydırma ($x^2 \cdot w(x)$): Bir önceki sendromda ($1 + x^2 + x^3 + x^4 + x^6$) $x^7$ terimi bulunmadığı için bu kez katsayı $s_7 = 0$ alınır:
$$\begin{aligned} S(x^2 w(x)) &= x \cdot S(x w(x)) - 0 \cdot g(x) \\ &= x(1 + x^2 + x^3 + x^4 + x^6) \\ &= x + x^3 + x^4 + x^5 + x^7 \end{aligned}$$
💡 İyi haber: Bulduğumuz bu yeni $x + x^3 + x^4 + x^5 + x^7$ sendromunu tabloda arattığımızda, $e'(x) = x^4 + x^{14}$ hata örüntüsüne karşılık geldiğini görüyoruz!
Sonuç ve Düzeltme: İki kez kaydırma yaptığımız için ($i=2$), orijinal alınan vektörümüz olan $w(x)$ polinomunu şu formülle deşifre ederiz:
$$\text{Kod Sözcüğü} = w(x) - x^{15-2} e'(x) = w(x) - x^{13}(x^4 + x^{14})$$Modulo $x^{15}-1$ altında çalıştığımız için $x^{17} \equiv x^2$ ve $x^{27} \equiv x^{12}$ denkliğini kullanarak hata vektörünü yerinde düşeriz:
$$\begin{aligned} \mathcal{C} \ni c(x) &= w(x) - (x^2 + x^{12}) \\ &= (1 + x^4 + x^7 + x^9 + x^{10} + x^{12}) - (x^2 + x^{12}) \\ &= 1 + x^2 + x^4 + x^7 + x^9 + x^{10} \end{aligned}$$Böylece hatalardan tamamen arındırılmış temiz kod sözcüğünü elde etmiş olduk. Dikkat edilirse bu çıktı, doğrudan $(1 + x^2)g(x)$ çarpımına eşittir ve kodun doğasını tam olarak yansıtır.