循环码和BCH码.

Presentation on theme: "循环码和BCH码."— Presentation transcript:

1 循环码和BCH码

2 简述 1957年开始研究 循环码的优点： 编码和校正子的计算容易实现 具有固定的代数结构，能找到很多实用的方法来译码

3 循环码定义 对一个n维码字向量v=(v0,v1,…,vn-1)做一次向右循环移位，得到v(1)=(vn-1,v0,…,vn-2)，类似，向右做i次移位，得到v(i)=(vn-i,vn-i+1,…,vn-i-1)，等价于向左移位n-i次 循环码：一个(n,k)线性码C，若每个码字的循环移位仍然是C的码字，则称其为循环码 为研究循环码的代数结构，将码字v的分量看做多项式的系数：v(x)=v0+v1X+v2X2+…+vn-1Xn-1 每个码字对应于一个次数等于或小于n-1的多项式 码字和多项式是一一对应的， v(x)叫做码多项式

4 码多项式 若v的码多项式为v(x)=v0+v1X+v2X2+…+vn-1Xn-1
则v(i)的码多项式为vn-i+vn-i+1X+…+vn-i-1Xn-1 计算xiv(x)-v(i)得到: (1) 也就是说v(i)就是xiv(x)除Xn+1后的余式

5 循环码的性质 循环码中非零次数最低的多项式是唯一的 循环码中非零次数最低多项式常数项为1
证明：(反证法)假设有两个最低次数一样的多项式，这这两个多项式之和的次数更低，而且应该是码多项式（线性，封闭性），矛盾。 循环码中非零次数最低多项式常数项为1 证明： (反证法)假设常数项为0，则码多项式可提取公因子X，另一个因子是次数更低的码多项式（循环左移1次），矛盾。 设g(X)=1+g1X+…+Xr是(n,k)循环码非零次数最低的多项式，次数小于或等于n-1的二进制多项式是码多项式当且仅当它是g(X)的整倍数。

6 循环码的性质 证明：1）若v(X)是g(X)的整倍数，即
v(X)=(1+u1X+...+uiXi)g(X)，Xig(X)是g(X)向左循环移位i次的码多项式，故v(X)是码的线性组合；2）设v(X)是码多项式，有v(X)= a(X)g(X)+ b(X)， b(X)次数小于g(X)， b(X)可以写成b(X)= a(X)g(X)+v(X)，故b(X)是码多项式或0，因g(X)是次数最低的非零多项式，故b(X)=0，即v(X)是g(X)的整倍数

7 循环码的性质 (n,k)循环码有且仅有一个n-k次的码多项式g(X)=1+…+Xn-k，这就是次数最小的码多项式，也称为码的生成多项式

8 循环码的性质 (n,k)循环码的生成多项式g(X)是Xn+1的一个因子
证明：由公式(1)显然。 若g(X)是次数为n-k，且是Xn+1的一个因子，则g(X)是生成多项式，生成一个(n,k)循环码 证明:略。 性质6说明Xn+1任何一个n-k次多项式都可以生成一个(n,k)循环码，当n很大时，可以构造很多的(n,k)循环码，有好有坏，如何选择？

9 例子： X7+1 X7+1=(1+ X)(1+X+X3)(1+X2+X3) 故有两个(7,4)循环码

10 循环码的系统形式 码字前n-k分量为校验位，后k分量是信息位 编码步骤： 用Xn-k乘信息序列u(X)
用生成多项式g(X)除Xn-ku(X)，得余式b(X)为校验位 得到码多项式Xn-ku(X)+b(X)

11 循环码的生成矩阵 设g(x)=g0+…+gn-kXn-k,则有生成矩阵如下： 若不是系统形式，可通过行变换变成系统形式

12 校验矩阵H 令h(X)满足， Xn+1=g(X)h(X),则h(X)的k个系数张成矩阵,h(X)称为校验多项式

13 循环码的对偶码 设码C的生成多项式为g(X)，校验多项式为h(X) 其对偶码的生成多项式为Xkh(X-1)，也是一个循环码
一个循环码被其校验矩阵唯一确定

14 例子 （7,4）循环码C，生成多项式g(X)=1+X+X3 其校验多项式为h(X)=（Xn+1）/g(X) =1+X+X2+X4
X4h(X-1)=1+X2+X3+X4

