We describe a subquadratic algorithm for systematic encoding of multiplicity codes. These codes generalise the construction of Reed-Muller codes by additionally evaluating partial derivatives, allowing higher rates to be obtained while retaining sublinear local decoding. We base our encoding algorithm upon the multivariate interpolation and evaluation algorithms of van der Hoeven and Schost (2013), which we partially generalise to handle the presence of derivatives.
Algorithmic Number Theory, Coding and Cryptography
