CRC Nedir nerde nasıl ne için kullanılabilir

Merhaba sevgili okurlarım, Google ve diğer botlar.

Bugün CRC’den size bahsedeceğim.  CRC – Cyclic Redundancy Check dediğimiz arkadaş bir veri kontrol formatıdır. Bugunlerde Check Digitlerden bahsettim bol bol birde CRC yani türkçe adı ile Döngüsel Artıklık Denetimi . “Hata sezen” kod olarakta bilinir.

Mantıksal anlatımını çok iyi yapmayacağımdan bunun ile ilgili beğendiğim bir yaziyi Copy/Paste yaparacagim.

Öncelikle belirteyim bu CRC haberleşmede kullanılan ve “hata sezen” kod adı verilen bir yöntemdir. Zaten iki tip yöntem var: Hata sezen ve hata düzelten. Hata sezen, adından da anlaşılabileceği gibi, sadece verinin düzgün iletilip iletilmediğini anlamaya yarar. Hata düzelten ise hatayı bulur ve düzeltir. Peki hangi durumlarda bu ikisinden biri seçilir:

Diyelim ki uydu ile haberleşiyoruz. Burada uyduya aktarılan veriler (Uplink) ve uydudan gelen veriler (Downlink) oldukça yavaş aslında. Sonuçta uydunun avantajı çok geniş bir alanı kaplamasıdır. (Tüm dünya misal?) Burada hata sezen kod kullanırsak olası bir hata durumunda uydu bu durumu, veriyi aldığı merkeze belirtir ve aynı veri tekrar aktarılır. Zaten sistem yavaş, üstüne de böyle bir durum olursa daha bir yavaşlar diye bu noktada hata düzelten kod kullanılır. Hatayı düzeltebilmesi için verinin boyutu arttırılmalıdır. Hata düzelten yöntemini daha sonra farklı bir yazıda açıklayacağım. Hata sezen kodlara geri dönelim…

Yukarıdaki açıklamadan sonra herhalde nerede kullanılabileceği tahmin edilebilir: Aktarım hızımız çok yüksekse ve hatalı bir veri gelince bunun tekrar alınması sisteme koymayacaksa kullanılması gayet güzeldir hata sezen kodların. İşte bizim CRC de bunu yapmakta.

CRC’deki temel mantık, gönderilecek verinin sonuna verinin daha önceden belirlenen bir sayıya bölümünden kalan eklenir. Karşı taraf bu veri kümesini alınca daha önceden belirlenmiş sayıya böler. Sonuç sıfır ise veri hatasız aktarılmıştır. Olayı rakamlara dökmek daha iyi açıklayacaktır:

Misal göndermek istediğimiz veri 10011010 olsun. (Tamamen attım) Bu bölücü sayımız da (bu noktadan itibaren buna polinom diyeceğim sınavda filan sorulursa işin ezberi bu şekilde çünkü) belirlenebilir bir şey. Misal bu polinom da 11001 olsun diyorsam tamamen atıyorum ama hem alıcı hem verici bunu biliyor farz ediyorumdur. Sınavda da zaten “Falanca veriyi şu polinomla, CRC kodlaması ile nasıl göndeririz?” gibi bir soru çıkacaktır. Bu noktada sadece bu iki sayıyı birbirine bölüp verinin sonuna dört bit olarak eklememiz kafi ancak yine işin biraz ezberine girelim:

Veri 10011010 denmişse bunu bir polinom gibi yazmamız gerekiyor önce: Bunun için ikilik tabandaki bir sayıyı onluk tabana çevirirken kullandığımız “iki üzeri” terimleri yerine “x üzeri” diyoruz. Yani normalde bu sayı 2^7+2^4+2^3+2^1 iken biz buna x^7+x^4+x^3+x^1 diyoruz. Aynı şekilde bölücü polinom da (11001 demiştik üstte) x^4+x^3+1 oluyor. (Son hane x^0=1 durumunda) Bu noktadan sonra kısaca verinin sonuna dört bit sıfır ekliyoruz demek yerine iletilecek polinomu x^4 ile genişletiyoruz diyoruz. Yani 10011010, 100110100000 oluyor ve yine bunu polinom olarak yazarsak x^11+x^8+x^7+x^5 oluyor. Daha sonra son halindeki veri polinomu ile elimizdeki polinom üzerinde bölme işlemi uygulayıp son bitleri kalan ile değiştiriyoruz ve iş bitiyor. Bu noktadan sonra bir konuya netlik getireyim: Sakın bu işlemi onluk taban üzerinden yapmayın!