15 循环码的编码 编码步骤： 用Xn-k乘信息序列u(X) 用生成多项式g(X)除Xn-ku(X)，得余式b(X)为校验位
得到码多项式b(X) +Xn-ku(X)

16 循环码的译码 同线性码 计算校正子 求错误模式 纠错或计算码字

17 查错 令v(X)表示输入码字，e(X)为错误模式，则接受向量r(X)=v(X)+e(X)=a(X)g(X)+e(X)，故有：e(X)=a(X)g(X)+b(X)g(X)+s(X)=c(X)g(X)+s(X)，即校正子是错误模式除以生成多项式的余式 从接受向量r(X)可以计算校正子s(X)，错误模式e是未知的，故需要从s(X)去求e(X)。若e(X)是标准阵的陪集首，则可用查表译码，由校正子获得错误模式。 若e(X)是0，则s(X)=0；若e(X)是码多项式，则e(X)是漏检错误模式。

18 计算校正子 设接受序列为r(X)，则有： r(X)=a(X) g(X)+s(X)，当且仅当r(X)是码多项式时，s(X)是0，s(X)就是校正子 性质：r(1)(X)的校正子s(1)(X)是s(X)的一次循环移动。 也就是说码字循环位移得到新码字的校验子是原校验子循环位移后除以生成多项式的余式，即： s(i)(X) =Xis(X)-b(X)g(X)=ri(X)-c(X)g(X)， s(i)(X) 的次数低于g(X)

19 译码 串行译码 每次只译一个接收比特,然后循环移位，继续译下一个接受比特
若校正子s(X)与Xn-1有错所对应的错误模式对应，则接受比特vn-1有错 得到修正接收多项式r1(X)=r0+r1X+…+rn-2Xn-2 +(rn-1+en-1)Xn-1，循环位移得到r1(1)(X)=(rn-1+en-1) +r0X+r1X2+…+rn-2Xn-1，且s1(1)(X)=s(1)(X)+1 Meggitt译码器（算法）

20 循环码的差错检测能力 假设错误是突发错误，即错误模式e包含连续若干个1，(n,k)循环码能检测长度小于等于n-k的突发错误
证明：e(X)=XjB(X),B(X)的次数小于等于n-k-1，小于g(X)的次数，又因为g(X)和Xj互素，因此e(X)不是g(x)的倍式，故s(X)不为0。检测出错误。 长度为n-k+1的突发错误中，不能被检测的数目占2-(n-k-1);长度>n-k+1,不能被检测的2-(n-k) 证明：共有2 (n-k-1)种突发错误，不能被检测的只有当e(X)是g(x)的倍式;共有2 (n-k)种突发错误，不能被检测的2l-(n-k)-2种。 差错检测能力强！

21 （23，12）格雷码 生成多项式: 若g1(X)=1+X2+X4+X5+X6+X10+X11, g2(X)=1+X+X5+X6+X7+X9+X11 X23+1=(1+X)g1(X)g2(X)

22 （23，12）格雷码的系统搜索译码 通过循环位移，不大于3个错误的错误模式在特定11个连续位（校验位）之外至多有1个错误 步骤： 计算校正子
接收向量和校正子循环位移23次，检查校正子重量是否小于等于3，若满足则可纠错 若否，则对第一个信息位取反，重复上一步，检查是否有重量小于2的校正子，若有则第1位错，校正子指出其他两个错，完成译码 若上一步判断是否定的，则第1位正确，恢复第1位，类似检查第二个信息位，第三个…，直到第12个信息位 每种错误数目不大于3个错误模式，至少1个错误，一旦纠正了，会令其他的错误在连续的11位中，可用普通方式来纠正（通过逐一取反12个信息位，假设检验）。

23 准循环码 每次循环移动n0位， 若n0=1，就是循环码，否则就是准循环码 N0叫做移位约束 准循环码的对偶码也是准循环码

24 BCH码 BCH三个人：Bose, Chaudhuri, Hocquenghem 是一类循环码，是汉明码的推广，可纠正多个错误 定义：
对任意正整数m(m>2)和t(t<2m-1)，存在具有如下参数的BCH码 分组长度 n=2m-1 奇偶校验位数目 n-k<=mt 最小距离 dmin>=2t+1 该码能校正小于等于t个错误

