Cmput: 2D parity error detection scheme

[hkstyles]

Question Details:
The following blocks have been encoded using the two-dimensional parity error detection scheme. That is, the rows have been encoded using odd parity and the last row holds the parity bits of the columns which have also been encoded using odd parity. There are two possible interpretations of the corner parity bit in the last block – it can either check the row or column parity. In this example, it has been used to check the column parity.

a) Is an error detected?

b) If there is an error (or more than one errors) detected: are there conditions where the error or errors can be corrected? If there is no error detected, could there have been errors that were not detected?

c) How many overhead bits are there in this example?

1 0 1 1 1 0 0 1
0 1 0 0 1 1 0 0
0 0 0 0 0 1 1 1
1 1 1 0 0 0 0 0
1 1 1 0 1 1 0 1

--------------------------------------------
also.. :
The following message bits are to be transmitted: 11010001010001001010. It is decided to split this message into blocks of 5 bits and apply the two-dimensional parity error detection scheme using even parity. Show the encoded blocks that would be transmitted.

 

[asd1249jf]

You have to show your work if you want to receive detailed help.

Here's something to start you off. Recall the definition of odd parity. The parity bit is set to 0 if you have an odd numbers of ones and it is set to 0 if you have an even number of ones.

In your case, the last row (bottom) and the last column (to the right) are the parity bits. Compare each row and column and see if you find any contradictions. If you do, then t here has been an error in the transmission.

 

[piercas]

a) Yes, an error is detected. The last block has a parity bit of 1, but the correct parity for the columns is 0. This means that there is an error in at least one of the columns.

b) In this case, the error can be corrected by flipping the bit in the last block's parity bit. This would correct the error in the columns. However, if there were more than one error, the error could not be corrected as the parity bit only indicates the presence of an error, not the location of the error.

If there is no error detected, it is possible that there were errors that were not detected. This is known as a "false negative" and can occur if the errors cancel each other out in terms of parity.

c) There are 3 overhead bits in this example - one for the row parity and two for the column parity.

Encoded blocks:
11011
10001
00100
01001
01010