線上訂房服務-台灣趴趴狗聯合訂房中心
發文 回覆 瀏覽次數:22656
推到 Plurk!
推到 Facebook!

[分享] RS232中 CRC檢查演算法

 
axsoft
版主


發表:681
回覆:1056
積分:969
註冊:2002-03-13

發送簡訊給我
#1 引用回覆 回覆 發表時間:2002-07-15 16:16:48 IP:61.218.xxx.xxx 未訂閱
CRC 錯誤偵測技術        即是所謂的循環冗餘檢查碼 (Cyclic Redundancy Check Code) ,簡稱     CRC 碼,它是由待傳輸的資料區塊計算出的,CRC 的計算方式是將待傳     輸的區塊視為一堆連續位元所構成的一整個數值,並將此數值除以一特     定的除數,通常以二進位表示,此除數又稱為衍生多項式 (Generation     Polynomial),該除數一般皆由設計硬體或軟體的廠商所提供,而除數     值位元數目則視欲得到的 CRC 位元數目而定,目前較常使用的 CRC 位     元數目有 8、16 或 32,一般縮寫為 CRC-8、CRC-16、CRC-32,通常,     CRC 碼越長,則數據發生干擾卻不反應在 CRC 值的機率也就越低,不     過得多花些時間傳送較長的 CRC 碼。根據理論統計,CRC-16 可完全偵     測資料區塊內單一或兩個位元的錯誤、奇數個位元的錯誤、連續 16 個     位元或少於此數的錯誤,超過 17 個連續位元的錯誤偵測率則有     99.9969% ,其它位元長度的錯誤偵測率則可達 99.9984% 。     底下是一些數學符號所表示的 CRC 碼運算過程。吾人可將待傳送的區     塊資料位元串表示成一個很大的二進位數字,並令此數字等於 F,例如     ,底下是某個區塊的位元串所連成的二進位數字:            F = 1011010111110111101110100100101110101... (區塊資料)        假設目前欲求 F 的 16 位元 CRC 值,並且,廠商所提供的衍生多項式     是:                    16    12    5         G(x) = x   + x         + x  + 1   (衍生多項式)        其中,x 是所採的進制,在二進位系統,x = 2,則 G 的值為:            G = 1,0001,0000,0010,0001   (二進位數字)        底下的式子中的餘數 C 即是 F 的 16 位元 CRC 值:                  16         F ‧ 2         = A ‧ G + C        由於 C 是此式中的餘式,故稱此值為 Redundancy。     例如,底下即是透過上述的 G(x) 求得 11010101 (D5H) 的 CRC 值:                                                             A                          ┌─────────────────     1,0001,0000,0010,0001│1101,0101 ‧ 1,0000,0000,0000,0000                          ╯......                          ──────────────────     (二進位長除法)        16 位元 CRC 值 → 1001,1011,1101,1000        衍生多項式的數值將影響到所產生的 CRC 值,根據理論計算,當衍生     多項式的數值恰為某些特定值時,所產生的 CRC 值最 "亂" ,換句話     說,它偵測資料受雜訊干擾的能力越高,在上個範例中所採用的多項     式也是 PC/XT 控制卡上μPD765A 所採用,該多項式也是 CRC-CCITT     v.41 所制定的標準,而目前在許多通訊上的應用亦採用此值。     理論上,在計算 CRC 時非常簡單,只要一個除法運算即可,運算之後     的餘數即是 CRC 值,但實際上所被除數 F 的位元數目可能以萬為單     位,如何利用程式以最簡易、最快的方式求得該餘數也是技術關鍵所     在。事實上,各式的檢查碼也不僅應用在網路通訊上,和數據的存取     、儲存、傳輸等類似的範疇也會用到,例如磁碟片或磁帶機上資料的     儲存即是,在 Apple 個人電腦的磁碟機即是利用 checksum 驗證所存     取資料的正確性,而 PC 的磁碟機則使用 CRC。        時間就是金錢 << 發問前請先找找舊文章 >>
axsoft
版主


