[Discuss-gnuradio] LDPC in GNURadio

[Sylvain Munaut]

Hi all,


I've spent the last day trying to understand the state of LDPC
encoding / decoding in GNURadio, to see how it could be improved. I
limit myself here to gr-fec and not the application specific ldpc that
can be found in gr-dtv for instance.
Here's what I think is the current state (please, anyone that knows
better, feel free to comment):

There are two distinct implementations that have nothing to do with each other :

* ldpc_encoder_impl.cc / ldpc_decoder.cc : This implementation uses
self written matrix / vector operations that can be found in
gf2{mat,vec}.cc in the gr-fec/lib directory. The decoder
implementation is a belief propagation system AFAICT.
* ldpc_gen_mtrx_encoder_impl.cc / ldpc_par_mtrx_encoder_impl.cc /
ldpc_bit_flip_decoder_impl.cc : This implementation uses GSL for its
matrix operations and the deocder is a bit flipping decoder.

I did some very quick benchmark encoding a bunch of data. Absolute
number are meaning less, they only make sense relative to each other :

 * GSL encoder : ~ 50 s
 * GF2Mat encoder : ~ 10 s
 * GSL decoder : ~ 15 s
 * GF2Mat decoder : ~ 10 s

Keep in mind the decoder were operating on perfect input data so it's
pretty much only checking the syndrome ...

Now when looking at the actual code, both these implementation are, to
say the least, sub-optimal from a performance point of view.

I also did some quick test, trying to compare the speed of using an
optimized matrix library operating on GF(2)  (M4RI
https://bitbucket.org/malb/m4ri )  rather than the naive
re-implementation found in GNURadio.
This shows an improvement up to 10x faster when encoding a codeword
(although I can't be sure how much is due to using an optimized
library vs just doing things better in general).

My first idea was to just replace both GSL and the custom GF2{Mat,Vec}
operations by calls to M4RI. I was hoping to remove the dependency to
GSL and replacing it by M4RI. However turns out GSL is used by
gr-filter and gr-wavelet as well, so this would effectively add a new
dependency to GNURadio.

However after reading the code, I don't think this would be enough.

(1) There is no reason to have 3 different encoder blocks ...
especially since 2 of them take the same input (parity check matrix).
The third one takes the generator matrix as input, but even then, it
doesn't make sense to have a separate block with different work
function and a re-implementation of the encoding and converting the
input matrices to the matrix needed for encoding at every iteration.
(2) Using GSL is just a bad idea. Either go with M4RI, or a naive
in-tree implementation, but using a library operating on 'double' to
do binary math and then applying a mod 2 operation on every cell is
just ... weird. To be honest I'm not sure what's the best option here.
I really don't fancy re-implenting some of the matrix operations
needed to convert from parity check to generator matrices for
instance. M4RI is not optimized for sparse matrices, but it is (1)
_way_ better than GSL. (2) better, both time and memory wise than any
in-tree implementation we can make. Cost is an added dependency.
(3) Having two decoders can make sense given they operate using
different algorithm. But they should still "look similar" rather than
being clearly completely different implementation that don't even take
the same parameters to specify the LDPC code.


So my questions would be :

(1) Is cleaning up the mess worth it ?
(2) Is completely breaking the API of those blocks acceptable ?
(There is no way I'm going to bother trying to maintain API
compatibility with the previous blocks)
(3) Is adding a dependency to M4RI library to gnuradio acceptable ?
(possibly optional one, disabling LDPC if not present).

I don't want to loose my time and make work that cannot be merged, so
if the answer to any of the above is "no", then I'll just move along.
It might see "harsh", but to be honest, I can't imagine that there are
any users of the code given the state it is in ATM ...


Cheers,

     Sylvain