Re: [Discuss-gnuradio] The GSoC project on LDPC codes.

[Manu T S]

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.

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

On Wed, Nov 6, 2013 at 5:47 PM, Miklos Maroti <address@hidden> wrote:

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

On Wed, Nov 6, 2013 at 5:38 AM, Manu T S <address@hidden> wrote:
> Hello Mikios
>
> Here is the link to the presentation and report I made for my
> thesis(intermediate evaluation) at IIT Bombay. Last part describes the
> results I have obtained.
> It has a BER plot as well.
>
> https://github.com/manuts/first_stage/blob/master/ppt.pdf
> https://github.com/manuts/first_stage/blob/master/report.pdf
>
> The implementation is generic, in the sense that if you input a code (in
> alist file format), we can construct the encoder and decoder.
> The decoder merely implements sum product algorithm. I have tested it
> against many regular codes, where there was the significant gap between the
> rate and the capacity. I'm yet to test it against an irregular code of large
> block length, mainly because the encoder and decoder becomes really slow.
> (Many optimizations are still in order.)
>
> I wish I could tell you I had a better BER plot, but what's there in the
> report is all I have currently.
> Thanks for checking out.
>
>
> On Tue, Nov 5, 2013 at 11:08 PM, Miklos Maroti <address@hidden>
> wrote:
>>
>> Dear Manu,
>>
>> Do you have any performance numbers on your LDPC decoder? I could not
>> find any info, even in your presentation. Do you have also a BER
>> figure, or even better would be some technical report. I would love to
>> get some sense on the performance of your implementation.
>>
>> Best,
>> Miklos
>>
>> On Tue, Nov 5, 2013 at 6:15 PM, Manu T S <address@hidden> wrote:
>> > Dear Max,
>> >
>> > You are correct. It is a bug. Now I'm wondering why I didn't get any
>> > segmentation faults.
>> >
>> > Probably I didn't get any segmentation faults because, after i = M - 1,
>> > EOF
>> > has reached.
>> >
>> > Thanks for the correction.
>> >
>> >
>> > On Tue, Nov 5, 2013 at 9:14 PM, ikjtel <address@hidden> wrote:
>> >>
>> >> Greetings
>> >>
>> >> I was very interested in this project for possible application to the
>> >> op25
>> >> project, since P25 uses several FEC codes
>> >> including RS and other block codes.  I've brought up the gr-ldpc
>> >> library
>> >> and have a few questions.  Due to the hateful YAhoo mail composer, I'm
>> >> hesitant to post lengthy emails to the general list with no opportunity
>> >> for
>> >> preview prior to hitting SEND, so I'll try breaking up the list of
>> >> questions
>> >> into several posts, one per question...
>> >>
>> >> First question: I was getting lots of errors, seg faults, aborts, and
>> >> other misbehavior from the code, which were traced to an apparent bug
>> >> in
>> >> alist.cc, all of which cleared up when I applied the following patch:
>> >>
>> >> --- ../../repo/gr-ldpc/lib/alist.cc     2013-10-18 10:25:47.508781061
>> >> -0400
>> >> +++ ./alist.cc  2013-11-05 11:21:03.879972116 -0500
>> >> @@ -123,7 +123,7 @@
>> >>      }
>> >>
>> >>      // Parse indices with non zero entries in ith row
>> >> -    for (int row = 0; row < N; row++) {
>> >> +    for (int row = 0; row < M; row++) {
>> >>          std::getline(file, line);
>> >>          ss << line;
>> >>          for (int entry = 0; entry < num_mlist[row]; entry++) {
>> >>
>> >> Can you confirm, is this really a bug?
>> >>
>> >> Thanks and Best
>> >>
>> >> Max
>> >
>> >
>> >
>> >
>> > --
>> > Manu T S
>> >
>> > _______________________________________________
>> > Discuss-gnuradio mailing list
>> > address@hidden
>> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
>> >
>
>
>
>
> --
> Manu T S

--
Manu T S