第6章 编码技术 6.1 概述 6.2 常用的差错控制编码 6.3 线性分组码 6.4 循环码 6.5 卷积码.

Presentation on theme: "第6章 编码技术 6.1 概述 6.2 常用的差错控制编码 6.3 线性分组码 6.4 循环码 6.5 卷积码."— Presentation transcript:

1 第6章 编码技术 6.1 概述 6.2 常用的差错控制编码 6.3 线性分组码 6.4 循环码 6.5 卷积码

2 6.1 概述 6.1.1 信源编码与信道编码 6.1.2 差错控制与编码分类 6.1.3 差错控制能力与编码效率 差错控制方式

3 6.1.1 信源编码与信道编码 信源编码(有效性编码) 信道编码(可靠性编码) 去除冗余 降低传输速率 添加冗余
降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性

4 6.1.2 差错控制与编码分类 差错控制编码 理论依据：香农信道编码定理
基本思想：通过对信息码元序列作某种变换,使原来彼此相互独立,没有关联的信息码元序列,经过这种变换后,产生某种规律性或相关性,使在接收端可根据这种规律性来检查,以至纠正传输序列中的差错 实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系…… 简单例子

5 香农信道编码定理 对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。

6 举例说明：假如要传送A、B两个消息 编码一： 消息A----“0”；消息B----“1”
若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。

7 编码二： 消息A----“00”；消息B----“11”
若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。 这表明增加一位冗余码元后码具有检出一位错码的能力

8 编码三： 消息A----“000”；消息B----“111”
传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。 在产生一位错码情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。 这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。

9 可见 纠错编码之所以具有检错和纠错能力，确实是因为在信息码元外添加了冗余码元（监督码元）
一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。

10 6.1.2 差错控制与编码分类 差错分类 随机差错／独立差错 突发差错 差错的出现随机，且差错之间是统计独立的 由随机噪声引起
存在这种差错的信道称为随机信道／无记忆信道 突发差错 差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关 因脉冲噪声，也可能是由存储系统中磁带的缺陷或读写头接触不良引起 存在这种差错的信道称为突发信道／有记忆信道

11 6.1.3 差错控制能力与编码效率 几个概念 码重：码字中非零码元的数目定义为该码字的重量，简称码重。如“10011”码字的码重为3。
码距：两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，称为汉明（Hamming）距离,简称码距。如两码字“10011”与“11010”间码距为2。 最小码距：在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为d0

12 最小码距与检、纠错能力关系 反之，若码的最小距离为d0，则最多能检测d0-1个错码。
一个码能检测e个错码，则要求其最小码距 d0≥e+1 反之，若码的最小距离为d0，则最多能检测d0-1个错码。 一个码能纠正t个错码，则要求其最小码距 d0≥2t+1 反之，若码的最小距离为d0，则最多能纠正(d0-1)/2个错码。 一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 d0≥e+t+1 (e>t)

13

14 Pn(r)=Cnr Per(1- Pe)n-r≈[n!/r!(n-r)!] Per
差错控制编码的效果 假设随机信道中发送“0”码与发送“1”码传错概率相等,为Pe,且Pe<<1 则在码长为n的码组中发生r个错误的概率为： Pn(r)=Cnr Per(1- Pe)n-r≈[n!/r!(n-r)!] Per

15 差错控制编码的效果 当码长n=7, Pe=10-3时，则有P7(1)≈7 Pe=7× 10-3 P7(2)≈21 Pe2=2.1× 10-5

16 编码效率 指一个码组中信息位所占比重，用η表示 η=k/n，其中k为信息码元的数目，n为码长

17 6.1.4 差错控制方式 接收端按一定规则对收到的码组进行有无错误的判别。若发现有错，则通知发送端重发，直到正确收到为止。 发 收
能够发现错误的码 判决信号 发 收 检错重发(ARQ) ARQ- Automatic Repeat-reQuest 接收端按一定规则对收到的码组进行有无错误的判别。若发现有错，则通知发送端重发，直到正确收到为止。

