Slashdot Mirror
Error-Proofing Data With Reed-Solomon Codes
ttsiod recommends a blog entry in which he details steps to apply Reed-Solomon codes to harden data against errors in storage media. Quoting: "The way storage quality has been nose-diving in the last years, you'll inevitably end up losing data because of bad sectors. Backing up, using RAID and version control repositories are some of the methods used to cope; here's another that can help prevent data loss in the face of bad sectors: Hardening your files with Reed-Solomon codes. It is a software-only method, and it has saved me from a lot of grief..."
It really depends where you store the FEC, some techniques store the fec separately others concatenate and others interleave the FEC. Each method has its own advantages and disadvantages.
Arash Partow's Philosophy: Be a person who knows what they don't know, and not a person who doesn't know.
checksums really only help in detecting errors. Once you've found errors, if you have an exact redundancy somewhere else you can repair the errors. What reed-solomon codes do is provide the error detecting ability but also the error correcting ability whilst at the same time reducing the amount of redundancy required to a near theoretical minimum.
btw checksums have limits on how many errors they can detect within lets say a file or other kind of block of data. A simple rule of thumb (though not exact) is that 16 and 32 bit checksums can detect upto 16,32 bit errors respectively anymore and the chance of not detecting every bit error goes up, it could even result in not finding any errors at all.
Arash Partow's Philosophy: Be a person who knows what they don't know, and not a person who doesn't know.
"Awk! Parroty Error! Parroty Error! Pieces of Seven, Pieces of Seven"
(*BOOM*) never did like that bird.
Do not mock my vision of impractical footwear
A CD-ROM sector contains 2352 bytes, divided into 98 24-byte frames. The CD-ROM is, in essence, a data disk, which cannot rely on error concealment, and therefore requires a higher reliability of the retrieved data. In order to achieve improved error correction and detection, a CD-ROM has a third layer of Reed-Solomon error correction.[1] A Mode-1 CD-ROM, which has the full three layers of error correction data, contains a net 2048 bytes of the available 2352 per sector. In a Mode-2 CD-ROM, which is mostly used for video files, there are 2336 user-available bytes per sector. The net byte rate of a Mode-1 CD-ROM, based on comparison to CDDA audio standards, is 44.1k/s×4B×2048/2352 = 153.6 kB/s. The playing time is 74 minutes, or 4440 seconds, so that the net capacity of a Mode-1 CD-ROM is 682 MB.
I'd say that's a yes.
Me failed English...
FreeBSD over Linux. If my comments seem odd, this may explain...
My biggest failed prediction in the world of computers was the CD-ROM.
I was an audio CD early adopter and I knew from articles I read that audio CD's often had a certain defect rate. The defect rate was usually such that you would never hear it. One artist even published all the defects in the liner notes.
Based upon this, I presumed that you would never get the defect rate to zero and that no one would trust a data medium with anything less than perfection - and thus predicted the CD-ROM would never catch on.
They don't have to get the rate to zero. Just close enough to zero for the RS to function.
This is a boring sig
The speed of encoding and decoding directly relates to the type of RS and the amount of FEC required. Generally speaking erasure style RS can go as low as O(nlogn) (essentially inverting and solving for a vandermonde or Cauchy style matrix) A more general code that can correct errors (the difference between an error and an erasure is that in the latter you know the location of the error but not its magnitude) may require a more complex process, something like Syndrome-Berlekamp Massey-Forney which is about O(n^2).
It is possible to buy specialised h/w (or even GPUs) to perform the encoding steps (getting roughly 100+MB/s) and most software encoders can do about 50-60+Mb/ for RS(255,223) - YMMV
Arash Partow's Philosophy: Be a person who knows what they don't know, and not a person who doesn't know.
quickpar especially has been in use on usenet/newsgroups for years....o yea...forgot....they are trying to kill it.
anyways...there's also dvdisaster which now has several ways of "hardening".
one of them seems to catch my attention: adds error correction data to a CD/DVD (via a disc image/iso)
That's a pretty fundamental part of information theory - communication in a noisy channel. If your communications (or data storage) are digital, you can overcome any level of random noise (error) at the cost of degraded transmission rate (increased storage requirement). Before CDs, it was (and still is) most prevalent in modem protocols and hard drives. Modern hard drives would probably be impossible without it - read errors are the norm, not the exception. It's just hidden from the high-level software by multiple levels of error correction in the low-level firmware.
Data is stored linearly on a CD (and DVD). So the data can survive huge scratches running from the center to edge, but is very susceptible to radial scratches rotated around the center. If you think of a CD as an old-style phonograph record, you can scratch across the grooves and the error correction will fix it; but scratching along a groove will quickly corrupt the data because the scratch will destroy sequential data (and its ECC). That's why they recommend cleaning CDs by wiping from the center out, never in a circular motion.
Another view is that everything is a code in a noisy environment, so there is no way to talk about "the underlying device" as it itself is just another type of coding. Magnetic recording can be viewed as a way of encoding information onto the underlying (thermal) noisy matter. There is some very deep stuff happening in information theory. Let's take the empty universe as a noisy channel. Now every structure in the universe (including you and me) becomes information encoded over the empty universe. One gets the feeling that any "ultimate theory" won't be expressed in terms of forces and fields but some underlying, unifying, concept of information.
The difference is that TFA interleaves the data so it is robust against sector errors. A bad sector contains bytes from many different data blocks so each data block only loses one byte which is easy to recover from. If you use PAR and encounter a bad sector, you're SOL.
PAR was designed to solve a different problem and it solves that different problem very well but it wasn't designed to solve the problem that is addressed by TFA. Use PAR to protect against "the occasional bit error" as you suggest, but use the scheme given in TFA to protect against bad sectors.
We don't see the world as it is, we see it as we are.
-- Anais Nin
I for one welcome our Perl Overlords
Table-ized A.I.
Working for a datarecovery company, I know that about half the cases where data is lost the whole drive "disappears". So, bad sectors? You can solve that problem with reed solomon! Fine! But that doesn't replace the need for backups to help you recover from: accidental removal, fire, theft and total disk failure (and probably a few other things I can't come up with right now)... .
Dude, put the bong down.
Those who sacrifice speed for data integrity deserve neither - BF
What?
I loved my DAT (for audio) portable recorder, it employed Double-Reed-Solomon error correction, you would have to do some serious hammering to the side of the recorder to get the tape to "skip" in a way the error correction could not correct it and you'd hear it drop out, running and recording was NOT out of the question though.
Now what do the consumers have for recorders - cr*ppy, cheap, nasty, low bitrate, overcompressed MP3 recorders. The recording industry killed off an excellent (but expensive) format to palm off rubbish compressed audio to the masses. (Proper PCM recorders are no different in price to the DAT decks).
Take Nobody's Word For It.
Radial scratches go from center to edge, azimuthal scratches go around the center.