COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Analysing CRC16 algorithm

• Email
• Follow

```I am learning CRC theory following a document of CRC16. The document
mentioned that CRC of B(X) is the remainder of B(X)*2^^16 / G(X). In
my undersdanding, G(X) is a constant. The document gives C source code
of the algorithm calculating CRC 16 bit by bit, and also gives the
code of byte by byte. The programs are given at bottom of this post. I
have some questions about CRC, see here below.

1. From the values of crc_ta[0:14] in the algorithm byte by byte, I
figured out that G(X) in this sample is 0xEFDF. So that 1*2^^16/G(X)
would have the remainder 0x1021, and until 0xE*2^^16/G(X) would have
the remainder 0xE1CE.

But 0xF*2^^16/G(X) would have the remainder 0x210. However, the table
in the program shows that the remaider is 0xF1EF. Notice that 0xF1EF >
0xEFDF, so it cannot be the remainder of division by 0xEFDF. How come?

Further elements are even more surprising. CRC of 17 (0x11) should be
( 0x11*2^^16 mod 0xEFDF = 0x2252 = 8786 ). I found that 0x2252 is not
crc_ta[17], but crc_ta[19] in this table. When I continue the
calculation, I found that many elements have different location from
what I expected. So what's the correct way to interpret this table?

2. The document gives following standards:
CRC-16:		G(X) = X16 + X15 + X2 + 1
CRC-CCITT:	G(X) = X16 + X12 + X5 + 1

In my understanding,
CRC-16: 	G(X) = X16 + X15 + X2 + 1
means using 11000000000000101 = 0x18005 as G(X), and
CRC-CCITT:	G(X) = X16 + X12 + X5 + 1
means using 10001000000100001 0 0x11021 as G(X).
Is this correct?

And G(X)=0xEFDF in this sample means that G(X)=1110111111011111
= X15 + X14 + X13 + X11 + X10 + X9 + X8 + X7 + X6 + X4 + X3 + X2 + X1
+ 1

Is this correct?

Thanks.

Source code in the document:

- - - - - - -
bit by bit
- - - - - - -

unsigned int cal_crc(unsigned char *ptr, unsigned char len) {
unsigned char i;
unsigned int crc=0;
while(len--!=0) {
for(i=0x80; i!=0; i/=2) {
if((crc&0x8000)!=0) {crc*=2; crc^=0x1021;}
else crc*=2;
if((*ptr&i)!=0) crc^=0x1021;
}
ptr++;
}
return(crc);
}

- - - - - - - -
byte by byte
- - - - - - - -

unsigned int cal_crc(unsigned char *ptr, unsigned char len) {
unsigned int crc;
unsigned char da;
unsigned int crc_ta[256]={
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};
crc=0;
while(len--!=0) {
da=(uchar) (crc/256);
crc<<=8;
crc^=crc_ta[da^*ptr];
ptr++;
}
return(crc);
}
```
 0
Reply chen_zhitao (71) 10/19/2009 1:09:42 PM

See related articles to this posting

0 Replies
57 Views

Similar Articles

12/7/2013 11:00:46 PM
page loaded in 108500 ms. (0)

Similar Artilces:

Looking for algorithm . . .
; remove 6 from 4,5,6 into own group > meld 7 and 8. > > > (This isn't a homework assignment. I've been out of school > for 18 years. I've just been away from graph theory/set theory > for too long.... and was hoping someone would recognize this > problem and point me to a solution). > What you are looking for is a 'minimal edit distance' algorithm. You might get good results just using the Unix 'diff' utility: list your numbers, one number per line, in files A and B and 'diff' the files. -- Roger On Tue...;> B: 1,2,4, 3,5,6 7 8 >> >> tell me: swap 3 and 4 >> remove 6 from 4,5,6 into own group >> meld 7 and 8. >> >> >> (This isn't a homework assignment. I've been out of school >> for 18 years. I've just been away from graph theory/set theory >> for too long.... and was hoping someone would recognize this >> problem and point me to a solution). >> > >What you are looking for is a 'minimal edit distance' algorithm. > >You might get good results just using

genetic algorithm
hi, i am looking for some information about genetic algorithms and genetic programming. i will really appreciate any help in this matter. with regards, Ashish. comp.ai.genetic http://www.aic.nrl.navy.mil/galist/ Randy Ashish Poddar wrote: > hi, > > i am looking for some information about genetic algorithms and genetic > programming. i will really appreciate any help in this matter. > with regards, > Ashish. >

Sudoku Algorithm
Hi For those that are interested we have a Sudoku Algorithm that has been kindly posted into our Forum at http://www.menkaura.com/Forum/index.php?topic=318 It certainly isn't my work so I can't take any credit. However it looks sound on scanning through it. If anyone has anything constructive to add then please do so. Thanks ... On Sat, 17 Dec 2005, Gary wrote: > > For those that are interested we have a Sudoku Algorithm that has been > kindly posted into our Forum at > http://www.menkaura.com/Forum/index.php?topic=318 > > It certainly isn't my work so I can't take any credit. However it looks > sound on scanning through it. If anyone has anything constructive to > add then please do so. It's not really an "algorithm," since it doesn't say what to do after step J2, in which we reach a dead end according to the five simple rules Peter uses to update the grid. Basically, this is an unnecessary computerization of the kind of process a human being would use to solve a Sudoku on paper, and it has the same flaw --- lack of logic. There are plenty of Sudoku grids that can't be solved by Peter's method; some

Algorithm for ERD
Hello, I have a binary tree (ER - Entity Relation), I want to make a diagram of that binary tree, but it should be very compact. What is the algorithm concept doing that ? Thanks :)