發表:681
回覆:1056
積分:969
註冊:2002-03-13

發送簡訊給我
#2 引用回覆 回覆 發表時間:2002-07-15 16:20:40 IP:61.218.xxx.xxx 未訂閱
CRC-8  範例    /* ------------------------------------------------------------------------ File   : crc.c    Descr  : Some CRC routines.          *NOTE*: if you want to add the CRC-checksum to the data                  it could be put at the end, MSB first !                  See below: 16-bit CRC-check of 16 bytes of Arr[]                  as shown is 0x4D8F; added as shown and included in the                  CRC calculation leads to a CRC-checksum of 0 (zero).    History: 04.05.99; Henk B&B; Created. --------------------------------------------------------------------------- */    #include  #include "general.h" /* ------------------------------------------------------------------------ */ /* ------------------------------------------------------------------------ */ BYTE crc8_calc(BYTE *byt, WORD size ) { /* Calculate CRC-8 value; uses The CCITT-8 polynomial, expressed as X^8 X^5 X^4 1 */ BYTE crc = (BYTE) 0xff; WORD index; BYTE b; for( index=0; index%s",Cod); crc8 = crc8_calc( Cod, 40 ); printf( "CRC=%x\n", crc8 ); } /* ------------------------------------------------------------------------ */ /* ------------------------------------------------------------------------ File : general.h Descr : Some useful general-purpose definitions. History: 30NOV.99; Henk B&B; Version for AVR applications. --------------------------------------------------------------------------- */ #ifndef GENERAL_H #define GENERAL_H /* ------------------------------------------------------------------------ */ /* ------------------------------------------------------------------------ */ /* Type definitions */ typedef unsigned char BOOLEAN; typedef unsigned char BYTE; typedef signed char CHAR; typedef unsigned int WORD; typedef unsigned long ULONG; /* ------------------------------------------------------------------------ */ /* Constants */ #define TRUE 1 #define FALSE 0 /* ------------------------------------------------------------------------ */ /* Macros */ #define BIT(x) (1 << (x)) #define SETBIT(addr,x) (addr |= BIT(x)) #define CLEARBIT(addr,x) (addr &= ~BIT(x)) #endif /* GENERAL_H */ /* ------------------------------------------------------------------------ */ 時間就是金錢 << 發問前請先找找舊文章 >>
axsoft
版主


發表:681
回覆:1056
積分:969
註冊:2002-03-13

發送簡訊給我
#3 引用回覆 回覆 發表時間:2002-07-15 16:31:16 IP:61.218.xxx.xxx 未訂閱
CRC-16範例    // Update the CRC for transmitted and received data using // the CCITT 16bit algorithm (X^16 + X^12 + X^5 + 1).        unsigned char ser_data;     static unsigned int crc;        crc  = (unsigned char)(crc >> 8) | (crc << 8);     crc ^= ser_data;     crc ^= (unsigned char)(crc & 0xff) >> 4;     crc ^= (crc << 8) << 4;     crc ^= ((crc & 0xff) << 4) << 1;    Note: It is best not to alter this code. For example, (crc<<8)<<4 does not generate the same code as crc<<12. Although the result of the computation is the same, the latter generates much more code and executes slower. 時間就是金錢 << 發問前請先找找舊文章 >>
axsoft
版主


發表:681
回覆:1056
積分:969
註冊:2002-03-13

發送簡訊給我
#4 引用回覆 回覆 發表時間:2002-07-15 16:35:24 IP:61.218.xxx.xxx 未訂閱
CRC16範例 (2)    PDF格式    http://www.summitinstruments.com/library/tn410.pdf    時間就是金錢 << 發問前請先找找舊文章 >>
axsoft
版主


發表:681
回覆:1056
積分:969
註冊:2002-03-13

