Next: Data Link Layer Up: Error Detection and Previous: Error Detection and

## Parity Check Codes

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).

• Single parity check: a single bit is appended to the end of each frame, the bit is 1 if the data portion of the frame has odd number of 1's. Otherwise, it is 0. This way, the total number of 1's in each data frame is always even. The problem with this approach is that if there are even number of errors, it can not be detected. Furthermore, it can not tell which bit is in error (the error may even be the parity bit itself), thus it can not fix the error. Therefore it has a one bit error detection capability but no error correction capability.
• Horizontal and vertical parity checks: multiple frames of equal lengths are layed down like a matrix, a single parity check is applied to each row and column of the matrix, resulting in a new row and a new column of parity bits. Each frame is then sent with the added bit, and a new parity frame (because of column parity check) is also sent. This method improves error protection because consecutive errors can also be detected. For example, the column check will be able to detect even if all the bits in one row are corrupted.
• Parity Check Codes: this is the generalization of the parity check. An example shows how this generaliatin is done:

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 .

• Cyclic Redundancy Codes(CRC): CRC is one type of parity code. In CRC the parity bits, described by is generated by using the expression:

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.

Next: Data Link Layer Up: Error Detection and Previous: Error Detection and

zhangj@
Mon May 23 15:29:10 EDT 1994