Re: [Discuss-gnuradio] On the convolutional code performance of gr-ieee802-11

[Jeon]

Thank you all of you who have answered to my questions.
I am sorry for anwering too late.

I'll try as many solutions as you suggested
and will let you know how I will have implemented it.

Regards,
Jeon.

2015-09-22 23:31 GMT+09:00 Jan Krämer :

> Hi all,
>
> my repo is here https://github.com/SpectreJan.
> Though the decoder that I presented last year at GRCON is not in
> there...long and shitty story. There is an optimized version of the
> gr-trellis decoder in gr-celec. You have to clone gr-celec and volk-fec
> from my repo. Then build volk-fec and then gr-celec. I renewed my fork of
> GNURadio and am starting implementing a generic version of cc_decoder that
> is cc_encoder compatible but to be honest, work is pretty slow.
>
> cheers and happy hacking,
> Jan
>
> 2015-09-22 15:24 GMT+02:00 Tom Rondeau :
>
>> On Tue, Sep 22, 2015 at 1:52 AM, Jeon  wrote:
>>
>>> Thanks for your answers, Ron and Marcus.
>>>
>>> I posted this question since my module is using both Reed Solomon (
>>> https://github.com/pjkundert/ezpwd-reed-solomon) and Convolutional Code
>>> (IT++).
>>> And I saw that CC is extremely slower than RS. Thus, I posted this
>>> question, but I made a question too short and lack some information.
>>> (Of course, this is because mechanism of RS is much much simpler than
>>> that of CC.
>>> Or it could be because ezpwd RS which I am using is optimized well, but
>>> IT++ CC is not.)
>>>
>>> To improve my OOT's performance, thus, I need to replace IT++ with other
>>> some heavily optimized library or module.
>>> I remember that...one of gr-fec, gr-dtv, gr-trellis can do this for me.
>>>
>>> Now I wonder which gr module supports some arbitrary polynomials and
>>> code rate.
>>> Specifically, I want one of three set of polynomials:
>>>
>>> - Polynomial 1 (g0 = 133, g1 = 171, g2 = 165)
>>> - Polynomial 2 (g0 = 131, g1 = 145, g2 = 133)
>>> - Polynomial 3 (g0 = 131, g1 = 171, g2 = 133)
>>>
>>> (Common: Code rate 1/4, 2/3 and 1/3, where 1/4 = repeat of code rate 1/2)
>>>
>>> The reason that I try to implement one of three is,
>>> document describing specification has some wrong points.
>>> Text says polynomial 1, but figure shows polynomial 2.
>>>
>>> One thing is hopeful:
>>>
>>> I think that polynomial 3 seems a sort of widely used one
>>> and that it has been already implemented by someone in GNU Radio,
>>> which has been heavily optimized... I hope...
>>>
>>> (While I am writing this, I've checked that gr-fec can do CC with
>>> arbitrary polynomials.
>>> gnuradio/gr-fec/examples/fecapi_cc_decodres.grc
>>> I still don't know optimization.)
>>>
>>> I will keep looking into those gr-fec, dtv, trellis modules.
>>> If someone have suggestions, I will appreciate it.
>>>
>>> Thanks a lot.
>>>
>>> Regards,
>>> Jeon.
>>>
>>
>>
>> Jeon,
>>
>> No, as the docs say, this block is only designed to handle rate 1/2, K=7
>> codes:
>> http://gnuradio.org/doc/doxygen/classgr_1_1fec_1_1code_1_1cc__decoder.html
>>
>> We had some work done for GSoC last year to improve the speed of the
>> Viterbi algorithm for other cases, but we have not yet merged that into the
>> code. This was Jan Kramer's work, though I'm having trouble finding a link
>> to his repo.
>>
>> Tom
>>
>>
>>
>>
>> ___
>> Discuss-gnuradio mailing list
>> Discuss-gnuradio@gnu.org
>> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
>>
>>
>
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] On the convolutional code performance of gr-ieee802-11

[Ron Economos]

The polynomial in gr-dtv is G1 = 171 and G2 = 133. It is a 1/2 rate code 
with puncturing to 2/3, 3/4, 5/6 and 7/8.


Ron

On 09/21/2015 10:52 PM, Jeon wrote:

Thanks for your answers, Ron and Marcus.

I posted this question since my module is using both Reed Solomon 
(https://github.com/pjkundert/ezpwd-reed-solomon) and Convolutional 
Code (IT++).
And I saw that CC is extremely slower than RS. Thus, I posted this 
question, but I made a question too short and lack some information.
(Of course, this is because mechanism of RS is much much simpler than 
that of CC.
Or it could be because ezpwd RS which I am using is optimized well, 
but IT++ CC is not.)


To improve my OOT's performance, thus, I need to replace IT++ with 
other some heavily optimized library or module.

I remember that...one of gr-fec, gr-dtv, gr-trellis can do this for me.

Now I wonder which gr module supports some arbitrary polynomials and 
code rate.

Specifically, I want one of three set of polynomials:

- Polynomial 1 (g0 = 133, g1 = 171, g2 = 165)
- Polynomial 2 (g0 = 131, g1 = 145, g2 = 133)
- Polynomial 3 (g0 = 131, g1 = 171, g2 = 133)

(Common: Code rate 1/4, 2/3 and 1/3, where 1/4 = repeat of code rate 1/2)

The reason that I try to implement one of three is,
document describing specification has some wrong points.
Text says polynomial 1, but figure shows polynomial 2.

One thing is hopeful:

I think that polynomial 3 seems a sort of widely used one
and that it has been already implemented by someone in GNU Radio,
which has been heavily optimized... I hope...

(While I am writing this, I've checked that gr-fec can do CC with 
arbitrary polynomials.

gnuradio/gr-fec/examples/fecapi_cc_decodres.grc
I still don't know optimization.)

I will keep looking into those gr-fec, dtv, trellis modules.
If someone have suggestions, I will appreciate it.

Thanks a lot.

Regards,
Jeon.





___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] On the convolutional code performance of gr-ieee802-11

[Tom Rondeau]

On Tue, Sep 22, 2015 at 1:52 AM, Jeon  wrote:

> Thanks for your answers, Ron and Marcus.
>
> I posted this question since my module is using both Reed Solomon (
> https://github.com/pjkundert/ezpwd-reed-solomon) and Convolutional Code
> (IT++).
> And I saw that CC is extremely slower than RS. Thus, I posted this
> question, but I made a question too short and lack some information.
> (Of course, this is because mechanism of RS is much much simpler than that
> of CC.
> Or it could be because ezpwd RS which I am using is optimized well, but
> IT++ CC is not.)
>
> To improve my OOT's performance, thus, I need to replace IT++ with other
> some heavily optimized library or module.
> I remember that...one of gr-fec, gr-dtv, gr-trellis can do this for me.
>
> Now I wonder which gr module supports some arbitrary polynomials and code
> rate.
> Specifically, I want one of three set of polynomials:
>
> - Polynomial 1 (g0 = 133, g1 = 171, g2 = 165)
> - Polynomial 2 (g0 = 131, g1 = 145, g2 = 133)
> - Polynomial 3 (g0 = 131, g1 = 171, g2 = 133)
>
> (Common: Code rate 1/4, 2/3 and 1/3, where 1/4 = repeat of code rate 1/2)
>
> The reason that I try to implement one of three is,
> document describing specification has some wrong points.
> Text says polynomial 1, but figure shows polynomial 2.
>
> One thing is hopeful:
>
> I think that polynomial 3 seems a sort of widely used one
> and that it has been already implemented by someone in GNU Radio,
> which has been heavily optimized... I hope...
>
> (While I am writing this, I've checked that gr-fec can do CC with
> arbitrary polynomials.
> gnuradio/gr-fec/examples/fecapi_cc_decodres.grc
> I still don't know optimization.)
>
> I will keep looking into those gr-fec, dtv, trellis modules.
> If someone have suggestions, I will appreciate it.
>
> Thanks a lot.
>
> Regards,
> Jeon.
>


Jeon,

No, as the docs say, this block is only designed to handle rate 1/2, K=7
codes:
http://gnuradio.org/doc/doxygen/classgr_1_1fec_1_1code_1_1cc__decoder.html

We had some work done for GSoC last year to improve the speed of the
Viterbi algorithm for other cases, but we have not yet merged that into the
code. This was Jan Kramer's work, though I'm having trouble finding a link
to his repo.

Tom
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] On the convolutional code performance of gr-ieee802-11

[Jeon]

Thanks for your answers, Ron and Marcus.

I posted this question since my module is using both Reed Solomon (
https://github.com/pjkundert/ezpwd-reed-solomon) and Convolutional Code
(IT++).
And I saw that CC is extremely slower than RS. Thus, I posted this
question, but I made a question too short and lack some information.
(Of course, this is because mechanism of RS is much much simpler than that
of CC.
Or it could be because ezpwd RS which I am using is optimized well, but
IT++ CC is not.)

To improve my OOT's performance, thus, I need to replace IT++ with other
some heavily optimized library or module.
I remember that...one of gr-fec, gr-dtv, gr-trellis can do this for me.

Now I wonder which gr module supports some arbitrary polynomials and code
rate.
Specifically, I want one of three set of polynomials:

- Polynomial 1 (g0 = 133, g1 = 171, g2 = 165)
- Polynomial 2 (g0 = 131, g1 = 145, g2 = 133)
- Polynomial 3 (g0 = 131, g1 = 171, g2 = 133)

(Common: Code rate 1/4, 2/3 and 1/3, where 1/4 = repeat of code rate 1/2)

The reason that I try to implement one of three is,
document describing specification has some wrong points.
Text says polynomial 1, but figure shows polynomial 2.

One thing is hopeful:

I think that polynomial 3 seems a sort of widely used one
and that it has been already implemented by someone in GNU Radio,
which has been heavily optimized... I hope...

(While I am writing this, I've checked that gr-fec can do CC with arbitrary
polynomials.
gnuradio/gr-fec/examples/fecapi_cc_decodres.grc
I still don't know optimization.)

I will keep looking into those gr-fec, dtv, trellis modules.
If someone have suggestions, I will appreciate it.

Thanks a lot.

Regards,
Jeon.
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] On the convolutional code performance of gr-ieee802-11

[Ron Economos]

Made a mistake. The DVB-T receiver is not part of the 3.7.8 release. 
It's a recent commit on the master branch (3.7.9git).


Ron

On 09/15/2015 01:31 AM, Ron Economos wrote:
The author of gr-dvbt looked at this issue when he developed the DVB-T 
receiver. Here's a blog entry on his findings.


http://yo3iiu.ro/blog/?p=1393

He benchmarked the IT++ decoder in last place.

IT++ = 2-3 Mbps
gr-trellis = 5 Mbps
Karn C = 7-8 Mbps
gr-dvbt = 39-40 Mbps

The gr-dvbt receiver is now part of GNU Radio as of the last release, 
3.7.8. The SSE2 viterbi decoder module is here:


https://github.com/gnuradio/gnuradio/blob/master/gr-dtv/lib/dvbt/dvbt_viterbi_decoder_impl.cc

In addition, I believe there's another decoder in gr-fec. I'm not very 
familiar with it, so maybe someone else can comment on it. Looks like 
it's in this module:


https://github.com/gnuradio/gnuradio/blob/master/gr-fec/lib/cc_decoder_impl.cc

Ron

On 09/15/2015 12:47 AM, Jeon wrote:
I've measured time taken by convolutional decoding in gr-ieee802-11. 
The module is using Punctured Convolutional Code class from IT++ 
library 
(http://itpp.sourceforge.net/4.3.0/classitpp_1_1Punctured__Convolutional__Code.html)


I've used chrono (chrono.h, chrono) to measure time taken. You can 
see how I made it from the following page 
(https://gist.github.com/gsongsong/7c4081f44e88a7f4407a#file-ofdm_decode_mac-cc-L252-L257)


I've measure time with a loopback flow graph (w/o USRP; 
examples/wifi_loopback.grc)


The result says that it takes from 5,000 to 30,000 us, which is 5 to 
30 ms to decode a signal with a length of 9,000 samples (samples are 
either 1 or -1.)


* Test environment: Ubuntu 14.04 on VMWare, 2 CPUs and 4 GB RAM allocated
* Host environmetn: Windows 7 with i7-3770 3.7 GHz

Since I am not familiar with error correcting codes, I have no idea 
how large the order of time taken is. But I think that one of the 
most efficient decoding algorithm is Viterbi and that IT++ must use it.'


Then I  can deduce that CC decoding takes a quite long time even 
though the algorithm (Viterbi) is very efficient. And is it a natural 
limitation of software decoding and SDR?


Another question comes that, the commercial off the shelf (COTS) 
Wi-Fi device achieves really high throughput and that must be based 
on super faster CC decoding. Is that because COTS is using heaviliy 
optimized FPGA and dedicated decoding chips?


Regards,
Jeon.



___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] On the convolutional code performance of gr-ieee802-11

[Ron Economos]

The author of gr-dvbt looked at this issue when he developed the DVB-T 
receiver. Here's a blog entry on his findings.


http://yo3iiu.ro/blog/?p=1393

He benchmarked the IT++ decoder in last place.

IT++ = 2-3 Mbps
gr-trellis = 5 Mbps
Karn C = 7-8 Mbps
gr-dvbt = 39-40 Mbps

The gr-dvbt receiver is now part of GNU Radio as of the last release, 
3.7.8. The SSE2 viterbi decoder module is here:


https://github.com/gnuradio/gnuradio/blob/master/gr-dtv/lib/dvbt/dvbt_viterbi_decoder_impl.cc

In addition, I believe there's another decoder in gr-fec. I'm not very 
familiar with it, so maybe someone else can comment on it. Looks like 
it's in this module:


https://github.com/gnuradio/gnuradio/blob/master/gr-fec/lib/cc_decoder_impl.cc

Ron

On 09/15/2015 12:47 AM, Jeon wrote:
I've measured time taken by convolutional decoding in gr-ieee802-11. 
The module is using Punctured Convolutional Code class from IT++ 
library 
(http://itpp.sourceforge.net/4.3.0/classitpp_1_1Punctured__Convolutional__Code.html)


I've used chrono (chrono.h, chrono) to measure time taken. You can see 
how I made it from the following page 
(https://gist.github.com/gsongsong/7c4081f44e88a7f4407a#file-ofdm_decode_mac-cc-L252-L257)


I've measure time with a loopback flow graph (w/o USRP; 
examples/wifi_loopback.grc)


The result says that it takes from 5,000 to 30,000 us, which is 5 to 
30 ms to decode a signal with a length of 9,000 samples (samples are 
either 1 or -1.)


* Test environment: Ubuntu 14.04 on VMWare, 2 CPUs and 4 GB RAM allocated
* Host environmetn: Windows 7 with i7-3770 3.7 GHz

Since I am not familiar with error correcting codes, I have no idea 
how large the order of time taken is. But I think that one of the most 
efficient decoding algorithm is Viterbi and that IT++ must use it.'


Then I  can deduce that CC decoding takes a quite long time even 
though the algorithm (Viterbi) is very efficient. And is it a natural 
limitation of software decoding and SDR?


Another question comes that, the commercial off the shelf (COTS) Wi-Fi 
device achieves really high throughput and that must be based on super 
faster CC decoding. Is that because COTS is using heaviliy optimized 
FPGA and dedicated decoding chips?


Regards,
Jeon.


___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio


___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] On the convolutional code performance of gr-ieee802-11

[Marcus Müller]

Hi Jeon,

speed depends on your hardware and the implementation of the decoder.
As a rule of thumb: the more "generally applicable" a decoder is, the
slower it gets.
Jan wrote a set of highly SIMD-optimized decoders, but these are (pretty
common) special cases, so they don't cover all the cases that gr-trellis
works in, or even more general, the ITPP decoders application range. I'd
assume you could get a significant speed boost if you replaced the IT++
implementation with your own, highly specialized decoder if you know
what you're doing, but honestly, implementing, leave alone optimizing,
decoders is a non-trivial task and one should definitely not start a
project like gr-ieee802-11 trying to write one's own decoder if there's
an existing decoder out there that's usable (IT++ can be a pain to use,
still).

Generally, I'd frown upon using a VM to benchmark decoders: Good
decoders might make substantial use advanced SIMD instructions, but
these might not be enabled in your virtualizer. Furthermore, if you want
to do real-world gr-ieee802-11 usage, *don't* work in a VM, unless
you're super knowledgable about how to configure VMs; latency and CPU
overhead is critical, so the default "NAT" network configuration will
not work well for network-attached USRPs, and USB3 support in VMs is
ranging between bad and horrible, so B2x0 aren't really the best thing
to be used in VMs, either.

Run "volk-config-info --avail-machines" and check whether the output
contains:
generic_orc;sse2_64_mmx_orc;sse3_64_orc;ssse3_64_orc;sse4_1_64_orc;sse4_2_64_orc;avx_64_mmx_orc;

If that's the case, your VMWare does allow AVX/SSE4 inside your VM.

Best regards,
Marcus

On 15.09.2015 09:47, Jeon wrote:
> I've measured time taken by convolutional decoding in gr-ieee802-11.
> The module is using Punctured Convolutional Code class from IT++
> library
> (http://itpp.sourceforge.net/4.3.0/classitpp_1_1Punctured__Convolutional__Code.html)
>
> I've used chrono (chrono.h, chrono) to measure time taken. You can see
> how I made it from the following page
> (https://gist.github.com/gsongsong/7c4081f44e88a7f4407a#file-ofdm_decode_mac-cc-L252-L257)
>
> I've measure time with a loopback flow graph (w/o USRP;
> examples/wifi_loopback.grc)
>
> The result says that it takes from 5,000 to 30,000 us, which is 5 to
> 30 ms to decode a signal with a length of 9,000 samples (samples are
> either 1 or -1.)
>
> * Test environment: Ubuntu 14.04 on VMWare, 2 CPUs and 4 GB RAM allocated
> * Host environmetn: Windows 7 with i7-3770 3.7 GHz
>
> Since I am not familiar with error correcting codes, I have no idea
> how large the order of time taken is. But I think that one of the most
> efficient decoding algorithm is Viterbi and that IT++ must use it.'
>
> Then I  can deduce that CC decoding takes a quite long time even
> though the algorithm (Viterbi) is very efficient. And is it a natural
> limitation of software decoding and SDR?
>
> Another question comes that, the commercial off the shelf (COTS) Wi-Fi
> device achieves really high throughput and that must be based on super
> faster CC decoding. Is that because COTS is using heaviliy optimized
> FPGA and dedicated decoding chips?
>
> Regards,
> Jeon.
>
>
> ___
> Discuss-gnuradio mailing list
> Discuss-gnuradio@gnu.org
> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio