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
Channel
model. The decoder implements the sum product algorithm[2]. Also two
algorithms for construction of LDPC codes have been implemented. I
prepared
a video presentation of my work to be presented at GR Con 2013, and the
presentation is available at
http://home.iitb.ac.in/~manu.ts/presentation.pdf (presentation) and
http://home.iitb.ac.in/~manu.ts/presentation.ogv (video). The gr-ldpc
OOT
module is available at GitHub - manuts/gr-ldpc. During the
project we also worked on porting the codes to fecapi, which is a
wonderful
framework for developing FEC blocks. I’m yet to finish porting gr-ldpc
to
FECAPI framework.
Overall, GSoC 2013 was a great experience. Frankly, I was not able to
meet
all the goals set in my proposal. I hope to fulfill all that I promised
in
the future. The encoder/decoder blocks have to be optimized. And in
future
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
opportunity.
Hoping for the feedbacks on the module,
–
Manu T S
[1] http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html
[2] http://www.cs.toronto.edu/~radford/ftp/LDPC-2012-02-11/decoding.html
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?
Miklos
Hi Miklos,
The implementation is quite slow. I don’t have any quantitative
performance
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
100
blocks. With smaller noise, this will be done a bit faster, for the
number
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
report.
It has a complexity of O((NM)^2). Once we have the encoder matrix
encoding
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
MB.
Since H is sparse, most of the entries in the M x N message matrix is 0
and
not used.
So these are the things in my agenda for the near future.
- Improving the space requirement in the decoder.
- 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
the
structure of the code. For example, for the (8000, 4000) code the size
of
the alist file for the encoder matrix was about 64MB. The only gain here
is
that we need not generate the encoder matrix every time we need to use
this
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.
Miklos