About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Tue, 28 Aug 2007

Why LDPC (and similar probabilistic) codes are not suitable for redundant storages.

Just because they operate on bits, and have probabilistic nature of the recovery process. Getting huge size of the word to be encoded and sparseness of matrix, there is a possibility to create a noise, which while being perfectly in the recovery range of the code, still can not be recovered. Fixed blocksize codes (like Reed-Solomon) are very constrained to how code was created, i.e. there is no possibility to add new checks after data was encoded, so it can not recover from errors more than level defined in encoding algorithm (like RAID5 can only recover after one erasure failover and RAID6 after two).
LDPC codes can be suitable for flow encoding of the data, which does not require guaranteed recovery (like voice data in GSM telephony), but for guaranteed recovery it must be coupled with fixed blocksize code (like Reed-Solomon or any other similar).

Another reason is that this codes are bit-based. There is no possibility to split data and checksum into bytes or other words and store them independently, and then recover if one or another set has failed, to implement this LDPC code operations must be performed over galois field GF(2^w), where 'w' is size of the elemental particle, which can be byte or word or whatever is needed. Operations over galois field of order 'w' require either O(2^w) memory overhead or system of 'w' equations to be solved, which is slow.

One can find a bit more on my implementation and tests of the LDPC codes here.

/devel/dst :: Link / Comments ()