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

$\mcc$, $n$-uzunluklu bir $q$-lu kod olsun. Eğer her $\vek c=(c_0,c_1,\ldots,c_{n-1})\in C$ için $(c_{n-1},c_0,\ldots,c_{n-2})\in C$ ise, $\mcc$'ye bir devirli kod adı verilir.

Örnek 7.16: 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.17

$\{000,110,101,011\}$ ikili $[3,2,2]$-doğrusal kodunun $\pi$ dönüşümüyle elde edilen kümesi $$\pi(\{000,110,101,011\})=\{0,1+x,1+x^{2},x+x^{2}\}$$

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.

1 / 2

Üretec Polinomları

Tanım 7.2: Temel İdeal

$R$ bir halka ve $I$, $R$'nin bir ideali olmak üzere, eğer $$I=\langle g\rangle=\{gr:r\in R\}$$

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

$I$, $\mathbb{F}_{q}[x]/(x^{n}-1)$'in bir ideali ve $g(x)$, $I$'nın sıfırdan farklı monik elemanları arasında derecesi en küçük olanı olsun. Buna göre $g(x)$, $I$ idealinin bir üretecidir ve $x^{n}-1$ polinomunu böler. Ayrıca bu özelliklere sahip tek bir $g(x)$ polinomu vardır.

Kanıt

$g(x)$, $I$'nın sıfırdan farklı monik elemanları arasında derecesi en küçük olanı olsun. $f(x)\in I$ olsun. $f(x)\neq 0$ seçebiliriz. $\deg(f(x)) < n$'dir. Bölme algoritması ile $$f(x)=q(x)g(x)+r(x)\quad\text{ve}\quad r(x)=0\text{ veya }\deg(r(x))<\deg(g(x))$$

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.

$g(x)$ polinomunun $x^{n}-1$'i böldüğünü göstermek için de bölme algoritmasını kullanacağız. $\ff_q[x]$ içinde $x^{n}-1$ polinomunu $g(x)$'e bölelim: $$x^{n}-1=q(x)g(x)+r(x)\quad\text{ve}\quad r(x)=0\text{ veya }\deg(r(x))<\deg(g(x))$$

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 $xⁿ-1=q(x)g(x)$ olur.

Tanım 7.3: Üretec Polinomu

$I$, $\mathbb{F}_{q}[x]/(x^{n}-1)$'in bir ideali olsun. $I$'nın sıfırdan farklı monik elemanları arasında derecesi en küçük olan polinoma $I$'nın üretec polinomu adı verilir. Bir $\mcc$ devirli kodu için $\pi(\mcc)$ idealinin üretec polinomuna $\mcc$ kodunun üretec polinomu denir.

Örnek 7.18

