School of Computing. Dublin City University. Home Blog Teaching Research Contact My big idea: Ancient Brain 


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 nonzero coefficient. This is polynomial of order 5.
Special case: We don't allow bitstring = all zeros.
Easy to use
framing or stuffing
to make framedandstuffed transmission never allzero,
while still allowing payload within it to be allzero.
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 01=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 recalculated 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 wellbehaved 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 (xc) = n y
(xc) div y gives remainder 0
Here (xc) = (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 singlebit 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
1bit or 2bit 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.
CRC8
= 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)^{n1}
Recall Data Link layer often embedded in network hardware.
man cksum