HomeTOOLSEXAMPLESEXPLORE EMBEDDEDE CSERVICESECU SAMPLESRegistration
Embedded C programming Tutorial , Keil C ide , microsoftware.gr
Keil CRC and CAN BUS codes.
1. Shift led left
2.It's time for DAVE! <7/6/13>
3.Capture/Compare unit 6
4.ASC0-GPT1-MACROS
5.ASC0-FIFO-PEC
6.Analog converter
7.Memory manipulation routines
8. Recursion
9.Understanding interrupt priorities using CAPCOM2 module
10. POINTERS TO FUNCTION <4/7/13>,<4/28/13>
11.Memory models, memory types
12. The heap , part 1
13. The heap , part 2
14. The heap , part 3
15. Structure example
16. Nested structures, Array of structures.
17. Passing array of structures to function using pointers.<1/5/13>
18. Self Referential Structures
19. BITFIELDS
20. Linked list example
21. Circular linked list
22. Union example
23. Enumeration example
24. Watchdog timer example
25. Void pointer example <7/4/13>
26. The sieve of Eratosthenes
27. The stack
28. Union and bitfields as flags example. <6/23/13>
29. Look up table example. <8/11/13>
30. Seven segment display multiplexing -four digits with dot- example
31. LCD character display example - JHD162A
32. Hash table introduction example <8/27/14>
33. Array of Linked Lists example
34. Array of Linked lists-more functions included.
35. Hash table construction,searching and printing.
36. Fininte state machines- a first approach.
37. Finite state machines- two events example.
38. SPI port and an AT25128 serial eeprom hardware.
39. CRC CHECK
40. Definite Integral Calculator for Scientists, Engineers...
41 .Hamming distance of a CRC polynomial
42. Linux play starting.
43. Galois GF(2^4) Finite Field
44. Construct your own time triggered real time operating system.
45. CANBUS C CODE EXAMPLE.
41 .Hamming distance of a CRC polynomial

Hamming distance of a CRC polynomial. <28/September/2015>


Studying
in article no 39 about crc error correction I am sure that you have a question!
Given a generator polynomial g(x) of order n are there polynomials all of  order m , where m is greater or equal to the order of g(x), having all the same CRC ?

Generally speaking the answer is Yes !

For example given the polynomial p(x) having order m (p is m+1 bits long) we can construct  new polynomials having order m or less than m and having the same CRC as p(x) like this:

q(x)=p(x)+ Σc*(x^k)*g(x)  and controlling the values of k's in such a way that all the polynomials q(x) to have maximum order m.
Greek capital Σ means "sum"  and maximum value of  k's at the sum belongs to [0, m-n] . Coefficients c will be 0 or 1.

Since CRC ( Σ c*(x^k)*g(x))= 0 polynomial we have CRC (p(x))= CRC (q(x)).

So, In Galois mod2 field we have:  p(x)+q(x)= Σ c*(x^k)*g(x).

We call e(x) the error polynomials e(x)=Σ c*(x^k)*g(x)    (1) . We produce a sequence of polynomials e for the different maximum values of k at the sum and for different combinations of values of c .

As we see the number of bits where polynomials p and q differ is reflected to the error polynomials e.

Given the order m ,we define the minimal Hamming distance (HD) of the polynomial
g(x) as the minimal number of non -zero coefficients among  all possible error polynomials e.

HD
depends of m.

A nice article is at  http://www.fit.vutbr.cz/~smrcka/pub/fmcrc-MEMICS06.pdf

. . .

Example
Consider the generator polynomial g=x8+x7+x6+x4+x2+1 or 0x1d5. We will find the HD of g for the case of 11 bits long messages (polynomials of order 10).
Following formula (1)  and using the polynomial calculator above we have:



1]   g+(x*g)   =    111010101  XOR  1110101010    =    1001111111

2]   g+((x^2)*g))= 111010101  XOR  11101010100   = 11010000001

3]   x*g+ ((x^2)*g))  =   1110101010 XOR 11101010100 = 10011111110

4]  g+ x*g+ ((x^2)*g)) = 111010101 XOR 1110101010  XOR 11101010100  =10100101011

5]    111010101

6]    1110101010

 7]   11101010100


So the HD is found at case 2]   and HD=4.

In words: Messages of 11 bits or less than 11 bits long must have to differ for at least 4 bits in order to have the same CRC under g.


Example:
Consider the message m=11000001111 , it is 11 bits long.

All of the following messages:

11000001111

11000001111 XOR 1001111111= 10001110000

11000001111 XOR 
11010000001  =  00010001110

11000001111  XOR 10011111110  01011110001

11000001111  XOR 
10100101011 =  01100100100

Have the same crc that is :  10001110


Hamming distance decreases as the bit length of the message increases. It is logical. See Koopman:

http://users.ece.cmu.edu/~koopman/pubs/KoopmanCRCWebinar9May2012.pdf


see also:   http://doc.utwente.nl/64267/1/schiphorst.pdf


Summer !

 

Home|TOOLS|EXAMPLES|EXPLORE EMBEDDEDE C|SERVICES|ECU SAMPLES|Registration