Zbr's days.

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.

LDPC iteractive decoding

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

Mon, 27 Aug 2007

LDPC code presentation.

I'm cooking up a nice LDPC code interactive decoding presentation.
It will be quite small (image is about 50x50 pixels), but I will increase pixel size on the resulted image.
Presentation (iteractive gif) will show several steps of the image after it was altered by guassian distribution of the noise.
Stay tuned, it will be ready tomorrow.

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

Wed, 22 Aug 2007

LDPC codes.

Ok, I've completed hard-decision decoding algorithm, with randomly generated matrix (if we are lucky) it can safely decode small words with multiple bits errors - for example word of 16 bit with 3-bit weight of the random matrix it is possible to decode at leat two bits of errors even if one of them is in transferred checksum itself. Unfortunately random matrix generation for larger word sizes does not work (at all). LDPC generation matrices must obey at least one rule - it must be invertible. Number of 1's in each column depends on number of 1's in each row, which is known as weight. So, to correctly decode damaged message one needs to have correct matrix, so I need to think about a good algorithm of creating it. In the regular (simpler) case, matrix has the same number of 1's in each row and column. The simplest case is wrapping sequence of bits, like this matrix with weight 3:

1 1 1 0 0 0 0 0
0 1 1 1 0 0 0 0
0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1
1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1
And so on, I will check if it works good.

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

Mon, 20 Aug 2007

Gallager codes.

Ok, I read number of papers and know kong-fu now - I understood main principles behind LDPC codes.

Main design principle is to send a redundant message over the channel, which contains a codeword and a checkword(s). The latter is created by multiplying generator matrix with a source codeword, usually it is very big (thousands of bits), but matrix is very sparse, so number of operations is not very big. Generation matrices must obey some rules, main one is that it must be invertible, otherwise one row can be selected as linear combinations of others, and thus appropriate information bit will be lost.
Decoding is quite simple - the most powerful algorithm is to use belief propagation - each check node in generation graph (or generation matrix, which is just a different representation of the same entity) sends to codeword nodes what they belief a valid bit with calculated probability, after error probabily that given bit is zero or one becomes less than requested number (according to Shannon's theorem code, which allows to reduce error probabily infinitely, always exist for given rate and communication capacity), codeword calcualtion (decoding) is completed. There are two mechanisms - hard and soft decision algos, the former is simpler, but the latter frequently is faster. Let me show an example of the hard decision algorithm (gotten from "LDPC Codes a brief Tutorial" by Bernhard M.J. Leiner, although description there is far from being perfect).
Let generation matrix to be this (not very sparse) set:

0 1 0 1 1 0 0 1
1 1 1 0 0 1 0 0
0 0 1 0 0 1 1 1
1 0 0 1 1 0 1 0
And source codeword is:
1 0 0 1 0 1 0 1
Check word, calculated my multiplication of matrix and codeword is:
0 0 0 0
Let's during transmission of the codeword and check word over the channel codeword was changed to this (secod bit changed):
1 1 0 1 0 1 0 1
Here is a generation graph (originally proposed by Tanner) of the given matrix:

LDPC generation graph

Here starts decoding algorithm, where each codeword node C first sends its bit to each check node F.
F0 node will receive 1 1 0 1 bits from C1, C3, C4 and C7 accordingly.
F1 node will receive 1 1 0 1 bits
F2 node will receive 0 1 0 1 bits
F3 node will receive 1 1 0 0 bits

Next step is to calculate the answer for each code node.
Received check word is 0 0 0 0 (calculated above), so set of simple equations starts here.
Each check node F gets three out of four received bits and XORing (summing modulo 2, since this example works in Galois finite field of power of 1 - GF(1)), and sends to the codeword node a bit it expects to be correct to satisfy received check bit.
Here is an example for first check node:
X0 ^ 1 ^ 0 ^ 1 = 0. X0 = 0
1 ^ X1 ^ 0 ^ 1 = 0. X1 = 0
1 ^ 1 ^ X2 ^ 1 = 0. X2 = 1
1 ^ 1 ^ 0 ^ X3 = 0. X3 = 0

Then we send Xi to Ci code bits. After all check nodes are processed, codeword nodes has following set of bits:
C0: 0 from F1, 1 from F3, 1 from originally received codeword.
C1: 0 from F0, 0 from F1, 1 from originally received codeword.
C2: 1 from F1, 0 from F2, 0 from originally received codeword.
C3: 0 from F0, 1 from F3, 1 from originally received codeword.
C4: 1 from F0, 0 from F3, 0 from originally received codeword.
C5: 0 from F1, 1 from F2, 1 from originally received codeword.
C6: 0 from F2, 0 from F3, 0 from originally received codeword.
C7: 1 from F0, 1 from F2, 1 from originally received codeword.

Then using the voting for each bit (i.e. which bit has more 'votes' in above table out of three cases), we get a new codeword:
1 0 0 1 0 1 0 1
The same steps then are repeated until cdeword stopped to change. In our case we get it after the first run.

Spft decision algorithm usses essentially the same logic, but it operates with probabilities of the bit to be 1 or 0, each probabilities are recalculated in each run, and after probability is higher than requested value (or error probability is less than requested value), loop stops.

Real world examples use much bigger codewords (up to several thousands of bits), but logic is always the same.

So, I've started initial userspace implementation, if stars are in the right order I will be able to complete it until move to climbing zone, otherwise I hope it to be ready tomorrow.
Stay tuned.

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

Tue, 19 Jun 2007

CRC performance depending on the word size.

To select perfect CRC coding technique which will be used for distributed storage I'm about to start designing, I've ran set of tests to determine how CRC speed depends on size of the word used in calculation. I use simple XOR CRC which just performs XOR operation over provided data block several times and then shows its performance (i.e. number of operations per timeframe).

Here is CRC performance for the same blocksize and number of iterations (i.e. number of CRC sums performed over the same block):

size: 4096, num: 100000, bits: 64, speed: 459.630646 kop/sec.
size: 4096, num: 100000, bits: 32, speed: 348.913483 kop/sec.
size: 4096, num: 100000, bits: 16, speed: 176.067184 kop/sec.
As expected, CRC speed was improved with increasing size of the word, unfortunately for galois field multiplication speed increase is not enough.
Let's discuss Reed-Solomon coding, which requires galois-field multiplication of checksummed (or raw) data words.
For 16 bit CRC sum galois filed multiplication can be performed using 2^16 table (2 lookups per multiplication or division operation) lookup, but for 32 bit CRC galois field multiplication in GF(2^32) can not be performed using table, since it will be too big. To perform galois field multiplication essentially one needs to solve a system of equations, number of equations is equal to size of the values being multiplied, i.e. 32 in our case. Even the fastest method of solving system of equations will be much much slower than 16 bit CRC plus its 2 lookups. Even using Cauchy matrixes for Reed-Solomon encoding with galois multiplication instead of Vandermonde one results in much slower code than table lookup.

So, for the maximum performance we either need to limit Reed-Solomon system to 16 bit CRC (galois field multiplication is used in RAID coding for example), or to use different coding method.
I'm studing WEAVER codes which are faster by design (and use only XOR operations without complex galois field multiplications), but they have own limits, so I'm trying to understand how distributed system with such erasure coding will suffer from using it.

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