發送簡訊給我
#5 引用回覆 回覆 發表時間:2002-07-15 16:50:00 IP:61.218.xxx.xxx 未訂閱
CRC-32範例    CRC-32 Checksum演算法,用於檢查檔案用途較多,不過目前已漸漸被MD5取代了!    資料來源: http://cell-relay.indiana.edu/cell-relay/publications/software/CRC/32bitCRC.c.html    

Charles Michael Heard's CRC-32 Code

* crc32h.c -- package to compute 32-bit CRC one byte at a time using */ /* the high-bit first (Big-Endian) bit ordering convention */ /* */ /* Synopsis: */ /* gen_crc_table() -- generates a 256-word table containing all CRC */ /* remainders for every possible 8-bit byte. It */ /* must be executed (once) before any CRC updates. */ /* */ /* unsigned update_crc(crc_accum, data_blk_ptr, data_blk_size) */ /* unsigned crc_accum; char *data_blk_ptr; int data_blk_size; */ /* Returns the updated value of the CRC accumulator after */ /* processing each byte in the addressed block of data. */ /* */ /* It is assumed that an unsigned long is at least 32 bits wide and */ /* that the predefined type char occupies one 8-bit byte of storage. */ /* */ /* The generator polynomial used for this version of the package is */ /* x^32 x^26 x^23 x^22 x^16 x^12 x^11 x^10 x^8 x^7 x^5 x^4 x^2 x^1 x^0 */ /* as specified in the Autodin/Ethernet/ADCCP protocol standards. */ /* Other degree 32 polynomials may be substituted by re-defining the */ /* symbol POLYNOMIAL below. Lower degree polynomials must first be */ /* multiplied by an appropriate power of x. The representation used */ /* is that the coefficient of x^0 is stored in the LSB of the 32-bit */ /* word and the coefficient of x^31 is stored in the most significant */ /* bit. The CRC is to be appended to the data most significant byte */ /* first. For those protocols in which bytes are transmitted MSB */ /* first and in the same order as they are encountered in the block */ /* this convention results in the CRC remainder being transmitted with */ /* the coefficient of x^31 first and with that of x^0 last (just as */ /* would be done by a hardware shift register mechanization). */ /* */ /* The table lookup technique was adapted from the algorithm described */ /* by Avram Perez, Byte-wise CRC Calculations, IEEE Micro 3, 40 (1983).*/ #define POLYNOMIAL 0x04c11db7L static unsigned long crc_table[256]; void gen_crc_table() /* generate the table of CRC remainders for all possible bytes */ { register int i, j; register unsigned long crc_accum; for ( i = 0; i < 256; i ) { crc_accum = ( (unsigned long) i << 24 ); for ( j = 0; j < 8; j ) { if ( crc_accum & 0x80000000L ) crc_accum = ( crc_accum << 1 ) ^ POLYNOMIAL; else crc_accum = ( crc_accum << 1 ); } crc_table[i] = crc_accum; } return; } unsigned long update_crc(unsigned long crc_accum, char *data_blk_ptr, int data_blk_size) /* update the CRC on the data block one byte at a time */ { register int i, j; for ( j = 0; j < data_blk_size; j ) { i = ( (int) ( crc_accum >> 24) ^ *data_blk_ptr ) & 0xff; crc_accum = ( crc_accum << 8 ) ^ crc_table[i]; } return crc_accum; } 時間就是金錢 << 發問前請先找找舊文章 >>
天外來客
初階會員


發表:22
回覆:199
積分:44
註冊:2001-11-27

發送簡訊給我
#6 引用回覆 回覆 發表時間:2002-07-30 12:01:26 IP:61.218.xxx.xxx 未訂閱
這裡還有一篇 CRC-16/CRC-32 程序代碼 作者:猛禽 http://www.dbgnu.com/bcb/doc/view.asp?page=120
系統時間:2024-03-28 22:51:17
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!