Interactive end-of-chapter exercises


Error Detection and Correction: Two Dimensional Parity

Suppose that a packet’s payload consists of 10 eight-bit values (e.g., representing ten ASCII-encoded characters) shown below. (Here, we have arranged the ten eight-bit values as five sixteen-bit values):

Figure 1

10001110 11100010
10010010 00101001
10111100 11110111
00101101 00000101
11010010 10110110

Figure 2

Both the payload and parity bits are shown. One of these bits is flipped.

10101111 00111011 1
01010011 10010111 1
00010100 11110101 0
01110011 11001100 1
11010100 01000100 0
11001111 11010001 1

Figure 3

Both the payload and parity bits are shown; Either one or two of the bits have been flipped.

11011100 01100000 1
11101100 11000110 1
10111101 10101011 1
11100010 11011010 1
11010111 01101110 1
10111000 10011001 1


Question List


1. For figure 1, compute the two-dimensional parity bits for the 16 columns. Combine the bits into one string

2. For figure 1, compute the two-dimensional parity bits for the 5 rows (starting from the top). Combine the bits into one string

3. For figure 1, compute the parity bit for the parity bit row from question 1. Assume that the result should be even.

4. For figure 2, indicate the row and column with the flipped bit (format as: x,y), assuming the top-left bit is 0,0

5. For figure 3, is it possible to detect and correct the bit flips? Yes or No




Solution


The full solution for figure 1 is shown below:

10001110 11100010 0
10010010 00101001 0
10111100 11110111 0
00101101 00000101 0
11010010 10110110 1
01011111 10001111 1

1. The parity bits for the 16 columns is: 01011111 10001111

2. The parity bits for the 5 rows is: 00001

3. The parity bit for the parity row is: 1

4. The bit that was flipped in figure 2 is (0,5):

10101111 00111011 1
01010011 10010111 1
00010100 11110101 0
01110011 11001100 1
11010100 01000100 0
11001111 11010001 1

For figure 3, the bit that was flipped is (10,5):

11011100 01100000 1
11101100 11000110 1
10111101 10101011 1
11100010 11011010 1
11010111 01101110 1
10111000 10011001 1

5. Yes, with 2D parity, you can detect and correct the a single flipped bit



That's incorrect

That's correct

The answer was: 0101111110001111

Question 1 of 5

The answer was: 00001

Question 2 of 5

The answer was: 1

Question 3 of 5

The answer was: 0,5

Question 4 of 5

The answer was: Yes

Question 5 of 5

Try Another Problem

We gratefully acknowledge the programming and problem design work of John Broderick (UMass '21), which has really helped to substantially improve this site.

Copyright © 2010-2022 J.F. Kurose, K.W. Ross
Comments welcome and appreciated: kurose@cs.umass.edu