Polynomial or matrix operations for GRS codes

Encoding/Decoding/membership/Syndrome etc. operations can be computed for GRS codes, either by the default matrix operations or by the polynomial representation.

Theoretically, the polynomial should beat the matrix representation for large enough codes. Preliminary tests (see experiments/timing_grs.sheet) indicate that matrix operations are much, much faster even for codes of length 1000. This might be due to bad implementations of e.g. lagrange_polynomial, but the matrix operations are also just incredibly well optimised.

A disadvantage of using matrix operations is that this will construct the generator matrix or parity check matrix. So there should at least be a threshold for when to switch to the more compact polynomial operations.

Case in point: The Gao decoder computes the Lagrange polynomial through the received word r as its first operation. This is -- in theory -- also the fast way of checking whether r is in the code (when the Lagrange polynomial has degree less than k). Thus the Gao decoder can use this check to return early. However, since for most GRS codes, computing the syndrome by vector-matrix multiplication is much faster than lagrange_polynomial, if one expect to often call decode_to_* on words with no errors, it would be more efficient to first check for code membership.

Comments (1)