Multidimensional parity-check code
 |
 | Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation. |
A multidimensional parity-check code is a particularly simple type of error correcting code used to correct errors that occur either when data is transmitted or while it resides in memory. It is best explained with an example.
If you want to transmit the 4 digit message '1234'. First you would arrange the digits in a square pattern:
12
34
then you add up rows and columns to get the parity digits:
123
347
46
this is the message that is actually transmitted. If any single error occurs during transmission then this error can not only be detected but can also be corrected as well. Let us suppose that the received message contained an error in the first digit.
923
347
46
The receiver can see that the first row and also the first column don't add up correctly. Using this knowledge and the assumption that only one error occurred, the receiver can correct the error. Modern memory produces, on average, about one error per gigabyte per month so the chance of two errors occurring together is negligible. This may not always be the case when transmitting the message over noisy long distance lines. More sophisticated codes are required for that.
One can, of course, increase the number of dimensions, arranging the digits into a cube instead of a square and summing in all three directions. In general, an n dimensional parity scheme can correct n/2 errors. So a 4 dimensional parity scheme can correct any 2 errors but at the cost of more parity digits per given amount of data.
Low-density parity-check codes are able to get much closer to the Shannon limit than multidimensional parity-check codes by forming the parity digits from groups of more or less randomly chosen data digits. But this only works with large blocks of data.