PDA

View Full Version : CRC7 Polynomial?

Javalin
11-18-2010, 07:48 AM
Hiya all,

I have a question, and I have to admit that I may not fully understand the answer. Sadly my maths are not wonderfull... :-(

I've been trying to get the CRC7 & CRC16 working on my SD card object, and after lots of reading have re-written a C example in SPIN - which works:

PUB crc7(buffer,count) | crc, c
crc := 0
repeat count
c := byte[buffer++]
repeat 8
crc <<= 1
if (c ^ crc) & \$80
crc ^= \$9
c <<= 1
result := crc & \$7F

However why is the poly \$9 not \$89 (%1000_1001)? as it is generated by x^7 + x^3 + 1?

Thanks,

James

Phil Pilgrim (PhiPi)
11-18-2010, 07:51 AM
and tags to preserve the indentation.

-Phil

Javalin
11-18-2010, 08:03 AM
Hiya Phil - done. Didn't know how to do that with this new forum software...

:-)

J

Phil Pilgrim (PhiPi)
11-18-2010, 03:06 PM
However why is the poly \$9 not \$89 ... ?
Could it be the last line in your routine (result := crc & \$7F), perhaps? :)

-Phil

Javalin
11-18-2010, 03:15 PM
No I don't think so. Thats just masking the bits. If I change:

if (c ^ crc) & \$80
crc ^= \$9

to

if (c ^ crc) & \$80
crc ^= \$89

I get a different result. I don't get it - I thought the x^7 + x^3 + 1 = %1000_1001, but the \$9 is just %1001 so why? Unless its just how this implemention works?

James

PS - how do you do bold, itallics and colour on this forum software now????

Phil Pilgrim (PhiPi)
11-18-2010, 03:28 PM
No I don't think so. Thats just masking the bits.
That's what I meant: \$89 & \$7F == \$09.

For formatting assistance, go to the forum FAQ and do a search on bbcode.

-Phil

Javalin
11-18-2010, 03:35 PM
oh - ok. I'll be home in an hour or so and i'll try the combinations and see. Sure I tested it with both - but will double check.

Thanks Phil.

James

KaosKidd
11-18-2010, 03:38 PM
PS - how do you do bold, itallics and colour on this forum software now????

Use [ I ] text to be italics [ / I ] For italics, use [ U ] text to be underline [ / U ] for underline and use [ B ] text to be bold [ / B ] for bold.
PS: Remove all spaces between the [ and ]!

Or you can use the B / I / U buttons (under the font selection box in the editor)

Now for the color...
[ COLOR = "Red" ][ / COLOR ] will produce Red,
[ COLOR = "Green" ][ / COLOR ] will produce Green, etc.
PS: Remove all spaces between the [ and ]!
Or, in the editor, next to the sizes drop down list, is a big A with a color line under it
select that drop down and pick your color!

Javalin
11-18-2010, 03:40 PM
ah ok - got it - ta.

James

Phil Pilgrim (PhiPi)
11-18-2010, 03:42 PM
KK,

You can also put your BBcode examples between and tags so you don't have to insert the extra spaces.

-Phil

Dave Hein
11-18-2010, 03:55 PM
Wow, most of the responses in this thread seem to be about formatting instead of answering the original question. I've never fully understood the binary polynomial math that is used in CRC's and correcting code. However, from what I can tell the highest polynomial bit postition is never included in the ex-or computation, but does determine which bit is tested and the final number of bits retained.

I believe the "crc ^= \$9" is correct. You should verify it with data that includes a known good CRC7 code.

Dave

Javalin
11-18-2010, 04:25 PM
Hiya Dave, Phil,

This is odd, I guess Dave is right. If I use \$89 or \$9 it still works. I've only got one test case at the moment (the CMD0 init string for SD cards) - so might behave differently with more testing

Was sure I tested both - perhaps that was a previous attempt....

Cheers both.

James

Dave Hein
11-18-2010, 04:51 PM
I found a table-driven version of the CRC7 algorithm that is written in C. I tested it against your routine (converted to C) and it matches. The C code is shown below.

Dave

#include <stdio.h>
#include <stdlib.h>