$\{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

$\mathbb{F}_{q}^{n}$ içindeki devirli kodlar ile $x^{n}-1\in\mathbb{F}_{q}[x]$ polinomunun monik bölenleri arasında bir birebir eşleme vardır. Buna göre birbirinden farklı $p_1(x),\ldots,p_r(x)\in\ff_q[x]$ indirgenemez polinomları için $$x^{n}-1=\prod_{i=1}^{r}p_{i}^{e_{i}}(x)$$

ise $\mathbb{F}_{q}$ üzerinde $n$-uzunluklu $\prod_{i=1}^{r}(e_{i}+1)$ adet devirli kod vardır.

Kanıt

$g(x) \longmapsto \langle g(x)\rangle$ eşlemesi, $\ff_q[x]$ içindeki $x^n-1$ polinomunun monik bölenlerini $\ff_q[x]/(x^n-1)$ halkasının ideallerine eşler. Teorem 7.1$I$, $\mathbb{F}_{q}[x]/(x^{n}-1)$'in bir ideali ve $g(x)$, $I$'nın sıfırdan farklı monik elemanları arasında derecesi en küçük olanı olsun. Buna göre $g(x)$, $I$ idealinin bir üretecidir ve $x^{n}-1$ polinomunu böler. Ayrıca bu özelliklere sahip tek bir $g(x)$ polinomu vardır.
📖 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.19: 6-Uzunluklu İkili Devirli Kodlar

$6$-uzunluklu bütün ikili devirli kodları bulmak için $x^{6}-1\in\mathbb{F}_{2}[x]$ polinomunu çarpanlarına ayırırız: $$x^{6}-1=(1+x)^{2}(1+x+x^{2})^{2}$$ $x^{6}-1$ polinomunun bütün monik bölenleri:

$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

$\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.

Kanıt

$\mcc$'nin boyutunun $k$ olduğunu göstermek için, $\mcc$'nin bir bazını oluşturacak $k$ tane kod sözcüğü olduğunu göstermek yeterlidir. $g(x)$'nin derecesinin $n-k$ olduğunu kabul ettiğimizden, $x^ig(x)$'nin derecesi $n-k+i$ olur. O zaman her $0\le i < k$ için $x^ig(x)$'nin derecesi $n-1$'den küçük veya ona eşit olur. Buna göre $x^ig(x)$, $\ff_q^n$'de bir sözcük olur. Dolayısıyla $\{g(x), xg(x), x^2g(x), \ldots, x^{k-1}g(x)\}$ kümesindeki her eleman $\mcc$'nin bir kod sözcüğü olur.

Ö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

$\mcc$ sıfıdan farklı $n$-uzunluklu bir devirli kod ve $g(x)$, $\mcc$'nin üreteç polinomu olsun. $g(x)$ polinomu $x^n-1$ polinomunu böldüğünden, $g(0) \neq 0$ olur. $g(x)=\sum_{i=0}^{n-k} g_i x^i$ denirse, bu durumda $g_0\neq 0$ olur. O zaman $$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}$$

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.20: 7-Uzunluklu İkili Devirli Kodlar

$x^{7}-1=(1+x)(1+x^{2}+x^{3})(1+x+x^{3})\in\mathbb{2}[x]$ olduğundan sadece iki tane ikili $[7,3]$-devirli kodu vardır. Bunlar $$\begin{aligned} \langle(1+x)(1+x^{2}+x^{3})\rangle&=\{0000000,1110100,0111010,0011101,\\ &\qquad 1001110,0100111,1010011,1101001\} \end{aligned}$$

$$\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.21

$\ff_2$ üzerinde $$x^9 - 1 = (x-1)(x^2+x+1)(x^6+x^3+1)$$

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.22: En küçük devirli kod bulma

$0\ 1\ 0\ 0\ 0\ 1\ 1$ sözcüğünü içeren 7-uzunluklu en küçük ikili devirli kodu bulalım.

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

$\ff_2$ üzerinde 15-uzunluklu devirli kodların üreteç polinomlarını ve boyutlarını bulunuz.

Eşlik Denetim Polinomları

Teorem 7.4

Bir devirli kodun duali de bir devirli koddur.

Kanıt

$\mcc$ $n$ uzunluklu bir devirli kod ve $(y_0,\ldots,y_{n-1})\in\mcc^\perp$ olsun. $(y_1,\ldots,y_{n-1},y_0)\in\mcc^\perp$ olduğunu göstermek yeter. $(c_0,\ldots,c_{n-1})\in\mcc$ alalım. $\mcc$ devirli olduğundan, $(c_{n-1},c_0,\ldots,c_{n-2})\in\mcc$ olur. O zaman $$y_0c_{n-1}+y_1c_0+\cdots+y_{n-1}c_{n-2} = y_1c_0+y_2c_1+\cdots+y_{n-1}c_{n-2}+y_0c_{n-1} = 0$$

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

$h(x)$, $\ff_q$ üerinde $k$-yıncı dereceden bir polinom olsun. O zaman $h_K(x) = x^k h(1/x)$ polinomuna $h(x)$'nin karşıt polinomu denir.

Örnek 7.23

$\ff_2$ üzerindeki $h(x)= 1 + x + x^3$ polinomunun karşıt polinomu $$h_K(x) = x^3 h(x^{-1}) = x^3 (1 + x^{-1} + x^{-3}) = x^3 + x^2 + 1$$

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.

$\fring{n,q}$ içinde bir $f(x) = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}$ polinomu için $$f(1/x) = x^n f(1/x) = a_{0} + a_{n-1}x + \cdots + a_1x^{n-1}$$

olur.

Lemma 7.5: (M. Solmaz)

$\vek u,\vek v\in\ff_q^n$ olsun. $\sigma:\ff_q^n\rightarrow\ff_q^n$ bir birimlik sağa devirli kaydırma dönüşümü olsun. O zaman $$u(x)v(1/x)=\sum_{i=0}^{n-1} \vek u\cdot\sigma^{i}(\vek v)x^i$$

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

$\vek u=(u_0,u_1,\ldots,u_{n-1})$ ve $\vek v=(v_0,v_1,\ldots,v_{n-1})$ olsun. O zaman $$\begin{align*} u(x)v(1/x) & = (u_0 + u_1x + \cdots + u_{n-1}x^{n-1})(v_0 + v_{n-1}x + \cdots + v_1x^{n-1}) \\ & = (u_0v_0+u_1v_1+\cdots+u_{n-1}v_{n-1}) + (u_0v_{n-1} + u_1v_2 + \cdots + u_{n-1}v_0)x + \cdots + (u_0v_{1} + u_1v_{2} + \cdots + u_{n-1}v_{0})x^{n-1} \\ & = \sum_{i=0}^{n-1} \vek u\cdot\sigma^{i}(\vek v)x^i \end{align*}$$

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

