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 111000000 10001000
00100011 00011011
00011100 01100110
11001000 11011001
00011001 10000000
Figure 2
Both the payload and parity bits are shown. One of these bits is flipped.
11111110 01001100 111011011 01010011 0
10110010 11101010 1
00111001 11000100 1
00011010 11110001 0
10110100 11000001 1
Figure 3
Both the payload and parity bits are shown; Either one or two of the bits have been flipped.
10001000 11100101 100011101 00001001 0
10101110 00111011 1
00010100 00010011 1
11100111 00000010 1
10001000 11000110 0
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:
11000000 10001000 0
00100011 00011011 1
00011100 01100110 1
11001000 11011001 0
00011001 10000000 0
00101110 10101100 0
1. The parity bits for the 16 columns is: 00101110 10101100
2. The parity bits for the 5 rows is: 01100
3. The parity bit for the parity row is: 0
4. The bit that was flipped in figure 2 is (15,0):
11111110 01001100 1
11011011 01010011 0
10110010 11101010 1
00111001 11000100 1
00011010 11110001 0
10110100 11000001 1
For figure 3, the bit that was flipped is (1,2):
10001000 11100101 1
00011101 00001001 0
10101110 00111011 1
00010100 00010011 1
11100111 00000010 1
10001000 11000110 0
5. Yes, with 2D parity, you can detect and correct the a single flipped bit
That's incorrect
That's correct
The answer was: 0010111010101100
The answer was: 01100
The answer was: 0
The answer was: 15,0
The answer was: Yes