Döngüsel artıklık denetimi

Döngüsel artıklık denetimi (CRC: Cyclic Redundancy Check), çoğunlukla sayısal şebekelerde ve depolama cihazlarında kullanılan ve ham veride yapılan hatalı değişimleri algılayan, uygulaması kolay ve güvenliği güçlü bir hata bulma yöntemidir.

CRC'ler, denetim (veri doğrulama) değerinde (enformasyon eklenmeden gönderilen) bir artıklık ve döngüsel kodların temelini oluşturan bir algoritma olduğu için bu adla adlandırılır. İkili donanımlarda uygulaması basit, matematiksel analizi kolay ve bilhassa iletim kanallarında gürültünün neden olduğu genel hataları algılamada iyi olduğu için CRC'lerin kullanımı yaygındır. Çünkü denetim değeri sabit bir uzunluğa sahiptir. Bunu oluşturan fonksiyon nadiren bir hash fonksiyonu olarak kullanılır.

Açıklama

CRC'ler ileri hata düzeltme yöntemindeki döngüsel kodun temelini oluştururlar. Sabit uzunlukta bir denetleme değeri ekleyerek mesajların kodunu çözen sistematik döngüsel kodları kullanarak, telekomünikasyon şebekelerinde hata düzeltme ilk olarak 1961'de W. Wesley Peterson tarafından yapılmıştır. Döngüsel kodların yalnızca uygulaması kolay değil, aynı zamanda özellikle patlama hatasının düzeltilmesi için çok idealdir. Patlama hataları, manyetik ve optik veri depolama cihazlarındaki kanallar gibi çoğu iletişim kanalında yaygın bulunan hatalardır. Bir n bitlik CRC'nin tipik uygulaması, rastgele uzunluklu bir veri bloğunun, n bitten uzun olmayan herhangi tek bir patlama hatasını algılamasıdır. Patlama hatalarının tümünün uzunluğu 1 - 2^-n ifadesinin bir kesri olarak algılanır. 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 fark edilmesi ve verilerin yeniden iletilmesi gerekir. CRC, bu amaçla kullanılır.

Bir CRC kodunu belirlemek için, sözde polinom kod tanımlamak gerekir. Bu polinomdaki, bölme algoritmasında, bölünen, bölen, bölüm ve kalan bulunur. Burada önemli olan polinom katsayıları, sonlu alanın aritmetiğine uygun olarak hesaplanmasıdır. Böylece toplama işlemi, (dijitler (rakamlar) arasında taşıma olmayan) bitsel paralelliği daima gerçekleştirebilir. Kalanın uzunluğu, polinom kod uzunluğundan daima daha küçüktür. Böylece sonucun hangi uzunlukta olacağı belirlenir.

Pratikte, kullanılan tüm CRC'ler, bilgisayar mimarisi ile eşleşen, 0 ve 1 olarak adlandırılan iki elemanlı GF(2) sonlu alanı ile ilgilidir.

En basit hata düzeltme sistemi, eşlik biti, 1 bitlik CRC'nin durumu ile ilgilidir. CRC-1 olarak adlandırılan ve iki terimli olan x + 1 polinom kodunu kullanır.

CRC'ler ve veri tutarlılığı

CRC'ler, özellikle iletişim kanallarında sıkça rastlanan hata türlerine karşı koruma sağlamak amacıyla tasarlanır. Teslim edilen mesajların tutarlılığını hızlı ve güvenli biçimde gerçekleştirebilirler. Fakat veride istenerek yapılan değişimlere karşı uygun değillerdir.

Birincisi, kimlik denetimi olmadığından dolayı saldırgan mesajı değiştirebilir ve bunun fark edilmeyecek şekilde CRC'yi tekrar hesaplayabilir. Veri yan yana saklandığında CRC'ler ve kriptografik hash fonksiyonları veride istenerek yapılan değişimlere karşı birbirlerini koruyamazlar. Bu tür saldırılara karşı korunmak için, (temelinde kriptografik özet fonksiyonu bulunan) mesaj doğrulama kodu veya dijital imza gibi kriptografik kimlik denetimi mekanizmaları kullanılmalıdır.

İkincisi, kriptografik özet fonksiyonu aksine, CRC kolay terslenebilir fonksiyondur. Bu da dijital imzaların kullanılmasını imkânsız kılar.

