# Gr-fec LDPC comments / questions

**URL:** <https://www.ruby-forum.com/t/gr-fec-ldpc-comments-questions/231184>\
**Category:** GNU Radio\
**Created:** [July 25, 2014, 8:26pm UTC](https://www.ruby-forum.com/t/gr-fec-ldpc-comments-questions/231184 "2014-07-25T20:26:16Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![addis\_a](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/c4cdca/32.png) [@addis\_a](https://www.ruby-forum.com/u/addis_a)\
**Post date:** [July 25, 2014, 8:26pm UTC](https://www.ruby-forum.com/t/gr-fec-ldpc-comments-questions/231184/1 "2014-07-25T20:26:16Z")

</div>

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](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

```

---

<div class="post-metadata">

**Author:** ![Sylvain\_M](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/839c29/32.png) [@Sylvain\_M](https://www.ruby-forum.com/u/Sylvain_M)\
**Post date:** [July 26, 2014, 2:44pm UTC](https://www.ruby-forum.com/t/gr-fec-ldpc-comments-questions/231184/2 "2014-07-26T14:44:13Z")

</div>

Hi Again,

> But in the paper I’m looking at (  
> [http://www.ldpc-codes.com/papers/encoding.pdf](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

---

<div class="post-metadata">

**Author:** ![Sylvain\_M](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/839c29/32.png) [@Sylvain\_M](https://www.ruby-forum.com/u/Sylvain_M)\
**Post date:** [July 27, 2014, 9:05pm UTC](https://www.ruby-forum.com/t/gr-fec-ldpc-comments-questions/231184/3 "2014-07-27T21:05:08Z")

</div>

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 M. 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.

> 1. 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.

> 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.

---

<div class="post-metadata">

**Author:** ![Sylvain\_M](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/839c29/32.png) [@Sylvain\_M](https://www.ruby-forum.com/u/Sylvain_M)\
**Post date:** [July 27, 2014, 10:23pm UTC](https://www.ruby-forum.com/t/gr-fec-ldpc-comments-questions/231184/4 "2014-07-27T22:23:13Z")

</div>

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