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
. . .
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
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 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:
see also: http://doc.utwente.nl/64267/1/schiphorst.pdf