Berlekamp 算法 - 算法的描述

发送的码字多项式 $C(X)$ 通过生成多项式构造，设编码所需求的最小汉明距离参数为 $2t + 1$。

根据代数编码的性质可知，给定发送的码字多项式 $C(X)$，错误码字多项式 $E(X)$，和接收的码字多项式 $R(X)$ 存在如下关系：

$$\label{1}\tag{1} R(X) = C(X) + E(X)$$

而解码的过程就是已知 $R(X)$ 去找 $C(X)$ 的过程，根据 ( $\ref{1}$ ) 可知，也就是寻找 $E(X)$ 的过程。

我们首先根据 $R(X)$ 去构建校验和多项式 $S(z)$，

$$S(z) = \sum_{i=1}^{2t} S_i z^i = R(\alpha^i)z^i。$$

根据 $S(z)$ 我们就可以应用 Berlekamp 译码算法得到错误位置多项式了。

算法如下：

得到的 $\sigma(z)$ 为错误位置多项式，得到的 $\omega(z)$ 为错误估值多项式。

遍历有限域中的所有数，若 $\sigma(\alpha^j) = 0$，就说明第 $j$ 个位置为错误的位置。

在得到所有的位置之后，根据 $\omega(z)$ 得到错误位置上的值 $Y_i$。

方法如下：

$$Y_i = \frac{\omega (X_i ^ {-1})}{\prod\limits_{j \neq i}(1-X_jX_i^{-1})}$$

将 $R(X)$ 对应的错误位置改正即完成了一次译码。