Bitstring represents polynomial.
e.g. 110001 represents:
1 . x^{5} +
1 . x^{4} +
0 . x^{3} +
0 . x^{2} +
0 . x^{1} +
1 . x^{0}
= x^{5} +
x^{4} +
x^{0}
The order of a polynomial is the power of the highest non-zero coefficient. This is polynomial of order 5.
Special case: We don't allow bitstring = all zeros.
Easy to use
framing or stuffing
to make framed-and-stuffed transmission never all-zero,
while still allowing payload within it to be all-zero.
We define addition and subtraction as modulo 2 with no carries or borrows.
This means addition = subtraction =
XOR.
Here's the rules for addition:
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0Multiplication:
0 * 0 = 0 0 * 1 = 0 1 * 0 = 0 1 * 1 = 1Subtraction: if 1+1=0, then 0-1=1, hence:
0 - 0 = 0 0 - 1 = 1 1 - 0 = 1 1 - 1 = 0Long division is as normal, except the subtraction is modulo 2.
Consider the polynomials:011 + (or minus) 110 --- 101
x + 1 +We're saying the polynomial arithmetic is modulo 2 as well, so that:
x^{2} + x
-------------
x^{2} + 2x + 1
= x^{2} + 1
2 x^{k} = 0for all k.
When the checksum is re-calculated by the receiver, we should get the same results.
All sorts of rule sets could be used to detect error.
It is useful here that the rules define a well-behaved field.
Consider the polynomials with x
as isomorphic
to binary arithmetic with no carry.
It is just easier to work with abstract x
so we don't make the mistake of starting to add, say.
3 x^{3}
to get
x^{4} + x^{3}
if we were thinking of x=2.
We work in abstract x
and keep
"the coefficients of each power nicely isolated"
(in mod 2,
when we add two of same power, we get zero, not another power).
In general, to multiply by x^{k}, add k zeros.
Do long division:
Divide (x+1) into x^{2} + 1
Divide 11 into 101
Subtraction mod 2
Get 11, remainder 0
11 goes into 10 once, remainder 1
A goes into B if it has the same number of bits
Polynomial primes do not correspond to integer primes.
Note any bitstring ending in 0
represents a polynomial that
is not
prime
since it has x as a factor
(see above).
All primes look like 1....1
Steps:
Special case: This won't work if bitstring = all zeros.
We don't allow such an M(x).
But M(x) bitstring = 1 will work, for example.
Can divide 1101 into 1000.
If:
x div y gives remainder c
that means: x = n y + c
Hence (x-c) = n y
(x-c) div y gives remainder 0
Here (x-c) = (x+c)
Hence
(x+c) div y gives remainder 0
110010000 + 100 should give remainder 0.
Note if G(x) has order n - highest power is x^{n},
then G(x) will cover (n+1) bits
and the remainder will cover n bits.
i.e. Add n bits to message.
In general, each 1 bit in E(x) corresponds to a bit that has been flipped in the message.
If there are k 1 bits in E(x), k single-bit errors have occurred.
A burst
error looks like 1....1
e.g. remainder when divide (1000+n) by 10
= remainder when you divide n by 10
If remainder when you divide E(x) by G(x) is zero, the error will not be detected.
In general, if you are unlucky enough that E(x) is a multiple of G(x), the error will not be detected.
Is this detected?
The remainder when you divide E(x)
by G(x)
is never zero with our prime G(x) =
x^{3} +
x^{2} +
1
because E(x) = x^{k}
has no prime factors other than 1 and x.
Hence error detected.
In general, if G(x)
is not equal to x^{i} for any i (including 0)
then
all 1 bit errors will be detected.
In general, if G(x)
is not equal to x^{i} for any i (including 0)
or x^{i}(x+1) for any i (including 0)
then
all 2 adjacent bit errors detected.
Detected if (x^{k}+1) cannot be divided by G(x) for any k up to frame length.
For example, it is true (though no proof provided here)
that G(x) = x^{15}+x^{14}+1
will not divide into any (x^{k}+1)
for k < 32768
Hence can add 15 bits to each block of 32 k bits
and can detect any
1-bit or 2-bit error.
This G(x) represents 1100000000000001.
This is
prime.
If G(x) will not divide into any (x^{k}+1) for k up to the frame length, then all 2 bit errors will be detected.
So if there are an odd no. of errors,
E(x) contains an odd no. of terms.
E(x) can't be divided by (x+1)
If we make G(x) not prime but a multiple of (x+1),
then E(x) can't be divided by G(x).
Can detect all odd no. of errors.
e.g.
CRC-8
= x^{8}+x^{2}+x+1
(=100000111)
which is not prime.
See its factors.
It equals (x+1) (x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1)
If G(x) is a multiple of (x+1) then all odd no. of errors are detected.
If G(x) contains a +1 term and has order n (highest power is x^{n}) it detects all burst errors of up to and including length n.
If G(x) contains a +1 term and has order n, the chance of it failing to detect a burst of length n+1 is (1/2)^{n-1}
Recall Data Link layer often embedded in network hardware.
man cksum