4 ms·

There's no such thing as dead sure error correction, and there cannot be.

sp332 4y ago
You could include a hash of the correct data, which would tell you in the (cosmically) vast majority of cases when your data has been corrupted.
- defrost 4y ago
  Indeed. That is, however, error detection and not error correction. Once an error is detected you can apply 'correction' to the nearest probably correct value .. which only 'works' for errors under a threshold. Hence the assertion in comment above yours.
- ars 4y ago
  How many hashes will you include? A single one for the whole CD? That tells you if you have an error, but not where? A 32 bytes hash for every 32 bytes? Then you double your storage requirements. There are actually WAY better algorithms for this than a hash (a hash is meant to handle secrets and cryptography - it's the wrong thing for this purpose). ECC codes can tell you if the data is bad - and you can choose how many bytes this covers, and that can also fix bad data, again, you can choose how many errors per byte you want. If you are curious: https://en.wikipedia.org/wiki/Error_correction_code https://en.wikipedia.org/wiki/Error_correction_code
  - ajsnigrutin 4y ago
    For ripping, would it matter? It's probably not a feature that was needed back in time when audio CDs were designed, but in retrospective, getting a notification "bit error was detected when ripping, not sure where, but now you know" would help preservers - they could then find another copy of the CD and get a 100% accurate digital copy of the song (within limits of hashing algos of course).
  - jefftk 4y ago
    > a hash is meant to handle secrets and cryptography - it's the wrong thing for this purpose The rest of your comment is good, but I wanted to quibble with this: hashing is useful for a very wide range of things, and are one of the main building blocks of modern algorithms (hash tables being the best know).
  - rawoke083600 4y ago
    >How many hashes will you include? A single one for the whole CD? That tells you if you have an error, but not where? Interesting ! At what point with today's high-capacity-disks (DVD etc), can we just say store the data x3 and take the value of the closest two ? If the only thing we really want is "high-audio-accuracy" ?
system2 4y ago
Heard of Checksum? https://en.wikipedia.org/wiki/Checksum https://en.wikipedia.org/wiki/Checksum
- SideQuark 4y ago
  Checksums don't provide error correction, nor are they without errors. And they cannot be - it's mathematical fact, hence my post.
  - system2 4y ago
    No, but it shows you if your copy is 100% accurate or not. Which proves that 100% identical copy is possible.
    - SideQuark 4y ago
      No, it most certainly does not. A N bit checksum can at most distinguish 2^n different bitstreams as "100% accurate", and that is assuming there are no transmission errors in transmitting the checksum itself. This is proven trivially by the pigenhole priinciple. And for most media, the checksum is itself transmitted over a noisy channel like the rest of the data. Read your link carefully.
extropy 4y ago
I think GP means prefect or nothing - it errors out if not able to get a valid read. Regular error correction + checksum is a pretty solid implementation of that.
hoseja 4y ago
You can however make it astronomically improbable.
- SideQuark 4y ago
  Which is not what the OP asked for. You simply reintroduced error correction, and you cannot surpass the noisy channel coding theorem bounds.
TheOtherHobbes 4y ago
Sure there is. https://ieeexplore.ieee.org/document/1056798 https://ieeexplore.ieee.org/document/1056798
- SideQuark 4y ago
  The zero error capacity is defined for infinite length codes, none of which are usable in practice. Another way to see it - care to list any error code used anywhere with zero error rate? Read the paper. Shannon write about this in his 1956 paper and subsequent work analyses further, but it's theoretical, and probably not practical for any real world error codes.
- SideQuark 4y ago
  Oh, and another limitation in that paper: to get positive zero-error rate, there has to be input symbols in the channel that cannot ever map to the same output channel, which is not the case for any binary channel in use I have ever seen (my PhD is in error correcting codes). So if noise in the channel could turn a 0 to a 1, or a 1 to a 0, then there is never a positive zero-error rate. This is explained in the paper, page 9, second column. So this is an interesting math question for channels that don't occur in practice, and has resulted (as far as I can tell) in no working codes usable even in labs. It certainly does not apply to transmitting binary data over any noisy channels or media, which is where most if not all error correction codes are actually used.

You could include a hash of the correct data, which would tell you in the (cosmically) vast majority of cases when your data has been corrupted.

defrost 4y ago
Indeed. That is, however, error detection and not error correction. Once an error is detected you can apply 'correction' to the nearest probably correct value .. which only 'works' for errors under a threshold. Hence the assertion in comment above yours.
ars 4y ago
How many hashes will you include? A single one for the whole CD? That tells you if you have an error, but not where? A 32 bytes hash for every 32 bytes? Then you double your storage requirements. There are actually WAY better algorithms for this than a hash (a hash is meant to handle secrets and cryptography - it's the wrong thing for this purpose). ECC codes can tell you if the data is bad - and you can choose how many bytes this covers, and that can also fix bad data, again, you can choose how many errors per byte you want. If you are curious: https://en.wikipedia.org/wiki/Error_correction_code https://en.wikipedia.org/wiki/Error_correction_code
- ajsnigrutin 4y ago
  For ripping, would it matter? It's probably not a feature that was needed back in time when audio CDs were designed, but in retrospective, getting a notification "bit error was detected when ripping, not sure where, but now you know" would help preservers - they could then find another copy of the CD and get a 100% accurate digital copy of the song (within limits of hashing algos of course).
- jefftk 4y ago
  > a hash is meant to handle secrets and cryptography - it's the wrong thing for this purpose The rest of your comment is good, but I wanted to quibble with this: hashing is useful for a very wide range of things, and are one of the main building blocks of modern algorithms (hash tables being the best know).
- rawoke083600 4y ago
  >How many hashes will you include? A single one for the whole CD? That tells you if you have an error, but not where? Interesting ! At what point with today's high-capacity-disks (DVD etc), can we just say store the data x3 and take the value of the closest two ? If the only thing we really want is "high-audio-accuracy" ?

system2 4y ago

Heard of Checksum? https://en.wikipedia.org/wiki/Checksum https://en.wikipedia.org/wiki/Checksum

SideQuark 4y ago
Checksums don't provide error correction, nor are they without errors. And they cannot be - it's mathematical fact, hence my post.
- system2 4y ago
  No, but it shows you if your copy is 100% accurate or not. Which proves that 100% identical copy is possible.
  - SideQuark 4y ago
    No, it most certainly does not. A N bit checksum can at most distinguish 2^n different bitstreams as "100% accurate", and that is assuming there are no transmission errors in transmitting the checksum itself. This is proven trivially by the pigenhole priinciple. And for most media, the checksum is itself transmitted over a noisy channel like the rest of the data. Read your link carefully.

extropy 4y ago

I think GP means prefect or nothing - it errors out if not able to get a valid read. Regular error correction + checksum is a pretty solid implementation of that.

hoseja 4y ago

You can however make it astronomically improbable.

SideQuark 4y ago
Which is not what the OP asked for. You simply reintroduced error correction, and you cannot surpass the noisy channel coding theorem bounds.

TheOtherHobbes 4y ago

Sure there is. https://ieeexplore.ieee.org/document/1056798 https://ieeexplore.ieee.org/document/1056798

SideQuark 4y ago
The zero error capacity is defined for infinite length codes, none of which are usable in practice. Another way to see it - care to list any error code used anywhere with zero error rate? Read the paper. Shannon write about this in his 1956 paper and subsequent work analyses further, but it's theoretical, and probably not practical for any real world error codes.
SideQuark 4y ago
Oh, and another limitation in that paper: to get positive zero-error rate, there has to be input symbols in the channel that cannot ever map to the same output channel, which is not the case for any binary channel in use I have ever seen (my PhD is in error correcting codes). So if noise in the channel could turn a 0 to a 1, or a 1 to a 0, then there is never a positive zero-error rate. This is explained in the paper, page 9, second column. So this is an interesting math question for channels that don't occur in practice, and has resulted (as far as I can tell) in no working codes usable even in labs. It certainly does not apply to transmitting binary data over any noisy channels or media, which is where most if not all error correction codes are actually used.