Parity check is a simple way to add redundancy bits to the packets such that the total number of 1's is even (or odd).
Suppose 3bit blocks, , are attached with 4 more parity check bits:
,
,
,
.
Here the additions are binary operations. That is: , ,, , , , etc.
Therefore each 3bit data frame is expanded into a 7bit coded data.
At the receiver, parity check is done through the above set of equations. If any equation is not satisfied at the receiver, the associated frame is corrupted. However, we again should know that all the checksum equations being satisfied does not mean there is no error. Each binary code word can be uniquely represented by the following symbolic polynomial expression:
. Here again the multiplications and additions are binary operations. It can be shown that this type of binary polynomials with binary coefficients are determined uniquely by their coefficients, distinctly represents the code word. For the above example, there are 8 distinct polynomials.
To make things a little easier to understand, we further define:
Therefore, .
In general, if there are bits in each data frame , and an additional bits for the CRC, , we have .
where is a predetermined polynomial of degree (therefore a sequence of predeterminted bits), called the generator polynomial. The polynomial division here is again binary. The division can also be equivalently done by using the underlying binary bit sequences. One such example is shown in page 210 of the textbook, where , and , the remainder is given by: .
Now let's see how it works to combat errors.
At the transmitter, the sender cut data streams into blocks of bits and attach an bit CRC code, generated by the above method, the transmitted code is therefore given by . If the channel is error free, then will also be what the receiver gets. The receiver can verify this by finding the followinger remainder
Since is already the remainder of , we have
Therefore,
Now suppose that the received sequence is in error: () is received. Let . Then we have
Now the receiver will fail to detect error if and only if
Obviously, we want this to be as unlikely as we can. Especially where there is only one or two errors, the above remainder equation should always be nonzero so that the error frame can be detected.
The flexibility we have at hand is the choice of . It turns out that some polynomial has better properties than others in terms of making .
It can be shown that when is the product of a primitive polynomial of degree and a polynomial , it can be used to detect all single and double errors, including the possible errors in CRC itself, for data frame of length up to .
For example, if , i.e., a 16bit CRC code is attached to a data frame, using the above choice of , we can detect single and double errors data frames of up to .
Here are two such examples:
, which corresponds to .
, which corresponds to .
Homework Problem: For each of the above , decompose it into two parts: , where is the primitive polynomial.