Bug #4508
closedViterbi Conv decoder performance
100%
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
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.
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.
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.
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.
Updated by tnt over 2 years ago
- File compare.png compare.png added
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
Updated by tnt over 2 years ago
Found the problem and the solution. Working on a proper patch now.
Updated by laforge over 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
Updated by laforge over 2 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 80
Updated by tnt over 2 years ago
- Status changed from In Progress to Resolved
- % Done changed from 80 to 100
Applied in changeset libosmocore|d5974e9155e8991bd8ab15342096109b197db24f.