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

Tue, 28 Aug 2007

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)

Comments are closed for this story.