…or more specifically, postal barcodes. But I guess any kind of barcode would work.
Let’s take postal barcoding for example. If you don’t know anything about checksums, you might not want to continue reading.
Example: let’s use 12345-6789-01 as the encoded number. This would provide a checksum digit of 4. Now let’s say that there was an error in the transmission and it came through as 12X45-6789-01. With the checksum of 4, we can determine that the lost digit is 3.
What happens if there are 2 or more errors? How is this corrected?
Example… if it comes through as 12XX5-6789-01 with a checksum of 4, we know that the missing 2 digits must add up to 7… but they could be 0 and 7, 1 and 6, 2 and 5, 3 and 4… or 6 and 1, 5 and 2, 4 and 3, or 7 and 0.
How does this method of error correction correct 2 or more corrupted segments?
At the risk of asking a dumb question, how do you know that it was the 3 that got mangled?
The checksum computation as far as I google it, adds an extra digit to make sure the encoded number comes out as a multiple of 10. Given this rather feeble error detection technique, you can’t know that it’s the 3 that got mangled. An error in transmission still gets decoded as data.
This is typical of a checksum, or even a more powerful CRC – it can be used to detect an error (maybe more than one). In fact, this checksum is so bad, that if two values were incorrect, the checksum could still ‘check out’. All it would take would be one value being bad in one direction and another value being bad in the other direction.
Anyway, if you knew it was the 3 that was bad, you could correct it, but you don’t necessarily know that, and the moment you have more than one error, you’re dead in the water.
This checksum does not allow error correction at all, unless you know, a priori, which digit had the error.
[/quote]
Anyway, if you knew it was the 3 that was bad, you could correct it, but you don’t necessarily know that, and the moment you have more than one error, you’re dead in the water.
[/quote]
You would know that the third digit is the erroneous digit. If you’re asking how you know that the third digit is the one that contains the error, the 5th bit is a checksum for each word in postal encoding. It is either a 1 or 0 depending on the number of 1s in the four-bit word (if there are 2, it’s a 0, if there is 1, it’s a 1). Since word 3 contains 3 bits of “1,” it has the error.
That also gives a checksum of 4, but it’s the 5’th digit that’s wrong (2 bits error, changing the parity bit). This error involves a single digit, but it has two bits wrong.
This has a single-bit error in the third digit, but the parity is correct. The checksum is wrong, but you can’t tell which digit failed!
Further:
00011 00101 00110 01011 01001 01100 10001 10010 10100 11000 00011 01001
This has 3 bit errors, and the checksum passes, but there’s a bit error on the 4th digit… but it’s the 5th digit error that is also wrong, making the checksum work out, but you can’t possibly detect that.
Oops, my mistake. My single-bit error change would have failed parity, and you could identify the offending digit.
So you can correct a single-digit error provided it has a single bit failure. But if you have more than one digit, or more than one bit in a single digit, you’re pooched.
There are other techniques for improving the error correction capability, and at least improving on error detection (an easier job). A CRC of sufficient number of bits tacked on the end of a message can add an impressive error detection strength for single and multiple bit errors, even burst errors, but you can’t correct the errors.
A Hamming code is a pretty efficient way of encoding 100% single-error-correction, but for single-digit encodings it would double the length of the message. There are ways to make it probably detect errors in less space usage with fewer bits, and of course you can reduce the overhead by protecting more bits at once (but then more than one error within that block becomes more likely).
FEC encoding is a fascinating tool, too… at the cost of doubling your message length, you can actually correct a fairly large number of errors before it collapses. Its probabilistic, and computationally intensive to decode, but quite efficient in terms of its correcting capability. There are a fair few variations.
