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 _______________________________________________ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio