BCH ve Reed-Solomon Kodları

Bu bölümde, devirli kodların önemli ailelerinden biri olan BCH kodlarını ve bu kodların Reed-Solomon kodları adı verilen bir alt ailesini inceleyeceğiz.

BCH Kodları

İkili BCH kodları, 1960 yılı civarında Hocquenghem tarafından ve bağımsız olarak Bose ile Ray-Chaudhuri tarafından keşfedilmiş; daha sonra Gorenstein ve Zierler tarafından tüm sonlu cisimlere genelleştirimiştir. BCH kodlarının literatürde ortaya çıktığı dönemde, Reed ve Solomon bugün kendi adlarıyla anılan kodlar üzerine yaptıkları çalışmalarını yayımladılar. Özel BCH kodları olarak da tanımlanabilen bu kodlar, aslında ilk kez Bush tarafından 1952'de ortogonal diziler bağlamında inşa edilmişti. Patlama tipi hata düzeltme yetenekleri nedeniyle Reed-Solomon kodları, uzun süre kompakt disklerin, dijital ses bantlarının ve diğer veri depolama sistemlerinin güvenilirliğini artırmak için kullanılmıştır.

Tanım 8.1: BCH Kodu

$2 \le \delta \le n$ olacak şekilde bir $\delta$ tamsayısı alalım. Uzunluğu $n$ ve tasarlanmış uzaklığı $\delta$ olan, $\mathbb{F}_q$ üzerindeki bir BCH kodu $\mcc$, aşağıdaki tanımlayıcı kümeye sahip dairesel bir koddur: $$T = C_b \cup C_{b+1} \cup \cdots \cup C_{b+\delta-2},$$

Burada $C_i$, $q$'nun $n$ modülüne göre $i$ elemanını içeren, dairesel kosettir. BCH Sınırı'na göre bu kodun minimum uzaklığı en az $\delta$'dır (bkz. Teorem 7.22$\mathcal{C}$, tanımlayıcı kümesi $T$ olan, $\mathbb{F}_q$ üzerinde $n$ uzunluğunda bir devirli kod olsun. $\mathcal{C}$'nin minimum ağırlığının $d$ olduğunu varsayalım. Eğer $T$, bir $\delta$ tam sayısı için $\delta - 1$ tane ardışık eleman içeriyorsa, bu durumda $d \ge \delta$ olur.
📖 Detaya Git).

$\delta$ değerini değiştirmek, minimum uzaklıkları ve boyutları farklı olabilen çeşitli kodlar elde etmemizi sağlar. $\delta=1$ olduğunda $\mcc$ koduna dar anlamlı BCH kodu diyeceğiz. Her devirli kodda olduğu gibi, eğer $n=q^t-1$ ise, $\mcc$ koduna ilkel BCH kodu denir.

Teorem 8.1

Tasarlanmış uzaklığı $\delta$ olan, $\mathbb{F}_q$ üzerinde bir $[n,k]$ BCH kodu $\mcc$ verilsin. Aşağıdakiler sağlanır:

$k \ge n-\operatorname{ord}_n(q)(\delta-1)$.
Eğer $q=2$ ve $\mcc$ dar anlamlı bir BCH koduysa, $\delta$ sayısının tek olduğu varsayılabilir; ayrıca $\delta=2w+1$ ise $$k \ge n-\operatorname{ord}_n(q)\,w$$
elde edilir.

Kanıt

her $q$-dairesel kosetinin büyüklüğü $\operatorname{ord}_n(q)$ sayısının bir bölenidir. Tasarlanmış uzaklığı $\delta$ olan bir BCH kodunun tanımlayıcı kümesi, her biri en çok $\operatorname{ord}_n(q)$ elemanlı en fazla $\delta-1$ adet $q$-dairesl kosetinin birleşimidir. Dolayısıyla kodun boyutu en az

$$n-\operatorname{ord}_n(q)(\delta-1)$$

olur; bu da bize (1)'i verir.

Kod dar anlamlı ve ikili ise $\{1,2,\ldots,\delta-1\}\subseteq T$ olur. $\delta$'nın çift olduğunu varsayalım. O zaman

$$\delta\in C_{\delta/2}\subseteq T$$

olduğundan, $T$ kümesi $\delta$ ardışık elemandan oluşan

$$\{1,2,\ldots,\delta\}$$

kümesini içerir. Bu da tasarlanmış uzaklığı çift olarak varsayıldığında onu 1 artırabileceğimizi gösterir. Dolayısıyla $\delta$'yı tek kabul edebiliriz. Eğer $\delta=2w+1$ ise,

$$T=C_1\cup C_2\cup\cdots\cup C_{2w}=C_1\cup C_3\cup\cdots\cup C_{2w-1}$$

olur, çünkü $C_{2i}=C_i$'dir. O halde $T$, her biri en çok $\operatorname{ord}_n(q)$ elemanlı en fazla $w$ adet $q$-cyclotomic sınıfın birleşimidir; buradan

$$k\ge n-\operatorname{ord}_n(q)\,w$$

sonucu elde edilir.

Aşağıdaki tabloda uzunluğu $2^m-1$ tipinde ve tasarlanmış uzaklığı $2t+1$ olan dar anlamlı ikili BCH kodlarının boyutları görülebilir:

