伯利坎普－韦尔奇算法

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

伯利坎普－韦尔奇算法通常被用于解码里德-所罗门码。假使在有限体${\displaystyle GF(q)}$上有${\displaystyle n}$个数字${\displaystyle m_1,\dots <!--\; \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 <!--\; \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 <!--\; \dots \; -->,m_n}$。