Hermite Interpolation With Error Correction
Résumé
Multiplicity code decoders are based on Hermite polynomial interpolation with error correction. In order to have a unique Hermite interpolant one assumes that the field of scalars has characteristic 0 or $\geq\ell+1$, where $\ell$ is the maximum order of the derivatives in the list of values of the polynomial and its derivatives which are interpolated. For scalar fields of characteristic $\ell+1$, the minimum number of values for interpolating a polynomial of degree $\leq D$ is $D+1+2E(\ell+1)$ when $\leq E$ of the values are erroneous. Here we give an error-correcting Hermite interpolation algorithm that requires fewer values, that is, that can tolerate more errors, assuming that the characteristic of the scalar field is either 0 or $\geq D+1$. Our algorithm requires $(\ell+1)D + 1 - (\ell+1)\ell/2 + 2E$ values.
As an example, we consider $\ell = 2$. If the error ratio (number of errors)/(number of evaluations) $\leq$ 0.16, our new algorithm requires $(4+7/17),D - (1+8 /17)$ values, while multiplicity decoding requires $25D+25$ values. If the error ratio is $\leq 0.2$, our algorithm requires $5D-2$ evaluations over fields of characteristic 0 or $\geq D+1$, while multiplicity decoding for an error ratio $0.2$ over fields of characteristic 3 is not possible for $D \geq 3$.
Our algorithm is based on Reed-Solomon interpolation without multiplicities, which becomes possible for Hermite interpolation because of the high redundancy necessary for error-correction.
As an example, we consider $\ell = 2$. If the error ratio (number of errors)/(number of evaluations) $\leq$ 0.16, our new algorithm requires $(4+7/17),D - (1+8 /17)$ values, while multiplicity decoding requires $25D+25$ values. If the error ratio is $\leq 0.2$, our algorithm requires $5D-2$ evaluations over fields of characteristic 0 or $\geq D+1$, while multiplicity decoding for an error ratio $0.2$ over fields of characteristic 3 is not possible for $D \geq 3$.
Our algorithm is based on Reed-Solomon interpolation without multiplicities, which becomes possible for Hermite interpolation because of the high redundancy necessary for error-correction.