Uzunluk ($n$)	Boyut ($k$)	$t$
7	4	1
15	11	1
15	7	2
15	5	3
31	26	1
31	21	2

BCH Kodları ile Kod Çözme - Sugiyama Algoritması

Bu kısımda BCH kodlarını da içeren Goppa kod sınıfı için Sugiyama vd.Y. Sugiyama, M. Kasahara, S. Hirasawa, T. Namekawa, A method for for solving a key equation for decoding Goppa codes, Inform, and Control 27 (1975), 87--99 tarafından 1975 yılında verilen kod çözme tekniğininin, BCH kodları üzerindeki uygulanışını ele alacağız.

Notasyon

$\alpha\in\ff_{2^r}$ bir ilkel eleman olsun. $\mcc$, $n=2^r-1$ uzunluklu, tasarlanmış uzaklığı $\delta=2t+1$ olan dar anlamlı ikili BCH kodu ve $\mcc$'nin üreteç polinomu $g(x)$ olsun.

$\ff_{2^r}$ üzerindeki $$H=\left[ \begin{array}{ccccc} 1 & \alpha & \alpha^2 & \ldots & \alpha^{n-1}\\ 1 & \alpha^2 & (\alpha^2)^2 & \ldots & (\alpha^2)^{n-1}\\ \vdots\\ 1 & \alpha^{2t} & (\alpha^{2t})^2 & \ldots & (\alpha^{2t})^{n-1}\\ \end{array}\right]$$

matrisini tanımlayalım.

Dikkat edilirse $\alpha,\alpha^2\ldots,\alpha^{2t}$ elemanlarının tümü $g(x)$'in köküdür ve $\vek c(x)\in\ff_2[x]$ için

$$\vek c(\alpha)=\vek c(\alpha^2)=\cdots=\vek c(\alpha^{2t})=0$$

olmasıyla $g(x)\mid \vek c(x)$ olması denktir. Diğer bir deyişle

$$\vek c(x)\in\mcc\quad\iff\quad \vek cH^T=0$$

olur.

Her $\vek c\in\ff_2^n$ için

$$S(\vek c)=\vek c\cdot H^T$$

sendromunu tanımlayalım. Buna göre her $\vek c,\vek c'\in \ff_2^n$ için

