CRC Matematiği

[kantirici]

@cicjoe açıklamalar için çok teşekkürler.

[cicjoe]

rica ederim =)

[SpeedyX]

C Compile time da verilen dizinin CRC-16-CCITT değerini hesaplayan makro yazmak istiyorum.

#define CRC16(s) (........)
crc = CRC16("deneme123");

x16 + x12 + x5 + 1 (CRC-16-CCITT) - 0x1021

Linkteki sayfada detaylar var ama #define ile bunu nasıl yapabiliriz hiç düşündünüz mü?

[ziyaretci]

Tablo yöntemiyle hesaplamada(8 bit için), eğer benim datam 128 ve polinomumda 32 ise ve alıcı tarafdaki data 64 ise veri hatalı alınmış oluyor yani hatayı sezemiyoruz.

Bu durumda, tabloyu oluşturma mantığı şöyle mi oluyor?

Polinom tablomu çift-tek-çift-tek değerler olarak hazırlarım. Data çift ise ve son kalanın indeks değeride çift ise son kalanımı bir arttırıp yeni indeksimle hesaba sokarım. Nasıl olasa bir sonrakinin çift ya da tek olduğunu biliyorum. Katı gelme durumunu böyle hallettik diyelim.

Ama tablodaki değerler neye göre belirleniyor halen anlayamadım. Ben çift olarak 0xAA, tek olarak 0x55 döşerdim.


Düşünüyorum..   Hocalarım bu duruma açıklık getirirse mükemmel olur. Şayet mantığını kavrayamadığım şeyi kullanmak beni huzursuz yapıyor ve kullanmak istemiyorum.

[mr.engineer]

CRC hesabının mantığı nedir?

CRC hesabında kullanılan polinom nasıl seçilir?

Google cevabı isteyene link verebilirim. Matematiğini tartışacaklar buyursun.

Kim bana CRC yi anlatabilir?

Geçen sene bir şirketin mülakat sorusuydu. Ben de o zaman araştırmıştım.
Elimizde bir message frame var. Hata kontrolü amacıyla bunu transmit etmeden önce sonuna seçilen bir polinoma göre n bits (CRC code) ekliyoruz.
Message frame =m(x)
Seçtiğimiz polinom = P(x)
CRC Code= c(x) olsun
Transmit sırasında oluşabilecek n-bitlik error = E(x)
Received message = R(x)


Seçilen polinomun derecesi kadar(yanlış olabilir kontrol ediniz) bit message frame sonuna eklenecek. Bu eklenen bitlere CRC code dersek; m'(x)+c(x) = 0(modP(x)) kuralı sağlanmalıdır. Not: Burada sonuna n tane bit eklediğimiz için m'(x) derecesi m(x)'den büyük olacak. c(x) de n-bit kadar olacak.

Şimdi biz transmitter'dan m'(x)+ c(x) yolladık. Receiver'da bizim kullandığımız polinmomu biliyor. Şu kontrol yapılacak R(x) ? 0(modP(x)). Transmit sırasında bir hata olmasını da hesaba katarsak received message;

R(x) = m'(x)+c(x) + E(x)

Şimdi bu R(x) eğer P(x) e tam bölünürse receiver diyecek ki hata yok, bölünmezse hata var diyecek.

m'(x)+c(x) zaten P(x) in katı olacak şekilde ayarlamıştık. Dolayısıyla E(x) = 0 (mod(P(x)) ise receiver hata yok diyecek.

E(x) = x ise ...00000010 sadece bir bitlik hata var demek.
E(x) = x2 + x+ 1 ise ...00000111 olmak üzere toplam üç bitlik hata var demek

