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 101010111 11000110
11011011 00010100
11010110 11011101
10011100 10100001
10110011 00110011
Figure 2
Both the payload and parity bits are shown. One of these bits is flipped.
11100110 01100110 111000000 10000110 1
01000010 00010000 1
10110011 11110110 1
00101010 00010001 0
11110101 00010111 0
Figure 3
Both the payload and parity bits are shown; Either one or two of the bits have been flipped.
01111110 00101100 111101001 01100001 0
01011010 01010011 0
10110010 10011010 1
10110100 11111011 1
01001011 01111111 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:
01010111 11000110 1
11011011 00010100 0
11010110 11011101 1
10011100 10100001 1
10110011 00110011 1
01110101 10011101 0
1. The parity bits for the 16 columns is: 01110101 10011101
2. The parity bits for the 5 rows is: 10111
3. The parity bit for the parity row is: 0
4. The bit that was flipped in figure 2 is (4,4):
11100110 01100110 1
11000000 10000110 1
01000010 00010000 1
10110011 11110110 1
00101010 00010001 0
11110101 00010111 0
For figure 3, the bit that was flipped is (0,3):
01111110 00101100 1
11101001 01100001 0
01011010 01010011 0
10110010 10011010 1
10110100 11111011 1
01001011 01111111 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: 0111010110011101
The answer was: 10111
The answer was: 0
The answer was: 4,4
The answer was: Yes