Error-Proofing Data With Reed-Solomon Codes 196
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..."
Been doing this from the past 3 decades (Score:2, Interesting)
slow news day anyone?
Re:Been doing this from the past 3 decades (Score:5, Funny)
"Awk! Parroty Error! Parroty Error! Pieces of Seven, Pieces of Seven"
(*BOOM*) never did like that bird.
Re: (Score:2)
Re: (Score:2)
LDPC based codes only work for pure erasure channels and do NOT work for static error channels. How does one perform loopy-belief propagation when the error probability distribution of the medium (in this case the disk) can not be modeled correctly?
Re: (Score:2)
if you haven't heard of loopy-belief propagation you're probably not aware of the state of the art in LDPCs, it has progressed a long way since Gallager's time rediscovered/reinvented a few times etc...
btw reaching channel capacity requires use of sparse matrices that have some very demanding properties. I believe the current direction at least for pure erasure channels (wifi, udp...) are Rateless codes or in other words Digital Fountains of which Tornado and LT style codes exist.
Re: (Score:2, Funny)
It can make files a bit hard to read, though (Score:4, Funny)
Re:It can make files a bit hard to read, though (Score:5, Insightful)
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.
Re:It can make files a bit hard to read, though (Score:5, Funny)
I for one welcome our Perl Overlords
Drives already do this (Score:4, Informative)
... at least CDROMs employ RS codes.
Re: (Score:2, Informative)
Yeah, but is there another problem elsewhere in the system? I have an el-cheapo USB-PATA adapter with a MTBF (mean time to bit flip) of about 2 hours. Every other disk was ruined, and I only knew because of a sick little obsession with par2. Disk data is ECC'd, PATA data is parity checked, and USB data is checksummed. Still, inside one little translator chip, all that can be ruined. and that's why data integrity MUST be an operating/file system service.
Yes, RS should be a file system service. (Score:4, Insightful)
I agree. I'm willing to have a small loss in speed and a small increase in price to have better data integrity.
There is already data integrity technology embedded in hard drives, and I support making it more robust.
Re:Yes, RS should be a file system service. (Score:5, Funny)
Those who sacrifice speed for data integrity deserve neither - BF
Re:Drives already do this (Score:4, Interesting)
My understanding is that it is possible to drill a few holes no larger than 2mm in diameter equally spread over the surface of an "audio cd" and with the help of h/w RS erasure decoding, channel interleaving and channel prediction (eg:probabilistically reconstruct missing right channel from known left channel) one can produce a near perfect reconstruction - that's what usually happens to overcome scratches and other kinds of simple surface defects.
Re: (Score:2)
That might be good for music where a near-lossless reconstruction is acceptable, but I'd suggest not drilling holes in your thesis paper, or any other type of data where lossy compression is unacceptable (everything except images, audio and video, basically)
Re: (Score:3, Funny)
You haven't read too many theses. There are holes all over the place...
Re:Drives already do this (Score:5, Informative)
Re:Drives already do this (Score:4, Informative)
Re:Drives already do this (Score:5, Informative)
Radial scratches go from center to edge, azimuthal scratches go around the center.
Re: (Score:2)
But not every drive/OS seems to really use it. Some anecdotal evidence:
Back in the Windows 9x days, I helped a friend of mine to reinstall Windows (98 IIRC). After copying files to the HD and restarting, the newly installed system always crashed. There was no error message that indicated there was a problem with reading the data from the CD-ROM (a Liteon which was known to be a bit dodgy).
We finally tried another drive and it worked on the first try. I conclude that there were unreported errors reading from
Yes, but not all... (Score:2)
.. at least CDROMs employ RS codes.
RS codes are good at corecting randomly scattered bit errors. The error mode in CDs is missing chunks (eg scrathces). So, they use a mechanism which scatters bits around. When a scratch (correlated errors) is descattered, they become randoml sacttered errors, so the RS codes can do their job.
Re:Drives already do this (Score:5, Informative)
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.
Re:Drives already do this (Score:5, Interesting)
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.
Re:Drives already do this (Score:5, Informative)
Re:Drives already do this (Score:5, Interesting)
Re:Drives already do this (Score:5, Funny)
Dude, put the bong down.
Re:Drives already do this (Score:4, Funny)
Other valid replies would have been "I'll have what he's having" or "Pass it around, please".
Re: (Score:2)
Don't bogart that joint!
Re: (Score:2)
You should read http://www.hpcoders.com.au/theory-of-nothing.pdf [hpcoders.com.au]
Re: (Score:3, Interesting)
Re:Drives already do this (Score:5, Interesting)
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).
Re: (Score:3, Insightful)
Thing is, the "overcompressed" MP3 recorders are good enough. Most people use them to record lecture notes, or a meeting, or just talking to themselves. Those are about the only reasons to really need a portable recorder, and for those uses, mp3 is very good. Just because it's low bitrate doesn't mean it's bad, and just because your DAT recorder had higher quality doesn't mean it's more fit for the purposes it would be used for. Seriously... running and recording? Why would you ever want to do that?
Re: (Score:2)
ZFS? (Score:3, Interesting)
Uh, is this not one of the main features of the ZFS file system? It does a checksum on every block written and will reconstruct the data if an error is found? (assuming you are using either raid-z or mirroring. Otherwise it will just tell you that you had an error).
Re:ZFS? (Score:5, Informative)
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.
Re: (Score:2)
Re: (Score:2)
Not really, but if you enable copies=2 ZFS will replicate all data on a single disk.
As I understand it... (Score:2)
ZFS checksums are actually hashes, as in "cryptographic hash", so they're pretty damn reliable (though theoretically 100% reliable) at detecting errors.
Re: (Score:3, Interesting)
From what I've read and heard, ZFS is designed to pretty much be the last filesystem we'll ever need. I'm pretty sure they've considered hash collisions with regards to data integrity.
Also consider that you probably won't need to reconstruct the entire sector, but only a few bits from it. If there was some sort of insane scenario where you had to reconstruct a complete 1GB block from a single MD5 hash... (ie, "here's an MD5 hash. Give me a sequence of 1073741824 bytes to make it") well it's technically p
Re: (Score:3, Insightful)
Re: (Score:2)
Well at a 1GB target size, I'm sure you'll encounter a number of hash collisions. But of all of the n arbitrary streams of bits that will hash down to whatever, I'd be very surprised to find more than one that would actually result in files that any software could open. Even if you had a hundred to pick from, you're in a situation where a human can figure out the rest (or be treated to some very unusual porn).
That's not entirely unlike the decentralized tracker system Bit-torrent clients have implement of
Re:As I understand it... (Score:4, Insightful)
You're asking the wrong question.
The right question is: Given a 1Gb file, how much "mutation" do you have to do to it to produce a file with the same hash? And the answer to that is: Enough to make the data unrecoverable no matter what you do.
Re: (Score:2)
That's not really true though. While unlikely, it is *possible* that a hash collision occurs on two inputs that vary only by one bit. In most cases we expect a one-bit change in the input to upset about 50% of the bits in the has output, but that's certainly not true for every possible pair of inputs. Checksums are useful for detecting most small errors, but redundant storage and comprehensive bit-by-bit comparison is the only way to be absolutely sure, and that's generally considered too expensive for use
Re: (Score:2)
That is correct, there is always the possibility that the data can still be viable after a large number of bit flips, and that a problem nonetheless
Re: (Score:2)
OK, so for a 256-bit hash, you need 2^255 bit flips to replicate the hash. You'd be flipping bits on the hash itself before that happened.
Incidentally, if we flip enough bits on my hard drive, there is the possibility that I could end up with the contents of your hard drive, via the infinite monkeys principle.
Re: (Score:2)
heard of the birthday paradox? don't need that much memory to come up with a collision, in fact most MD hash attacks are based on that principle.
I see... (Score:2)
That'll teach me to leave out a "not". Of course, I meant "theoretically NOT 100% reliable". :)
The odds of collisions against a given fixed hash (which a hash for a data block is) of course depend on the method, but they are miniscule -- probably less than random bits flips on the bus or in RAM. Has anyone even ever found a single example of a SHA256 collision?
Even so, you can *NEVER* be absolutely 100% sure that the data is what you wrote. Even a two-way RAID1 doesn't get you there since you could (theoret
Re:ZFS? (Score:4, Informative)
I have been a ZFS user for a while and know a lot of its internals. Let me comment on what you said.
Not in ZFS. When the checksum reveals silent data corruption, ZFS attempts to self-heal itself by rewriting the sector with a known good copy. Self-healing is possible if you are using mirroring, raidz (single parity), raidz2 (dual parity), or even a single disk (provided the copies=2 filesystem attribute is set). The self-healing algorithm in the raidz and raidz2 cases is actually interesting as it is based on combinatorial reconstruction: ZFS makes a series of guesses as to which drive(s) returned bad data, it reconstructs the data block from the other drives, and then validates whether this guess was correct or not by verifying the checksum.
All the ZFS checksumming algorithms (fletcher2, fletcher4, SHA-256) generate 256-bit checksums. The default is fletcher2 and offers very good error detection (even errors affecting more than 256 bits of data) assuming unintentional data corruption (the fletcher family are not a cryptographic hash algorithms, it is actually possible to intentionally find collisions). SHA-256 is collision-resistant therefore it will in practice detect all data corruptions. It would be computationally infeasible to come up with a corrupted data block that still matches the SHA-256 checksum.
A good intro to the ZFS capabilities are these slides [opensolaris.org]
Re: (Score:2)
Re: (Score:2)
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.
Having both, however, can be useful. For example, you can arrange your data in a rectangle and use standard error detecting checksums along the rows and RS on the columns. Knowing that particular rows may have an error can effectively double the error correction rate of Reed Solomon. See Erasure [wikipedia.org]
Re: (Score:3, Informative)
Mirroring is RAID-1, not 0.
Re: (Score:2)
Interesting (Score:2)
I've been burned by scratched DVD+Rs too many times. I'd be interested if there were a way to do this kind of thing in Windows..
Re: (Score:2)
The WinRAR archiver has an optional recovery record which protects against bad blocks.
When you create an archive just specify the amount of protection you require (in practice 3% has served me well).
Re: (Score:2)
I believe the underlying code used in RAR for the recovery record is in fact an RS(255,249) codes
Re: (Score:3, Informative)
The cross platform program dvdisaster [dvdisaster.net] will add extra information to your DVD as an error correcting code. Alternatively, you can make a parity file for an already-existing DVD and save it somewhere else.
It actually has a GUI too, so it must be user friendly.
Re: (Score:2)
Bit-torrent?
No seriously. I don't know a whole lot about network infrastructure (nor do I care, strictly speaking), but there's clearly some sort of error-checking/correcting going on behind the scenes as I'll grab huge disk images that pass verification before they get mounted (ex. iPhone SDK ~ 1.2GB) all the time. Some sort of network-based solution is really ideal for data transfer.
Of course with residential upload speeds it's often slower than the ol' sneakernet (depends where it's going, how it's get
Re: (Score:2)
It is possible for a well designed h/w decoder to detect the loss of laser tracking and from there signal the decoder that the current bit or byte read-in is an erasure (ie: it is erroneous, the position is known but the amount of error, meaning the difference from what the decoder gets and what it really should be is unknown) - this is known as side-channel information.
In these cases the decoder is capable of decoding mixtures of errors and erasures. In an "all erasure" decoding scenario and decoder should
Harden Files (Score:3, Funny)
When he said "harden files", I thought he was going into a long soliloquy on all the porn on his computer, so I went to the next story.
Never underestimate the redunancy... (Score:3, Interesting)
Look, if it's secret, one copy is too many. For everything else, gmail it to five separate recipients. It's not like Google has ever lost any of the millions of emails I've received to date. (This is not a complaint -- they don't show me the spam unless I ask for it).
And if they ever did lose an email, well, to paraphrase an old Doritos commercial, "They'll make more."
Seriously, personally I view the the persistence of data as a problem. It's harder to let go of than it is to keep.
Speed? (Score:4, Interesting)
My question is of speed; this seems a promising addition to anyone's back up routine. However, most folks I know have 100s of gigs of data to back up. While differentials could be involved, right now tar'ing to tape works fast enough taht the backup is done before the first staff shows up for work.
I assume we're beating the hell out of the processor here; so I'm wondering how painful is this in terms of speed?
Re: (Score:3, Informative)
Well since my $100 Radio Shack CD [wikipedia.org] player I bought in 1990 could do it in real-time I'm guessing that the requirements are pretty low. In fact a lot of hardware already uses it.
If you read the rest of the page you find out it's very ingenious and efficient at doing what it does.
While it's certainly not new (it's from 1960) or unused (hell, my phone uses it to read QR codes) I'm sure its something that has been under the radar of a lot of Slashdot readers, so I'll avoid making a "slow news day" snark.
Re:Speed? (Score:5, Interesting)
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
Version control != backups (Score:3, Insightful)
Re: (Score:3, Insightful)
Well, you shouldn't commit until you believe you have it in a state where the changes are usable (i.e. don't break the tree), but beyond that, I'd rather see more commits of smaller amounts of code than giant commits that change ten thousand things. If you end up having to back out a change, it's much easier if you can easily isolate that change to a single commit. My rule is commit early, commit often. I'm not the only one, either:
http://blog.red-bean.com/sussman/?p=96 [red-bean.com]
Re:Version control != backups (Score:4, Insightful)
The best solution is for developers to use their own private branches. Then they can commit as much as they want, and integrate into the main branch when they're ready. Unfortunately subversion has crappy support for integration (even with version 1.5 AFAICT) compared to something like perforce.
This is not very useful for changing data... (Score:2)
This might be useful for archived files, but not something you change on a regular basis.
I wish PAR2 would have kept improving... (Score:2)
Yes, CDs and DVDs have error correction built in, but they don't do much if you happen to a nice scratch that follows the spin of the disk. I.e. a moderate scratch from the outside to the inside of a CD is reasonably OK for data, but a scratch the other way will kill your data much more easily.
For a while I was using PAR2, yes, the PAR2 used on USENET, to beef up the safety of my DVD backups of my home data. Unfortunately, PAR2 never really evolved to handle subdirectories properly, which mattered when I
Re: (Score:3, Informative)
Unfortunately this software looks like it is closed source and windows only. A program to apply error correcting codes to your archived files is only useful if you still have a platform to run it on. Hopefully 15 years from now when you go to recover your files y
Re: (Score:2, Insightful)
Agreeing with Fnord666, the software does not use an open algorithm. The general tone of the site is "use this software it is awesome, don't argue". There d
Or you could just use PAR... (Score:3, Interesting)
TFA introduces some new ".shielded" file format. But do we need yet another file format when PAR (Parchive) [wikipedia.org] has been doing the same job for years now? The PAR2 format is standardized and well-supported cross-platform, and might just have a future even IF you believe that Usenet is dying [slashdot.org]...
I always thought it would be cool to have a script that:
With a system like this, you wouldn't have to worry about throwing away old backups for fear that some random bit error might have crept into your newer backups. Also, if you back up the PAR2 files together with your data, as your backup media gradually degrades with time, you could rescue the data and move it to new media before it was too late.
Of course, at the filesystem level there is always error correction, but having experienced the occasional bit error, I'd like the extra security that having a PAR2 file around would provide. Also, filesystem-level error correction tends to happen silently and not give you any warning until it fails and your data is gone. So a user-level, user-adjustable redundancy feature that's portable across filesystems and uses a standard file format like PAR would be really useful.
This is not the same thing as PAR ... (Score:5, Informative)
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.
PAR2, anyone? (Score:2)
Doesn't par2 already employ reed-solomon? (http://en.wikipedia.org/wiki/Parchive [wikipedia.org])
And it has all sorts of options let you configure the amount of redundancy you'd like?
And it has (ahem) been very well tested in the recovery of incomplete binary archives ... ?
Now that usenet has been stripped of binaries, we'll have to find other uses for these tools ....
what about quickpar and dvdisaster? (Score:5, Informative)
quickpar [quickpar.org.uk] especially has been in use on usenet/newsgroups for years....o yea...forgot....they are trying to kill it.
anyways...there's also dvdisaster [dvdisaster.net] 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)
Why IS storage quality going down? (Score:2)
I'm glad it's not just me thinking my drives are dying sooner than they once did.
Why is storage quality going down, and what does that mean for that 1TB drive for $200 bucks? Will it's lifespan exceed two years?
Re: (Score:2)
Because everybody uses desktop quality SATA drives in enterprise RAIDs. And every vendor pushes density in desktop drives as hard as possible even though it's been getting more and more difficult.
The market for high end "enterprise" drives is almost dead. When was the last time you saw a SCSI (FC,SAS) drive?
There's nothing wrong with the basic approach but you have to do the math and use the correct AFR and TTR numbers. We just went from RAID 5 to RAID 6 because the observed drive failure rates were higher
Re: (Score:2)
The market for high end "enterprise" drives is almost dead. When was the last time you saw a SCSI (FC,SAS) drive?
I can look over my shoulder at approximately 45 FC drives, 60-70 Ultra320 SCSI Drives, and another dozen or two SAS drives. That's just from my little window into the server room.
Enterprise class drives are far from dead. Unless, of course, you just can't afford them.
uhhm, raid6? (Score:2)
RAID6 [wikipedia.org] uses Reed-Solomon error correction. In fact, RAID5 can be viewed as a special case of RAID6.
This thing looks like a solution in search of a problem. Slow news day?
Is this step really necessary? (Score:2)
Yes, this has been done forever etc. but has anyone experienced any ugly "bit rot"? I mean, I've had firewalls that would checksum applications and if it ever complained about surprise changes I didn't catch it. Equally I have about 100GB for which I have CSVs - no spontanious corruption to note. Source code should very easily fail to compile if a random bit was flipped, also can't think of any case. I guess if it's that important having a PAR file with some recovery data won't hurt but first you I'd take R
Information Theory 101 (Score:2)
Channel noise can be overcome via increased redundancy in transmission/storage, thereby reducing the effective transfer rate/storage density. Film at 11.
I could be wrong, but I'm pretty sure this is why we have on-disk (and on-bus) checksums and ECC RAM. And frankly if your mission-critical data is being ruined by DVD scratches, adding RS codes to your DVDs is probably not going to solve the fundamental problem of system administrator incompetence.
/ Seriously, these days Fark has more technically competent
Datarecovery "data". (Score:5, Insightful)
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)... .
Re: (Score:2)
user interface proble (Score:2)
I'm sorry, but this is stupid. Error correction is done at the level of the disk controller. You gain nothing by re-doing it at the level of the file system. You only get file-system level errors when you don't pay attention to the disk controller telling you that the disk is going bad and wait for the disk to degrade to the point where errors can't be corrected anymore.
Install one of the many utilities that monitor disk health and replace your disk when they tell you there's a problem with your disk.
VDM FEC (Score:2)
Re: (Score:2)
Re: (Score:2)
I'm still waiting for the 5 year warranty to expire on my hard drives.
huh??? (Score:3, Insightful)
I have been around this industry quite a while, and I call bullshit on that.
Re: (Score:2)
Fine we are all dumb, now tell me what happens when the errors on the disk are spread over all the files and the par2 equally to the extent at which the drive wont even send data back - what does one do then? how do you tell the drive about the par fec?
its best to spread data equally over multiple devices as if one device was to totally fail you could still get something back (reconstruct) from the other devices.
Re: (Score:2, Informative)
I do the same as the AC, but I keep a copy of the smallest par2 from the set on my local drive for recovery (and back these up as well). If a CD/DVD ever goes bad to the point it won't even read the FS, you can still create an ISO file of it including all errors. The par2 recovery can be done using the ISO image at that point, and as long as the damage to the DVD didn't exceed the redundancy level, full recovery of the original files is possible.
Note that you aren't recovering the ISO itself at this point
Re: (Score:2)
I hope you are joking. PAR2 is nothing more than an implementation of RS codes. So how can RS codes be ancient compared to PAR2?
From the PAR2 specification introduction [sourceforge.net]:
"The redundant data in the PAR files is computed using Reed-Solomon codes. These codes can take a set of equal-sized blocks of data and produce a number of same-sized recovery blocks. Then, given a subset of original data blocks and some recovery block, it is possible to reproduce the original data blocks. Reed-Solomon codes can do this reco
I don't want to spend time making Par2 files. (Score:2)
Par2 is apparently Reed-Solomon [wikipedia.org] done in a more helpful way.
Quote from the Parity Volume Set Specification 2.0 [sourceforge.net]: "PAR 2.0 uses a 16-bit Reed-Solomon code and can support 32768 blocks."
Re:You are all dumb as there is only one way. (Score:4, Interesting)
Reed-Solomon is ancient compared to par2.
No, you're dumb. Par2 IS Reed-Solomon. Silly me to expect an AC to fact-check the most trivial subjects of a post.
The procedure explained in TFA is basically adapting a different tool to behave more or less like single-file par2. That makes it redundant (in the /. sense, not the data-recovery sense).
There is one thing I would love to see, and that's local disk checksumming. That's right, take a 500gb disk, chop it into slices and do RAID-5 on them as if they were individual spindles. It's been years since I've had a hard drive actually die on me, but I've seen bit-errors more often than I'd like. Having self-checking built into the filesystem (or low-level disk access) would help ensure 100% data integrity, and you could still do RAID-1 on top of it for safety.
Re: (Score:2)
About the bit errors...
Hard drives themselves already do extensive error correction and checksumming of all their blocks, which led me to believe that any bit errors are not from the hard drives themselves (since the checksum would fail then and it would be flagged as a read error). It's therefore extremely unlikely that a hard drive returns you data with a bit error in it, unless of course it already had this error when the block was written.
I used to have problems on an older system where copying 100 GB
Re: (Score:2)
The problem with par2 and dvdisaster is that they're not ubiquitous or, apparently, interesting enough to developers.
What is needed is something *like* par2, but that works over directory trees, generally fits in well with the the other unix tools, and is as ubiquitous as dd, tar, cp and gzip.
What good is including ECC with your data if the tools that can be used to recover it lost interest and withered away half a decade after you burned it?
Further, the "best" way would be to extend the CD spec to arbitrar
Re: (Score:2)
RS codes are a subset of BCH codes, if anything is far superior it would be RS codes as they are more generalized and have better specific decoding techniques and can be both systematic and linear.
Again as mentioned before LDPCs are not useful in these situations they are only useful in overcoming erasures within data communications.
Re: (Score:2)
Again as mentioned before LDPCs are not useful in these situations they are only useful in overcoming erasures within data communications.
Why aren't erasure codes any good here? What errors are we trying to recover from?
Don't we have known bad sectors from the disk?
I don't know if, when you get a bad sector the drive returns nothing or whether the drive can be told to return its best guess so I can see it might depend whether your code word is a sector or something smaller.
Tim.
they're good for different things (Score:2)
BCH is good for correcting large numbers of small errors. RS is good for correcting "bursty" errors.
You want to use BCH in media where bits bear no relation to each other, like in NAND where a cell contains only 1 or 2 bits, and adjacent cells are unaffected.
RS is better on things like hard drives where a flaw in the media is likely to produce longer runs of errors in a row. Two sequential bits on a hard drive are interdependent.
Also, the whole article is dumb. First, hard drives don't appear to be getting
Re: (Score:3, Informative)
Your comment is incorrect, RS codes are a subset of BCH codes. In fact BCH codes are a general definition of a class of algebraic codes nothing more. your comment about one being better than the other for a specific purpose is wrong.
Think of BCH codes as "vehicle" and RS codes as "The Bugatti Veyron" that is the relationship.
Re: (Score:2)
pretty much all 2D barcodes use RS codes as well. These include, QRcode, PostBar, MaxiCode, DataMatrix etc...
Re: (Score:2)
Read the article: after adding the parity information, the data is interleaved every 512 bytes to withstand losing whole sectors.