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 https://github.com/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