[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Discuss-gnuradio] gr-fec LDPC comments / questions.
From: |
Perez, Tracie R |
Subject: |
Re: [Discuss-gnuradio] gr-fec LDPC comments / questions. |
Date: |
Sun, 27 Jul 2014 19:03:23 +0000 |
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