Ama burada şöyle bir sorun var; öyle bir hata meydana gelir ki E(x) sıfırdan farklı iken E(x) = 0 (mod(P(x)) olur ve hata olmasına rağmen receiver hata olduğunu anlayamaz.
 
Dolayısıyla hangi polinomu seçersek seçelim undetected errors olacak. Amaç tespit edilemeyen hata sayısını en azda tutacak şekilde bir polinom seçmek.
Mesela A polinomu bir framede 3-bitlik oluşabilecek hata sayısı (toplam E(x) kombinasyon sayısı) (n,3) ise bunlardan x tanesi tespit edilecek geriye kalanı edilemeyecek.

Her polinom için 2,3,4,5,6,7,... bitlik tespit edilemeyen hata sayısını belirten (buna hamming distance deniyordu galiba) aşağıdaki linkde tablo bulabilirsiniz.



https://users.ece.cmu.edu/~koopman/crc/index.html
https://www.ece.unb.ca/tervo/ece4253/crc.shtml         //Burada işin matematiği basit şekilde anlatılıyor
https://en.wikipedia.org/wiki/Cyclic_redundancy_check  // Detaylı anlamak için burayı okuyunuz.

Aklımda kalanlar bunlardı. Ben de herhangi bir polinom için n-bitlik tespit edilemeyen hata sayısını hesaplayan bir kod yazmıştım. Galiba yukarıdaki Philip Koopman'a ait sayfada bu değerleri tablo şeklinde veriyordu.

Not: Polinom rastgele seçilmiyor. Onun da matematiksel kuralları var. Vikipedia kontrol ediniz. Sadece primitive polinomlar kullanılıyor galiba.

[Tagli]

Not: Polinom rastgele seçilmiyor. Onun da matematiksel kuralları var. Vikipedia kontrol ediniz. Sadece primitive polinomlar kullanılıyor galiba.

Bildiğim kadarıyla iletişim hattının doğasına/dinamiklerine bağlı olarak belirleniyor ve bu iş akademik çalışma konusu. Yani işin uzmanlarına bırakılması gerek. Yani "şu iş için bu CRC polinomu kullanılmalı" deniyorsa çok da kurcalamamak lazım.

Ben CRC hesabı konusuna hakim değilim. Modbus'ın CRC16'sı için internette bulduğum hazır kodları kullanıyorum. Hız daha önemli ise ve flash bellekte yer bolsa tablo yöntemini kullanıyorum.

STM32'lerin USB ve CAN donanımları gerekli bazı CRC hesaplarını donanım seviyesinde yapıyorlar zaten. Bunlara kafa yormaya gerek yok.

Bunlar dışında CRC gerekirse ve çok özel bir polinom gereksinimi yoksa, bildiğim kadarıyla her STM32'de olan ethernet polinomunu (0x4C11DB7) kullanmak en kolayı çünkü donanım tarafından hesaplandığı için ne hız ne de bellek maliyeti var. Bazı STM32'ler başka polinomları da hesaplayabiliyorlar ama her işlemcide yok bu özellik.

[mr.engineer]

Ben hiç CRC kullanmadım ama @Tagli nin dediği gibi belli protokoller için seçilmiş CRC'ler vardır ama kendi protokolünüzü tasarlamak isterseniz bu bilgi gerekebilir. Message frame boyutuna göre hazırda olan tablodan uygun CRC seçimi yapılabilir.




Yukarıdaki tabloda 40 bit messagge frame ve 8 bit CRC kodundan oluşan toplam 48 bitlik frame için 2, 3, 4, 5 ve 6 bitlik tespit edilemeyen hata sayısı yer alıyor. Mesela 0x2F polinomu N = 2,3 ve 5 değerleri için 0 gösteriyor. Yani 2,3 ve 5-bitlik hataların hepsini tespit edebiliyor ama N=6 için tespit edemediği hata sayısı yükselmiş. Bu durumda diğerlerine göre avantajlı görünüyor. Eğer çok sayıda bitin transmit sırasında değişmeyeceğini varsayarsak bu polinomu kullanmak mantıklı olabilir.

Bunu örnek olsun diye söyledim tabi varsayımla olmaz, @Tagli nin dediği gibi akademik bir arka planı vardır. Yani bir iletişim kanalında transmit yaparken frame de ne kadar bit sayısında hata olabilir gibi bir olasılık hesabı falan vardır.

Merak edenler için Philip Koopman'ın bu konuyla ilgili makalesi de vardı.