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

LDPC iteractive decoding.

This is low-dencity parity check code iteractive decoding algorithm presentation.
Original image was 50x50 bitmap 'transferred' over gaussian (in that degree, how glibc random number generator (rand()) matches) channel, where 10% of the noise (swapped bits) were introduced. Rate of the 'transmission' is 0.5 (i.e. only half of the channel was used to transfer the data, and half for the parity bits).
Code uses hard decoding algorithm, which stops after 4 iterations, since all errors are detected. Algorithm for matrix generation (takes most of the processing time) is a bit buggy (can crash, what do you want, I spent 3 hours Sunday night to write it :), but it does not matter for this presentation.
One can find original presentation by MacKay and Neal (1995) here, where authors fully recovered 10000 bits image after 'transmission' over 7.5 % noise channel.



According to my study, LDPC codes and any other similar (let's call them 'probabilistic') codes can not be used for any reliable transfer, since probability of the error detection is never equal to one. So, for some matrix some noise can be fixed, but different noise will not. There will be matrices which will fix at least number of errors, if I understood LDPC correctly, but its generation is generally very complex (my algorithm tries to automate that a bit though), and I failed to find a precise description of the error-recovery rate (i.e. how many bits can be 100% recovered by given matrix (set of weights and word/checksum sizes)). So, for guaranteed transmission some kind of combined algoritms must be used - LDPC or any other probabilistic code to detect some errors (as much as possible) and then provide given image to fixed blocksize decoder (like Reed-Solomon), which guarantees recovery of number of bits, specified during encoding time. Such combined algorithm will behave better than any of its parts (LDPC and RS separately), since because of probabilistic nature of the LDPC code, number of errors will be detected, so that error rate becomes small enough for RS decoder.

One can find source code for LDPC encoder/decoder (code.c), image to bitmap translator (file2bit.c) and bitmap to picture viewer (gen_images.c) in archive. Last two require GTK development library.
I've also created a homepage for this project.

/devel/math/codes :: Link / Comments (0)

[:||||:]

:)

/other :: Link / Comments (0)