error correction

Berlekamp-Welch

假设我们接收到的系数为 \(r_0 \cdots r_{d+2k}\)

假设替换的所有下标集合为 \(Z={r_i \not=P(i)}\), 大小为 \(|Z|\leq k\)

构造一个多项式 \(\displaystyle E(x)=\prod_{i\in Z}(x-i)\)

则我们有恒等式 \(P(x)\cdot E(x)=r_x \cdot E(x)\)

同时如果 \(|Z|=k\), 那么 \(E(x)\) 可表示成 \(x^k+e_{k-1}x^{k-1}+\cdots+e_0\)

\(P(x)\cdot E(x)\) 可表示成 \(f_{d+k}x^{d+k} + \cdots +f_0\)

那么将所有 \(x=0,\cdots,d+2k\) 插入多项式恒等式，得到了 \(d+2k+1\) 个未知量，\(d+2k+1\) 个等式

未知量指 \(f_{d+k}, \cdots ,f_0,e_{k-1},\cdots,e_0\)

解线性方程得到所有的 \(f_{d+k}, \cdots ,f_0,e_{k-1},\cdots,e_0\)

输出多项式 \(\frac{P(x)\cdot E(x)}{E(x)}\), 系数即为所求