浅析BCH码的编码方法

1、根据生-表示一个二进制移位寄存器，符号表示模根据生-表示一个二进制移位寄存器，符号表示模2加法器，符号浅析BCH码的编码方法0引言数字信号在传输系统中传输时，不免会受到各种因素的干扰，使到达接收端的数字信 号中混有噪声，从而引发错误判决。为了抗击传输过程中的干扰，必然要利用纠错码的差错 控制技术。BCH码是纠错码中最重要的子类，其具有纠错能力强，构造方便，编码简单， 译码也较易实现一系列优点，在实际应用中被工程人员广泛应用。BCH 码BCH码是1959年由霍昆格姆（Hocquenghem）, 1960年由博斯（Bose）和查德胡里 （Chandhari ）各自提出的纠多个随机错误的循环码，这是

2、迄今为止发现的最好的线性分组码之 一，它有严格的代数结构，它的纠错能力很强，特别是在短和中等码长下，其性能接近理论 值，并且构造方便编码简单，特别是它具有严格的代数结构，因此它在编码理论中起着重要 的作用。BCH码是迄今为止研究的最为详尽，分析得最为透彻，取得成果也最多的码类之 一。该码的生成多项式与最小距离d之间有密切关系，根据d的要求可以很容易地构造出码， 利用该码的代数结构产生了多种译码方法。BCH码可以采用查表编码方法，这是一种利用BCH码作为线性分组码和循环码的性 质和结构特点来编写编码表，然后通过查表来编码的一种方法，也可以采用编码器进行编码， 还可以应用代数算法，在本文将分别介绍

3、这些算法。BCH码的n - k级编码器J,k） BCH码是一类循环码，它的编码方法和传统的循环码完全相同，根据循环码的 生成多项式gG）或校验多项式h（x），可推出BCH码的编码电路是一个n - k级或k级移存 器电路，在kn-k时，一般采用n - k级编码电路。用于产生系统码n-k级编码器的原理这样的：将信息多项式 mG）乘以xz成为 xn-km（x），然后用g（x）除xn-km（x）得到余式r（x）, r（x）的系数就是校验位，因此这可以反馈连接的移位寄存器构成的除法电，路完成。见图1。符号g, =1，表示连线，若g, =0，表示断开（对二进制而言）。从图1可以看出，该n-k级移位寄存器编

4、码电路的硬件主要包括:1、n - k级移位寄存 器（譬如n - k个触发器），2、大约（n - k2个模2加法器，3、反馈连接中的门电路，4、一个控制输出开关和反馈连接门的时钟计数电路，可由m级移位寄存器构成（m是使nV2m 的最小整数）。图1移位寄存器编码电路羊3 BCH码的代数编码（1）图1移位寄存器编码电路羊3 BCH码的代数编码（1）共轭和最小多项式如果将GFG刀）看成是GF（2）的一个m阶扩展，则映射a a 2称为共轭。共轭是线性的，即整数，则a的共轭类是包括G k），而不能属于其他任何一个更小的域。因子，并且a e GFa的共轭类是序列a,a2,a孵，中取值不同的元素。因此，如果k

5、是满足a2 = a的最小 ,a2,a211整数，则a的共轭类是包括G k），而不能属于其他任何一个更小的域。因子，并且a e GFa的最小多项式为系数属于GF（2）、阶数最低、首项系数为1且满足f （a ）= 0的多项式f 1）。f G）在GFG）上是不可约的，但在更大的域GF（m ）中，f G）可以进行线性因式分解:f G)= Ga)C-a 式分解:f G)= Ga)C-a 2).(-a 2阵】)(2)如果a是GFGm）中的一个本原根，则a的最小多项式称为GF（如果a是GF利用本原多项式可以来构造域，通过查表可以发现f。）= x4 + x +1是GF（2）上的一个本 原多项式。即f G ）是

6、GF （16）中一个本原根的最小多项式。通过反复利用等式a 4 =a+1，可以将每个幂a i表示为a的一个次数 3的多项式。例如:a 11 =a3 +a2 +a，可以得出表（1）：表（1）将GF （16）表示为a的幂，其中a 4 =a+1ia i00001100102010031000400115011061100710118010191010100111111110121111131101141001同理：fG）= x 3 + x +1 是 GF（8） 上一个本原根的最小多项式。反复应用等式a 3 =a+1，可以将每个幂a /表示为a的一个次数 2的多项式。例如：a 5 =a 3+a 2,

