Berlekamp 算法 - 有限域的构造与运算
本节仅讨论有限域的特征为 2 时的情况。
有限域中的数可以由有限域当中的本原元 $\alpha$ 生成，本原元为本原多项式的根。
下面以 GF( $2^4$ )为例，介绍有限域的构造与运算。
选择本原多项式为：
有限域的构造
根据本原多项式，可以构造线性反馈移位寄存器用于得到有限域的向量表示和次数表示的对应。
由于
因此有
即 $\alpha^4$ 与 $\alpha + 1$ 是等价的。
根据该性质，得到的线性反馈移位寄存器的示意图如下图所示，
得到的对应的关系表为：
| 次数表示 | 向量表示 |
|---|---|
| 0 | ( 0, 0, 0, 0 ) |
| 1 | ( 0, 0, 0, 1 ) |
| $\alpha$ | ( 0, 0, 1, 0 ) |
| $\alpha^2$ | ( 0, 1, 0, 0 ) |
| $\alpha^3$ | ( 1, 0, 0, 0 ) |
| $\alpha^4$ | ( 0, 0, 1, 1 ) |
| $\alpha^5$ | ( 0, 1, 1, 0 ) |
| $\alpha^6$ | ( 1, 1, 0, 0 ) |
| $\alpha^7$ | ( 1, 0, 1, 1) |
| $\alpha^8$ | ( 0, 1, 0, 1) |
| $\alpha^9$ | ( 1, 0, 1, 0 ) |
| $\alpha^{10}$ | ( 0, 1, 1, 1 ) |
| $\alpha^{11}$ | ( 1, 1, 1, 0 ) |
| $\alpha^{12}$ | ( 1, 1, 1, 1 ) |
| $\alpha^{13}$ | ( 1, 1, 0, 1 ) |
| $\alpha^{14}$ | ( 1, 0, 0, 1 ) |
有限域上的运算
有限域的加法
- 向量表示的异或运算得到新的向量表示。
有限域的减法
- 同加法
有限域的乘法
- 次数表示的次数相加，得到新的次数表示，但要注意 0。
有限域的除法
- 次数表示的次数相减，得到的新的次数表示，但同样也要注意 0，也要注意除零错误。