18 发 收 (b) 前向纠错（FEC） 发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正
不需要反馈信道，特别适合只能提供单向信道场合自动纠错，不要求检错重发，延时小，实时性好纠错码必须与信道的错误特性密切配合 若纠错较多，则编、译码设备复杂，传输效率低

19 在实时性和译码复杂性方面是FEC和ARQ的折衷。
能够发现和纠正错误的码 发 收 (c)混合纠错检错（HEC） 判决信号 FEC与ARQ的结合 发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。 在实时性和译码复杂性方面是FEC和ARQ的折衷。

20 数据信息 发 收 (d)信息反馈 收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，并把有错误的数据序列再次传送，直到发端没有发现错误。 不需要纠错、检错的编、译码器，设备简单。 需要和正向信道相同的反向信道，实时性差。 发端需要一定容量的存储器以存储发送码组。 仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统。

21 6.2 常用的差错控制编码 奇偶校验码 二维奇偶校验码 群计数码

22 奇偶校验码 在信息码元后附加一位监督位，使得码组中“1”的个数为偶数或奇数 只能检测出单个或奇数个错误，不能纠错
应用：以随机错误为主的计算机通信系统，难于对付突发错误 最小码距dmin=2 计算机内部的数据传送，就是采用这种码

23 水平奇偶监督码 将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶监督码，但发送时按列的顺序传输
接收端将码元排成发送时的方阵形式，再按行进行奇偶校验 能够发现某行上所有奇数个错误以及突发长度不大于方阵行数的突发错误

24

25 二维奇偶校验码 将水平奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输
接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验

26 二维奇偶校验码 能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误；并有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好分布在矩阵的四个顶点时，则检测不出 可纠正一些错误

27

28 群计数码 码组中的监督码元是信息序列中“1”码个数的二进制表示 假设待编码信息序列为1011101，则编码后码组为1011101101
较强的检错能力，能检测出几乎所有形式的差错（除同时发生“0”变“1”和“1”变“0”的成对错误外）

29 等比码（恒比码） 每个码组中含“1”和“0”的个数的比例恒定，又称等重码
能检测出所有单个和奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出） 简单，适应于对字母或符号进行编码 恒比码是一种检错码 国际无线电报码就是一种恒比码

30 6.3 线性分组码 6.3.1&2 (n,k)线性分组码及构成原理 6.3.3 生成矩阵和一致校验矩阵 6.3.4 伴随式和检错能力
生成矩阵和一致校验矩阵 伴随式和检错能力 汉明码

31 汉明码的构造 回忆奇偶监督偶校验码 发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数。 接收端译码：
计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1⊕an-2 ⊕ ……⊕a0 … …… ……… ……（1） S=0认为没错，S=1认为有错。 （1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式

32 监督位增加到2位：有两个监督方程，两个伴随式；两个伴随式组合有四种（00表示无错，01、10、11表示一位错码的三种可能位置）
监督位增加到r位：可指示一位错码的（2r-1）个可能位置 一般说来，对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置，则要求： 2r-1≥n 即2r ≥k+r+1 …… …… …… ……（2）

33 举例：构造一（n，k)分组码，k=4并能纠正一位错码
欲纠正一位错码，由（2）式知r ≥3。取r=3，则n=k+r=7 设7位码元为：a6a5 ……a0；三个伴随式：S1、S2、S3；则可规定S1S2S3的八种组合与一位错码的对应关系如下（也可规定为另一种对应关系）：

34

35 从上表可见： 当一位错码发生在a2、a4、a5或a6上时，S1为1；否则为0。即a2、a4、a5和a6构成偶监督关系： S1= a2⊕a4⊕a5⊕a6 同理，a1、a3、a5和a6构成偶监督关系： S2= a1⊕a3⊕a5⊕a6 a0、a3、a4和a6构成偶监督关系： S3= a0⊕a3⊕a4⊕a6

36 发端编码原则 信息码元a6 、a5 、a4、a3来源于待编码的信息序列；
监督码元 a2 、a1、 a0的取值应根据信息码元按监督关系式来决定，即使上面三式中的S1、 S2 、S3均为0： a2⊕a4⊕a5⊕a6=0 a1⊕a3⊕a5⊕a6=0 …… …………（3） a0⊕a3⊕a4⊕a6=0

