深入解析 BCH 码：定义、特点及应用
BCH码是Bose、Bose、Bose独立提出的一种可以纠正多个随机错误的循环码。
BCH码的定义：给定任意有限域GF(q)及其扩展域GF(qm)（其中q是素数或素数幂），m是正整数，如果从GF中取出码元(q)循环 码生成多项式g(x)的根集R中有σ-1个连续根αm0、αm0+1、αm0+σ-2，则该循环码称为q元BCH码。其中α∈GF(qm)为定义域中的n层元素，αm0+i∈GF(qm)(0 ≤ i≤ σ-2)，m0为任意整数，通常取值为0或1，当m0 =1 时生成的BCH码为窄BCH码。如果生成多项式g(x)的根中存在GF(qm)的本原元素，则BCH码的码长为n=qm-1，对应的BCH称为本原BCH码。
假设mi(x)和ei分别为αm0+i(i = 1,2,…,σ-2)元素的最小多项式和次数，则BCH码的生成多项式和码长分别为：
BCH代码的属性
对于BCH码，有以下性质和结论。
①（BCH限制）BCH码的最小距离d至少为σ；若BCH码的生成多项式g(x)的根集为R = {αm0, αm0+c, αm0+(σ-2)c}且(n, c) = 1，则其最小距离d ≥ σ 。
②（HT极限）若BCH码的生成多项式g(x)的根集R有s组σ-1个连续的α元素（α∈GF(qm)为n层元素），即R = {αm0+ σi+j ,i = 0,1,…,s-1; j = 0,1,…,σ-2}且(n,α) = 1，则BCH码的最小距离d ≥ σ + s - 1 。类似地，（GHT极限）若BCH码的生成多项式g(x)的根集为R= {αm0+σ1i+σ2j , i = 0,1,…,s-1; j = 0,1,…, σ-2} 且 (n, σ1) < σ, σ ≥ 2，则 BCH 码的最小距离 d ≥ σ + s - 1。
③若二进制原始BCH码的码长为n=2m-1，设计距离σ=2t+1，则若满足：
那么，当t --> 0时，BCH码的实际距离等于设计距离。
④若二进制BCH码的码长为n=ab，设计距离σ=a，则该码的实际距离为a。
⑤若GF(q)上BCH码的码长为n=qm-1，设计距离σ=qh-1，则该码的实际距离为σ。
⑥ 原始BCH码与GF(q)上设计距离σ的实际最小距离d≤qσ+q-2。
在我们平时的编码中，主要讨论q=2的二进制窄BCH码。
生物信息安全信息交换所的结构
对于二进制 BCH 码，码元取自 GF(2)。根据BCH码的定义，若m0=1，σ=2t+1，则α为GF(2m)上的本原元素[0, 1]，若该码以α,α2,...,α2t为根，每个根对应的最小多项式为mi(x)，i = 1, 2, ..., 2t，则二进制BCH码的生成多项式为：
这个BCH代码可以纠正t错误。
在特征为2的GF(2m)上，(αi)2和αi的最小多项式相同，因此BCH码以α，α3，...，α2t-1为根，其生成多项式可写为:
对应的代码长度为：
其中，ei(i = 1, 3,..., 2t-1) 为 αi(i = 1, 3,..., 2t-1) 的级别。
根据生成多项式和循环码的循环移位特性可以构造BCH码的生成矩阵G()。若 C(x) = q(x)g(x) 为 BCH 码的任意码字，则 α, α3,..., α2t-1 为码多项式 C(x) 的根，即如果代码多项式为：
然后还有：
根据CHT=0，可知BCH码的校验矩阵H为：
对于二进制BCH码，得到以下结论：
对于任意正整数m和t，必然存在以α、α3、...、α2t-1为根、码长为n=2m-1或2m-1因子的二进制BCH码，可以纠正t个错误。代码中的校验元素个数为mt（生成多项式g(x)的次数）。
示例：对于 GF(24) 上定义的本原 BCH 码，m = 4，α 是 GF(24) 上的本原元素，GF(24) 上的本原多项式 p(x) = x4+x+ 1，则不同的t值，可以构造不同码参数的BCH码（假设码长n=2m-1=15）。
①若t=1，则构造的BCH码以α为根，α2、α4、α8也是BCH码的根。 α的最小多项式是本原多项式，所以生成多项式为g(x)=x4+x+1，校验元素个数mt=4，得到的是(15,11,4)BCH码具有纠错能力 t = 1。
参考下表：
功率表示 二进制表示 十进制表示
0000
0001
α1
0010
α2
0011
α3
0100
α4=α+1
0101
α5=α2+α
0110
α6=α3+α2
0111
α7=α3+α+1
1000
α8 = α2+1
1001
α9=α3+α
1010
10
α10=α2+α+1
1011
11
α11=α3+α2+α
1100
12
α12=α3+α2+α+1
1101
13
α13=α3+α2+1
1110
14
α14=α3+1
1111
15
根据表中GF(24)的元素列表和BCH码校验矩阵的形式，(15,11,4)BCH码的校验矩阵H可写为：
和循环码生成多项式矩阵的构造方法来写。
②如果t=2，则构造的BCH码以α和α3为根。 α 的最小多项式为 m1(x) = x4+1，α3 的最小多项式为 m3(x) = x4+ x3+ x2+x+1。因此，生成多项式为：g(x)=m1(x)m3(x)=x8+x7+x6+x4+1，校验元素个数mt=8，得到纠错能力t=2( 15 ,7,5) BCH 代码。参照上表中GF(24)的元素列表和BCH码校验矩阵的形式，(15,7,5)BCH码的校验矩阵H可写为：
BCH码的生成矩阵G可以根据校验矩阵H和生成矩阵G之间的对偶关系来写，或者根据生成多项式g(x)和循环码生成多项式矩阵的构造方法来写。
③若t=3，则构造的BCH码以α、α3、α5为根，α的最小多项式为m1(x)=x4+1，α3的最小多项式为m3(x)=x4+x3+x2+x+ 1. α5 的最小多项式为 m5(x) = x2+x+1，因此生成多项式为： g(x) = m1(x) m3(x)m5(x) = x10+ x8+ x5+x4+x2 +x +1，校验元素个数mt=12，得到具有纠错能力t=3的(15,5,7)BCH码。参考GF(24)的元素列表，形式结合上表中的BCH码校验矩阵，(15,5,7)BCH码的校验矩阵H可写为：
④若t=4，则构造的BCH码以α、α3、α5、α7为根，α的最小多项式为m1(x)=x4+1，α3的最小多项式为m3(x)=x4+x3+x2+ x+1，α5 的最小多项式为 m5(x) = x2+x+1，α7 的最小多项式为 m7(x) = x4+ x3+1，因此生成多项式为： g(x) = m1( x) m3 (x)m5(x)m7(x) = x14+ x13+x12+x11+x10+x9+ x8+x7+x6+ x5+x4+x3+ x2+x+1，结果为 (15, 1, 15 ) BCH码，即重复码。本规范的设计距离为 σ = 2t+1 = 9，则本规范的实际最小距离可计算为 d = 15。此时，设计距离不等于实际最小距离，该规范设计太过分了。该代码实际上可以纠正 (d-1)/2 = 7 个随机错误。
与线性分组码和循环码类似，扩展BCH码也可以通过添加全奇偶校验位来实现。
BCH码编码
BCH码编码的关键是生成多项式的选择，或者说生成矩阵G和校验矩阵H的构造。对于定义在GF(qm)上、群长n = qm-1且能够校正的BCH码t错误，编码步骤如下：
①选择m次约化多项式并构造GF(qm)。
②求αi的最小多项式mi(x)，i = 1, 3,..., 2t-1。
③ 构造一个可以纠正 t 个错误的代码生成多项式 g(x) = m1(x) m3(x)…m2t-1(x)。
④根据循环码和逆行编码的编码方法和编码电路（所有加法运算和乘法运算都在GF(qm)中。
中提供了BCH码的编解码相关函数和仿真模块，具体描述如下：
——：该函数根据码长n和信息组长度k计算窄BCH码的生成多项式。语法结构是：
genpoly = bchgenpoly(n,k)
genpoly = bchgenpoly(n,k,prim_poly)
[genpoly,t] = bchgenpoly(……)
其中，输入参数n为码长，k为信息组长度，码长n必须等于2m-1，3≤m≤16，输入为按幂降序排列的整数，表示本原多项式的系数。输出为GF(2)上按幂降序排列的生成多项式系数，输出t代表代码的纠错能力。
示例：生成纠错能力为 3 的 (15,5) BCH 代码生成多项式。
m = 4;
n = 2^m-1; % 码长
k = 5; % 信息组长度
[genpoly,t] = bchgenpoly(n,k) % 计算生成多项式和纠错能力
disp(genpoly); % 显示 genpoly
disp(t); % 显示 t
输出结果：
genpoly:
1×11 gf 数组 - 属性:
x: [1 0 1 0 0 1 1 0 1 1 1]
m: 1
prim_poly: 3
t:
3
利用生成多项式，可以对BCH码进行编码和解码。
——：该函数计算给定参数条件下BCH码的可纠正错误数。语法结构为：
T = bchnumerr(N)
T = bchnumerr(N,K)
语法结构1表示在给定码长N的情况下，当所有可能的信息组长度K组成不同的(N，K)个BCH码时，返回可纠正错误数T。返回值 T 是一个包含 3 列元素的矩阵。 ，第一列是码长N，第二列是可能的信息组长度K，第三列是纠错能力T。
例：当N=15时，输出结果T为：
T = bchnumerr(15)；
T =
15 11 1
15 7 2
15 5 3
即对于N＝15的情况，可以生成块长度K为11、7、5的BCH码，其纠错能力分别为1、2、3。
语法结构2要求输入信息组长度K，函数执行后返回(N，K)BCH码的纠错能力T。
——：该函数是BCH码的编码函数。语法结构为：
code = bchenc(msg,n,k)
code = bchenc(……,paritypos)
该函数使用窄(n,k)BCH码的生成多项式对输入消息组msg的BCH码进行编码。信息组msg定义在GF(2)上，可以是矩阵形式，每行包含k个元素作为一个信息组。最左边的符号是最高位。校验符号位于在输出GF(2)域上编码的码字中的每个码字的右端。
语法结构2中的参数用于指定校验符号的位置。取值可以为“end”或“”，分别表示校验符号位于输出码字信息组的开头和结尾。默认值为“结束”。
举例：假设对(15, 5) BCH码进行编码，输入为：
code = bchenc(msg,n,k)
code = bchenc(……,paritypos)
如果输入是：
msg = gf([1 0 1 0 1; 0 1 0 1 0 ]);
code = bchenc(msg,15,5);
输出是：
code：
2×15 gf 数组 - 属性:
x: [2×15 uint32]
[1,0,1,0,1,1,0,0,1,0,0,0,1,1,1;
0,1,0,1,0,0,1,1,0,1,1,1,0,0,0]
m: 1
prim_poly: 3
BCH码解码
1. 伴随解码
BCH码的校正子解码分为以下三个步骤：
①根据接收码多项式R(x)，用公式：
计算伴随表达式 S(x)。
②根据相关公式S(x)，在码字纠错能力范围内得到错误模式E(x)的估计E^(x)。
③估计发送的码字C^(x)=R(X)+E^(x)。
2. 迭代解码
BCH码伴随译码最复杂的部分是错误位置多项式系数的计算和根的求解。提出了一种通过迭代求解误差位置多项式根的方法（BM算法）。与Chien搜索电路结合，可以加快误差多项式的求解速度，简化译码过程。
BCH码的迭代译码分为以下五个步骤：
①根据接收到的编码多项式R(x)，使用公式：
计算伴随表达式 S(x)。
②使用BM算法求解误差位置多项式的系数。
③利用Chien搜索法求误差位置多项式的根。
④计算误差值（对于二进制码，此步骤可省略）。
⑤根据错误位置（和错误值），得到错误模式E(x)的估计E^(x)并解码，C^(x) = R(X)+E^(x)。
——：该函数是BCH码的解码函数，使用BM算法对BCH码进行解码。语法结构是：
decoded = bchdec(code,n,k)
decoded = bchdec(……,paritypos)
[decoded,cnumerr] = bchdec(……)
[decoded,cnumerr,ccode] = bchdec(……)
其中，输入参数n和k分别表示编码长度和信息组长度，code是GF(2)上定义的接受的编码符号序列，用于指定校验符号的位置（对应） 。
输出参数表示解码输出码字，其定义在有限域中，可以是矩阵形式。每行对应输入代码中一行码字的解码输出。如果函数检测到一行代码中的错误超过其纠错能力t（错误数量大于t），则解码失败。在这种情况下，该函数输出输入代码中每行的前 k 个符号（默认 =“end”）。输出参数中返回的是一个列向量，其中每个元素都是对输入代码的每一行进行解码时纠正的错误。如果一行解码失败，则列向量中对应的元素值为-1。在输出参数中，ccode返回纠正代码中的错误后的代码向量（或矩阵），其格式与输入代码相同。如果解码失败，则直接输出代码中相应行。
示例：对 (15,5) BCH 代码进行编码和解码。
n = 15;
k = 5;
dat = randi([0,1],4,k);
msg = gf(dat);
code = bchenc(msg,n,k);
decode = bchdec(code,n,k);
% 检查译码过程是否正确
chk = isequal(decode,msg);
上面的例子中，要求编码函数和解码函数中的参数值必须相同才能正确解码。