算法

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

错误辨认多项式

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

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。