Hermite Interpolation With Error Correction: Fields of Zero or Large Characteristic and Large Error Rate
Hermite Interpolation With Error Correction: Fields of Zero or Large Characteristic and Large Error Rate
复制标题
带纠错的 Hermite 插值：零或大特征和大错误率的字段
DOI：
10.1145/3452143.3465525
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Yang, Zhi-Hong
中科院分区：
文献类型：
--
作者：
Kaltofen, Erich L.;Pernet, Clément;Yang, Zhi-Hong
多重码解码器是基于带有误差校正的埃尔米特多项式插值。为了得到唯一的埃尔米特插值，我们假设标量域具有0或≥𝓁+1的特征，其中𝓁是被插值的多项式及其导数的值列表中导数的最大阶。对于特征为𝓁+1的标量场，当阶数≤D的多项式的值≤E错误时，插值的最小值为D+1+2E（𝓁+1）。假设标量场的特征值为0或≥D+1，我们给出了一种需要更少的值即可以容忍更多误差的纠错Hermite插值算法。我们的算法需要（𝓁+1）D +1 -（𝓁+1）𝓁/2 + 2E值。例如，我们考虑𝓁= 2。当错误率（错误数）/（评估数）≤0.16时，我们的新算法需要（4+7/17），D -(1+8 /17)个值，而多重解码需要25D+25个值。当错误率≤0.2时，我们的算法需要对特征为0或≥D+1的域进行5D-2次评估，而当D≥3时，对特征为3的域进行错误率为0.2的多重解码是不可能的。我们的算法基于Reed-Solomon插值，没有多重性，由于纠错所需的高冗余，这使得Hermite插值成为可能。
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 ≥ 𝓁 +1, where 𝓁 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 𝓁+1, the minimum number of values for interpolating a polynomial of degree ≤ D is D+1+2E(𝓁+1) when ≤ 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 ≥ D+1. Our algorithm requires (𝓁+1)D + 1 - (𝓁+1)𝓁/2 + 2E values.As an example, we consider 𝓁 = 2. If the error ratio (number of errors)/(number of evaluations) ≤ 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 ≤ 0.2, our algorithm requires 5D-2 evaluations over fields of characteristic 0 or ≥ D+1, while multiplicity decoding for an error ratio 0.2 over fields of characteristic 3 is not possible for D ≥ 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.
登录
查看更多内容
冗余残差系统的输出敏感解码
DOI：
--
发表时间：
2010
期刊：
International Symposium on Symbolic and Algebraic Computation
影响因子：
--
作者：
M. Khonji;Clément Pernet;Jean;Thomas Roche;Thomas Stalinski
通讯作者：
Thomas Stalinski
超过最小距离一半的稀疏多项式插值码及其解码
DOI：
--
发表时间：
2014
期刊：
International Symposium on Symbolic and Algebraic Computation
影响因子：
--
作者：
E. Kaltofen;Clément Pernet
通讯作者：
Clément Pernet
带误差修正的 Hermite 有理函数插值
DOI：
10.1007/978-3-030-60026-6_19
发表时间：
2020
期刊：
Proc. Computer Algebra in Scientific Computing (CASC
影响因子：
--
作者：
Kaltofen, Erich L.;Pernet, Clement;Yang, Zhi-Hong
通讯作者：
Yang, Zhi-Hong
关于多重码的一些说明
DOI：
10.1090/conm/625/12497
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Swastik Kopparty
通讯作者：
Swastik Kopparty
通过导数码进行最优速率列表解码
影响因子：
2.5
作者：
V. Guruswami;Carol Wang
通讯作者：
Carol Wang