25 g(X)的次数最多为mt，因为每个多项式的次数至多为m，也就是n-k<=mt
BCH码的生成多项式（本原BCH码） 设a是GF(2m)的生成元。码长为2m-1，纠正t个或少于t个错误的BCH码的生成多项式 就是以 为根的最低次多项式。 设 的最小多项式为 ，则 任何整数i都可以写成 i=i’2l，其中i’是奇数 ，我们有 ，当l>1时， 是 的共轭元，具有相同的最小多项式 ，故g(X)可写为 g(X)的次数最多为mt，因为每个多项式的次数至多为m，也就是n-k<=mt

26 非本原BCH码 给定正整数m(m>2)和t(t<2m-1)之后，通过选择FG(2m)中的本原元构建生成多项式获得本原BCH码
若选择的不是本原元，则得到非本原BCH码，n!=2m-1 BCH码就是循环码的生成多项式的根是连续的FG(2m)的元素 ，该码的最小距离至少为2t+1

27 BCH的码多项式 设码 ，其码多项式为： 故码多项式有生成多项式g(X)的全部根，也就是 及其共轭元，有一个码多项式的定义：当且仅当包含有 为根的多项式 称为码多项式 对1<=i<=2t，码多项式

28 BCH的码多项式 也就是向量内积： 对任意的1<=i<=2t，上式都成立，即码向量v和下列矩阵H的乘积为0
vHT=0 ，H是该码的校验矩阵

29 简化的校验矩阵H 码多项式 其共轭元 必然满足 H中偶数行的 是某个奇数行的共轭元，故H可以简化为如下：

30 BCH码的译码 假设发送码字 ，传输中的错误导致了 令错误模式为 有 译码第一步，计算校正子
假设发送码字 ，传输中的错误导致了 令错误模式为 有 译码第一步，计算校正子 令 的最小多项式为 ，并将接收向量写为： ，故有S的第i个分量 ，即在r(X)除以 的最小多项式的余式 中代入 ，得到 Si

31 例子：纠2个错误的（15，7）BCH码 α是GF(24)的本原元，且1+ α+ α4=0 α的最小多项式Φ1(X)=1+X+X4
α3的最小多项式Φ3(X)=1+X+X2+X3+X4 α5的最小多项式Φ5(X)=1+X+X2 码长：n=24-1=15, t=2的BCH码的生成多项式为: g(X)=LCM{Φ1(X), Φ2(X), Φ3(X), Φ4(X)}= LCM{Φ1(X), Φ3(X)} Φ1(X), Φ3(X)不可约，g(X)= Φ1(X)Φ3(X) = 1+X4+X6+X7+X8 （15，7）BCH，dmin=5

32 例子：纠2个错误的（15，7）BCH码 假设接收向量为(100000001000000),对应接收多项式为r(X)=1+X8
校正子有4个分量：S=(S1,S2,S3,S4) α， α2， α4的最小多项式 Φ1(X)=1+X+X4，r(X)/ Φ1(X)的余式 b1(X)=X2 α3的最小多项式 Φ3(X)=1+X+X2+X3+X4 ， r(X)/ Φ1(X)的余式 b3(X)=1+X3 S=(α2，α4 ， 1+α9 ， α8) =(α2，α4 ，α7 ， α8)

33

34 e(αj) = e0+e1αj+e2α2j+...+en-1α(n-1)j
假设错误模式有v个错误，位置分别为j1,j2,...,jv，那么就有 S1 = αj1+ αj αjv S2 = (αj1)2+ (αj2) (αjv)2 ... S2t = (αj1)2t+ (αj2)2t+...+ (αjv)2t 上面这些方程组中，校正子已知，要求位置j1,j2,...,jv，我们求αj1， αj2， ...，αjv即可

35 位置多项式 σ(X) = (1+ αj1X) (1+ αj2X)... (1+ αjvX) = σ0 + σ1X1 +...+ σvXv

36 BCH码的译码步骤 由接收多项式r(X)计算校正子 由校正子分量确定错误位置多项式 通过求解 的根，确定错误位置，并纠正r(X)中的错误