unsigned char crc7_syndrome_table[256] = {
0x00, 0x09, 0x12, 0x1b, 0x24, 0x2d, 0x36, 0x3f,
0x48, 0x41, 0x5a, 0x53, 0x6c, 0x65, 0x7e, 0x77,
0x19, 0x10, 0x0b, 0x02, 0x3d, 0x34, 0x2f, 0x26,
0x51, 0x58, 0x43, 0x4a, 0x75, 0x7c, 0x67, 0x6e,
0x32, 0x3b, 0x20, 0x29, 0x16, 0x1f, 0x04, 0x0d,
0x7a, 0x73, 0x68, 0x61, 0x5e, 0x57, 0x4c, 0x45,
0x2b, 0x22, 0x39, 0x30, 0x0f, 0x06, 0x1d, 0x14,
0x63, 0x6a, 0x71, 0x78, 0x47, 0x4e, 0x55, 0x5c,
0x64, 0x6d, 0x76, 0x7f, 0x40, 0x49, 0x52, 0x5b,
0x2c, 0x25, 0x3e, 0x37, 0x08, 0x01, 0x1a, 0x13,
0x7d, 0x74, 0x6f, 0x66, 0x59, 0x50, 0x4b, 0x42,
0x35, 0x3c, 0x27, 0x2e, 0x11, 0x18, 0x03, 0x0a,
0x56, 0x5f, 0x44, 0x4d, 0x72, 0x7b, 0x60, 0x69,
0x1e, 0x17, 0x0c, 0x05, 0x3a, 0x33, 0x28, 0x21,
0x4f, 0x46, 0x5d, 0x54, 0x6b, 0x62, 0x79, 0x70,
0x07, 0x0e, 0x15, 0x1c, 0x23, 0x2a, 0x31, 0x38,
0x41, 0x48, 0x53, 0x5a, 0x65, 0x6c, 0x77, 0x7e,
0x09, 0x00, 0x1b, 0x12, 0x2d, 0x24, 0x3f, 0x36,
0x58, 0x51, 0x4a, 0x43, 0x7c, 0x75, 0x6e, 0x67,
0x10, 0x19, 0x02, 0x0b, 0x34, 0x3d, 0x26, 0x2f,
0x73, 0x7a, 0x61, 0x68, 0x57, 0x5e, 0x45, 0x4c,
0x3b, 0x32, 0x29, 0x20, 0x1f, 0x16, 0x0d, 0x04,
0x6a, 0x63, 0x78, 0x71, 0x4e, 0x47, 0x5c, 0x55,
0x22, 0x2b, 0x30, 0x39, 0x06, 0x0f, 0x14, 0x1d,
0x25, 0x2c, 0x37, 0x3e, 0x01, 0x08, 0x13, 0x1a,
0x6d, 0x64, 0x7f, 0x76, 0x49, 0x40, 0x5b, 0x52,
0x3c, 0x35, 0x2e, 0x27, 0x18, 0x11, 0x0a, 0x03,
0x74, 0x7d, 0x66, 0x6f, 0x50, 0x59, 0x42, 0x4b,
0x17, 0x1e, 0x05, 0x0c, 0x33, 0x3a, 0x21, 0x28,
0x5f, 0x56, 0x4d, 0x44, 0x7b, 0x72, 0x69, 0x60,
0x0e, 0x07, 0x1c, 0x15, 0x2a, 0x23, 0x38, 0x31,
0x46, 0x4f, 0x54, 0x5d, 0x62, 0x6b, 0x70, 0x79
};

int crc7(unsigned char *buffer, int count)
{
int i, c, crc;
crc = 0;
while (count-- > 0)
{
c = *buffer++;
for (i = 0; i < 8; i++)
{
crc <<= 1;
if ((c ^ crc) & 0x80) crc ^= 0x9;
c <<= 1;
}
}
return crc & 0x7f;
}

int crc7x(unsigned char *buffer, int count)
{
int c, crc;
crc = 0;
while (count-- > 0)
{
c = *buffer++;
crc = crc7_syndrome_table[(crc << 1) ^ c];
}
return crc;
}