7、可以得出表（2）：表（2） GF（8）中a的幂，其中a3 =a+1ia i0001101021003011411051116101（2）BCH码生成多项式&）的求法每个BCH码都以它的生成多项式gG）为特征。根据生成多项式的定义知道gG）是码 中次数最低的码多项式，即满足g（a）= gC3）= = gC如-1 ）= 0的最低次多项式。gG）的系数在GF(2)中，但是a不同次数的幂在更大的域GFGm )中。根据BCH码的定义，gG) 若以GF(2m)中的元素a,a2,a3,.,a力(为2m 1级元素)为根，且g(g(x)= m (xm (x).m(x)其中 m G)m(),m (x)分别为 a,

8、a3, ,a2t1 在 GF(2) 上的最小多项式。m (x)在GF(2)上是不可约多项式，但是在更大的域GFGm )中可以分解为：m (x)=(x-a)x a2).( a2.一) i因此，gG)是GFGm)的子集A = a,a3,a5,a2t)在GF(2)上的最小多项式的 乘积。所以，如果定义A中元素的共轭为A* = 12, : p G A,i 0I那么gG)可以表示为：g(x)= n (x p)pe A *即上述文字可以用如下结论总结：，其中 a * 是 GF Gm)中 A = 0, a 3, a 5, , a 2，其中 a * 是 GF Gm)中 A = 0, a 3, a 5, , a

9、 2t-1 的 GF (2)-共轭的集合。(3)利用归纳法验证结论一所描述的求生成多项式方法的正确性可以通过查表的方法来验证所求的生成多项式是否正确。表一给出了n 31的二进制 本原BCH码表，可以根据此表查出码长为n，纠正t个错误的BCH码的生成多项式gG)。nW31的二进制本原BCH码表g (p)nW31的二进制本原BCH码表g (p)(八进制表示)%151531313131313131712621166262113 23 721 246745 3551 107657 5423325 313365047 75 2303表中各多项式是以八进制形式给出的。比如：3）8 =001011=x3 +

10、 x +1。意指将十进制 数“ 13”转换为八进制数“001011”，即生成多项式g（x）二 X 3 + x + 1。下面通过举例的方法对结论一的正确性进行验证：a）考虑当m = 3时，码长n = 2m -1 = 7，纠正1个错误的BCH码。（m为 3的任意正 整数）令侦是GF（8）的一个本原元；则根据结论一，生成多项式是集合 A = L, a 3, a 5, .,a如-1 的最小多项式的乘积。/ t = 1:. A = x ）a的共轭类为：a 2i = 0时，为ai = 1时，为a 2i = 2时，为a 4i = 3 时，为a8 =a8-7 =ai只能取到2因此，A* = ,a2,a4根据结

11、论一，维数是7-4=3。式gG）是a的最小多项式。a的最小多项式：要实际计算出gG）,需要式gG）是a的最小多项式。a的最小多项式：g(x)=n (x-&)Pe A*=(x a )x a 2)( a 4)而一致校验多项式为h（x ）= X7 +1 g 1）= X4 + X2 + x +1查表一得码长为7,纠正一个错误的BCH码的gG）为:g G）=G3）8 =001011 =X 3 + X + 1 可以看出由结论一的方法计算出的g G）是正确的。b）考虑码长为15、纠正2个错误的BCH码。令侦是 GF （16） 的一个本原元；则根据结论一，生成多项式是集合A = 4,a3,a5, ,a21）的

12、最小多项式。因为t = 2，故 A = 4,a3a的共轭类为：a的共轭类为：a 2,i = 0时，为ai = 1时，为a 2i = 2时，为a 4i = 3时，为a 8i = 4 时，为 a 16 =ai只能取到3 所以a的共轭类为：,a2,a4,ada 3a 3的共轭类为：a 3x2,i = 0时，为a 3i = 1时，为a 6i = 2 时，为 a 12i = 3 时，为 a 24 = a 24-15 = a 9所以a3的共轭类为：a3,a6,a12,a9 因此，A* = ,a2,a3,a4,a6,a8,a9,a 12根据结论一，维数是15-8=7。根据结论一，生成多项式g G）是a和a

13、3的最小多项式的乘积。利用a 4 =a+1的本原元a的幂来表示GF(16)并利用表(1 )进行化简，求得a的最小多项式为:g(x)=n (x-p)(a )(a 4)(-a 8)a 3的最小多项式记为一g (x)= g + g x + g x2 + g x3 + g x4 必须满足 TOC o 1-5 h z 33031323334g ( 3 )= 0。由表(2)，这等价于 g t)001+ g 11000+ g 1100+ g 11010+330313233g G111M000。 这个方程组由包含5个未知数的4个齐次方程组成，它的唯一非全零 34解为 t , g , g , g , g =11111,因此 g (x) =x4 + x3 + x2 + x + 1。因此，码长为3031323334315、纠正2个错误的BCH码的生成多项式为：g (x )= (4 + x + 1)(4 + x 3 + x 2 + x + 1)。而一致校验多项式为 h(x )= x15 +1 g (x )= x7 + x6 + x4 +1。查表得n = 15,t = 2的生成多项式gG)为:g (x )=(721)8 = 111010001 =x 8 + x 7 + x 6 + x 4 +1 。可见按照结论一求得的g (x)是正确的。综上所见，按照结论