|
|
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 ()
|