Posted on 2004-01-09 05:25:16 by AceEmbler
Don't know about error correction, but know about xor error detection.

It works like this:
You have some data that you wish to protect from corruption.
You start by calculating some kind of hash for it, be it md5 or what you like.
You then xor each byte of the hash with each byte of the data.
Now you append your hash to the end.

The receiver of the protected packet takes the hash from the end.
They xor it against the protected data payload, and then they calculate the hash for the data and compare it to the hash they received.
If the hashes do not match, the data was corrupted and must be retransmitted.

It's just a variation on a CRC which is far less likely to produce false results due to the content of the data.
Posted on 2004-01-10 08:00:20 by Homer
The only error correcting code I've looked at was Hamming code.
At the time i studied it, it was difficult to understand. It has been too long ago...I don't remember how it worked.
Posted on 2004-01-10 16:04:31 by tenkey
Since it's rather late this will be rather quick. I'll be happy to explain better another day if anyone so desires ^^

Quick reminder - Modulo 2 addition:
0 + 0 = 0

0 + 1 = 1
1 + 0 = 1
1 + 1 = 0

Suppose you want to send 4 bits to someone, and you want to know a) if an error occurred, and b) how to correct the error. The Hamming (7,4) code works for single bit errors.

Call the bits in your message x1, x2, x3, x4. Then you append 3 more bits (called parity bits) onto the message as follows:

x5 = x1 + x2 + x3
x6 = x1 + x2 + x4
x7 = x2 + x3 + x4

This gives you a 7 bit code word to transmit, x1, x2, x3, .. x7.

You can rewrite the equations for the parity bits, by adding x5/x6/x7 to both sides, as:

x1 + x2 + x3 + x5 = 0
x1 + x2 + x4 + x6 = 0
x2 + x3 + x4 + x7 = 0

(Look at the table at the top, notice adding either 1 to itself or 0 to itself equals 0)

So what adding these bits gives you is a system of equations to solve. It can be re-written, in matrix form, like this:

If the message was sent along fine then you get a resulting column vector with all 0 entries as expected. However, if there was an error, then you get some non-zero vector.

To determine which bit was damaged in transmission, compare the result against each column of the parity check matrix. Whichever column matches is the damaged bit (eg if you get [1, 0, 1] you know the third bit was damaged). If the parity bits were damaged, who cares. We only cared about the first four bits anyway :)

If the result doesn't match any columns in the parity check matrix, then more than 1 bit was damaged, in which case you'd need to have that block re-sent.

Quick and ugly, but I'm sleepy. Hope its useful anyway
Posted on 2004-01-13 00:12:34 by Miko