37 进一步推导得： a2=a4⊕a5⊕a6 a1=a3⊕a5⊕a6 …… …… …… ……（4） a0=a3⊕a4⊕a6
于是，给定信息位后，根据上式算出各监督位，于是该编码的所有码组如下表：

38

39 汉明码的编码电路如图7-7(a)所示

40 线性分组码 监督矩阵： 沿（7，4）汉明码出发，（3）式可改写成： 1×a6⊕1×a5⊕1×a4⊕0×a3⊕1×a2⊕0×a1⊕0×a0=0
……… (5)

41 写成矩阵形式： …………… (6)

42 可化简为： H·AT=0T 或A·HT=0 其中， H= 称为线性码监督矩阵

43 监督矩阵H r×n阶矩阵 监督矩阵H确定了编码时监督码元与信息码元的关系
把具有[P·Ir]形式的H矩阵称为典型形式的监督矩阵，其中P为r ×k阶矩阵, Ir为r ×r阶单位方阵 H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关

44 生成矩阵 （4）式也可写成矩阵形式，即 对（7）式两侧作矩阵转置，得： 与（6）式比较，可看出：（7）式右部前矩阵就是监督矩阵H中的P矩阵。
…………… (7)

45

46 构造矩阵G：在Q矩阵的左边加上一个k ×k阶矩阵，即 G=[IkQ]=
其中Q=PT可见，Q为k ×r阶矩阵。 构造矩阵G：在Q矩阵的左边加上一个k ×k阶矩阵，即 G=[IkQ]= 称为线性码的生成矩阵

47 生成矩阵G： k ×n阶矩阵 编码方法完全由生成矩阵G确定
把具有[Ik·Q]形式的G矩阵称为典型形式的生成矩阵，其中，Ik为k×k阶单位方阵，Q为k ×r阶矩阵 由典型生成矩阵产生的分组码一定是系统码 G矩阵的各行应线性无关，每行均为许用码组

48 举例 例6-1：设（7,4）线性码的生成矩阵G为： 当信息位为0001时，试求其后的监督位。

49 例6-2：试求上题的监督矩阵H 解：根据生成矩阵和监督矩阵的关系： G= [Ik·Q]，H=[P·Ir] 其中Q=PT，可得监督矩阵H为：

50 校正子与检错 错误矩阵/错误图样E：设发送码组为A，接收码组为R，则 E=R-A=[en-1, en-2, en-3……, e0]
接收端计算校正子S，即 S=RHT=（A+E）HT=AHT+EHT=0+ EHT= EHT 可见校正子只与E有关，即错误图样与校正子之间有确定的关系，所以可从错误图样与校正子的关系表中确定错码位置，加以纠正。

51 校正子与检错 以（7，4）汉明码为例， 设发送码组A=（0001011）， 接收码组R=（0000011）， 则收端译码过程如下：
计算校正子S=RHT=[ ]HT=[011]T 查表得a3为错误位置，即可纠正

52 线性分组码的主要性质 封闭性： 码的最小距离等于非零码的最小重量 指码中任意两许用码组之和仍为一许用码组。
证明：设A1和 A2为码中任意两许用码组，则有 A1·HT=0 A2·HT=0 于是A1·HT+ A2·HT=（ A1 + A2）·HT=0 即（ A1 + A2）必是该码中一许用码组 码的最小距离等于非零码的最小重量 由封闭性，两个码组之间的距离必是另一码组的重量

