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?
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.
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.
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.
"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.
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.
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.
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?
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.
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?
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.
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.
Nice! Thanks too for putting the work into this library.
Performance result are presented here as far as I understand: https://github.com/brian-armstrong/fec#performance
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.