Show HN: SIMD Viterbi Decoder in Rust (github.com)

64 points by brian-armstrong 1mo ago ↗ HN

I wrote libcorrect in C in 2016 and wanted to revisit it in Rust. Instead of doing just a direct conversion, I went down the rabbit hole of making Rust's std::simd work for me. I ended up with a templated, generic Viterbi decoder for convolutional codes that dispatches the decode at runtime depending on which instruction sets are available. For small rates and orders, the entire decode lives in registers. Larger codes work through memory but take advantage of some acceleration structures.

I also spent some time building a tool to find optimal (max d_free) conv codes for a given rate and order. Of course, there are better mechanisms available today, but I'm happy to talk through anything I learned in the process.

4 comments

[ 0.36 ms ] story [ 6.5 ms ] thread

ChadNauseam 1mo ago ↗

I thought this might have something to do with sentencepiece's unigram (which uses viterbi). But they seem to be totally different domains. What an amazing algorithm, to show up in so many different places.

eminence32 1mo ago ↗

Could this library be used decode signals from a GOES satellite downlink? goestools uses libcorrect for this and building a rust version might be fun.

[1] https://github.com/pietern/goestools

nickcw 1mo ago ↗

I was looking at the reed Solomon implementation. I've done a few of those in the past! I note that you are using logs for multiplication. I always used to use a 64kb table for direct lookup, though maybe that isn't faster on modern processors?

Next LDPC codes?

brian-armstrong 1mo ago ↗

Interesting. I'll have to give it a try. If I understand your suggestion, you're saying that rather than doing 2 lookups for logs, then an addition, and then another lookup to exp back, we could just precompute the whole thing for any 2 arguments and do one lookup in a table? It's worth noting that some of the operations already use the mul_log format which just does an add with wraparound, but I could certainly see the big table option helping when we truly need field.mul

As far as LDPC, I'd love to, but I need to get a better understanding of them first. I'll probably go for Turbo next just because conceptually they feel closer to the convolutional codes I have already. But time willing, it'd be fun to do both.