$\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}$$

Kanıt

$\mcc$'nin boyutu $k$ olduğundan $\mcc^\perp$ dual kodunun boyutu $n-k$ olur. $\mcc^\perp$ kodu da bir devirli kod olduğundan üreteç polinomunun derecesi $k$ olmalıdır. Buna göre $h_K(x)\in\mcc^\perp$ olduğunu göstermek yeterlidir.

Dikkat edilirse Lemma 7.5$\vek u,\vek v\in\ff_q^n$ olsun. $\sigma:\ff_q^n\rightarrow\ff_q^n$ bir birimlik sağa devirli kaydırma dönüşümü olsun. O zaman $$u(x)v(1/x)=\sum_{i=0}^{n-1} \vek u\cdot\sigma^{i}(\vek v)x^i$$ 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.
📖 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.

$\mcc$, $\ff_q$ üzerinde bir $[n,k]$ devirli kodu olsun. $\mcc$'nin üreteç polinomu $g(x)$ olsun. Buna göre $g(x)$'in derecesi $n-k$ olur. $\mcc$'nin boyutu $k$ olduğundan, tüm kodlanacak mesajları $\ff_q^k$ uzayından seçeriz. Aşağıdaki ilk kodlama algoritmasında mesajımızı derecesi en fazla $k-1$ olan $\ff_q$ üzerindeki polinomlar ile kodluyoruz.

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 x^n-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

$\mcc$ devirli kodunun 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'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$, $\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.

Kanıt

$0$ bir eşkare olduğundan $\mcc=0$ ise gösterecek bir şey yoktur. Bu nedenle $\mcc\neq0$ olsun.

Önce (ii)'yi göstereceğiz. $e(x)$, $\mcc$'nin birimi ise her $c(x)\in\mcc$ için $c(x)=e(x)c(x)\in\langle e(x)\rangle$ olacağından $\mcc=\langle e(x)\rangle$ olur. Tersine, $\mcc=\langle e(x)\rangle$ olsun. Buna göre her $c(x)\in\mcc$ için $c(x)=f(x)e(x)$ olacak şekilde $f(x)\in\fring{q,n}$ vardır. O halde, $c(x)e(x)=f(x)e(x)^2=f(x)e(x)=c(x)$ olacağından $e(x)$, $\mcc$'nin birimidir.

$\mcc\neq0$ olduğundan $e_1(x)$ ve $e_2(x)$, $\mcc$'nin iki eşkare üreteci ise her ikisi de $\mcc$'nin birimi olacağından $e_1(x)=e_1(x)e_2(x)=e_2(x)$ elde edilir. Dolayısıyla, $\mcc$'nin bir eşkare üreteci olduğunu göstererek ispatı tamamlayabiliriz. $\mcc$'nin üreteç polinomu $g(x)$ olsun. Özel olarak $g(x)\mid X^n-1$'dir. $h(x)=\frac{x^n-1}{g(x)}$ olsun. $x^n-1$'in indirgenemez bölenlerinin cebirsel katlılığı 1 olduğundan $\ebob{g(x),h(x)}=1$ olur. Öklid algoritmasından $a(x)g(x)+b(x)h(x)=1$ olacak şekilde $a(x),b(x)\in\ff_q[x]$ vardır. $e(x)\equiv a(x)g(x)\pmod{x^n-1}$ olsun. Buna göre $$e(x)^2\equiv(a(x)g(x))(1-b(x)h(x))\equiv a(x)g(x)\equiv e(x)\pmod{x^n-1},$$ yani $\fring{q,n}$'de $e(x)^2=e(x)$ olur. Diğer taraftan, $c(x)\in\mcc$ ise bir $f(x)\in\fring{q,n}$ için $c(x)=f(x)g(x)$ olacağından $e(x)c(x)=f(x)g(x)(1-b(x)h(x))=f(x)g(x)=c(x)$ ve böylece $c(x)\in\langle e(x)\rangle$ bulunur. Dolayısıyla, $\mcc=\langle e(x)\rangle$ olur.

Örnek 7.24

Ü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

$\mcc$, $\ff_q$ üzerinde $n$ uzunluklu bir devirli kod olmak üzere $\mcc$'nin eşkare üreteci $e(x)$ olsun. Buna göre $\mcc$'nin üreteç polinomu $g(x)=\ebob{e(x),x^n-1}$ olur.