53 6.4 循环码 线性分组码中的一类重要码，且为系统码 与一般线性分组码相比，循环码还具有循环特性：
若（an-1，an-2，……，a1，a0)是一(n，k)循环码的码组，则（an-2，an-3，……，a1，a0 ，an-1) （an-3，an-4，…… ， a0 ， an-1 ，an-2) …… …… （ a0 ，an-1 ， an-2，an-3，……，a2，a1) 也都是该循环码的码组 （7，3）循环码(见教材P119 表6-3）

54

55 码多项式的按模运算 在整数除法中，设n为除数，把所有的整数按除以n所剩的余数进行分类──称为剩余类(或同余类)，这就是按模n运算。
例如，可把所有整数分为以下五类： 模2运算

56 码多项式的按模运算 码多项式的按模运算： 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和次数小于n的余式R(x)，即：F(x)=N(x)Q(x)+R(x) 则在按模N(x)运算下，有 F(x)≡R(x) (模N(x)) 此时，码多项式系数仍按模2与运算，即系数只取0和1。 例（樊P252）

57 A(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0
码多项式 我们把码字中码元当作多项式的系数(取值0或1)，把n长的码字写成最高次为n－1次的多项式 若码组A=（an-1，an-2，……，a1，a0)，则其相应的码多项式为：A(x)= an-1xn-1+ an-2xn-2+ ……+ a1x+ a0 对于（7，3）循环码的任意码组可表示为： A(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0

58 码多项式与码组的关系：本质上是一回事，仅是表示方法的不同而已
如码组（ ）对应的码多项式可表示为 A7(x)= 1·x6+1 · x5+ 0 · x4 + 0 · x3 + 1 · x · x+1 = x6 + x5 + x2 +1 码多项式与码组的关系：本质上是一回事，仅是表示方法的不同而已

59 重要结论 在循环码中，若A(x)是一个长为n的许用码组，则xi· A(x)在按模xn+1运算下，也是一许用码组。 即若
xi· A(x)≡Ai(x) （模xn+1）， 则Ai(x) 也是一许用码组，且为A(x)码组向左循环移位i次的结果。 一个长为n的(n，k)循环码，它必为按模xn+1运算的一个余式。

60 生成多项式与生成矩阵 问题：寻找构成生成矩阵的k个线性无关的许用码组 由封闭性，可知循环码中一定包含全0码组
于是(n，k)循环码中一定能找到这样一个码组：前面的k-1位都是0，而第k位及第n位为1，其它各位gi为0或1：（000…01gn-k-1gn-k-2 …g2 g11)

61 其对应的码多项式为g(x)，且 g(x)一定是码中唯一的一个n-k次多项式，这唯一的 n-k次多项式g(x)称为码的生成多项式
根据循环性，xg(x)，x2 g(x)， … …， xk-1g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x)：

62 注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵。