streamline algorithm
Hi: does anyone knows how to see the algorithm of Matlab streamline coz the actual steps showing how to calculate a streamline is in the stream3c (mex file). And I can't easily googled an answer for this. I think it basicly use "Line Integral Convolution"!? but what's the condition to terminate/stop a streamline? In some paper I see there are two conditions to terminate a streamline. (1). while two adjacent streamlines hit a pixel edge and cause a singularity case. (2). when the velocity is zero at the pixel. However, in my data, I don't have zero data and sometimes streamlines pass one single pixel without ending. Thanks Tim

optimization algorithm
Hi, I am seeking for literature/ optimization algorithms for my problem. I have about 10 parameters which I set in a file and I optimize a given `area` according to certain `constraints` using a `Genetic Algorithm, GA` library. The area could be typically a city and constraints could be for example, location of train stations, schools, residence areas, trees etc... Now, at the end of the simulation I get an optimized `area` (with maximum `score`) for the given set of parameters. But now, in addition to that, I would require to experiment by changing the parameters I already have... a given > `area` according to certain `constraints` using a `Genetic Algorithm, > GA` library. The area could be typically a city and constraints could > be for example, location of train stations, schools, residence areas, > trees etc... > > Now, at the end of the simulation I get an optimized `area` (with > maximum `score`) for the given set of parameters. But now, in addition > to that, I would require to experiment by changing the parameters I > already have within certain range and find the `optimized area` with > the maximum `score`. > > I don

Algorithm problems
/latex/hyperref/pdfmark.def File: pdfmark.def 2003/11/30 v6.74m Hyperref definitions for pdfmark specials \pdf@docset=\toks19 \pdf@box=\box52 \pdf@toks=\toks20 \pdf@defaulttoks=\toks21 \Fld@listcount=\count108 \@outlinefile=\write3 )) (./algorithm.sty Package: algorithm Document Style `algorithm' - floating environment (/usr/local/teTeX-new/share/texmf/tex/latex/float/float.sty Package: float 2001/11/08 v1.3d Float enhancements (AL) \c@float@type=\count109 \float@exts=\toks22 \float@box=\box53 \@float@everytoks=\toks23 \@floatcapt=\box54 ) (/usr/local/teTeX-new/share/texmf/tex/latex/base/ifthen.sty Package: ifthen 2001/05/26 v1.1c Standard LaTeX ifthen package (DPC) ) \@float@every@algorithm=\toks24 \c@algorithm=\count110 ) (./algorithmic.sty Package: algorithmic 2006/06/02 Document Style `algorithmic' - environment (/usr/local/teTeX-new/share/texmf/tex/latex/tools/calc.sty Package: calc 1998/07/07 v4.1b Infix arithmetic (KKT,FJ) \calc@Acount=\count111 \calc@Bcount=\count112 \calc@Adimen=\dimen117 \calc@Bdimen=\dimen118 \calc@Askip=\skip47 \calc@Bskip=\skip48 LaTeX Info: Redefining \setlength on input line 59. LaTeX Info: Redefining \addtolength on input line 60

for_each() algorithm
I have a function which calculate standard deviation. I am trying to re-write it using STL algorithm. I am thinking of using for_each() algorithm, but that will require my function passing in to have state (e.g. the value of standard deviation sum). I read some online article that having state is not a good idea. So is there a better solution? Thank you. /** Calculate the standard deviation, given the mean of the numbers */ double sd( const vector<int>& v, const double mean ) { double stdDev = 0.0; int N = v.size(); const double mean_ = mean; // calculate the standard deviation sum double stdDevSum = 0; double x; for (int i = 0; i < N; i++) { x = v[i] - mean_; stdDevSum = stdDevSum + (x * x); } double variance = stdDevSum / static_cast<double>(N-1); stdDev = sqrt( variance ); return stdDev; } // sd silverburgh.meryl@gmail.com wrote: > I have a function which calculate standard deviation. I am trying to > re-write it using STL algorithm. > I am thinking of using for_each() algorithm, but that will require my > function passing in to have state (e.g. the value of standard deviation > sum). I

ICA algorithm
Hi, Could anyone suggest me the best-explained book and algorithm on Independent Component Analysis (ICA) ?? I have sufficient background knowledge on Applied Linear Algebra and also a little working knowledge on Principal Component Analysis (PCA). I am to work in a project to try and eliminate the noise in the experimental EEG signal. In case, there are any other alternatives or equally sophisticated methods, I would be very delighted if you could share those as well. regards, Arun.

Unshuffle algorithm
Hi there, I have an array of numbers made up of two sequences that have been sorted. I am trying to find an algorithm that can extract separate arrays made up of these sequences. For example: arr1 = sort([1:5 7:0.5:10]); This first case is straight-forward, as the two sequences don't overlap. I can get the 1st index of the two sequences using diff: indices = find(diff(arr1,2))+2; % +2 because a 2nd order diff is taken. sequence_indices = {1:indices(1)-1, indices(1):length(arr1)} However, this technique only works if the two sequences are non-overlapping. For example, a more difficult case is: arr2 = sort([1:5 4.2:10]); Can anyone point out I should tackle the problem of extracting the two sequences in this case? Thanks for any suggestions, Sven. "Sven " <sven.holcombe@removethis.gmail.com> wrote in message <f91dom\$3hv\$1@fred.mathworks.com>... > Hi there, > I have an array of numbers made up of two sequences that > have been sorted. I am trying to find an algorithm that can > extract separate arrays made up of these sequences. > > For example: > arr1 = sort([1:5 7:0.5:10]); If I might ask, what is the source of this problem