CRC7 Polynomial?

[Javalin]

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)]

Since Spin is indentation-sensitive, it's impossible to follow your code. Please repost it between
and tags to preserve the indentation.

-Phil

[Javalin]

Hiya Phil - done. Didn't know how to do that with this new forum software...

:-)

J

[Phil Pilgrim (PhiPi)]

However why is the poly $9 not $89 ... ?
Could it be the last line in your routine (result := crc & $7F), perhaps? :)

-Phil

[Javalin]

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)]

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]

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]

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]

ah ok - got it - ta.

James

[Phil Pilgrim (PhiPi)]

KK,

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

-Phil

[Dave Hein]

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]

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]

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]

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]

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]

Dave - your a star. Top man. That works!



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


Thanks!

James

[Beau Schwabe (Parallax)]

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...

http://forums.parallax.com/showthread.php?t=117333&highlight=polynomial+schwabe

Reference:
http://www.ross.net/crc/download/crc_v3.txt

[Javalin]

thanks Beau

[tonyp12]

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