Simple Parity Check Code

Linear Block Codes:

A linear block code is a code in which the exclusive OR (addition modulo-2) of two valid code words creates another valid code word.

The scheme in the above table is a linear block code because the result of XORing any code word with any other code word is a valid code word. For example, the XORing of the second and third code words creates the fourth one.

Minimum Distance for Linear Block Codes:

It is simple to find the minimum Hamming distance for a linear block code. The minimum Hamming distance is the number of 1s in the nonzero valid code word with the smallest number of 1s. In the above table the numbers of 1s in the nonzero code words are 2, 2, and 2. So the minimum Hamming distance is dmin =2.

Simple Parity-Check Code:

The simple parity-check code is the most familiar error-detecting code. In this code, a k-bit data word is changed to an n-bit code word where n = k + 1. The extra bit, called the parity bit, is selected to make the total number of 1s in the code word even. Although some implementations specify an odd number of 1s. The minimum Hamming distance for this category is dmin =2, which means that the code is a single-bit error-detecting code and it cannot correct any error.

The following figure shows possible structure of an encoder (at the sender) and a decoder (at the receiver).

The encoder uses a generator that takes a copy of a 4-bit data word (a0, a1, a2 and a3) and generates a parity bit r0. The data word bits and the parity bit create the 5-bit code word. The parity bit that is added makes the number of 1s in the code word even.

This is normally done by adding the 4 bits of the data word (modulo-2).

            r0=a3+a2+a1+a0 (modulo-2)

The result is the parity bit. In other words, If the number of 1s is even, the result is 0; if the number of 1s is odd, the result is 1.In both cases, the total number of 1s in the code word is even.

The sender sends the code word which may be corrupted during transmission. The receiver receives a 5-bit word. The checker at the receiver does the same thing as the generator in the sender with one exception: The addition is done over all 5 bits.

s0=b3+b2+b1+b0+ q0 (modulo-2)

The result, which is called the syndrome, is just 1 bit. The syndrome is 0 when the number of 1s in the received code word is even; otherwise, it is 1.

The syndrome is passed to the decision logic analyzer. If the syndrome is 0, there is no error in the received code word, the data portion of the received code word is accepted as the data word, if the syndrome is 1, the data portion of the received code word is discarded. The data word is not created.

For example, the sender sends the data word 1011. The code word created from this data word is 10111, which is sent to the receiver. We examine five cases:

1. No error occurs; the received code word is 10111. The syndrome is 0. The data word 1011 is created.

2. One single-bit error changes a1. The received code word is 10011. The syndrome is 1. No data word is created.

3. One single-bit error changes r0. The received code word is 10110. The syndrome is 1. No data word is created. Note that although none of the data word bits are corrupted, no data word is created because the code is not sophisticated enough to show the position of the corrupted bit.

4. An error changes r0 and a second error changes a3. The received code word is 00110. The syndrome is O. The data word 0011 is created at the receiver. Note that here the data word is wrongly created due to the syndrome value. The simple parity-check decoder cannot detect an even number of errors. The errors cancel each other out and give the syndrome a value of O.

5. Three bits-a3, a2, and a1-are changed by errors. The received code word is 01011. The syndrome is 1. The data word is not created. This shows that the simple parity check, guaranteed to detect one single error, can also find any odd number of errors.

A better approach is the two-dimensional parity check. In this method, the data word is organized in a table (rows and columns). In the following figure, the data to be sent, five 7-bit bytes, are put in separate rows. For each row and each column, 1 parity-check bit is calculated. The whole table is then sent to the receiver, which finds the syndrome for each row and each column.

As shown in the figure, the two-dimensional parity check can detect up to three errors that occur anywhere in the table (arrows point to the locations of the created nonzero syndromes). However, errors affecting 4 bits may not be detected.