Üçüncüsü, CRC aşağıdaki denkleme sahip bir doğrusal fonksiyondur. $\operatorname {crc} (x\oplus y\oplus z)=\operatorname {crc} (x)\oplus \operatorname {crc} (y)\oplus \operatorname {crc} (z)$ ;

Sonuçta CRC bir dizi şifresi (veya blok şifreleme kipi) ile şifrelenmiş olsa bile, şifreleme anahtarını bilmeye gerek kalmaksızın hem mesaj hem de ilgili CRC ele geçirilebilir. Bu, WEP iletişim kuralının bilenen bir kusurudur.

CRC hesaplama

n bitlik ikili CRC'yi hesaplamak için, bir satırdaki girişi ifade eden bitler ve (polinom olarak adlandırılan) CRC'nin bölenini ifade eden (n+1) bitlik dizinin konumu satırın sol alt köşesindedir.

İkili sayı sistemine örnek

Aşağıdaki örnekte 14 bitlik mesajın kodunu 3 bitlik CRC ve x³+x+1 polinomu ile çözeceğiz. 3.dereceden bir polinomdur ve dört katsayıya sahiptir. Bu polinom ikili sayı sisteminde katsayılarla şöyle yazılır; 1x³+0x²+1x+1. Bu durumda katsayılar; 1, 0, 1 ve 1'dir. Hesaplama sonucu 3 bit uzunluğundadır.

Mesaj şu kod çözülerek başlar:

11010011101100

CRC'nin n bit uzunluğuna uygun olarak ilk önce sıfırlar eklenir. 3 bitlik bir CRC'yi hesaplamak için ilk hesaplama adımı şöyledir:

11010011101100 000 <--- 3 bit girişin sağına eklenir
1011               <--- bölen (4 bit) = x³+x+1
------------------
01100011101100 000 <--- sonuç

Her bir adımda bitlere yukarıdaki bölen doğrudan etki eder. Bu yineleme için sonuç, yukarıdaki bitlere sahip bitsel XOR bölen polinomudur. Yukarıda olmayan bitler için bölen basitçe doğrudan bu adımın altına kopyalanır. Bölen sağa bir bit kaydırılır. Bölen, giriş satırının en sağ köşesine ulaşıncaya kadar bu işlem tekrarlanır. İşlemin tamamı şöyledir:

11010011101100 000 <--- 3 bit girişin sağına eklenir
1011               <--- bölen
01100011101100 000 <--- sonuç (ilk dört bitin, altındaki bölen ile aynı ve XOR olduğuna dikkat edin, bitlerin geri kalanı değiştirilmedi)
 1011              <--- bölen ...
00111011101100 000
  1011
00010111101100 000
   1011
00000001101100 000 <--- bölümdeki sonraki 1 ile hizalanması için bölenin taşındığına dikkat edin (çünkü burada bölüm sıfır idi)
       1011             (yani her yinelemede yalnızca bir bit kaydırma gereksizdir)
00000000110100 000
        1011
00000000011000 000
         1011
00000000001110 000
          1011
00000000000101 000 
           101 1
-----------------
00000000000000 100 <--- kalan (3 bit). Bölme algoritması burada durduruldu. Çünkü bölüm sıfıra eşittir.

Bölenin en solundaki bit 1 olduğundan dolayı her bir girişte en soldaki bölüm biti sıfırlanır. Yalnızca giriş satırının (bölümün) en sağındaki n bit sıfırlanamadığında bu işlem sonlandırılır. n bit, bölme adımındaki kalandır. Bunlar aynı zamanda CRC fonksiyonunun değeri olur.

Alınan bir mesajın geçerliliği, yukarıdaki hesaplama tekrar gerçekleştirilerek kolayca doğrulanabilir. Burada sıfırlar yerine denetleme değeri konur. Eğer hata algılanmazsa kalan sıfıra eşitlenir.

11010011101100 100 <--- denetleme değerli giriş
1011               <--- bölen
01100011101100 100 <--- sonuç
 1011              <--- bölen ...
00111011101100 100

......
  
00000000001110 100
          1011
00000000000101 100 
           101 1
------------------
                 0 <--- kalan

Onlu sayı sistemine örnek

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.2ⁿ+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 2ⁿ 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.

                              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 her bir 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 fark edilememiş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)=b_n-1.x^n-1+ b_n-2.x^n-2 +...+ b₁.x¹ + b₀.x⁰

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

P(x)=1.x⁹ +0.x⁸ +1.x⁷ +0.x⁶ +0.x⁵ +1.x⁴+0.x³+1.x²+1.x¹+1.x⁰

   =x⁹+X⁷+X⁴+X²+X+1

