0:00
In today's class, we continue on
CRC Error Detection Capability Analysis as well as Internet Checksum.
The CRC Encoding uses polynomial codes generating checkbits.
The first step is to multiply information polynomial by x plus n minus
k. The second step is to divide the shift data information polynomial by g x.
And, again our remainder polynomial,
r x which is a CRC checkbits.
Finally, add the remainder polynomial r x to the information polynomial.
And the resulting polynomial will be the transmitted codeword.
As CRC code may seem to be sophisticated,
let's see one more example and let's go over the procedure step by step.
In this example, the information frame is one one zero one zero one one zero one one.
And the generated polynomial is x plus four plus x plus one,
which is exactly one zero one one in binary.
The frame message is a appended of four zeros.
That is a lower order because that generator degree is four.
A division is executed step by step,
according to the binary arithmetic.
In step one, the first bit of quotient of one is generated.
In step two, the second bit of quotient of one is generated.
In step three, the third bit of quotient is generated.
It is zero because the highest power of
the interim remainder is smaller than the highest power of the divisor.
In step four, in step five,
and in step six,
each newly generated quotient bit is zero Now in step seven,
a new quotient bit of one is generated.
Please note here that only if the highest power of
the interim remainder polynomial is equal
or greater than the highest power of the divisor.
A new quotient term is computed along with a new interim remainder polynomial.
In Step 8, the newly generated quotient bit is zero.
Because the highest power of the interim remainder is
smaller than the highest power of the divisor.
In step nine, the newly generated quotient bit is again zero.
In step 10, that division process stops
when the degree of remainder is less than the degree of divisor.
The calculated remainder is 1 1 1 0 which is a CRC checkbits.
Finally this CRC checkbits are appended as
a low order position and the transmitted frame is therefore generated.
One may ask what kind of errors will be detected by CRC technique?
Imagine that a transmission error vector e x occurs,
e x has ones in error locations and zeros elsewhere which is an additive error model.
Adding bit by bit to the input code word v x by using modulo 2 or arithmetic,
instead of b x transmitted by the sender,
the receiver will now receive b x plus e x,
receiver divides the receiver polynomial.
x by g x,
the blind spot occurs if e x is a multiple of g x.
That is e x is divisible by g x.
The error will not be detected.
So how do we select the g x that have good detection capability?
We should select generated polynomial.
So the likely error patterns are not a multiple of g x.
Single errors means e x equals 2x plus i.
If g x has more than one term,
it cannot divide x plus i and they are forcing the errors detected.
Double errors e x equals to x plus i plus x plus g. If g has more than one term,
it cannot divide x plus i.
If g x is a primitive polynomial,
it cannot divide x plus n plus 1 for all m that is less than 2 plus n minus k minus 1.
In this case, we need to keep codeword length less than 2 plus n minus k minus one.
Primitive polynomials can be found by consulting coding theory books.
Designing good polynomial codes for more than 2 bit errors is more sophisticated.
We leave it to more advanced readers.
Here we give four standard CRC generator polynomials,
CRC-8 is using ATM.
CCITT-16 is using HDLC and XMODEM.
CCITT-32 is using IEEE 802 LAN as well as DoD.
Internet protocols including IP TCP,
UDP, use check bits to detect errors instead of using CRC polynomial.
The rationale is the simplicity the checksum must be recalculated at every router,
the algorithm for the checksum was selected for its ease of
implementation instead of strength of error detection capability.
IP header consist of a certain number,
say L of 16 bit words,
b0, b1 to bL minus 1.
The 16 bit of checksum b L is calculated as false.
Each 16-bit word is treated as an integer.
Find x that equals to the sum of the 16 bit of words.
Modulo 2 power of 16 minus one.
The checksum is then given by negative X which is
carried out in software using one's complement arithmetic.
By doing the checksum,
the header must satisfy the following pattern.
The sum of the 16 bit of words and as a checksum modulo 2 power of 16 minus 1,
the result must be zero.
Otherwise, there is an error.
We give an example.
For simplicity, let's assume 4-bit words instead of 16- bit words.
The checksum calculation process thus use modulo 2 power of
four minus 1 arithmetic instead of all modulo 2 power of 16 minus one.
One can read that the checksum calculation process is using
muodulo arithmetic or using binary arithmetic by himself.
As a quick summary,
choosing good generator polynomial codes
determines the capability of CRC error detection.
Internet checksum, however, values more on
ease of implementation than on detection capability.
Xiaobo ZhouProfessor, Interim Dean
