Two Dimensional Parity Check

Simple parity check method fails to detect an error if total number of bits in error is even. Two-dimensional parity check method is a better approach of detecting an error. Two-dimensional parity check method is also based on the concept of redundancy. This means, in this method of error detection sender needs to send some redundant bits with original data so that receiver will use these redundant bits to detect an error. These bits are called parity bits. Let us understand how sender computes these parity bits and how receiver detects an error with simple example.

Assume that data to send is

1011 000 1011 011 1011 001

I will explain the process into four steps.

Step 1.

The first step is to divide the given data into some segments having equal number of bits. In this example I have divided this data into three segments and organised these three segments into a table so that there will be three rows and seven columns.

Step 2.

row parities

Sender compute parity of each row and make the parity even. Here parity of the first row is odd parity. There are three 1’s, so to make it even 1 is added as parity bit to make the parity even. For the second row there are five 1’s i.e., odd parity. To make the parity even, parity bit ‘1’ is added to make the party even. In third row there are four 1’s, that means the parity of this row is already even. So parity bit ‘0’ is added in the row and therefore parity remains even.

Column Parities

In the same way column parties are also computed and made even. In each column one parity bit is added and parity is made even as shown below.

Once we computer row parities and column parities we get the code word.

10110001 10110111 10110010 10110100

This data (including redundant bits or parity bits) are send to the receiver.

Assuming that there is no error in the data transmission receiver will receive exactly the same code word transmitted by the sender. The received data is

10110001 10110111 10110010 10110100

Step 3.

Receiver divides the received data into segments and organise them in a table in the same way as the sender. So, at receiver side we have four segment; four rows and eight columns. First row is 10110001 the second row is 10110111 third row will be 10110010 and the last fourth row is 10110100.

Step 4.

In the last step, to detect an error, receiver checks the parity of each row and each column. If the parity of each row and each column is even it is assumed that the data is received correctly. There is no error in the received data and then data will be accepted discarding the extra bits or redundant bits sent by the sender.

In this example, receiver checks the row parities.

First row; there are four 1’s ; even parity.

Second row; there are six 1’s; even parity.

Third row; there are four 1’s; even parity. And

Fourth row; there are four 1’s even parity.

In the same way, column parities are also checked.

First column; there are four 1’s; even parity.

Second column; there are zero number of 1’s; even parity.

Third column; there are four 1’s; even parity.

Fourth column; there are four 1’s; even parity.

Fifth column; there are zero number of 1’s; even parity.

Sixth column; there are two 1’s; even parity.

Seventh column; there are two 1’s; even parity.

Eighth column; there are two 1’s; even parity.

As parity of each row and each column is even, data assumed to be correct. Therefore, the data is accepted discarding parity bits.

How is error detected?

Let us see, how 2-dimensional parity check method detects an error. Suppose in the received data 5th bit in the first segment is changed where zero becomes one. Therefore, the received data will be.

To check the row parities and column parities. This data unit is arranged in a table as shown above.

In this example, there are two parity violations.

In the first row, there are five 1’s; odd parity, and
In the fifth column, there is one 1; odd parity.

As there are two parity violations in the received data, data assumed to be corrupted. Therefore, the data will not be accepted by the receiver. So, 2-dimensional parity check method detects error when even number of bits are in error. 2-dimensional parity check method overcomes the drawback of simple parity check method. 2-dimentional parity check method detects an error if 2 bits are in error, 3 bits are error. That means 2-d parity check method detects single bit error and burst error. Detects burst error, if even number of bits are in error, also when odd number of bits are in error.

Drawback of 2-Dimensional parity check

2-Dimensional Parity Check can detect almost all burst errors. 2-Dimensional Parity check of n bits can detect a burst error of n bits. A burst error of more than n bits is also detected by 2-D Parity check with a high-probability. However, there is one pattern of error that remains undetected. If two bits in one data unit are changed or damaged and two bits in exactly same position in another data unit are also changed or damaged. Then the 2-Dimensional Parity check checker will not detect an error.
Example, If in the above example first and the third data unit/segment is damaged. If third and last bits in each of them is damaged, making the data units as

In this example, total 4 bits are in error. But there are no parity violations in row parities and column parities. All row parities are even, and column parities are also even. In 2-dimensional parity check if there are no parity violations the received data assumed to be correct or not damaged and data is accepted discarding the parities bits. In this pattern of error 2-dimensional parity check fails to detect an error.

Example, If in the above example first and the third data unit/segment is damaged. If third and last bits in each of them is damaged, making the data units as