Kanıt

$d(x)=\ebob{e(x),x^n-1}$ ve $g(x)$, $\mcc$'nin üreteç polinomu olsun. $d(x)\mid e(x)$ olduğundan, $e(x)$'in her katı $d(x)$'in de bir katı olacağından, $\mcc\subseteq\langle d(x)\rangle$ olur. $g(x)\mid x^n-1$ ve $e(x)\in\mcc$ olduğudan $g(x)\mid e(x)$ ve böylece $g(x)\mid d(x)$, yani $d(x)\in\mcc$. O halde $\mcc=\langle d(x)\rangle$ olur. $d(x)$, $\mcc$'nin $x^n-1$'i bölen bir monik üreteci olduğundan $d(x)=g(x)$ olur.

Teorem 7.9

$\mcc$, $\ff_q$ üzerinde bir $[n,k]$-devirli kodu ve $\mcc$'nin eşkare üreteci $e(x)=\sum_{i=0}^{n-1}e_ix^i$ olsun. O halde \begin{pmatrix} e_0&e_1&e_2&\ldots&e_{n-2}&e_{n-1}\\ e_{n-1}&e_0&e_1&\ldots&e_{n-3}&e_{n-2}\\ \vdots&&&&&\vdots\\ e_{n-k+1}&e_{n-k+2}&e_{n-k+3}&\ldots&e_{n-k-1}&e_{n-k} \end{pmatrix}

matrisi $\mcc$'nin bir üreteç matrisidir.

Kanıt

$\{e(x),xe(x),\ldots,x^{k-1}e(x)\}$ kümesinin doğrusal bağımsız olduğunu göstermek yeter. Bunun için derecesi en fazla $k$ olan bir $a(x)\in\ff_q[x]$ için $a(x)e(x)=0$ olduğunda $a(x)=0$ olması gerektiğini gösterelim. $\mcc=\langle g(x)\rangle$ olsun. $a(x)g(x)=a(x)e(x)g(x)=0$ ve $\{g(x),xg(x),\ldots,x^{k-1}g(x)\}$ kümesi doğrusal bağımsız olduğundan $a(x)=0$ olur.

$\mcc_1$ ve $\mcc_2$ aynı uzunlukta iki doğrusal kod olmak üzere $$\mcc_1 + \mcc_2 = \{c_1 + c_2 \mid c_1\in\mcc_1,\ c_2\in\mcc_2\}$$

ş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$ ve $\mcc_2$, üreteç polinomları sırasıyla $g_1(x)$ ve $g_2(x)$ olan $n$ uzunluklu iki devirli kod olsun. Ayrıca $\mcc_1$ ve $\mcc_2$'nin eşkare üreteçleri sırasıyla $e_1(x)$ ve $e_2(x)$ olsun. Bu takdirde aşağıdakiler sağlanır.

$\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

Teorem 7.10 (i)'i kanıtlayınız.

İlkel Eşkareler

$x^n-1=f_1(x)\ldots f_s(x)$ ve $f_1(x),\ldots,f_s(x)$, $\ff_q$ üzerinde indirgenemez polinomlar olsun. $\ebob{n,q}=1$ olduğundan $i\neq j$ iken $f_i(x)\neq f_j(x)$ olur. $1\le i\le s$ için $$\hat{f}_i(x)=(x^n-1)/f_i(x)$$

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

$\igen{\hat{f}_i(x)}$'in eşkare üretecini $\hat{e}_i(x)$ şeklinde gösterelim. $\hat{e}_1(x),\ldots,\hat{e}_s(x)$ eşkarelerine $\fring{q,n}$ halkasının ilkel eşkareleri denir.

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.

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

$$\hat{e}_i(x)\hat{e}_j(x) = \hat{f}_i(x)c_i(x)\hat{f}_j(x)c_j(x)=\hat{f}_i(x)\hat{f}_j(x)c_i(x)c_j(x)=0$$

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

$\cm$, $\fring{q,n}$ halkasının bir minimal ideali olsun. O zaman $\cm$, $\ff_q$ cisminin bir genişlemesidir.

Kanıt

$\cm$ bir $\ff_q$-uzayıdır. Diğer taraftan $\cm$ üzerinde, birim elemanı olan bir çarpma işlemi olduğundan $\cm$ bir halka yapısına sahiptir. Dolayısıyla $\cm$'nin sıfırdan farklı her elemanının tersinir olduğunu görmek yeterlidir. $e(x)\in\cm$ birim eleman ve $f(x)\in\cm$ sıfırdan farklı bir eleman olsun. $(0)\subset\igen{f(x)}\subseteq\cm$ ve $\cm$ minimal olduğundan $\cm=\igen{f(x)}$ olur. Buna göre $e(x)=f(x)g(x)$ olacak şekilde bir $g(x)\in\fring{q,n}$ vardır. $a(x)=e(x)g(x)$ olsun. O zaman $a(x)\in\cm$ ve $f(x)a(x)=f(x)e(x)g(x)=f(x)g(x)=e(x)$ elde edilir. Yani $f(x)$, $\cm$ içinde tersinirdir.