10011010 onluk tabanda 154’e karşılık gelmektedir. Elimizdeki bölücü polinom da (11001) 25’e denk geliyor. İkisini birbirine bölersek kalan dört çıkar. Bölüm bizi zerre ilgilendirmiyor ama kalan önemli. Onluk tabanda dört, ikilikte 0100’a denk gelmekte. Yani gönderilecek veri 100110100100 olacak… Değil aslında. Haydi diyelim sonun dört sıfır atmıştık yeni veri 100110100000 aslında diyelim ve o da onluk tabanda 2464’e denk gelmekte. Buna da 25’i bölersek kalan 13(1101) çıkıyor. Ancak donanımsal olarak bu bölme işlemi biraz farklı olduğundan az sonra göreceksiniz ki sonuç farklı çıkmakta…

100110100000| 11001
11001 | Bölüm de artık neyse… Siyah yazdıklarım bölme gereği bir aşağı inen bitler
010100
11001
011011
11001
00010000
11001
010010
11001
010110
11001
01111 —> Bakıyoruz ki kalan ne 0100 ne de 1101 çıktı.

Bilenler fark etmiştir sürekli iki değeri XOR’ladık. (Özel veya) XOR’un mantığı, aynı olan bitler 0, farklı olan bitler 1 çıkışı verir. Polinom aritmetiğinde bölme bölme diye sürekli söylediğim yerde bu XOR kullanılır ki bu fark da buradan geliyor. Hadi diyelim ben bu işlemi yanlış yaptım. Hemen Prentice Hall: Computer Networks, Fourth Edition kitabındaki örneği yazının sonuna yapıştırıyorum. Buradaki örneği ondalık olarak ele alalım:

Burada gönderilecek veri 1101011011 olarak belirtilmiş ve kendisi 859 yapıyor ondalık olarak. Bunun bi de sonunda dört sıfır olan 11010110110000 halini ele alırsak o da 13744 ‘e denk gelmekte. Bölüyoruz polinoma ki kendisi de 10011, ondalık 19, ilk hali ile kalan dört, uzatılmış halinde kalan yedi. Eee resme bi bakıyoruz (adamlar bölmüş güzel güzel göstere göstere) ve sonuç 1110 çıkmış, ondalık da 14 ediyor kendisi.

Bu ondalık işine nerden bulaştın derseniz; internette Türkçe kaynaklar genelde bu ondalık sistem üzerinden anlatıyor. Ben de garibim baktım çok da mantıklı geldi (kolay da), sınavda tuttum böle yaptım. Hocaya göstermelik de bu bölme işlemini yaptım ama bi baktım sonuç farklı! Dedim heralde yanlış işlem yaptım ondalık rakamlar yalan söylemez(!) sonucu değiştirverdim. Sonuç: Sınavdan -10 puan…

Neyse işte bu şekilde CRC kodlama ile gönderdik kodu, karşı tarafta alıp bölme işlemini yapıyor. Bu sondaki kalan eklenmiş halinde polinom bölmesi yapınca sonuç sıfır oluyor! Oldu ise tamam, durum güzel. Bu bölücü polinom iki tarafca da biliniyor kabul ediyoruz, tekrar belirteyim. Zaten en basitinden şifreli bir dosya açarken “CRC failed” diye bir hata alırsınız eğer şifre yanlışsa. Bu şifre de bizim polinomumuz olmuş oluyor.

Umarım yeterli açıklama yapabilmişimdirim. İnternet iyi güzel hoş, bilgi var da doğru bilgiyi ayırt edebilmek lazım(mış). Ben CRC için yapamadım bu ayrımı, sınavdan sonra dank etti ama olan oldu bi kere…

CRC.jpg

1 comment

  1. Geri bildirim: Encryption.ml

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.