Döngüsel kod

Kodlama kuramında döngüsel kod, her bir kod sözcüğün dairesel kaydırılarak başka bir sözcük oluşturan bir blok koddur. Cebirsel özelliklere sahiptir ve ileri hata düzeltme yöntemini kullanarak hata bulma ve düzeltmeye etki eder.

Eğer 00010111 geçerli bir kod sözcüğü olursa, sağa dairesel kaydırılarak 10001011 dizisi elde edilir. Kod eğer döngüsel ise 10001011, tekrar geçerli bir kod sözcüğü olur. Genellikle sağa dairesel kaydırma işleminde, düşük öncelikli bir (LSB) en sol konuma gider. Böylece yüksek öncelikli bit (MSB) olur. Diğer konumlar 1 bit sağa kaydırılır.

Tanım

${\mathcal {C}}$, n blok uzunluğuna sahip ve $GF(q)$ sonlu alanında bir doğrusal kod olsun. Eğer C deki tüm kod sözcükler için c=(c₁,...,c_n) oluyorsa, ${\mathcal {C}}$, döngüsel kod olarak adlandırılır. $GF(q)^{n}$ deki (c_n,c₁,...,c_n-1) ifadesi dairesel sağa kaydırma ile elde edilir. Çünkü bir döngüsel sağa kaydırma, n − 1 döngüsel sola kaydırmaya eşittir. Bir döngüsel kod, döngüsel sola kaydırma ile de tanımlanabilir. Bu yüzden tüm döngüsel kaydırmalar altında sabit kaldığı müddetçe, ${\mathcal {C}}$ doğrusal kodu kesin döngüseldir.

Cebirsel yapısı

Döngüsel kodlar, belirli halkalara bağlanabilir. $R=A[x]/(x^{n}-1)$, $A=GF(q)$ sonlu alanında bir polinom halka olsun. R polinomunda C döngüsel kodun $(c_{0},\ldots ,c_{n-1})$ elemanları $c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}$ polinomu ile eşleştirilerek belirlenir: Burada bir döngüsel kaydırmaya uygun olarak x ile çarpılır. Ardından C, R sonlu alanında bir ideal olur.

Kod ideal olduğunda indirgenemez kod, döngüsel kod olur. Bu kod indirgenemez polinom ile oluşturulur.

Örnekler

Örneğin, eğer A=$\mathbb {F} _{2}$ ve n=3 olursa, (1,1,0) döngüsel kodundan oluşan kod sözcüğü kümesi aynen şöyle olur:

$((0,0,0),(1,1,0),(0,1,1),(1,0,1))\,$.

$(1+x)$ ile oluşturularak $\mathbb {F} _{2}[x]/(x^{3}-1)$ de ideal hale gelir.

$(1+x)$, polinom halkasında bir indirgenemez polinom olduğuna dikkat edin. Çünkü kodu indirgenemez.

Ayrıca bakınız

• Döngüsel artıklık denetimi
• Polinom kod