void main(void)
{
int i;
unsigned char buffer[1000];

for (i = 0; i < 1000; i++) buffer[i] = rand() & 0xff;

printf("crc7 = %02x, crc7x = %02x\n", crc7(buffer, 1000), crc7x(buffer, 1000));
}

Javalin
11-18-2010, 05:00 PM
Wow - thanks Dave.

You haven't anything for the crc16 CCITT one have you??? - thats the next task to get it working for the SD card data blocks...

Found this so far:

unsigned short crc16(data_p, length)
char *data_p;
unsigned short length;
{
unsigned char i;
unsigned int data;
unsigned int crc;

crc = 0xffff;

if (length == 0)
return (~crc);

do {
for (i = 0 data = (unsigned int)0xff & *data_p++;
i < 8;
i++, data >>= 1) {
if ((crc & 0x0001) ^ (data & 0x0001))
crc = (crc >> 1) ^ POLY;
else
crc >>= 1;
}
} while (--length);

crc = ~crc;

data = crc;
crc = (crc << 8) | (data >> 8 & 0xFF);

return (crc);
}

from http://www.drdobbs.com/199904926;jsessionid=5XQ05NE50QGWLQE1GHPCKH4ATMY32 JVN

which i've translated as :

PUB crc16a(buffer,count) | crc, c
crc := \$FFFF
repeat count
c := byte[buffer++]
repeat 8
if (crc & \$1) ^ (c & \$1)
crc := (crc >> 1) ^ \$8404
else
crc >>=1
c >>= 1
crc := ~crc
c := crc
crc := (crc << 8) | (c >> 8 & \$FF)
return crc

Doesn't work though - comes out at

CRC16 = -011265 or \$D3FF or %110100111111111

thanks again,

James

Dave Hein
11-18-2010, 05:10 PM
The CRC16 routine I use for YMODEM is as follows:

PUB ComputeCRC(ptr, num)
repeat num
result ^= (byte[ptr++] << 8)
repeat 8
result <<= 1
if result & \$10000
result ^= \$1021
result &= \$ffff

\$8408 is the bit-reversed value of \$1021. It depends on whether the data is shifted out MSB first or LSB first.

Dave

Javalin
11-18-2010, 05:17 PM
Dave - your a star. Top man. That works!

CRC16 = 032673 or \$7FA1 or %0111111110100001 CORRECT!

Thanks!

James

Beau Schwabe
11-18-2010, 05:22 PM
Javalin,

An important property of the polynomial generator is the width, which is defined as the position of its highest bit set to 1. The high-order bit of the polynomial is omitted when representing the divisor itself because the high-order bit should always be equal to 1. This makes sense if you look at the CRC in binary long hand.

Here is a link to something I did awhile back for our RF modules...

Reference:

Javalin
11-18-2010, 05:24 PM
thanks Beau

tonyp12
06-04-2012, 08:44 PM
Run this code in a loop five times, input is the 5 bytes sdio-cmd, crc to be started with 0.
On the result, just add the stop bit and you all set.
for example:
CMD17 (Argument=0) --> 01 010001 00000000000000000000000000000000 "0101010" 1

1. temp  =  XOR(input[],crc)    // begin  high  nibble
2. temp  =  AND(temp,0xf0)    // four  bit‐pair  XOR  values  ready
3. temp2  =  RIGHT SHIFT(temp,3)
4. temp  =  XOR(temp,temp2)    // eight  bit‐pair  XOR  values  ready
5. crc  =  LEFT SHIFT(crc,4)    // unpaired  values  positioned
6. crc  =  XOR(crc, temp)     // new  CRC7  complete
7. temp  =  LEFT SHIFT(input,4)  // begin  low  nibble
8. temp  =  XOR(temp,crc)
9. temp  =  AND(temp,0xf0)    // four bit‐pair  XOR  values  ready
10. temp2  =  RIGHT SHIFT(temp,3)
11. temp  =  XOR(temp,temp2)    // eight bit‐pair  XOR  values  ready
12. crc  =  LEFT SHIFT(crc,4)    // unpaired  values  positioned
13. crc  =  XOR(crc, temp)     // new  CRC7  complete