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

[Miklos Maroti]

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

On Wed, Nov 6, 2013 at 3:17 PM, Manu T S <address@hidden> wrote:
> 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