Show HN: SIMD Viterbi Decoder in Rust

#1

Post by brian-armstrong » Tue, Aug 04, 2026, 10:37 PM UTC

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.

Show HN: SIMD Viterbi Decoder in Rust
github.com

Re: Show HN: SIMD Viterbi Decoder in Rust

#2

Post by ChadNauseam » Wed, Aug 05, 2026, 1:13 AM UTC

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.

Re: Show HN: SIMD Viterbi Decoder in Rust

#3

Post by eminence32 » Wed, Aug 05, 2026, 4:01 AM UTC

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

Re: Show HN: SIMD Viterbi Decoder in Rust

#4

Post by brian-armstrong » Wed, Aug 05, 2026, 4:32 AM UTC

eminence32 wrote: post #3

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

You could certainly call this crate through a shim in goestools but you'd have to add a Rust dependency. But you could also rewrite goestools in Rust, though it wouldn't be a small undertaking. This crate does have everything you'd need for the forward error correction, at least.

Re: Show HN: SIMD Viterbi Decoder in Rust

#5

Post by femto » Wed, Aug 05, 2026, 8:50 AM UTC

brian-armstrong wrote: post #4

eminence32 wrote: post #3

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

You could certainly call this crate through a shim in goestools but you'd have to add a Rust dependency. But you could also rewrite goestools in Rust, though it wouldn't be a small undertaking. This crate does have everything you'd need for the forward error correction, at least.

How do you find the speed of the Rust version of your FEC vs, the C version?

Re: Show HN: SIMD Viterbi Decoder in Rust

#6

Post by brian-armstrong » Wed, Aug 05, 2026, 9:20 AM UTC

femto wrote: post #5

brian-armstrong wrote: post #4

Earlier quoted context omitted.

You could certainly call this crate through a shim in goestools but you'd have to add a Rust dependency. But you could also rewrite goestools in Rust, though it wouldn't be a small undertaking. This crate does have everything you'd need for the forward error correction, at least.

How do you find the speed of the Rust version of your FEC vs, the C version?

I used the benchmarking binaries that ship with libfec. My own crate has a libfec-compatible C shim, so I can link the benchmark against the Rust crate. The benchmark itself reports time spent for a given number of iterations, so the throughput can just be extrapolated from that.

Re: Show HN: SIMD Viterbi Decoder in Rust

#7

Post by femto » Wed, Aug 05, 2026, 10:02 AM UTC

brian-armstrong wrote: post #6

femto wrote: post #5

Earlier quoted context omitted.

How do you find the speed of the Rust version of your FEC vs, the C version?

I used the benchmarking binaries that ship with libfec. My own crate has a libfec-compatible C shim, so I can link the benchmark against the Rust crate. The benchmark itself reports time spent for a given number of iterations, so the throughput can just be extrapolated from that.

I got caught out by my Australianism!

"How do you find the speed of the Rust version of your FEC vs, the C version?"

translates from "Australian" to "English" as:

"What is the speed of the Rust version of your FEC vs, the C version?

Though it was interesting to know how you do it. I'm interested in the speed, as I once looked into using Rust for a signal processing project, but ultimately went with C++ because the team wasn't familiar with Rust. At the time, it seemed to me that Rust had the potential to go faster.

Re: Show HN: SIMD Viterbi Decoder in Rust

#8

Post by nickcw » Wed, Aug 05, 2026, 10:06 AM UTC

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?

Re: Show HN: SIMD Viterbi Decoder in Rust

#9

Post by johschmitz » Wed, Aug 05, 2026, 10:43 AM UTC

femto wrote: post #5

brian-armstrong wrote: post #4

Earlier quoted context omitted.

You could certainly call this crate through a shim in goestools but you'd have to add a Rust dependency. But you could also rewrite goestools in Rust, though it wouldn't be a small undertaking. This crate does have everything you'd need for the forward error correction, at least.

How do you find the speed of the Rust version of your FEC vs, the C version?

Performance result are presented here as far as I understand: https://github.com/brian-armstrong/fec#performance

Re: Show HN: SIMD Viterbi Decoder in Rust

#10

Post by brian-armstrong » Wed, Aug 05, 2026, 10:48 AM UTC

femto wrote: post #7

brian-armstrong wrote: post #6

Earlier quoted context omitted.

I used the benchmarking binaries that ship with libfec. My own crate has a libfec-compatible C shim, so I can link the benchmark against the Rust crate. The benchmark itself reports time spent for a given number of iterations, so the throughput can just be extrapolated from that.

I got caught out by my Australianism! "How do you find the speed of the Rust version of your FEC vs, the C version?" translates from "Australian" to "English" as: "What is the speed of the Rust version of your FEC vs, the C version? Though it was interesting to know how you do it. I'm interested in the speed, as I once looked into using Rust for a signal processing project, but ultimately went with C++ because the te…

Oh! Gotcha! I put a table in the README that lays it all out https://github.com/brian-armstrong/fec#performance

tldr: My library matches or beats libfec's SSE2 assembly for convolutional codes and pretty steadily beats it in Reed-Solomon. For the convolutional codes, my crate is using a generic, templated decoder rather than hand-written assembly, so it was nice to see that I could match the performance.