Teorem 7.13

$\mcc_1,\ldots,\mcc_t\subseteq\ff_q^n$ birer devirli kod olsun. Buna göre \begin{align} \boy(\mcc_1+\cdots+\mcc_t) &=\sum_{i=1}^t\boy(\mcc_i) - \sum_{i<j}\boy(\mcc_i\cap\mcc_j)\\ &\quad + \sum_{i<j<k}\boy(\mcc_i\cap\mcc_j\cap\mcc_k) - \cdots\\ &\quad\ \ +(-1)^{t-1}\boy(\mcc_1\cap\ldots\cap\mcc_t) \end{align}

olur.

Ç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.

$\mcc\in\ff_q^n$ bir doğrusal kod olsun. $\sigma\in\mathcal{S}_n$ için $\mcc$'nin kod sözcüklerinin her birinin koordinatlarına $\sigma$ permütasyonu uygulanarak elde edilen doğrusal kodu $\mcc^\sigma$ ile gösterelim. Buna göre $\mcc$ ile $\mcc^\sigma$ kodları permütasyon-denktir. Fakat her $\sigma\in\mathcal{S}_n$ için $\mcc^\sigma$ ile $\mcc$'den farklı bir kod elde edemeyebiliriz. Böyle bir durumda, yani $\mcc^\sigma=\mcc$ olması durumunda, $\sigma$ permütasyonuna $\mcc$'nin bir permütasyon otomorfizması diyeceğiz. $\mcc$'nin tüm permütasyon otomorfizmalarının kümesini $\paut(\mcc)$ ile göstereceğiz. Dikkat edilirse $\paut(\mcc)$, $\mathcal{S}_n$'nin bir alt grubudur.

Çarpan

$n$ ile aralarında asal olan bir $a$ doğal sayısı seçelim. $\mu_a$, $\{1,\ldots,n-1\}$ kümesi üzerinde her $1\le i\le n-1$ için $$\mu_a(i)\equiv a\cdot i \pmod{n}$$

ş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.

$\mu_a$ çarpanını, $\fring{q,n}$ üzerine bir etki olarak tanımlamak oldukça kullanışlıdır. Buna göre $f(x)=f_0+f_1x+\cdots+f_{n-1}x{n-1}\in\fring{q,n}$ için $$\mu_af(x)=f_0+f_1x^{\mu_a(1)}+\cdots+f_ix^{\mu_a(i)}+\cdots+f_{n-1}x^{\mu_a(n-1)}$$

ş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

$f(x),g(x)\in\fring{q,n}$ olsun. $a$ bir tamsayı olmak üzere $a$ ile $n$ aralarında asal olsun. Aşağıdakiler sağlanır:

$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)

Teorem 7.14'ü kanıtlayınız.

Not 7.3

Teorem 7.14 (iv)'te belirtildiği gibi, $\mu_q$ permütasyonunun mertebesi $q$'nun $n$ modülüne göre çarpımsal mertebesine eşittir. Bu metrebeyi $\ord{n}{q}$ ile göstereceğiz.

Not 7.4

$f(x)=a_0+a_1x+\cdots+f_rx^r\in\ff_q[x]$ olsun. O zaman her $a\in\ff_q$ için $a^q=a$ ve her $u(x),v(x)\in\ff_q[x]$ için $(u(x)+v(x))^q=u(x)^q+v(x)^q$ olduğundan \begin{align} f(x^q) & = a_0+a_1x^q+\cdots+f_rx^{qr}\\ & = a_0^q + a_1^qx^q + \cdots + f_r^q(x^r)^q\\ & = \left(a_o+a_1x+\cdots+f_rx^r\right)^q\\ & = f(x)^q \end{align}

elde edilir.

Teorem 7.15

$\mcc\subseteq\ff_q^n$ bir devirli kod olmak üzere $e(x)$, $\mcc$'nin eşkare üreteci olsun. $a$, $n$ ile aralarında asal bir tamsayı olsun. O zaman

$\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.

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 (vi)'dan $e(x)=\sum_{t\in T}\hat{e}_t(x)$ olacak şekilde $T\subseteq\{1,\ldots,s\}$ vardır.