Döngüsel artıklık denetimi

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

CRC (Cyclic Redundancy Check) verilerin hatalı olup olmadığını anlamamıza yardım eden bir yöntemi anlatır. Uygulaması kolay ve güvenliği güçlü bir tekniktir. Gönderici her çerçeveye n bitlik FCS (Frame Check Squence) dizi ekler. CRC veri iletiminde kullanılan en yaygın hata denetimi yöntemidir. Az bir ek bilgi ile daha fazla hata tespiti sağlanır. Veri iletirken ya da saklarken ilettiğimiz/sakladığımız veri ile alınan verinin aynı olduğundan emin olmamız gerekir. Veriler iletim hattında bozunuma uğrarsa bunun farkedilmesi ve verilerin yeniden iletilmesi gerekir. CRC, bu amaçla kullanılır.

CRC veri bitlerini polinom kodlar olarak ele alır. Veriler gönderici tarafından çerçevenin içeriğine göre her çerçevenin sonuna eklenecek bir denetim seti(check digits) hesaplanarak gönderilir. Alıcı taraf veri üzerinde aynı denetim işlemlerini gerçekleştirerek aldığı veride hata olup olmadığını kontrol eder. İki sonuç uymuyorsa bu hata olduğunu gösterir. n bitlik FCS için n+1 bit bir P polinomu kullanılır. Amaç FCS'yi Q/P sıfır olacak şekilde elde etmektir.

(M.2n+R)/P=Q+(R/P+R/P)

M: k bitlik asıl veri
R: kalan n bitlik sayı
P: üreteç polinomu n+1 bit
Q: FCS dizisi

CRC oluşturulması ilk olarak veri içeriği 2n ile çarpılır. Bu verinin sonuna n adet 0 ekleme demektir.İkinci adımda P üreteç polinomu ile bölünmesi üçüncü adımda kalanın FCS olarak iletilmesidir.

CRC kontrolü ise ilk olarak veri çerçevesi alınır. İkinci adımda P üreteç polinomuna bölünür. Üçüncü adımda kalan kontrol edilir. Kalan 0 ise veri doğru aksi halde hata oluşmuştur.

Bir örnek verelim:

                              VERİLER                                CRC
       90     69     66     82     65     79     78     69            3
Yukardaki verilerin rakamsal toplamı 598’dir. Örnekteki P sayımız da 17 olsun.
Toplam=598
P=17
598/17=35, kalan=3
Bu veri alındığında da şu işlem yapılır:
598-3)/17=35, kalan=0 (hatasız iletim)

Eğer iletilen veriler hatalı ise bu verilerin toplamı 598 olmayacaktır, dolayısı ile kalan da 0 olmaz. Buradan verilerde bir bozulma olduğu anlaşılır ve veriler tekrar iletilir/saklanır. CRC’nin kelime anlamı da yapılan işlemi anlatır (dönemsel kalan kontrolü; dönemseldir, çünkü bütün veri bloklara bölünür ve CRC işlemi herbir blok için uygulanır)

CRC yöntemi yüzde yüz güvenilir bir yöntem değildir. Yine örneğimizdeki verilere dönersek altıncı verinin 79 değil de 96 olacak şekilde bozulduğunu varsayalım (yani P kadar). Bu durumda karşı tarafın eline geçen verilerin toplamı 615 olacaktır. CRC işlemini uyguladığımızda:

       (615-3)/17=36, kalan=0

Yani, bir hatalı iletim söz konusu olduğu halde bu hata farkedilememiştir. Ama verilerin P ve P’nin katları kadar bozulma olasılığı hayli düşüktür. Bu yüzden hataların büyük bölümü CRC yöntemi ile saptanabilir.

Matematiksel İfade

1-)Veri katarı P(x) denilen bir polinom ile gösterilir.

P(x)=bn-1.xn-1+ bn-2.xn-2 +...+ b1.x1 + b0.x0


(1010010111) bit dizisine karşılık gelen polinom

P(x)=1.x9 +0.x8 +1.x7 +0.x6 +0.x5 +1.x4+0.x3+1.x2+1.x1+1.x0

   =x9+X7+X4+X2+X+1

2-)P(x) polinomu XP ile çarpılır.Bu işlem sonucu elde edilir.Önceki bit katarı ile onun sonuna eklenmiş P tane 0 bitinden oluşur. 1010010111 00...00 P tane

3-) XP.P(x) polinomu P. Derecede G(x) üreteç polinomuna bölünür.Üreteç polinom belirli hata sezme özelliğine sahip standart bir polinomdur.

X16+x15+x2+1, x12+x11+x3+x2+x+1, x16+x15+x5+1

4-)XP.P(x)/G(x)

XP.P(x)=Q(x).G(x)+R(x) şeklindedir.

XP.P(x)+R(x)=Q(x).G(x)

XP.P(x)-R(x)=Q(x).G(x)

Gönderi alıcıya P(x) yerine XP.P(x) +R(x) polinomu göndersin.Alıcı kendisine gelen bit dizisini G(x)’e böler.Bölme sonunda kalan olmamaktadır.Alıcı hata yoksa bit dizisinin en sonundaki P adet biti atarak bilgiyi elde eder.

Örnek) (11100101011) bit dizisini içeren CRC bitini hesaplayınız?

1-) P(x) =x10+X9+X8+X5+X3+X+1

2-)Üreteç Fonksiyon=G(x)= x4+x2+x+1 => XP = x4 olur.

    x4.P(x)= x4(x10+X9+X8+X5+X3+X+1)
           = x14+x13+X12+X9+X7+X5+X4

3-) x4.P(x)’i üreteç fonksiyona bölme

  CRC2.jpg
    XP.P(x)= x14+x13+X12+X9+X7+X5+X4     
       G(x)= x4+x2+x+1   
       Q(x)= x10+x9+X3
       R(x)= X3   

4-)Q(x).G(x)= XP.P(x)+ R(x)

           =  x14+x13+X12+X9+X7+X5+X4+X3
           =(11100101011 - 1000)  
               P(x)     - CRC biti