School of Computing. Dublin City University.
Online coding site:
Ancient Brain
coders JavaScript worlds
School of Computing. Dublin City University.
Online coding site:
Ancient Brain
coders JavaScript worlds
Bitstring represents polynomial.
e.g. 110001 represents:
1 . x5 +
1 . x4 +
0 . x3 +
0 . x2 +
0 . x1 +
1 . x0
= x5 +
x4 +
x0
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:
x2 + x
-------------
x2 + 2x + 1
= x2 + 1
2 xk = 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 x3
to get
x4 + x3
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 xk, add k zeros.
Do long division:
Divide (x+1) into x2 + 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 xn,
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) =
x3 +
x2 +
1
because E(x) = xk
has no prime factors other than 1 and x.
Hence error detected.
In general, if G(x)
is not equal to xi for any i (including 0)
then
all 1 bit errors will be detected.
In general, if G(x)
is not equal to xi for any i (including 0)
or xi(x+1) for any i (including 0)
then
all 2 adjacent bit errors detected.
Detected if (xk+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) = x15+x14+1
will not divide into any (xk+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 (xk+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
= x8+x2+x+1
(=100000111)
which is not prime.
See its factors.
It equals (x+1) (x7+x6+x5+x4+x3+x2+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 xn) 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