Re: [Discuss-gnuradio] gr-fec LDPC comments / questions.
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
Re: [Discuss-gnuradio] gr-fec LDPC comments / questions.
Hi, 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. Ok good. Whenever we move to a more efficient implementation that doesn't use GSL for GF2 operation, it would probably make sense to have those pre-allocated to avoid alloc/free cycles. 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. Yes, OK, it probably make sense to have another matrix class for the R_U encoder and then have another encoder and matrix class for the [ I | P ] case. For that latter case, it can just copy the systematic bit, then use a sparse multiply by P to get the parity bits. However for the decoder that really shouldn't matter and the same code should handle both. You should just be able to give it the matrix and it should only use it to compute the syndrome and that's it. The only change to the decoder is that it should be able to handle both case where the systematic bits are at the front or at the back. So I guess both those matrix classes should inherit a common base that can just return the H() matrix itself for the decoder. The matrix H() doesn't fully define the code tough. You need to separately specify which ones are the systematic bits. 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. Yes, you can but that takes _forever_ to precompute and shouldn't really be necessary. In the DVB and GMR code, P is sparse so I don't really see the point of using the R_U method in that case at all and the decoder should be able to cope with it no problem. Cheers, Sylvain ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
Re: [Discuss-gnuradio] gr-fec LDPC comments / questions.
Hi Again,
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.
Digging through the decoder I also found this assumption that the
codewords are provided with the parity bits first, then the systematic
bits :
for (index = 0; index d_frame_size; index++) {
unsigned int i = index + n - d_frame_size; /* HERE */
int value = gsl_matrix_get(x, i, 0);
out[index] = value;
}
All the codes I know (granted it's only GMR and DVB) use the opposite
convention, so I think he'd be wise to either flip the convention in
the GR code, or make it configurable.
Do you know of any LDPC codes in common application where the parity
bits are placed/sent first ?
Cheers,
Sylvain
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
[Discuss-gnuradio] gr-fec LDPC comments / questions.
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 ? 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. 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 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. Cheers, Sylvain ___ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
