News for hackers. Stuff that matters.
Re:Reed-Solomon coder computing one million ECC blocks at 1 ... by Tomte on Monday May 08, 2017 @12:40PM (#14293213)
I'm always confused about all those codes (RS, LDPC, Turbo etc.).

If you have the parchive use case, i.e. you want to "armor" files on disk so that you can detect and correct bit flips (including bursts), which codes are useful and which aren't?

RS obviously is (parchive, optical disks etc.). But are fountain codes usable? Low density parity codes? I have no idea how I would select a code family.

Re:Reed-Solomon coder computing one million ECC blocks at 1 ... by 112233 on Monday May 08, 2017 @12:59PM (#14293408)
Also depends on failure mode of your media. E.g. if you can lose data by 4k sectors, then it makes sense to use RS with 4k symbols instead of 8 bit (if there is such a thing...), because you do not need partial sector recovery. If you can flip separate bits, then BCH is kind of optimal. If you plan to stream, maybe some sort of FEC code, et cettera. For example, in ye olde NAND that had 512 byte pages with 16 byte OOB area per page it made sense to use BCH, because bit errors were kind of independent from each other. Bit errors in TLC NAND are not independant anymore.
Re:Reed-Solomon coder computing one million ECC blocks at 1 ... by Bulat-Ziganshin on Tuesday May 09, 2017 @05:18PM (#14303883)
when encoding larger blocks, they are just split into multiple small words. f.e when GF(256) is used, each word is just a single byte. then you have f.e. 20 data blocks and encode corresponding words of each blocks as a single group, and each group generates a single word for each of parity blocks. you may consider it just as interleaving

overall, encoding in GF(2^n) is faster when n is smaller (since you need smaller multiplication tables that better fits into cpu cache). But OTOH encoding with K data+parity blocks require that 2^n>K, so for best speed n is choosen as small as possible among 8/16/32 depending on the K value

Re:Reed-Solomon coder computing one million ECC blocks at 1 ... by 112233 on Wednesday May 10, 2017 @03:02AM (#14306380)
what I meant is that smallest unit that RS can correct is one word, which usually is byte. So 8 bit errors in one word can be restored with less EC than 8 bit errors in different words.

In case of BCH, location of bit errors does not influence error correction strength, so it is more suited to correcting independant bit errors, while RS is more suited for bursty/whole block errors.

Re:Reed-Solomon coder computing one million ECC blocks at 1 ... by Bulat-Ziganshin on Tuesday May 09, 2017 @05:01PM (#14303785)
short answer: they all are suitable. i even has (unfinished) ldpc-based program that is pretty similar to par2

long answer: what you need is Forward Error Correction, that is implemented by any Error-Correcting Code (see wikipedia for both)

Reed-Solomon and BCH error-correcting codes are known since 60s. They are pretty slow (even my fastest implemenation is about 10x slower than good LDPC one with pretty close recovery ability), but well-studied and mostly free from patents

LDPC, fountain, Raptor and so on codes were started development in 90s as faster approach to FEC. They are preferred now in commercial environment due to their speed. But since they are so useful, they are patented all around

So, one advantage of my library is that while not as fast as best codes, it's still fast enough for any practical needs and absolutely patent-free. Well, i hope so :)