Position : 7 6 5 4 3 2 1 Bit: d3d2 d1 p2 d0 p1 p0 Given that p2 = d3 XOR d2 XOR
ID: 1830212 • Letter: P
Question
Position : 7 6 5 4 3 2 1 Bit: d3d2 d1 p2 d0 p1 p0 Given that p2 = d3 XOR d2 XOR d1 p1 = d3 XOR d2 XOR d0 p0 = d3 XOR d1 XOR d0 Question: Normally 3 parity bits in a 7-bit Hamming code do notprovide the ability to correct more than one errors. However, if weare able to get extra information regarding the number of errorsand the possible positions where an error can occur, we may be ableto correct more errors.Assume we know for sure that no errorscan occurin the parity bits, while exactly3errors exist in the data bits. Under thisassumption, do you think it is possible to correct all these 3errors? If you think so, please briefly explain your errorcorrection approach. Otherwise, please show an examplewherein 3 errors in data bits can not becorrected. (Hint: you can think about the idea of flippingall the data bits.)
Position : 7 6 5 4 3 2 1 Bit: d3d2 d1 p2 d0 p1 p0 Given that p2 = d3 XOR d2 XOR d1 p1 = d3 XOR d2 XOR d0 p0 = d3 XOR d1 XOR d0 Question: Normally 3 parity bits in a 7-bit Hamming code do notprovide the ability to correct more than one errors. However, if weare able to get extra information regarding the number of errorsand the possible positions where an error can occur, we may be ableto correct more errors.
Assume we know for sure that no errorscan occurin the parity bits, while exactly3errors exist in the data bits. Under thisassumption, do you think it is possible to correct all these 3errors? If you think so, please briefly explain your errorcorrection approach. Otherwise, please show an examplewherein 3 errors in data bits can not becorrected. (Hint: you can think about the idea of flippingall the data bits.)
Explanation / Answer
The problem says that there can be exactly 3 errors in thedata bits and no errors in the parity bits. To be able to correct any such errors, we need to be able touniquely identify all possible errors from the state of the paritybits. The table below lists all possible combination of data bitsfor possible errors and then checks which parity bits are effectedby this error. "same" under a parity bit means it is not changed by thecorresponding error and "change" means it is changed by thecorresponding error.Possible error p2 p1 p0
d3 d2 d1 change same same d3 d1 d0 same same change d2 d1 d0 same same same
Since we are using XOR between 3 bits, a parity bit willchange only if 1or 3 of the 3 bits have error and the paritybit will remain same if 0 or 2 of the 3 bits have error.
From above table, we can see that the condition of the 3parity bits will not uniquely identify the possible error cases. Ifthere are errors in d2 d1 and d0 bits, then the error will goundetected. SO all possible cases cannot be corrected by thisscheme.
I hope you have understood how to do this.