伯利坎普-韦尔奇算法

伯利坎普－韦尔奇算法（英语：Berlekamp-Welch algorithm）是一种用于高效地解码BCH码与里德-所罗门码的演算法，其名取自埃尔温·伯利坎普与劳埃德·韦尔奇。伯利坎普－韦尔奇算法的优点在于这一演算法仅需利用矩阵运算。这一演算法的时间复杂度为$O(N^{3})$。

演算法

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

错误辨认多项式

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