CRC Matematiği

[z]

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?

[kenan_re]

bende baya baktım baktım yok olmuyor, oturmuyor kafaya. Bu başlığın takibindeyim

[skara1214]

http://ww1.microchip.com/downloads/en/AppNotes/01148a.pdf

[Okan AKÇA]

http://en.wikipedia.org/wiki/Computation_of_CRC

http://www.lammertbies.nl/comm/info/crc-calculation.html?crc=010301000001&method=hex

[z]

Linkleri boşverin karşı karşıya sohbet edelim. Verdiğiniz linkin içeriğini anladığınız için mi verdiniz yoksa bunu oku işte anlamında mı?

[Okan AKÇA]

açıkcası bi akademisyen gibi incelemedim zaten incelememde sadece örneklere bakarak modbus driver yazarken crc hesaplattım.

[speak48]

gönderilecek veri 18  böleni 5 seçelim kalan   3
[18,3] gönderdik [19,3] geldi 19 da kalan 4 4!=3  crc hatası meydana gelmiş

[z]

Biraz daha açarmısın?

Mesela bölme işlemi yapmadan kalanı nasıl hesaplarsın? Polinomu nasıl seçiyorlar?

[Okan AKÇA]

/*=================================================================================
/*                        CRC HESABI İÇİN ALT PROGRAM
/*================================================================================*/
/* CRC High byte look up table */ 
const char Table_CRC_Hi[256] = { 
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 
0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 
0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 
0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 
0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 
0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 
0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 
0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 
0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 
0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 
0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 
0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 
0x40 
} ; 

/*CRC Low byte look up table*/ 
const char Table_CRC_Lo[256] = { 
0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06, 0x07, 0xC7, 0x05, 0xC5, 0xC4, 
0x04, 0xCC, 0x0C, 0x0D, 0xCD, 0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09, 
0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A, 0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 
0x1D, 0x1C, 0xDC, 0x14, 0xD4, 0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3, 
0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3, 0xF2, 0x32, 0x36, 0xF6, 0xF7, 
0x37, 0xF5, 0x35, 0x34, 0xF4, 0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A, 
0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29, 0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 
0x2E, 0x2F, 0xEF, 0x2D, 0xED, 0xEC, 0x2C, 0xE4, 0x24, 0x25, 0xE5, 0x27, 0xE7, 0xE6, 0x26, 
0x22, 0xE2, 0xE3, 0x23, 0xE1, 0x21, 0x20, 0xE0, 0xA0, 0x60, 0x61, 0xA1, 0x63, 0xA3, 0xA2, 
0x62, 0x66, 0xA6, 0xA7, 0x67, 0xA5, 0x65, 0x64, 0xA4, 0x6C, 0xAC, 0xAD, 0x6D, 0xAF, 0x6F, 
0x6E, 0xAE, 0xAA, 0x6A, 0x6B, 0xAB, 0x69, 0xA9, 0xA8, 0x68, 0x78, 0xB8, 0xB9, 0x79, 0xBB, 
0x7B, 0x7A, 0xBA, 0xBE, 0x7E, 0x7F, 0xBF, 0x7D, 0xBD, 0xBC, 0x7C, 0xB4, 0x74, 0x75, 0xB5, 
0x77, 0xB7, 0xB6, 0x76, 0x72, 0xB2, 0xB3, 0x73, 0xB1, 0x71, 0x70, 0xB0, 0x50, 0x90, 0x91, 
0x51, 0x93, 0x53, 0x52, 0x92, 0x96, 0x56, 0x57, 0x97, 0x55, 0x95, 0x94, 0x54, 0x9C, 0x5C, 
0x5D, 0x9D, 0x5F, 0x9F, 0x9E, 0x5E, 0x5A, 0x9A, 0x9B, 0x5B, 0x99, 0x59, 0x58, 0x98, 0x88, 
0x48, 0x49, 0x89, 0x4B, 0x8B, 0x8A, 0x4A, 0x4E, 0x8E, 0x8F, 0x4F, 0x8D, 0x4D, 0x4C, 0x8C, 
0x44, 0x84, 0x85, 0x45, 0x87, 0x47, 0x46, 0x86, 0x82, 0x42, 0x43, 0x83, 0x41, 0x81, 0x80, 
0x40 
};

long int CRC16(char *message, int length) 
{ 
   char CRC_Hi = 0xFF;             
   char CRC_Lo = 0xFF;          
   long int CRC;            
   int index=0;               
   while (length--) 
   { 
      index = CRC_Hi ^ *message++;          
      CRC_Hi = CRC_Lo ^ Table_CRC_Hi[index]; 
      CRC_Lo = Table_CRC_Lo[index]; 
   } 
   CRC = CRC_Hi;                   
   CRC = (CRC<<8) | CRC_Lo; 
   return CRC; 
}
/*--------------------------------------------------------------------------------------*/

en hızlı crc hesaplama bu şekilde oldugu söyleniyor

[kantirici]

hocam güzel bir konuya değinmişsiniz. Bende bir türlü tam anlayamadım.

@cyclone hocam işte bu diziler nasıl hesaplandı???

Bir veri için adım adım bir örnek verilebilirse kafamızdaki soru işaretler gidecektir.

[cetinkaya]

