Lib.rs

› Algorithms
#reed-solomon #erasure #encoding #algorithm

reed-solomon-novelpoly

An implementation of a reed solomon code / encoder / decoder with complexity O(n lg(n))

by Bernhard Schuster, Parity Technologies, Jeff Burdges

3 releases (1 stable)

1.0.0 Mar 26, 2021
0.0.3 Mar 19, 2021
0.0.2 Mar 19, 2021
0.0.1 Mar 16, 2021
0.0.0 Mar 11, 2021

#631 in Algorithms

Download history 7392/week @ 2022-10-09 7864/week @ 2022-10-16 5481/week @ 2022-10-23 6360/week @ 2022-10-30 8056/week @ 2022-11-06 7298/week @ 2022-11-13 6697/week @ 2022-11-20 7487/week @ 2022-11-27 7923/week @ 2022-12-04 7240/week @ 2022-12-11 7375/week @ 2022-12-18 3890/week @ 2022-12-25 6375/week @ 2023-01-01 7366/week @ 2023-01-08 8757/week @ 2023-01-15 7237/week @ 2023-01-22

29,941 downloads per month
Used in reed-solomon-16

Apache-2.0 AND MIT

125KB
2K SLoC

Rust 1.5K SLoC // 0.1% comments C 269 SLoC // 0.1% comments

reed-solomon-novelpoly

An implementation of Novel Polynomial Basis and its Application to Reed-Solomon Erasure Codes 1 2 .

Runs encoding and reconstruction in O(n lg(n)). Note that for small number n there is a static offset due to a walsh transform over the full domain in reconstruction.

Goals

Be really fast for n > 100.

Non-goals

TODO

Dependencies

~1–1.7MB
~35K SLoC