$$S(\vek c) = S(\vek c')\quad\iff\quad \vek c - \vek c' \in \mcc$$

yazabiliriz.

Şimdi yavaş yavaş kod çözme tekniğimize geçelim. Kabul edelim ki en fazla $t$ tane hata sonucunda $\vek w(x) = w_0 + w_1x + \cdots + w_{n-1}x^{n-1}\in \ff_2[x]$ sözcüğü alınmış olsun. $\mcc$ kodunun tasarlanmış uzaklığı $\delta=2t+1$ için

$$t = \left\lfloor \frac{\delta -1 }{2} \right\rfloor \le \left\lfloor \frac{d(\mcc) - 1}{2}\right\rfloor$$

olduğundan, $\mcc$ kodu $t$ adet veya daha daha az sayıdaki hatayı düzeltebilir.

$\vek w$ sözcüğünün sendromu $\vek s =(s_0,s_1,\ldots,s_{2t-1})$ denirse $S(\vek w) = \vek w\cdot H^T$ eşitliğinden $$\vek s = (\vek w(\alpha),\vek w(\alpha^2),\ldots,\vek w(\alpha^{2t}))\in\ff_2^{2t}$$

yazılabilir. Buna göre her $i=0,\ldots,2t-1$ için $s_i=\vek w(\alpha^{i+1})$ olur.

$\ell\le t$ olmak üzere hata polinomu $$\vek e(x) = x^{k_0} + \cdots + x^{k_{\ell-1}}$$

olsun. $\vek w$ ve $\vek e$ $\mcc$'nin aynı kosetinde olduğudan her $i=0,\ldots,\ell-1$ için

$$s_i=\vek w(\alpha^{i+1}) = \vek e(\alpha^{i+1})\tag{1}$$

olur.

Her $i=0,\ldots,\ell-1$ için $A_j=\alpha^{k_j}$ olmak üzere

$$\sigma(z) := \prod_{j=0}^{\ell-1}(1-A_jz)\in\ff_{2^r}[z]$$

polinomunu tanımlayalım. Bu $\sigma(z)$ polinomuna hata konumlayıcı polinomu denir. Dikkat edilirse $\sigma(z)$ polinomunun köklerini bulmak demek hata yerlerini de bulmak demektir. Bu da $\sigma(z)$'nin neden hata konumlayıcı polinomu olarak anıldığını açıklar. $\sigma(z)$ polinomunun köklerini bulmak için özncelikle $\sigma(z)$ polinomunun kendisini belirlemek gerekir. Bunun için Öklid algoritmasının zekice kullanıldığı bir yöntem vereceğiz.

Hata konumlayıcı polinomunu belirlemede oldukça kullanışlı başka bir polinomu, hata hesaplayıcı polinomunu şu şekilde tanımlayalım:

$$\varepsilon(z):=\sum_{j=0}^{\ell-1}A_j\prod_{\substack{i=0\\ i\neq j}}(1-A_iz)=\sum_{j=0}^{\ell-1}A_j\frac{\sigma(z)}{1-A_jz}\tag{2}$$

Dikkat edilirse $\der{(\sigma(z))}=\ell-1$ ve $\der{(\varepsilon(z))}\le \ell-1$'dir

Her $i=0,\ldots,\ell-1$ için $s_i=e(\alpha^{i+1})$ olmak üzere daha önce tanımladığımız

$$\vek s(z) = s_0 + s_1z +\ldots + s_{2t-1} z^{2t-1}$$

sendrom polinomunu $z$ değişkenine bağlı olarak yazalım. (2) eşitliğinin sağ tarafını biçimsel kuvvet serisi şeklinde açarak

$$\begin{align} \varepsilon(z) & = \sigma(z)\sum_{j=0}^{\ell - 1} A_j\frac{1}{1-A_jz} = \sigma(z) \sum_{j=0}^{\ell - 1}(A_jz)^i \\ & =\sigma(z)\sum_{i=0}^{\infty}\Big(\sum_{j=0}^{\ell-1}A_j^{i+1}\Big)z^i \end{align}$$

eşitliğini yazabiliriz. Buna göre

$$\varepsilon(z)\equiv\sigma(z)\sigma_{i=0}^{2t-1}\Big(\sum_{j=0}^{\ell-1}A_j^{i+1}\Big)z^i\pmod{z^{2t}}$$

kongrüensi elde edilir. Fakat her $i$ için $s_i=e(\alpha^{i+1})=\sum_{j=0}^{\ell-1}A_j^{i+1}$ olduğundan bu kongrüensi

\begin{equation} \varepsilon(z)\equiv \sigma(z)\vek s(z)\pmod{z^{2t}} \tag{3} \label{key_eq} \end{equation}

biçiminde yeniden yazabiliriz. Bu denkleme anahtar denklemi diyeceğiz.

$\sigma(z)$ polinomunun kökleri $A_j^{-1}$ ($0\le j \le \ell - 1$) fakat $$\varepsilon(A_j^{-1})=A_j\prod_{\substack{i=0\\ i\neq j}}(1-A_j^{-1}A_i)\neq 0$$

olduğundan, $\sigma(z)$ ve $\varepsilon(z)$ polinomları aralarında asaldır.

Tanım 8.2: Siguyama Algoritması

$\vek s(z)$ verildiğinde $\eqref{key_eq}$ eşitliğindeki $\varepsilon(z)$ ve $\sigma(z)$ polinomlarını, Öklid algoritmasını da kullanarak, Sugiyama Algoritması olarak bilinen aşağıdaki algoritmayla bulabiliriz:

Adım I. $r_{-1}(z)=z^{2t}$, $r_0(z)=\vek s(z)$, $b_{-1}(z)=0$ ve $b_0(z)=1$ başlangıç polinomlarını tanımla.
Adım II. $i=1,2,\ldots$ için $h_i(z)$, $r_i(z)$ ve $b_i(z)$ polinomlarının belirlendiği $$\begin{align} r_{i-2}(z) &= r_{i-1}(z)h_i(z) + r_i(z),\qquad\der{(r_i(z))}<\der{(r_{i-1}(z))}\\b_i(z) &= b_{i-2}(z) - h_i(z)b_{i-1}(z) \end{align}$$
hesaplamalarını, $\der{(r_\kappa(z))}<t$, $\der{(r_{\kappa-1}(z))}\ge t$ olacak şekilde $r_\kappa(z)$ kalanı bulana kadar yap.
Adım III. $\sigma(z)$ polinomu, II. adımda bulunan $b_\kappa(z)$ polinomunun bir sabit katıdır.

Lemma 8.2

Yukarıdaki Sugiyama Algoritmasının gösterimleri ile, $a_{-1}(z)=1$, $a_0(z)=0$ ve her $i\ge 1$ için $a_i(z)=a_{i-1}(z)-h_i(z)a_{i-1}(z)$ ise aşağıdakiler sağlanır:

$a_i(z)\dot z^{2t} + b_i(z)\vek s(z) = r_i(z).$
$b_i(z)r_{i-1}(z) - b_{i-1}(z)r_i(z) = (-1)^i z^{2t}.$
$a_i(z)b_{i-1}(z) - a_{i-1}(z)b_i(z) = (-1)^{i+1}.$
$\der b_i(z) + \der r_{i-1}(z) = 2t.$

Kanıt

Bu maddelerin tümünü tümevarım ile ispatlayabilriz. $f(z)=z^{2t}$ alalım.

(i) için, $i = -1$ ve $i = 0$ durumları doğrudan Sugiyama Algoritmasının I. Adımında ayarlanan başlangıç değerlerinden ve $a_{-1}(z) = 1$ ile $a_0(z) = 0$ değerlerinden elde edilir. (i)'nin $i$ yerine $i - 1$ ve $i - 2$ konularak sağlandığını varsayarsak, şunları elde ederiz:

$$\begin{aligned} a_i(z)f(z) + b_i(z)s(z) &= [a_{i-2}(z) - h_i(z)a_{i-1}(z)]f(z) \\ &\quad + [b_{i-2}(z) - h_i(z)b_{i-1}(z)]s(z) \\&= a_{i-2}(z)f(z) + b_{i-2}(z)s(z) \\ &\quad - h_i(z)[a_{i-1}(z)f(z) + b_{i-1}(z)s(z)] \\ &= r_{i-2}(z) - h_i(z)r_{i-1}(z) = r_i(z), \end{aligned}$$

bu da (i)'i verir.

(ii) maddesi, $i = 0$ iken, Sugiyama Algoritmasının I. Adımından elde edilir. (ii)'nin $i$ yerine $i - 1$ konularak sağlandığını varsayalım. O zaman

$$\begin{aligned} b_i(z)r_{i-1}(z) - b_{i-1}(z)r_i(z) &= [b_{i-2}(z) - h_i(z)b_{i-1}(z)]r_{i-1}(z) - b_{i-1}(z)r_i(z) \\ &= b_{i-2}(z)r_{i-1}(z) - b_{i-1}(z)[h_i(z)r_{i-1}(z) + r_i(z)] \\ &= b_{i-2}(z)r_{i-1}(z) - b_{i-1}(z)r_{i-2}(z) \\ &= -(-1)^{i-1}f(z) = (-1)^i f(z), \end{aligned}$$

bu da (ii)'yi doğrular.

$i = 0$ iken, (iii) Sugiyama Algoritmasının I. Adımından, $a_{-1}(z) = 1$ ve $a_0(z) = 0$ değerlerinden elde edilir. (iii)'ün $i$ yerine $i - 1$ konularak sağlandığını varsayalım. O zaman $$\begin{aligned}a_i(z)b_{i-1}(z) - a_{i-1}(z)b_i(z) &= [a_{i-2}(z) - h_i(z)a_{i-1}(z)]b_{i-1}(z) \\ &\quad - a_{i-1}(z)[b_{i-2}(z) - h_i(z)b_{i-1}(z)] \\ &= -[a_{i-1}(z)b_{i-2}(z) - a_{i-2}(z)b_{i-1}(z)] \\ &= -(-1)^i = (-1)^{i+1}, \end{aligned}$$

bu da (iii)'ü ispatlar.

$i = 0$ iken, (iv) yine Sugiyama Algoritmasının I. Adımından elde edilir. (iv)'ün $i$ yerine $i - 1$ konularak sağlandığını varsayalım, yani $\der b_{i-1}(z) + \der r_{i-2}(z) = \der f(z)$. Sugiyama Algoritmasının II. Adımında, $\der r_i(z) < \der r_{i-1}(z)$ elde ederiz. Dolayısıyla $\der(b_{i-1}(z)r_i(z)) = \der b_{i-1}(z) + \der r_i(z) < \der f(z)$ olup, bu da (ii) kısmı kullanılarak $i$ durumu için (iv)'ü gerektirir.

Şimdi Sugiyama Algoritmasının çalıştığını doğrulayalım. Yukarıdaki lemmanın (i) şıkkı gereğince

$$a_\kappa(z)z^{2t} + b_\kappa(z)\vek s(z) = r_\kappa(z). \tag{4}$$

eşitliğini elde ederiz. Anahtar denklemden, şunu da biliyoruz:

$$a(z)z^{2t} + \sigma(z)\vek s(z) = \varepsilon(z) \tag{5}$$

bazı $a(z)$ polinomları için. (4)'ü $\sigma(z)$ ile ve (5)'i $b_\kappa(z)$ ile çarparak şu eşitlikleri elde ederiz:

$$a_\kappa(z)\sigma(z)z^{2t} + b_\kappa(z)\sigma(z)\vek s(z) = r_\kappa(z)\sigma(z) \tag{6}$$ $$a(z)b_\kappa(z)z^{2t} + \sigma(z)b_\kappa(z)\vek s(z) = \varepsilon(z)b_\kappa(z). \tag{7}$$ $z^{2t}$ modülüne göre bunları $$r_\kappa(z)\sigma(z) \equiv \varepsilon(z)b_\kappa(z) \pmod{z^{2t}}. \tag{8}$$

kongrüensine dönüştürebiliriz. $\kappa$'nın seçimi gereği $\der \sigma(z) \le t$ olduğundan, $\der(r_\kappa(z)\sigma(z)) = \der r_\kappa(z) + \der \sigma(z) < t + t = 2t$ olur. Yukarıdaki lemmanın (iv) şıkkından, $\kappa$'nın seçimi ve $\der \varepsilon(z) < t$ olmasından dolayı, $\der(\varepsilon(z) b_\kappa(z)) = \der \varepsilon(z) + \der b_\kappa(z) < t + \der b_\kappa(z) = t + (\der z^{2t} - \der r_{\kappa-1}(z)) \le 3t - t = 2t$ elde edilir. Bu nedenle (8), $r_\kappa(z)\sigma(z) = \varepsilon(z)b_\kappa(z)$ olduğunu gösterir. Bu ise, (6) ve (7) ile birlikte

$$a_\kappa(z)\sigma(z) = a(z)b_\kappa(z). \tag{9}$$

olduğunu gösterir. Ancak, yukarıdaki lemmanın (iii) şıkkı, $a_\kappa(z)$ ve $b_\kappa(z)$'in aralarında asal olduğunu ve dolayısıyla (9)'a göre $a(z) = \lambda(z)a_\kappa(z)$ olduğunu gösterir. Bunu (9)'da yerine koyarak

$$\sigma(z) = \lambda(z)b_\kappa(z). \tag{10}$$

eşitliğini elde ederiz. Bunları (5)'te yerine koyduğumuzda $\lambda(z)a_\kappa(z)z^{2t} + \lambda(z )b_\kappa(z)\vek s(z) = \varepsilon(z)$ elde ederiz. Böylece (4) ile

$$\varepsilon(z) = \lambda(z)r_\kappa(z). \tag{11}$$

eşitliği elde edeilir. $\sigma(z)$ ve $\varepsilon(z)$ polinomları aralarında asal olduğundan yukarıdaki (10) ve (11) gereğince, $\lambda(z)$ sıfırdan farklı bir sabit olmalıdır, bu da Sugiyama Algoritmasının III. Adımını doğrular.Sadece $\sigma(z)$'in kökleriyle ilgilendiğimiz için, II. Adımda üretilen $b_\kappa(z)$'in köklerini bulmak yeterlidir; bu da istenen hata konum indekslerini verir.

Örnek 8.5

$\alpha\in \ff_8$ olmak üzere $1+\alpha+\alpha^2=0$ eşitliği sağlansın. $\mcc$, uzunluğu $7$ ve tasarlanmış uzaklığı $3$ olan dar anlamlı ikili BCH kodu olsun. $2$'nin $7$ modülüne göre 1 ve 2'yi içerein dairesel kosetleri $$C_1=\{1,2,4\}=C_2$$

şeklinde olduğundan $\mcc$, $(x-\alpha)(x-\alpha^2)(x-\alpha^4)=1+x+x^3$ ile üretilen ikili devirli koddur.

Kabul edelim ki $\vek w(x)=1+x+x^2+x^3$ sözcüğü alınmış olsun. $\vek w(x)$'in senromu

$$(s_0,s_1) = (\vek w(\alpha),\vek w(\alpha^2)) = (1+\alpha+\alpha^2+\alpha^3,1+\alpha^2+\alpha^4+\alpha^6)=(\alpha^2,\alpha^4)$$

olarak hesaplanır. (Bu hesapları kolayca yapabilmek için bir defaya mahsus $\ff_8$'in Zech logaritma tablosunu yapmak yararlı olabilir. Biz burada hesaplama detaylarını geçerek, yalnızca bu hesaplamalar ile elde edilen sonuçlara odaklanıyoruz. Okuyucu mutlaka bu hesapları doğrulamak için zaman ayırmalı ve eksik bırakılan adımları kendisi adına atmalıdır.)

Şimdi $\varepsilon(z)$ ve $\sigma(z)$'nin belirsiz olduğu $\eqref{key_eq}$ anahtar denklemini çözelim. Bunun için Siguyama algoritmasında tarif edilen adımları takip edeceğiz. İlk adım gereği

$$r_{-1}(z)=z^{\delta-1}=z^2,\quad r_0(z)=\vek s(z) = \alpha^2 + \alpha^4 z,\quad b_{-1}(z)=0,\quad b_0(z)=1$$

başlangıç değerlerini kabul edelim. Buna göre bölme algoritması ile

$$z^2=(\overbrace{\alpha^2+\alpha^4z}^{r_0})(\overbrace{\alpha+\alpha^3z}^{h_1}) + \overbrace{\alpha^3}^{r_1}$$ $$b_1(z)=b_{-1}(z) - h_1(z)b_0(z) = \alpha + \alpha^3z$$

elde edilir. $\der{r_1(z)}=0 < 1 = t$ olduğundan algoritmanın II. adımı burada sona erdirilir. Buna göre $\sigma(z)$ polinomu, $b_1(z)=\alpha+\alpha^3z$ polinomunun bir sabit katıdır. $b_1(\alpha^5)=0$ olduğundan $\alpha^5$, $\sigma(z)$'nin de bir köküdür. $\der{\sigma(z)}=1$ olduğundan yalnız bir koordinatta hata vardır. Eğer bu hata koordinatına j dersek, \alpha^j+1=(\alpha^5)^-1 olacağından $j=3$ elde edilir. Başka bir deyişle hata polinomu $e(x)=x^2$ olur ve $\vek w(x)$ sözcüğü, $\vek w(x) - e(x) = 1 + x + x^3$ şeklinde çözülür.

Örnek 8.6

$\alpha$, $x^4+x+1\in\ff_2[x]$ polinomunun bir kökü olsun. Bu durumda $\alpha$, $\ff_{16}=\ff_2(\alpha)$ cisminin bir ilkel elemanıdır. 15 uzunluklu ve tasarlanmış uzaklığı $\delta=5$Yani $t=2$. olan dar anlamlı ikili BCH kodunu düşünelim. 2'nin 15 modülüne göre 1,2,3 ve 4 sayılarını içeren dairesel kosetleri $$C_1=C_2=C_4=\{1,2,4,8\}\qquad C_3=\{3,6,9,12\}$$

olduğundan

$$(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)(x-\alpha^6)(x-\alpha^8)(x-\alpha^9)(x-\alpha^12)=1+x^4+x^6+x^7+x^8$$

Kabul edelim ki $\vek w(x)=1+x^3+x^6+x^7+x^{12}$ sözcüğü alınmış olsun. $\ff_ {16}$ cisminin $\alpha$'nın kuvvetlerine göre Zech logaritma tablosu yapılırsa $\vek s(x)$ sendrom polinomunun katsayıları aşağıdaki gibi elde edilebilir:

\begin{align} s_0 & = \vek w(\alpha) = 1 + \alpha^3 + \alpha^6 + \alpha^7 + \alpha^{12} = {\color{turquoise}1}\\ s_1 & = \vek w(\alpha^2) = 1 + \alpha^6 + \alpha{12} + \alpha^{14} + \alpha^{9} = {\color{turquoise}1}\\ s_2 & = \vek w(\alpha^3) = 1 + \alpha^9 + \alpha^3 + \alpha^6 + \alpha^6 = {\color{turquoise}\alpha^4}\\ s_3 & = \vek w(\alpha^4) = 1 + \alpha^{12} + \alpha^9 + \alpha^{13} + \alpha^3 = {\color{turquoise}1} \end{align}

Özetle, $\vek w(x)$'in sendromunu $\vek s(x) = 1 + x + \alpha^4x^2 + x^3$ olarak hesaplarız.

Şimdi anahtar denklemini çözelim.

💻
$$z^4 = \vek s(z)(\underbrace{\alpha^4 + z}_{h_1}) + (\underbrace{\alpha^4 + \alpha z + \alpha^2 z^2}_{r_1})$$ $$b_1(z) = b_{-1}z - h_1(z)b_0(z) = \alpha^4 + z$$
💻
$$\vek s(z) = r_1(z)(\underbrace{\alpha^7+\alpha^{13}z}_{h_2})+ \underbrace{\alpha^{12}}_{r_2}$$ $$b_2(z) = b_0(z) - h_2(z)b_1(z) = \alpha^{12} + \alpha^{12}z + \alpha^{13}z^2$$

💡 $\der{r_2(z)} = 0 < 2 = t$ ve $\der{r_1(z)} = 2 =t$ olduğundan, $\sigma(z)$, $b_2(z)$'nin bir sabit katıdır.

Hata polinomu $\vek e(x) = x^{i_0} + x^{i_1}$ olsun. ($\der{\sigma(z)} = 2$ olduğundan iki adet hata vardır.)

$$b_2(z)=\alpha^{13}z^2 + \alpha^{12}z + \alpha^{12}=\alpha^{13}(z^2 + \alpha^{14}z + \alpha^{14})$$

ve $\alpha^6\cdot\alpha^8 = \alpha^{14}$ ve $\alpha^6 + \alpha^8 = \alpha^{14}$ olduğundan $\alpha^6$ ve $\alpha^8$, $b_2(z)$'nin (dolayısıyla da $\sigma(z)$'nin) kökleridir. $(\alpha^6)^{-1}=\alpha^9$ ve $(\alpha^8)^{-1} = \alpha^7$ olduğundan $\vek e(x) = x^7 + x^9$ olur.

🚀 Dolayısıyla $\vek w(x)$ sözcüğü, ${\color{magenta}\vek w(x) - \vek e(x) = 1 + x^3 + x^6 + x^9 + x^{12}}$ olarak çözülür.

Reed-Solomon Kodları

Bu bölümde Reed-Solomon kodlarını BCH kodlarının bir alt ailesi olarak tanımlayacağız. Ayrıca dar-anlamlı Reed-Solomon kodları için, bu önemli kodları genelleştirmemize olanak tanıyacak başka bir denk tanım da vereceğiz.

$\mathbb{F}_q$ üzerinde bir Reed-Solomon kodu, kısaca RS kodu, uzunluğu $n = q - 1$ olan bir BCH kodudur. Dolayısıyla $\text{ord}_n(q) = 1$ olacağından $x^n - 1$'in tüm indirgenemez çarpanlarının tek katlı olduğu ve $q$'nun $n$ modülüne göre tüm dairesel kosetlerininin tek elemanlı olduğu anlamına gelir. Aslında, $x^n - 1$'in kökleri tam olarak $\mathbb{F}_q$'nun sıfır olmayan elemanlarıdır ve birimin $n$-yinci dereceden her ilkel kökü, $\mathbb{F}_q$'nun ilkel bir elemanıdır. Dolayısıyla, eğer $\mathcal{C}$, tasarlanmış uzaklığı $\delta$ olan bir Reed-Solomon kodu ise, $\mathcal{C}$'nin tanımlayıcı kümesi $\delta - 1$ elemanlıdır ve bir $b$ tamsayısı için $T = \{b, b + 1, \dots, b + \delta - 2\}$ şeklindedir. Ayrıca, $\mathcal{C}$'nin boyutu $k$ ve minimum uzaklığı $d$ ise (Singleton sınırını da dikkate alarak) $k = n - \delta + 1 \ge n - d + 1 \ge k$ eşitsizlikleri sağlanır. Dolayısıyla her iki eşitsizlik de eşitliktir, bu da $d = \delta$ ve $k = n - d + 1$ olduğu anlamına gelir. Özel olarak, $\mathcal{C}$ bir MDS kodudur. Böylece aşağıdaki teoremi elde edmiş oluruz.

Teorem 8.3

$\mathcal{C}$, $\mathbb{F}_q$ üzerinde uzunluğu $n = q - 1$ ve tasarlanmış uzaklığı $\delta$ olan bir RS kodu olsun. O halde:

$\mathcal{C}$'nin tanımlayıcı kümesi $T = \{b, b + 1, \dots, b + \delta - 2\}$ olacak şekilde bir $b$ tamsayısı vardır;
$\mathcal{C}$'nin minimum uzaklığı $d = \delta$ ve boyutu $k = n - d + 1$'dir;
$\mathcal{C}$ bir MDS koddur.

Not 8.1

Genel olarak bir BCH kodunun duali ve devirli tümleyeni de BCH kodu olmak zorunda değildir; ancak RS kodları için durum farklıdır. $T$, uzunluğu $n$ ve tasarlanmış uzaklığı $\delta$ olan bir RS kodu $\mathcal{C}$ için tanımlayıcı küme olsun. O zaman $T$, $\mathcal{N} = \{0, 1, \dots, n - 1\}$ kümesinden alınan $\delta - 1$ tane ardışık elemanın oluşturduğu bir kümedir. O zaman Teorem 7.20$\mathcal{C}$, $\mathbb{F}_q$ üzerinde uzunluğu $n$, üreteç polinomu $g(x)$,eşkare üreteci $e(x)$ ve tanımlayıcı kümesi $T$ olan devirli bir kod olsun. $\mathcal{C}^c$, $\mathcal{C}$'nin devirli tümleyeni olsun. Aşağıdakiler sağlanır.

• $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.
📖 Detaya Git gereğince $\mathcal{C}$'nin devirli tümleyeni olan $\mathcal{C}^c$'nin tanımlayıcı kümesi $\mathcal{N} \setminus T$'dir, ki bu da $n - \delta + 1$ tane ardışık elemandan oluşan bir kümedir; bu da $\mathcal{C}^c$'nin RS olduğunu gösterir. Benzer şekilde, $(-1)T \pmod n$ de $\mathcal{N}$'den alınan $\delta - 1$ tane ardışık elemanın bir kümesi olduğundan, Teorem 7.21$\mathcal{C}$, $\mathbb{F}_q$ üzerinde üreteç polinomu $g(x)$, eşkare üreteci $e(x)$ ve tanımlayıcı kümesi $T$ olan bir $[n, k]$ devirli kodu olsun. $h(x) = (x^n - 1) / g(x)$ olsun. Aşağıdakiler sağlanır:

• $\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.
📖 Detaya Git gereği, $\mathcal{C}^\perp$'nin tanımlayıcı kümesi olan $\mathcal{N} \setminus (-1)T \pmod n$'nin de ardışık $n - \delta + 1$ elemandan oluşan bir küme olduğunu görürüz. Bu nedenle $\mathcal{C}^\perp$ bir RS kodudur.

Örnek 8.7

$\mathbb{F}_{13}$'ün ilkel bir elemanı 2'dir. $\mathcal{C}$, $\mathbb{F}_{13}$ üzerinde tasarlanmış uzaklığı 5 olan dar-anlamlı Reed-Solomon kodu olsun. Bu, tanımlayıcı kümesi $\{1, 2, 3, 4\}$ ve üreteç polinomu $(x - 2)(x - 2^2)(x - 2^3)(x - 2^4) = 10 + 2x + 7x^2 + 9x^3 + x^4$ olan 12 uzunluğunda bir koddur. Teorem 8.3$\mathcal{C}$, $\mathbb{F}_q$ üzerinde uzunluğu $n = q - 1$ ve tasarlanmış uzaklığı $\delta$ olan bir RS kodu olsun. O halde:

• $\mathcal{C}$'nin tanımlayıcı kümesi $T = \{b, b + 1, \dots, b + \delta - 2\}$ olacak şekilde bir $b$ tamsayısı vardır;

• $\mathcal{C}$'nin minimum uzaklığı $d = \delta$ ve boyutu $k = n - d + 1$'dir;

• $\mathcal{C}$ bir MDS koddur.
📖 Detaya Git'ten, $\mathcal{C}$'nin minimum uzaklığı 5'tir ve $\mathcal{C}$ bir $[12, 8, 5]$ MDS kodudur. $\mathcal{C}^\perp$, tanımlayıcı kümesi $\{0, 1, 2, 3, 4, 5, 6, 7\}$ ve üreteç polinomu $(x - 2^0)(x - 2^1)(x - 2^2) \dots (x - 2^7) = 3 + 12x + x^2 + 5x^3 + 11x^4 + 4x^5 + 10x^6 + 5x^7 + x^8$ olan bir $[12, 4, 9]$ Reed-Solomon kodudur. $\mathcal{C}$'nin dairesel tümleyeni, tanımlayıcı kümesi $\{5, 6, 7, 8, 9, 10, 11, 0\}$ ve üreteç polinomu $(x - 2^0)(x - 2^5)(x - 2^6) \dots (x - 2^{11}) = 9 + 6x + 12x^2 + 10x^3 + 8x^4 + 6x^5 + 9x^6 + 4x^7 + x^8$ olan $[12, 4, 9]$ Reed-Solomon kodudur.

Şimdi dar-anlamlı Reed-Solomon kodlarının alternatif bir formülasyonunu sunuyoruz ki bu Reed ve Solomon'un orijinal formülasyonudur. Dar-anlamlı RS kodlarının bu alternatif formülasyonu özellikle önemlidir çünkü sonraki bölümlerde göreceğimiz gibi genelleştirilmiş Reed-Solomon kodlarının, Goppa kodlarının ve cebirsel geometri kodlarının tanımlarının temelini oluşturur.

$k \ge 0$ için, $\mathcal{P}_k$, $\mathbb{F}_q[x]$ içinde sıfır polinomu da dahil olmak üzere derecesi $k$'dan küçük olan polinomların kümesini göstersin. Dikkat edilirse $\mathcal{P}_0$ sıfır polinomundan ibarettir. Ayrıca $\mathcal{P}_k$, $\ff_q$ üzerinde $k$ boyutlu bir vektör uzayıdır.

Teorem 8.4

$\alpha$, $\mathbb{F}_q$'nun ilkel bir elemanı olsun ve $k$, $0 \le k \le n = q - 1$ koşulunu sağlayan bir tamsayı olsun. O halde $$\mathcal{C} = \{(f(1), f(\alpha), f(\alpha^2), \dots, f(\alpha^{q-2})) \mid f \in \mathcal{P}_k\}$$ $\mathbb{F}_q$ üzerinde dar-anlamlı $[n, k, n - k + 1]$ RS kodudur.

Kanıt

$\mathcal{P}_k$, $\mathbb{F}_q[x]$'in $\mathbb{F}_q$ üzerinde doğrusal (lineer) bir alt uzayı olduğu için, $\mathcal{C}$'nin $\mathbb{F}_q$ üzerinde doğrusal bir kod olduğu açıktır. $\mathcal{P}_k$, $k$-boyutlu olduğundan, eğer $f$ ve $f_1$, $\mathcal{P}_k$'nın farklı elemanlarıysa bunlara karşılık gelen $\mathcal{C}$'deki elemanların da farklı olduğunu gösterebilirsek, $\mathcal{C}$ de $k$-boyutlu olacaktır. Eğer bu ikinciler eşitse, o zaman aralarındaki fark $\mathbf{0}$ vektörü olur ki bu da derecesi en fazla $k - 1$ olan sıfır olmayan $f - f_1$ gibi bir polinomunun $n \ge k$ tane kökü olacağı anlamına gelir; bu da bir çelişkidir. Dolayısıyla $\mathcal{C}$, $k$-boyutludur. $\mathcal{D}$, $\mathbb{F}_q$ üzerinde dar-anlamlı $[n, k, n - k + 1]$ RS kodu olsun. O zaman $\mathcal{D}$'nin tanımlayıcı kümesi $T = \{1, 2, \dots, n - k\}$ olur. $\mathcal{C} = \mathcal{D}$ olduğunu gösterelim. Her iki kod da $k$-boyutlu olduğundan $\mathcal{C} \subseteq \mathcal{D}$ olduğunu ispatlamak yeterlidir. $c(x) = \sum_{j=0}^{n-1} c_j x^j \in \mathcal{C}$ olsun. O zaman $0 \le j < n$ için $c_j = f(\alpha^j)$ olacak şekilde bir $f(x) = \sum_{m=0}^{k-1} f_m x^m \in \mathcal{P}_k$ vardır. $c(x) \in \mathcal{D}$ olduğunu göstermek için, $i \in T$ için $c(\alpha^i) = 0$ olduğunu göstermemiz gerekir. Eğer $i \in T$ ise, o zaman $$\begin{aligned} c(\alpha^i) &= \sum_{j=0}^{n-1} c_j \alpha^{ij} = \sum_{j=0}^{n-1} \left(\sum_{m=0}^{k-1} f_m \alpha^{jm}\right) \alpha^{ij} \\ &= \sum_{m=0}^{k-1} f_m \sum_{j=0}^{n-1} \alpha^{(i+m)j} = \sum_{m=0}^{k-1} f_m \frac{\alpha^{(i+m)n} - 1}{\alpha^{i+m} - 1}. \end{aligned}$$

Fakat $\alpha^{(i+m)n} = 1$ ve $1 \le i + m \le n - 1 = q - 2$ olduğundan ve $\alpha$ birimin $n$-yinci dereceden bir ilkel kökü olduğundan $\alpha^{i+m} \neq 1$'dir. Bu nedenle $i \in T$ için $c(\alpha^i) = 0$'dır, bu da $\mathcal{C} \subseteq \mathcal{D}$ olduğunu gösterir. Sonuç olarak $\mathcal{C} = \mathcal{D}$ elde edilir.