örnek 1,0,0,1,1,1,0,1 polinomu :

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define CRC32MASK 0x04C11DB7 /* CRC-32 Bitmaske */
 
int datastream[] = {1,0,0,0,1,1,0,0};
int databits = 8;
uint32_t crc32 = 0; /* Schieberegister */
/*__int32 crc32 = 0; => für MS VS */
 
int main(void)
{
    int i;
    for (i = 0; i < databits; ++i)
        if (((crc32 & 0x80000000) ? 1 : 0) != datastream[i])
             crc32 = (crc32 << 1) ^ CRC32MASK;
        else
             crc32 <<= 1;
    printf("0x%08X\n", crc32);
    return EXIT_SUCCESS;
}

crc hesaplama
http://zorc.breitbandkatze.de/crc.html

alintidir.

[Okan AKÇA]

hesaplamadım hocam hazır buldum kullandım daha once z hocamının dedigi gibi bölme işlemi olacak şekilde kod yazmıştım bilindigi gibi işlemcilerde bölme işlemi biraz kasıntı iş sonra bu kodla denemeler yaptım modbus aynı anda 16mips işlemciyle aynı anda 250 tag sorulama ları hic bir kopma olmadan haberleşti

[cetinkaya]

@cyclone modbusu mikroislemcilermi kullandiniz yoksa PLC ler ilemi?

[cicjoe]

Hocam, yakin zamanda Data Communications dersinin lab'inda 4bit CRC hesaplayan program yazmamizi istemislerdi.
CRC'nin kac bit olacagina gore generator polinomu belirleniyor, 1 bit fazlasi olmasi lazim.
En bilinen ve kolay olani seri port'ta karsimiza cikan even/odd parity.

G(x)={ x     , odd
           x+1 , even

yani odd icin 10, even icin 11.. elimizdeki data 0110 0001 (97, 'a') olsun..

1- CRC'miz 1 bit cikacagi icin Data'nin sagina 1 tane 0 ekliyoruz.
2- Generator polinomunu, Data polinomunun set edilmis en degerlikli bitine kadar sola kaydiriyoruz.
3- D(x) ^ G(x) yapiyoruz (xor)
4- Sonuc belirledigimiz bit araligindan fazla oldugu surece isleme devam ediyoruz (goto 2)

even:

1100 0010 -> sagina 1 adet 0 eklenmis (sola shift edilmis) data'miz
1100 0000 -> data'nin set edilmis en degerli bitine denk gelene kadar sola kaydirilmis generator
------------
0000 0010 -> ilk asama sonucu

0000 0010 -> sonuc uzerinden islemlere devam
0000 0011 -> generator'un sola kaymasina gerek kalmadi.. kalabilirdi
------------
0000 0001 -> generator'dan kucuk, parity bit'imizi bulduk (yani bit sayisi olarak kucuk)
even ->1


odd:

1100 0010 -> sagina 1 adet 0 eklenmis (sola shift edilmis) data'miz
1000 0000 -> data'nin set edilmis en degerli bitine denk gelene kadar sola kaydirilmis generator
------------
0100 0010 -> ilk asama sonucu

0100 0010 -> sonuc uzerinden islemlere devam
0100 0000 -> data'nin set edilmis en degerli bitine denk gelene kadar sola kaydirilmis generator
------------
0000 0010 -> ikinci asama sonucu

0000 0010 -> sonuc uzerinden islemlere devam
0000 0010 -> generator'un sola kaymasina gerek kalmadi.. kalabilirdi
------------
0000 0000 -> generator'dan kucuk, parity bit'imizi bulduk

odd -> 0


islemler xor..

Peki neden 1 bit parity bize yetmiyor? Ornegin gelen data'da 1 bit'in yolda boluldugunu ve 1 gelmesi gerekirken 0 geldigini dusunelim. Bu durumda parity'ye bakarak, yahu cift dedin, tek cikiyo diyerek anlayabiliyoruz. Ancak yolda 2 bit hataya ugrarsa, bu durumda sikintilar basliyor. Bu nedenle bit sayisini arttirarak bu problemin onune gecilebiliyor. Tabi data kadar uzun parity secmenin de dezavantajlari var. Bu seferde atiyorum 20bit yollayip, aslinda 8bit data icin harcamis olmak var. Hoca bunlarla ilgili bi ton istatistiksel hesaplama yapti da bakalim persembe sinavda napcaz artik..

Yani parity 1 bit oldugu durumda, generator 2 bit olmasi gerektiginden, soldaki bit mecbur 1 oluyor ve geriye sagdaki bit icin 2 secenegimiz kaliyor. Sonuclara bakinca da bakinca bunlarin bit sayisini tek ve cift'e tamamlayan bit oldugu anlasilinca muhtemelen boyle bir isimlendirme yapilmis. 2 tarafinda onceden generator'u bilmesi gerekiyor. Yani sifre cozen bir anahtar gibi dusunebilirsiniz.. Daha yuksek bit sayisindaki CRC'ler icin, bu key'i paylasmaniz gerekir. Tabi bunun icin standartlasmis CRC'ler de mevcutmus sanirim..

NOT: even/odd parity bit ornegi basitlik icin, tabiki daha kolay hesaplanabilir bit'leri sayarak.

[Okan AKÇA]

işlemci de kullanıyorum genelliklede 18f serilerinde kullanıyorum.