伯利坎普－韦尔奇算法

伯利坎普－韦尔奇算法通常被用于解码里德-所罗门码。假使在有限体${\displaystyle GF(q)}$ 上有${\displaystyle n}$ 个数字${\displaystyle m_{1},\dots ,m_{n}}$ ，利用RS码编为${\displaystyle n-1}$ 次多项式${\displaystyle P(i)=m_{i}}$ 。如果已知传输信道会错误传输${\displaystyle k}$ 个值，那么RS码可以传输${\displaystyle P(i)}$ 上的${\displaystyle n+2k}$ 个点${\displaystyle (i,P(i))}$ 。因此，解码者的问题在于要辨认出哪${\displaystyle k}$ 个点是错误的。令解码者接收到的点值为${\displaystyle R(i)}$ ，可以看出对于且仅对于所有正确传输的点${\displaystyle i}$ ，${\displaystyle P(i)=R(i)}$ 。

错误辨认多项式

伯利坎普－韦尔奇算法引入了错误辨认多项式的概念，也即多项式${\displaystyle E(i)=(i-e_{1})(i-e_{2})\dots (i-e_{k})}$ ，其中${\displaystyle e}$ 的值为所有${\displaystyle k}$ 个错误传输的点的${\displaystyle i}$ 值（均未知）。由于${\displaystyle E(i)=0}$ 当且仅当${\displaystyle i}$ 对应一个错误传输的点，可以看出对于所有${\displaystyle i}$ 值，${\displaystyle P(i)E(i)=R(i)E(i)}$ ，其中${\displaystyle R(i)}$ 对于所有i均为已知常量。令${\displaystyle Q(i)=R(i)E(i)}$ ，可以看出左侧为一个${\displaystyle n+k-1}$ 次的多项式，右侧为一个${\displaystyle k}$ 次的多项式，但其最高次系数为1。因此，整个线性系统有${\displaystyle n+2k}$ 个方程式与${\displaystyle n+2k}$ 个未知数，可以用线性代数的方法解出，并可以由${\displaystyle P(i)=Q(i)/E(i)}$ 解出原始的编码多项式并读出编码值${\displaystyle m_{1},\dots ,m_{n}}$ 。