Zbr's days.
←August→
Sun Mon Tue Wed Thu Fri Sat
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
←2007→
Months
Jan Feb Mar
Apr May Jun
Jul AugSep
Oct Nov Dec

About TODO Blog RSS Old blog Projects Gallery Notes

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

Please solve this captcha to be allowed to post (need to reload in a minute): 15 * 16

Comments are closed for this story.