The GSoC project on LDPC codes

Hello Everyone,

I’m Manu, one of the GSoC student under GNU Radio this year. I worked on
LDPC Codes, mentored by Jens. Another GSoC student Tracie also worked on
LDPC Codes this summer. We both worked such that there is minimum
duplicates and both our work complemented each other.

As the final output I have an Out Of Tree module gr-ldpc which
implements a
generic decoder and a generic encoder for LDPC codes. The encoder block
expects an LDPC code specified in alist[1] format. There are two decoder
blocks, one for Binary Symmetric Channel model and another for AWGN
model. The decoder implements the sum product algorithm[2]. Also two
algorithms for construction of LDPC codes have been implemented. I
a video presentation of my work to be presented at GR Con 2013, and the
presentation is available at (presentation) and (video). The gr-ldpc
module is available at GitHub - manuts/gr-ldpc. During the
project we also worked on porting the codes to fecapi, which is a
framework for developing FEC blocks. I’m yet to finish porting gr-ldpc
FECAPI framework.

Overall, GSoC 2013 was a great experience. Frankly, I was not able to
all the goals set in my proposal. I hope to fulfill all that I promised
the future. The encoder/decoder blocks have to be optimized. And in
I intend to bring more of Coding techniques into fecapi framework.

There is lot many people to whom I’m thankful for this wonderful
experience. I don’t pick any name just so that the mail is concise as
possible. I also thank the entire GNU Radio community for this

Hoping for the feedbacks on the module,

Manu T S


Hi Manu,

Thanks for the report, it was more informative than the presentation.
Yes, I have seen the BER figure, but that is not very will presented
(e.g. you should use logarithmic scale for BER) and should have better
resolution on the Eb/N0 axes. You write that it does not use VOLK or
SSE2. How fast is it? Do you have any performance number? Do you plan
to work on it in the near future?


Hi Miklos,

The implementation is quite slow. I don’t have any quantitative
measures, yet.
Nevertheless I have some empirical measures. For example, on testing the
implementation (all C++ and no GNU Radio) with a (8000, 4000) code(rate
0.5, regular), in with AWGN of 0.8 added to it (capacity 0.678),
it took about 15-20 minutes[*] on an i7 machine to transmit and decode
blocks. With smaller noise, this will be done a bit faster, for the
of decoding iterations required is less.

The major time consuming factor in the implementation is the encoder
construction. You may find the encoding method I implemented in the
It has a complexity of O((NM)^2). Once we have the encoder matrix
is done in O(K^2) time. Decoding doesn’t take that much time, but the
current space requirement is huge. I’m using a M x N matrix(double
elements) to hold the messages being passed between check nodes and
variable nodes. For the (8000, 4000) code that turns out to be some 244
Since H is sparse, most of the entries in the M x N message matrix is 0
not used.

So these are the things in my agenda for the near future.

  1. Improving the space requirement in the decoder.
  2. Find better methods(eg. Sparse LU) to implement encoder.

I will start work with VOLK after the above mentioned improvements.

[*] As I said before encoder construction took huge time. So to test the
codes, I generated the encoder matrix and saved it in a separate alist
file. This file is not generally sparse. The file size would depend on
structure of the code. For example, for the (8000, 4000) code the size
the alist file for the encoder matrix was about 64MB. The only gain here
that we need not generate the encoder matrix every time we need to use
code. We can load it from the alist file. Had I not done this, the
experiment would have taken longer.

Wow, interesting to read all about this. Thanks for all the good work.