Re: [Discuss-gnuradio] gr-fec LDPC comments / questions.

[Perez, Tracie R]

Hi Sylvain,

Thanks for looking at this code. I really appreciate the feedback. 
Comments/questions inline below.

~ tracie perez

On Jul 25, 2014, at 1:25 PM, Sylvain Munaut wrote:

> Hi,
> 
> 
> I've been looking at the LDPC code and I have a few comments / questions :
> 
> 1) Memory management seems to be lacking. I see only 3 calls to
> gsl_matrix_free but much more matrices being allocated and create by
> operations. Am I missing something here or is the code leaking tons of
> memory at each encode/decode ?

For the ldpc_par_chk_matrix class: There are 6 other submatrices, but they're 
submatrix views of the larger parity check matrix H. Since they're only views 
of the matrix already stored in memory, freeing the memory for H should be all 
that's necessary, if I'm understanding the GSL functions correctly. Then there 
are only 2 other matrices for which to free memory, so 3 calls total. To be 
clear - the idea is that a parity check matrix object is created, and then 
remains in memory through each encode/decode. 

For the encoder/decoder, you're totally right. I didn't free any of the 
temporary matrices. I just updated those classes with gsl_matrix_free calls.

> 
> 2) Encoder efficiency : AFAIU, the method implemented in
> ldpc_R_U_encoder_impl is meant to be efficient for real-time encoding.
> But the efficiency is derived mainly because it makes a lot of the
> operation work on sparse matrix and those can be efficiently
> multiplied. This is not exploited here at all. The gsl matrix
> multiplication is just the plain old classic algorithm for dense
> matrix and so the R_U method is probably slower than just using a
> multiplication by the generator matrix.

Yea, you are totally correct here too. The way to exploit it is to use back 
substitution in the steps to calculate the codeword, rather than regular matrix 
multiplication calls.  I need to write a routine to do this, since the GSL 
linear algebra functions don't support GF(2), as far as I can tell. This should 
be straightforward; I'm working on it now. 


> 3) Format of the H matrix and support for degenerate/ideal case :
> 
> I've been trying to trace the BER curve for the codes used in the
> GMR-1 satcom standard. I have the H matrix in numpy and saved it to
> alist using the method in the python code in the gr-fec repo.
> 
> The H matrix is of the form : [ P' | I ] already, so it's already in
> lower triangular form (actually even more than this, since it's the
> identity matrix on the right side). So I'd assume I could use this
> matrix with the code in the repo and use gap=0, but this doesn't work.
> 
> Digging a bit more in the code, I see that the code decomposes it as follows :
> 
> / T | A | B \/
> | ---+---+--- |
> \ E | C | D /
> 
> But in the paper I'm looking at (
> http://www.ldpc-codes.com/papers/encoding.pdf ) the T & E matrices are
> on the right side, which would match much better of course and
> honestly makes more sense to me since the reulting codeword often has
> the systematic bits first and then the parity bits.

I didn't reference that paper. My GSoC mentor last summer, Jens, pointed me to 
their textbook Modern Coding Theory. In the book's method, the matrix is of the 
form you see in my code (TAB/ECD). Yes, to respond to your follow-up email - 
this is why I assumed the parity part would come first when I wrote the 
decoder. 

My LDPC knowledge is still pretty limited to just these few algorithms. I agree 
that we should be consistent with whatever the community is used to, or somehow 
make it configurable. If y'all think it's best to change it to ABT/CDE form, I 
can change it, but I won't be able to get back to this for a couple of weeks.

> I don't really understand why it's like that in the code. Also, should
> the code already work with the degenerate case where g=0 (which I
> think should be pretty common if you provide a check matrix that's
> already in the "nice" [ P' | I ] form.

So now I'm sure you can see why a matrix in the form [P | I ] would not work 
with this TAB/ECD decomposition.

If this class had a more unique name, it would probably be more clear that this 
parity check matrix class is specifically for use with the R_U encoder. So, 
I've renamed it from ldpc_par_chk_mtrx to ldpc_R_U_mtrx.

I think it makes sense to have a separate FECAPI encoder variable for using a 
generator matrix in the standard form [ I | P ] (or given a parity check matrix 
in the form [P' | I ]. That has been on my to-do list to write.

For a given parity check matrix that is full rank, or can be brought to full 
rank, it can be ran through the algorithm to bring it into TAB/ECD, or ABT/CDE 
form. I could add that functionality to the python script intended to be 
executed as preprocessing step.

> 
> 
> 
> Cheers,
> 
>    Sylvain