63 循环码的任一码多项式A(x)都是g(x)的倍式，即都可被g(x)整除；任一次数不大于(k-1）的多项式乘g(x)都是码多项式。
于是，码多项式A(x)可写成： A(x) =h(x)·g(x) 码多项式必定是xn+1的一个因式 循环码的生成多项式一定是xn+1的一个(n-k)次多项式 例如

64 编码方法：设信息位对应的多项式为m(x)
用xn-k乘m(x)，相当于将信息位移至码组的最前面 用g(x)除xn-k m(x)，得到余式为r(x) 编出码组为：A(x)= xn-k m(x)+ r(x)

65 举例： 设（7，3）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为110，则m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5 而 即余式r(x)=x2+1 于是，对应码组A(x)= x6+x5+ x

66 可见，上例编出的循环码就是系统码。 于是，以多项式形式表示的系统循环码的生成矩阵为： 其中,rn-i(x)是g(x)除xn-i (i=1,2,…，k)所得的余式。

67 译码方法 检错：用g(x)去除接收到的码组R(x)，根据余式是否为0，判断传输正误 纠错： 较之检错要复杂得多
要求每个可纠正的错误必须与一个特定的余式建立一一对应关系

68 3.循环码的生成多项式g(x)及生成矩阵G(x)
[定理1] 若T(x)是n长循环码中的一个码多项式，则xiT(x)按模xn＋1运算的余式，必为循环码中另一个码多项式，即一定有： 3.循环码的生成多项式g(x)及生成矩阵G(x) [定理2] 在循环码中，n-k次码多项式有一个，而且仅有一个 [定理3 ] 在循环码中，所有的码多项式都能被g(x)整除 推论：任何次数不大于k-1次的多项式与g(x)的乘积都是码多项式。 [定理4] 循环码的生成多项式g(x)是xn＋1的一个因式。 这个定理告诉我们，可以从xn＋1的因式分解中找出n-k次且常数项不为零的因式，把它作为n长循环码的生成多项式，从而确定了循环码的生成矩阵 4.循环码的编码和译码 当给定(n，k)循环码的信息码位m(x)和选定生成多项式g(x)后，我们就可以进行编码

69 以上编码过程可由除法电路实现，如(7,3)码g(x)＝x4＋x3＋x2＋1的除法电路示于图7-8
编码过程如下： 第一步：信息位向左移n-k＝4位,得xn-km(x)： 第二步：除法，求余数 第三步：拼加,T(x)＝xn-km(x)＋r(x) 以上编码过程可由除法电路实现，如(7,3)码g(x)＝x4＋x3＋x2＋1的除法电路示于图7-8

70 接收端译码的目的，可能是检错,也可能是纠错，其译码原理与实现有所不同
译码器的核心就是一个除法电路及缓冲移位寄存器。检错译码器的原理框图如图7-9所示

71 原则上纠错可以按以下步骤进行： ①用生成多项式g(x)除接收码组R（x）=c（x）+e（x），得出余式r(x)。 ②按余式r(x)用查表的方法或通过某种运算得到错误图样e（X）。 ③从R（x）中减去e（x），得到已纠正错误的原发送码组c（x）。现以（7,3）码为例给出一种纠错译码器的原理方框图，如图7-10所示

72 例6-3：试求（7，3）循环码的生成多项式和生成矩阵
解：对（7,3）循环码k=3 x7+1=(x+1)(x3+x2+1)(x3+x+1) n-k = 7-3 = 4次的因式有： (x+1)(x3+x2+1)=x4+x2+x+1……………(a) (x+1)(x3+x+1)=x4+x3+x2+1……………(b)

73 若按(a)构成生成多项式: 生成多项式为：g(x)= x4+x2+x+1 生成矩阵为：

74

75 将第1行与第3行模2加作为第1行，则有 为典型生成矩阵。

76 若按(b)构成生成多项式: 生成多项式为：g(x)= x4+x3+x2+1 生成矩阵为：

77

78 进行线性变换，得典型生成矩阵为：

79 缩短循环码 在(n，k)循环码的2k个码组集合中，选择前i个信息位为0的所有码组（共2k-i个），组成一个新的码组集合，这一新的码组集合就构成了(n-i，k-i)码，称它为(n，k)的缩短循环码。 例如要构造一个能够纠正一位错误的(12，8）码，我们可以从（15，11）汉明码中挑出前三位均为0的码组来构成。

80 缩短循环码 例如要构造一个能够纠正一位错误的(12，8）码，我们可以从（15，11）汉明码中挑出前三位均为0的码组来构成。

81 在(n，k)的缩短循环码中，每一个码组必定能被g(x)除尽（注： g(x)是原循环码的生成多项式）
每一个码组是原来循环码的码组，只是这码组的前i个信息码元为0，所以它必定能被g(x)除尽。 换言之，所有次数小于n-i次，且能被g(x)除尽的多项式都是(n-i，k-i)缩短循环码的码多项式。

82 在(n，k)的缩短循环码中，所有码组的前i位为0，故发送时可不发送这i个0，仅传输后面的n-i位码元。
(n-i，k-i)码的纠检错能力不低于原来的(n，k)循环码的纠检错能力。 缩短循环码的所有码组是原来循环码组集合中的一部分，且监督码元位数没变。

83 缩短循环码的生成矩阵可从原循环码的典型生成矩阵中除去前i行和前i列得到。
例如（7，3）循环码的一种典型生成矩阵为： 除去其第一行第一列，便得到（6，2）缩短循环码的生成矩阵G（6,2）。 缩短循环码的码组之间并不一定存在循环关系。

84 循环码的检错能力 能检出全部的单个错误： 能检出全部离散的二位错： 能检出全部的奇数个错码：
对应一位错码的错码多项式E(x)=xi，而多于一项的生成多项式g(x)=……+1，显然xi除以g(x)的余数不会等于0，也即能检测出全部单个错码。 能检出全部离散的二位错： 对应的错码多项式E(x)=xi+xj=xi(1+xj-i)，只要选取的g(x)不能除尽(xj-i+1)，且(n-k)>(j-i) 能检出全部的奇数个错码： 含有奇数项错码的多项式必不含(x+1)因子，只要选取的g(x)含有(x+1)因子

85 E(x)=xi(eb-1xb-1+ eb-2xb-2+……+e1x+1)= xi E1(x)
能检测所有长度不超过(n-k)的突发错误： 突发长度不大于b的突发错误对应的错码多项式为 E(x)=xi(eb-1xb-1+ eb-2xb-2+……+e1x+1)= xi E1(x) 由于g(x)除不尽xi； g(x)为n-k次多项式，只要E1(x)的次数b-1不超过(n-k-1)次， g(x)便除不尽E1(x)。也就是说，能检测长度不超过(n-k)的突发错误。

86 在突发长度b大于(n-k)的错误中，若b=n-k+1，则(n，k)循环码不能检测概率为2-(n-k-1)；若b>n-k+1，则不能检测概率为2-(n-k）。
设错码多项式为E(x)= xi E1(x) ，E1(x)的次数为(b-1)，必有x0 和xb-1项，还应有b-2项xj，因此共有2b-2种不同的多项式。 只有E1(x)有g(x)的因子时，即E1(x)= g(x) Q(x)时，这种错码才不能检测出来。 g(x)为(n-k)次，所以Q(x)定为[b-1-(n-k)]次；当b-1=n-k（即b=n-k+1），则Q(x)=1，此时仅有一个E1(x)= g(x)的错误图样不可检测，占突发错误图样总数的1/2b-2=2-(n-k-1)

87 BCH码 发现者：Hocguenghem(59)，Bose和 Chaudhuri(60) 特点：能纠正多个随机错误，并有严密的数学结构
循环码中一类重要子码：g(x)与dmin关系密切 BCH码的码长n与监督位、纠错能力t间关系： 对于任一正整数m和t(t>n/2)，必定存在一个码长n=2m-1，监督位n-k≤mt，能纠正所有不大于t个随机错误的BCH码

88 BCH码 分两类： 本原BCH码：g(x)中含有最高次数为m的本原多项式，且码长n= 2m-1
非本原BCH码： g(x)中不含这种本原多项式，且码长n是2m-1的一个因子

89 本原多项式（次数为m)：不含因式的既约多项式，能除尽 ，但除不尽xr-1，r< 2m-1。
例如m=3时， 2m-1=7， x7-1=（x+1)(x3+x2+1)(x3+x+1)，此时最高次数为3的本原多项式有两个：(x3+x2+1) 和(x3+x+1)，它们都能除得尽x7-1，但除不尽x6-1和x5-1

90 具有循环性质的汉明码就是纠正单个随机错误的本原BCH码：
汉明码是纠正单个随机错误的码，其码长n= 2m-1，k= 2m-1-m

91 BCH码的构造举例 例1：构造一个纠错能力为3，码长为15的BCH码。
查表9-8得：n=15，k=5，t=3的BCH码，对应码多项式标号为(2467)8=( )2，g(x)=x10+x8+x5+x4+x2+x+1

92 BCH码的构造举例 例2：试求Golay码（23，12）（非本原BCH码）码的生成多项式。
查表9-9得： （23，12）非本原BCH码对应码多项式标号为(5343)8=( )2 ，g(x)=x11+x9+x7+x6+x5+x+1

93 扩展BCH码 在BCH码上增加一奇偶校验位，扩展后码距增加1，同时具有检错、纠错能力，但不再是循环码了。

94 RS码 多进制BCH码 具有很强的纠错能力，特别适合于纠正突发错误 纠t个符号错误的(n,k) RS码：
码长n=2m-1 个符号 m(2m-1 ) bit 信息段k个符号 m·k bit 监督段n-k=2t个符号 m ·(n-k ) bit 最小码距dmin=2t+1个符号 m · (2t+1) bit

95 6.5 卷积码 几点说明： 又名连环码，是一种非分组码 与分组码相比，在同等码率和相似的纠错能力下，卷积码的实现往往更简单
6.5 卷积码 几点说明： 又名连环码，是一种非分组码 与分组码相比，在同等码率和相似的纠错能力下，卷积码的实现往往更简单 卷积码主要应用于FEC数据通信系统中

96 基本原理： 在任何一段规定时间里编码器产生的n个码元，不仅取决于这段时间中的k个信息码元,而且还取决于前m(m= N-1)段规定时间内的信息码元，编码过程中相互关联的码元为Nn个。 m或N段时间内的码元数目Nn称为卷积码的约束长度。 记作(n，k，N)或 (n,k,m)，编码效率R=k/n。

97 卷积码(2,1,2)编码器

98 起始状态，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定
表 (2,1,2)编码器的工作过程

99 卷积码的描述 1. 树图 (2,1,2)码的树图

100 2. 状态图 (2,1,2)码的状态图

101 3. 格图 (2,1,2)码的格图

102 卷积码的译码 1. 维特比译码 维特比译码格图

103 2. 序列译码 当m很大时，可以采用序列译码法。 其过程如下： 译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较， 沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后得到一条路径。若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门限值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。

104 举例说明：

105 编码： 输入信息码位一方面直接输出，另一方面可暂存在移位器中。每当输入编码一个信息位，就立即计算出一监督位，并且此监督位紧跟此信息位之后发送出去。 t m1 m2 m3 m4 t m1c1 m2c2 m3c3 m4c4

106 编码器工作过程：移位寄存器按信息位的节拍工作，输入一位信息，电子开关倒换一次，即前半拍（半个输入码元宽）接通m端，后半拍接通c端。
编码公式：c1=0+m1 c2=m1+m2 c3=m2+m3 …… ci=mi-1+mi

107 可见： 卷积码结构为：“信息码元、监督码元、信息码元、监督码元、 ……”。
一个信息码元和一个监督码元组成一组，但每组中的监督码元除与本组信息码元有关外，还跟上一组信息码元有关。

108 1 D2 D1 + 信息码 输出 卷积码 输入 D3 S m’c’ 3 2 译码： c’ 简单 (2,1,2)卷积码译码器

109 解码器工作过程 解码器输入端的电子开关按节拍把信息码元与监督码元分接到m’端与c’端；
3个移位寄存器的节拍比码序列节拍低一倍，其中移位寄存器D1，D2在信息码元到达时移位，监督码元到达期间保持原状；而移位寄存器D3在监督码元到达时移位，信息码元到达期间保持原状；

110 3. 移位寄存器D1，D2和模2加法器1构成与发端一样的编码器，它从接收到的信息序列中计算出对应的监督序列来；
4. 模2加法器2把③计算出的监督序列与接收到的监督序列进行比较：两者相同，输出“0”；两者不同，输出“1”，显然此时，必定出现了差错。 5. 如果有差错，则要确定差错位置并纠错

111 具体判决如下： 根据译码图，有校验子S的方程——即解码方程如下： S0=（0+m1’)+c1’ S1=（ m1’ +m2’)+c2’
…… Si=（ mi’ +mi+1’)+ci+1’

