Project

General

Profile

Actions

Bug #4508

closed

Viterbi Conv decoder performance

Added by tnt almost 4 years ago. Updated about 2 years ago.

Status:
Resolved
Priority:
High
Assignee:
Category:
libosmocoding
Target version:
-
Start date:
04/21/2020
Due date:
% Done:

100%

Spec Reference:

Description

There seems to be some evidence that the viterbi decoder might not be performing as well as it should (vis-as-vis its ability to correct errors).

The tested code was a very short packet encoded with this code in tail-biting mode :

code = conv_gen.ConvolutionalCode(20,
        [
                ( conv_gen.poly(0,2,3,5,6), 1 ),
                ( conv_gen.poly(0,1,2,3,6), 1 ),
                ( conv_gen.poly(0,1,2,4,6), 1 ),
        ],
        name='lte'
)

Decoding results with each time # of bit erasure, % failed packet, % of bit errors.

libosmocore:

 0   0.00   0.00
 5   0.00   0.00
10   0.00   0.00
15   1.33   0.13
20   1.33   0.13
25   3.33   0.37
30  14.00   1.83
35  40.00   8.10
40  89.33  40.30

HW decoder:
 0   0.00   0.00
 5   0.00   0.00
10   0.00   0.00
15   0.00   0.00
20   0.00   0.00
25   0.00   0.00
30   0.00   0.00
35   2.67   1.43
40  56.67  24.90

Files

compare.png View compare.png 54.4 KB tnt, 12/21/2021 01:11 PM
Actions #1

Updated by laforge over 3 years ago

  • Category set to libosmocoding
  • Assignee set to Hoernchen
  • Priority changed from Normal to High

Let's increae priority of this issue and actually assign it to someone with related area of expertise.

tnt: You compared the results of some FPGA hardware implementation with those of our software implementation? Do we know if this also happens in the convolutional decoding for GSM/GPRS/EGPRS? In the latter case, we should definitely investigate this ASAP.

Might also be a good idea to have unit tests that verify the error recovery matches the expected performance.

tnt if you have time/interest to work on this, sysmocom is happy to pay for it - but I somehow fear you have other priorities at the moment, hence I'm assigning it to Hoernchen for now.

Actions #2

Updated by tnt over 3 years ago

Yeah, I can look at it in ~ 1 month if Hoerchen hasn't gotten around to it by then.

I had a look back when I first reported the issue and spent about half a day and couldn't really see anything. Behavior was the same both with the "normal" and the "sse" version of the code despite them sharing almost nothing.

I don't know if the same thing is true for the normal GSM codes. Unfortunately trying a different code, using another termination mode and using different packet length isn't something trivial to change for the hardware decoder so it would take a good few hours to implement that to try.

Actions #3

Updated by Hoernchen about 3 years ago

tnt did you have time to look at this?

Actions #4

Updated by laforge over 2 years ago

  • Assignee changed from Hoernchen to tnt

Assigning to tnt, maybe he can find some spare cycles to investigate.

Actions #5

Updated by tnt over 2 years ago

Mmm ... I did some test comparing another viterbi implementation on the XCCH GSM code and found no such issue.

I'll retry with the 1/3 code above, see if I see anything.
Or maybe the issue is with tail-biting only ... or maybe there is no issue and my initial testing was flawed somehow.

Actions #6

Updated by tnt about 2 years ago

I continued work on this today and finally managed to reproduce my initial observation.
Comparing results from libosmocore with those from libcorrect ( https://github.com/quiet/libcorrect Just a random lib I picked because it suported arbitrary codes ).

Because libcorrect doesn't have any native support for tail biting codes, the decoding is done by feeding the same message 3 times consecutively and then using the "middle" part of the decoding result as the decoded results.

AFAICT the problem is limited to tail-biting codes.

See comparison graph :
- X axis is the number of injected erasures.
- Blue is libosmocore message error rate (i.e. decoded packet has error)
- Green is libcorrect message error rate
- Orange is libosmocore bit error rate
- Red is libcorrect bit error rate

Actions #7

Updated by tnt about 2 years ago

Found the problem and the solution. Working on a proper patch now.

Actions #8

Updated by laforge about 2 years ago

tnt wrote in #note-7:

Found the problem and the solution. Working on a proper patch now.

Thanks a lot for looking into this. Patch is at https://gerrit.osmocom.org/c/libosmocore/+/26657

Actions #9

Updated by laforge about 2 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 80
Actions #10

Updated by tnt about 2 years ago

  • Status changed from In Progress to Resolved
  • % Done changed from 80 to 100
Actions

Also available in: Atom PDF

Add picture from clipboard (Maximum size: 48.8 MB)