2-)P(x) polinomu X^P 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-) X^P.P(x) polinomu P. Derecede G(x) üreteç polinomuna bölünür.Üreteç polinom belirli hata sezme özelliğine sahip standart bir polinomdur.

X¹⁶+x¹⁵+x²+1, x¹²+x¹¹+x³+x²+x+1, x¹⁶+x¹⁵+x⁵+1

4-)X^P.P(x)/G(x)

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

X^P.P(x)+R(x)=Q(x).G(x)

X^P.P(x)-R(x)=Q(x).G(x)

Gönderi alıcıya P(x) yerine X^P.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.

Karışık örnek

11100101011 bit dizisini içeren CRC bitini hesaplayalım

1-) P(x) =x¹⁰+X⁹+X⁸+X⁵+X³+X+1

2-)Üreteç fonksiyon: G(x)= x⁴+x²+x+1 => X^P = x⁴ olur.

    x⁴.P(x)= x⁴(x¹⁰+X⁹+X⁸+X⁵+X³+X+1)
           = x¹⁴+x¹³+X¹²+X⁹+X⁷+X⁵+X⁴

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

    X^P.P(x)= x¹⁴+x¹³+X¹²+X⁹+X⁷+X⁵+X⁴     
       G(x)= x⁴+x²+x+1   
       Q(x)= x¹⁰+x⁹+X³
       R(x)= X³

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

           =  x¹⁴+x¹³+X¹²+X⁹+X⁷+X⁵+X⁴+X³
           =(11100101011 - 1000)  
               P(x)     - CRC biti

CRC matematiği

Bu bölme benzeri işlemde, iyi hata düzeltme özelliklerini garanti altına almak için nasıl bir bölen seçilmesi gerektiğinde matematik analizin önemi açığa çıkar. Bu analizde, bit dizisindeki rakamlar, x—değişkenine sahip bir polinomun katsayılarıdır. Bunlar, bilinen sayılar yerine, daha çok GF(2) sonlu alanının elemanlarıdır. İkili polinomlar kümesi, bir matematik halkasıdır.

CRC polinomunu tasarlama

Polinom kodun seçilmesi, CRC algoritmasını uygulamanın en önemli kısmıdır. Hata düzeltme kabiliyetini azami yapacak ve aynı anda çakışma ihtimalini asgari seviyeye indirecek şekilde polinom seçilmelidir.

Polinomun uzunluğu (herhangi bir terimin en büyük derecesi (üssü) +1) en önemli özelliğidir. Çünkü bu hesaplanan denetleme değerinin uzunluğunu doğrudan etkiler.

Sıkça kullanılan polinom uzunlukları şunlardır:

9 bit (CRC-8)
17 bit (CRC-16)
33 bit (CRC-32)
65 bit (CRC-64)

Denetleme değeri n bit olan bir CRC n bitlik CRC olarak adlandırılır. En yüksek derecesi n olan bir polinomun n+1 terimi vardır. Bu polinomun uzunluğu n+1'dir. Kalan n uzunluğundadır. CRC, CRC-n-XXX biçimini alır.

Korunacak azami toprak blok uzunluğuna (veri + CRC bitleri), belirlenen hata düzeltme özelliklerine ve CRC uygulamasındaki kaynak türlerine ve hatta istenen performansa göre CRC polinomunu tasarlanır. En büyük yanılgı, "en iyi" CRC polinomlarının ya indirgenemez polinom ya da indirgenemez polinomların 1 + x faktörü ile çarpılmasıyla türetilebileceğidir. Gerçekte, yukarıda bahsedilen tüm faktörler, polinom seçme yöntemi olabilir ve indirgenebilir polinoma yol gösterebilir. Fakat indirgenebilir polinom seçme, bölüm halkasının sıfır böleni bulunduğundan dolayı, hataları azaltmada belirli bir orana sahiptir.

Sıkça kullanılan ve standartlaşan CRC'ler

Ad	Kullanımları	İfadeleri
Ad	Kullanımları	Normal	Ayrılmış	Karşılıklı ayrılmış
CRC-1	çoğu donanım; eşlik biti olarak da bilinir	0x1	0x1	0x1
CRC-4-ITU	G.704	0x3	0xC	0x9
CRC-5-EPC	Gen 2 RFID	0x09	0x12	0x14
CRC-5-ITU	G.704	0x15	0x15	0x1A
CRC-5-USB	USB paketleri	0x05	0x14	0x12
CRC-6-CDMA2000-A	hücresel ağlar	0x27	0x39	0x33
CRC-6-CDMA2000-B	hücresel ağlar	0x07	0x38	0x23
CRC-6-ITU	G.704	0x03	0x30	0x21
CRC-7	telekomünikasyon sistemleri, G.707, G.832, MMC, SD	0x09	0x48	0x44
CRC-7-MVB	Tren haberleşme şebekesi, IEC 60870-5	0x65	0x53	0x72
CRC-8		0xD5	0xAB	0xEA
CRC-8-ITU-T	I.432.1; ATM HEC, ISDN HEC ve hücre betimleme	0x07	0xE0	0x83
CRC-8-Dallas/Maxim	1 kablolu veriyolu	0x31	0x8C	0x98
CRC-8-SAE J1850	AES3	0x1D	0xB8	0x8E
CRC-8-WCDMA	hücresel ağlar	0x9B	0xD9	0xCD
CRC-10	ATM; I.610	0x233	0x331	0x319
CRC-10-CDMA2000	hücresel ağlar	0x3D9	0x26F	0x3EC
CRC-11	FlexRay	0x385	0x50E	0x5C2
CRC-12	telekomünikasyon sistemleri	0x80F	0xF01	0xC07
CRC-12-CDMA2000	hücresel ağlar	0xF13	0xC8F	0xF89
CRC-13-BBC	Zaman sinyali	0x1CF5	0x15E7	0x1E7A
CRC-15-Denetleyici alan ağı (CAN)		0x4599	0x4CD1	0x62CC
CRC-15-MPT-1327		0x6815	0x540B	0x740A
Chakravarty	yüklere özel ≤64 bit	0x2F15	0xA8F4	0x978A
CRC-16-ARINC	ACARS uygulamaları	0xA02B	0xD405	0xD015
CRC-16-CCITT	X.25, V.41, HDLC FCS, XMODEM, Bluetooth, PACTOR, SD, diğer bir çokları; CRC-CCITT olarak da bilinir	0x1021	0x8408	0x8810
CRC-16-CDMA2000	hücresel ağlar	0xC867	0xE613	0xE433
CRC-16-DECT		0x0589	0x91A0	0x82C4
CRC-16-T10-DIF	SCSI DIF		0xEDD1	0xC5DB
CRC-16-DNP	DNP, IEC 870, M-Bus	0x3D65	0xA6BC	0x9EB2
CRC-16-IBM	Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, diğer bir çokları; CRC-16 ve CRC-16-ANSI olarak da bilinir	0x8005	0xA001	0xC002
Fletcher	Adler-32 A & B CRC'ler kullanılır	Bir CRC değildir
CRC-17-CAN	CAN FD	0x1685B	0x1B42D	0x1B42D
CRC-21-CAN	CAN FD	0x102899	0x132281	0x18144C
CRC-24	FlexRay	0x5D6DCB	0xD3B6BA	0xAEB6E5
CRC-24-Radix-64	OpenPGP, RTCM104v3	0x864CFB	0xDF3261	0xC3267D
CRC-30	CDMA	0x2030B9C7	0x38E74301	0x30185CE3
Adler-32	Zlib	Bir CRC değildir
CRC-32	HDLC, ANSI X3.66, ITU-T V.42, Ethernet, SATA, MPEG-2, PKZIP, Gzip, Bzip2, PNG, diğer bir çokları	0x04C11DB7	0xEDB88320	0x82608EDB
CRC-32C (Castagnoli)	iSCSI, SCTP, G.hn yükü, SSE4.2, Btrfs, ext4	0x1EDC6F41	0x82F63B78	0x8F6E37A0
CRC-32K (Koopman)		0x741B8CD7	0xEB31D82E	0xBA0DC66B
CRC-32Q	havacılık; AIXM	0x814141AB	0xD5828281	0xC0A0A0D5
CRC-40-GSM	GSM kontrol kanalı	0x0004820009	0x9000412000	0x8002410004
CRC-64-ECMA	ECMA-182, XZ Utils	0x42F0E1EBA9EA3693	0xC96C5795D7870F42	0xA17870F5D4F51B49
CRC-64-ISO	HDLC, Swiss-Prot/TrEMBL; bozma için uyarı olarak nitelendirilir	0x000000000000001B	0xD800000000000000	0x800000000000000D