112 可见每个信息码元出现在两个S方程中，即mi’与Si-1和Si有关，在判决mi’是否有错时，应根据Si-1和Si的值。
（正交：决定Si-1和Si值的共有5个码元，但其中只有mi’与Si-1、Si两值都有关，而其他码元只与一个值有关，这称为方程Si-1与Si正交于mi’；或者说校验子方程Si-1与Si构成mi’的正交方程组。）

113 在差错不多于1个条件下，根据正交性得判决规则如下：
当Si-1、Si都为“0”时，解码方程与编码方程一致，判决无错 当Si-1、Si都为“1”时，必定是mi’有错，给予纠正 当Si-1、Si中只有一个“1”时，必定是mi’以外四个码元：mi-1’ 、mi+1’、 ci’ 及ci+1’中的一个出错，判决mi’无错 同样对其他信息码元进行判决。 完成上述判决规则的电路是译码器中的移位寄存器D3，与门及模2加法器3：

114 从该例可以看到：该码可以纠正连续3个码组中的一位差错（因为解码的正交方程组中，涉及5个码元，即3个码组）

115 卷积码的译码与编码过程类似 与分组码类似，卷积码也可用来检测和纠正错误 目前，无论从理论上还是从实际中，都已证明卷积码在性能上等于或优于分组码