本文对 BCH码 进行简单介绍 1。
更新：2023 / 6 / 11
在信息论中，BCH codes 是指 Bose–Chaudhuri–Hocquenghem codes，可以用来纠错。BCH码利用了多项式一些很好的性质。本文将从0开始，用详细的例子解释二进制域中的BCH码 2。
多项式
二进制与多项式
首先考虑二进制域，即所有每个位的取值只能是 0 或 1。
我们可以尝试把二进制数表示为多项式，二进制数中的从左往右第 j 位，是多项式 x^j 的系数。例如 11011，可以表示成为 1 + x + x^3 + x^4。
二进制域的四则运算与我们常见的十进制差不多，但由于在二进制 1 + 1 = 2 = 0，所以我们每次计算后相当于模上 2。
例如计算 11*11，11 可表示为 1 + x，那么 11*11 在多项式表示就是 (1 + x)*(1 + x) = 1 + 2*x + x^2 = 1 + x^2，因为在这里 2*x 的 x 的系数 2 在二进制中等于 0。另外很重要的概念就是二进制域中，加等于减，例如 x^2 + 1 = 0 相当于 x^2 = 1 。
校验与纠错
我们先回顾简单的奇偶校验码和 hamming码 。
简单的奇偶校验码只能检查出错误而不知道具体是哪里出错，而 hamming码 只能纠正一位错误。
因此我们想能不能有一种方法可以纠正多位错误呢？此时，多项式的威力就发挥了出来。
假如我们的真正的消息是 m(x)，然后乘上一个编码多项式 p(x)，得到 m(x)p(x) 再将其发送过去。发送过程中会会受到很多干扰，于是多项式被加上错误多项式 e(x)，而接收者接收者的消息为 c(x)，就有
c(x) = m(x)p(x) + e(x)
接收者怎么知道消息有没错呢？
- 接收者事先就会和发送者商量好
p(x)，然后就很简单，只要让c(x)除以p(x)，如果余项是0，即没有e(x)，没有受到干扰，那么商就是m(x)，就是正确的消息。 - 如果余项不是零，我们的商就变成了
m(x) + e(x)/p(x)，无法将真正的消息分离出来。
上述方法有个前提，在 m(x) + e(x)/p(x)，p(x) 必须是不可约的本原多项式 ( primitive polynomials )，这样才能让 e(x) 不被除尽，我们才能意识到有干扰的存在。至于如何寻找素多项式，将在之后说明。
### 纠单个错的例子 下面来看个例子。例如我们要发送的消息 `m(x)` 是 `1001`，而编码多项式 `p(x)` 是 `1101`，于是我们要发送出去的消息就是 `1100101`。假如接收者也接收到了这个消息，用 `p(x)` 除后余项是 `0`，没有错误存在，商是 `1001`，就是发送者发送的消息，自然皆大欢喜。
但如果发送过程中，有一个位被某种不可抗拒的神秘力量改变了，变成了 1100111，接收者同样用 p(x) 去除，得到了余项 1110000，这下不好了，接收者知道出错了。但现在怎么去找出错误多项式 e(x) 呢？
我们知道，这个余项 1110000，就是 e(x)/p(x) 的余项。为了找出 e(x)，我们可以反过来推。于是制作一张表格
上面这个方法之所以能奏效，对于所有的可能的错误。是因为右边的每一个余项都不相同，我们才不至于混淆。如果我们把 p(x) 换成 10001 会发生什么呢？这里 10001 不是本原多项式，因为 10001 可以分解成 101 乘以 101。
备注：
101 X 101需要做二进制的取模运算，而不是二进制运算，那么101x101=10001。
e(x) |
e(x)/p(x) 的余项，p(x)=10001
|
|---|---|
| 1000000 | 1000000 |
| 0100000 | 0100000 |
| 0010000 | 0010000 |
| 0001000 | 0001000 |
| 0000100 | 1000000 |
| 0000010 | 0100000 |
| 0000001 | 0010000 |
我们可以看到，右侧重复了。
假如我们的到余项 1000000，我们无法知道 e(x) 究竟是第一行的 1000000 还是第五行的 0000100。
而本原多项式就好在，在所有错误余项 e(x) 出现前 e(x)/p(x) 的余项不会重复，之后将开始重复，这就是被称为 (Cyclic) 码的原因。
寻找本原多项式
如何确定一个多项式是否是本原多项式呢？根据以下原则：
- 如果是
r次多项式，最高次项x^r的系数必须是1； - 多项式如果不包含常数项
1，就会被x整除； - 多项式不能是偶数项，比如
1 + x + x^2 + x^4有四项，很容易将其分解为(1+x)(1+x^2+x^3)；
备注：
(1+x)(1+x^2+x^3) = 1+x^2+x^3+x+x^3+x^4=1+x^2+2x^3+x^4=1+x^2+x^4
- 每一项的次数也不能都是偶数，否则将每一项次数减半就能得到因子。例如，
1 + x^2 + x^4 = (1+x+x^2)(1+x+x^2) = (1 + x + x^ 2)^2；
备注：
(1+x+x^2)(1+x+x^2)=1+x+x^2+x+x^2+x^3+x^2+x^3+x^4=1+2*x+2*x^2+x^2+2*x^3+x^4=1+x^2+x^4
于是，我们很容易找到以下的表格：
| 次数 | 本原多项式 |
|---|---|
1 |
1+x |
2 |
1+x+x2 |
3 |
1+x+x3 |
4 |
1+x+x^4，1+x^3+x^4，1+x+x^2+x^3+x^4
|
按照上述方法可以继续寻找更多的本原多项式。次数越高，数量越多。
BCH码
如果想要纠正多个错误呢？此时仅一个编码多项式 p(x) 就不够了，我们还需要更多的编码多项式来让我们能找出多个错误 3。
这时就轮到 BCH 码出场了，其编码多项式标准形式是：
Q(x) = p(x)p3(x)p5(x)p2t-1(x)
其中 p(x) 是本原多项式，而 p~3~(x^3)， p~5~(x^5) … 都是可以被 p(x) 除余0的多项式。即
p3(x^3)=p5 (x^5)···p2t-1 (x^2t-1) = 0 (mod p(x))
如果我们要设计一个可以纠正两个错误的编码多项式，就让 Q(x) = p(x)p3(x)。
要设计一个可以纠正三个错误的编码多项式，就让 Q(x) = p(x)p3(x)p5(x)。
现在我们先说如何寻找 p3(x)：
看不懂了…
留下下回更新…
参考链接
-
BCH码 ↩︎
-
【举例子详细分析】BCH码(BCH code) ↩︎文章来源：https://www.toymoban.com/news/detail-490139.html
-
第四章-- 线性分组码（2）BCH码、RS码 ↩︎文章来源地址https://www.toymoban.com/news/detail-490139.html
到了这里，关于通信算法 | BCH码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
