1、第10章 差错控制学习要求1.理解差错控制的基本概念及其原理等；2.掌握信道编码的基本原理；3.了解常用检错码的特性；4.掌握线性分组码的一般特性；5.掌握汉明码以及循环码的编译码及其实现原理；6.掌握卷积码的编译码基本原理。10.1 差错控制的基本概念及原理1.差错分类10.1.1 差错控制的基本概念随机差错：又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。突发差错：是指一串串，甚至成片出现的差错，差错之间有相关性。目的：提高通信系统的可靠性噪声分类：随机噪声和脉冲噪声。误码产生原因：信道不理想造成的符号间干扰；噪声对信号的干扰。2.错误图样BAEE中，“0”表示正确，“1”表
2、示错误下一页上一页 随机错误错误图样错误图样 突发错误错误图样2.差错控制的基本思路 发送端：将被传送的信息码（无规律）按照一定的规则加入监督码元后进行传输，加入的监督码元与信息码元存在某种确定的约束关系。接收端：检验信息码元与监督码元之间的既定的约束关系，如关系被破坏，则传输中有错。差错控制也称纠错编码，信道编码。信息码(k)+监督码(r)=码组(n)信息码元(k)+监督码元(r)=码组(n)3.差错控制方式（1）检错重发（ARQ）优缺点所需的监督码位数少，编码效率比较高；译码设备较简单；接收端检测到差错后，要通过反向信道发回NAK，要求发端重发，所以需要反向信道，实时性差ARQ有有3种重发
3、方式，即停发等候重发，返回重发和选择重发。种重发方式，即停发等候重发，返回重发和选择重发。a）停发等候重发b）返回重发c）选择重发（2）前向纠错（FEC）优缺点 不需要反向信道，自动纠错，不要求重发，因而实时性好；缺点是所选择的纠错码必须与信道的错码特性密切配合，否则 很难达到降低错码率的要求；要纠正较多的错码，译码设备复杂，且要求附加的监督码较多，编码效率低。（3）混合纠错检错（HEC）是ARQ和FEC方式的折衷方案 优缺点 集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性，但需要反向信道。（4）信息反馈（IRQ）数据信息 数据信息 （d）信息反馈 优缺
4、点 优点是不需要纠错、检错，设备简单；缺点是需要和前向信道相同的反向信道，实时性差，且发送端需要一定容量的存储器。10.1.2 差错控制的基本原理1.差错控制的原理10.1.2 差错控制的基本原理（续）1.差错控制的原理（续）要想具有检错和纠错能力，必须有禁用码组。禁用码组的获得方法：加监督位。码长：码组或码字中编码的总位数为码组的长度。2.汉明距离与检错和纠错能力的关系（1）几个概念码重：码组中非零码元的数目为码组的重量。例如“11010”的码长为5，码重为3。码距：两个等长码组中对应码位上具有不同二进制码的数目 称为码距。例如：码组1 11010 码组2 01101汉明距离（最小码距）：在
5、一种编码中，任意两个许用码组间距离的最小值。（2）汉明距离和检错和纠错能力的关系a)为了检测e位错码，要求最小码距 min1de b)为了纠正t位错码，要求最小码距 min21dt c)为了纠正t位错码，同时检测e(et)位错码，要求最小码距 min1det 3.纠错编码的分类(1)按码组的功能分，有检错码和纠错码两类。(2)按码组中监督码元与信息码元之间的关系分，有线性码和 非线性码两类。(3)按照信息码元与监督码元的约束关系，可分为分组码和 卷积码。(4)按照信息码元在编码前后是否保持原来的形式不变，可分为系统码和非系统码。(5)按纠正差错的类型可分为纠正随机错误的码和纠正突发 错误的码。
6、(6)按照每个码元取值来分，可分为二进制码与多进制码。10.2.1 奇偶监督码 10.2 简单的差错控制编码特点：只有一个监督位。偶监督：码组中“1”的个数为偶数。1210,nnaaa a 12100nnaaaa 信息位监督位奇监督：码组中“1”的个数为奇数。12101nnaaaa 只能检出奇数位错码。10.2.2 水平奇偶监督码 思想方法：将信息码序列按行排成方阵，每行后面加一个奇或偶监督码，即每行为一个奇（偶）监督码组，但发送时则按列的顺序传输：11101110011000010101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。信信 息息 码码 元元 监督码元监督码元
7、 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1水平偶监督码可以检出奇数位错误和长度不大于方阵中行数的突发错误。10.2.3 二维奇偶监督码（水平垂直奇偶监督码）思想方法：在水平监督基础上对方阵中的每一列再进行奇偶校验。发送时按行或按列的顺序传输，接收端重新将码元排成与发送时的方阵形式，然后每行、每列都进行奇偶校验。二维偶监督码 信信 息息 码码 元元 监督码元监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1
8、 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1监督码元监督码元 0 1 1 0 1 1 0 0 0 1 1可以纠1位错码；可以检出某行或某列上的奇数位错码和长度不大于方阵中行数(列数)的突发错码；可以检出一部分偶数位错码；不能检出错码恰好分布在矩阵4个顶点上的偶数位错码。10.3 汉明码及线性分组码汉明码特点 可以纠正一位错码，且d0=310.3.1 汉明码 1.码长和监督位的关系：1021nnaSaaa 若使用偶监督：只有一位监督位 0a接收端译码时，实际上就是计算：0S 1
9、S 若 无错；有错。1位监督位，有1个校正子。只能表示有错和无错，不能指示错码位置。21rn 7,44,3,kr如汉明码，只能纠一位错码 码长和监督位的关系2位监督位，就有2个监督关系式，也有2个校正子。12S S1200 01 10 11S S ，无错 指示错码位置（n,k）汉明码，监督位 r=n-k，可构造出r个监督关系式 来指示一位错码的n种可能位置，要求346035614562aaaaaaaaaaaa1.（7,4）汉明码）汉明码a6 a5 a4 a3：信息码元；a2 a1 a0：监督码元信息码元与监督码元的关系：表10.3.1（7,4）汉明码的许用码组 P322假设发送端的码字是A15
10、=1111111，传输过程中第4位a3出现了错误，即接收的码字是B=1110111 不是许用码组。信息码a6 a5 a4 a3码组Aa6 a5 a4 a3 a2 a1 a0信息码a6 a5 a4 a3码组Aa6 a5 a4 a3 a2 a1 a00 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0 0 0 0 00 0 0 1 0 1 10 0 1 0 1 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 0 1 1 0 10 1 1 0 0 1 10 1 1 1 0 0 01 0 0 01 0 0 11 0
11、 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 11 0 0 0 1 1 11 0 0 1 1 0 01 0 1 0 0 1 01 0 1 1 0 0 11 1 0 0 0 0 11 1 0 1 0 1 01 1 1 0 1 0 01 1 1 1 1 1 11.（7,4）汉明码汉明码16542Saaaa s1 s2 s3 错码位置错码位置 0 0 0 无错 0 0 1 a0 0 1 0 a1 1 0 0 a2 0 1 1 a3 1 0 1 a4 1 1 0 a5 1 1 1 a6 校正子与错码位置的关系26531Saaaa 36430Saaaa 3r 有3个校正子1
12、23,SSS例例10-1 接收端收到某（7,4）汉明码为1001010，问：此（7,4）汉明码是否有错？错码位置如何？计算校正子1654210001Saaaa 2653110111Saaaa 3643010100Saaaa 得校正子 为110，123S S S码组有错。5a正确码组：1101010 346035614562aaaaaaaaaaaa654265316430000aaaaaaaaaaaa 2）（）（7,4）汉明码的产生汉明码的产生由监督关系式：移项，解出监督位：解决问题：由信息位计算监督位解决问题：由信息位计算监督位例例10-2 已知信息码为1101，求所对应的（7,4）汉明码。计
13、算监督位26541100aaaa 16531111aaaa 06431010aaaa 汉明码码组：11010103）编码效率编码效率（7,4）汉明码的编码效率：457%7kRn 10.3.2 线性分组码线性码：监督码元与信息码元之间满足一组线性方程。分组码：监督码元仅对本码组中的码元起监督作用。1.监督矩阵以（7,4）汉明码为例654265316430000aaaaaaaaaaaa 654321065432106543210111010001101010010110010aaaaaaaaaaaaaaaaaaaaa 简写为+线性分组码：既是线性码又是分组码。6543210111010001101
14、0100210110010aaaaaaa 模111010011010101011001H写成矩阵形式00TTTHAAH 简写为r=P I265416530643aaaaaaaaaaaa 6251403111011011011aaaaaaa 2106543111110101011a a aa a a a 6543a a a aQ TQP 其中：监督位 信息位 监督位与信息位的关系（矩阵表示）2.生成矩阵用途：由信息位和生成矩阵可得出整个码组。生成矩阵：kGI Q 以（7,4）汉明码为例 120nnAaaaG 信信息息位位典典型型的的111110101011Q kGI Q 100011101001
15、1000101010001011 如（7,4）汉明码表中的第3个码组 P322信息码a6 a5 a4 a3码组Aa6 a5 a4 a3 a2 a1 a0信息码a6 a5 a4 a3码组Aa6 a5 a4 a3 a2 a1 a00 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0 0 0 0 00 0 0 1 0 1 10 0 1 0 1 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 0 1 1 0 10 1 1 0 0 1 10 1 1 1 0 0 01 0 0 01 0 0 11 0 1 01 0 1
16、11 1 0 01 1 0 11 1 1 01 1 1 11 0 0 0 1 1 11 0 0 1 1 0 01 0 1 0 0 1 01 0 1 1 0 0 11 1 0 0 0 0 11 1 0 1 0 1 01 1 1 0 1 0 01 1 1 1 1 1 166432106643Aa a a a a a aa a a aG 求整个码组 10001110100110001000101010001011 0010101 注意：生成矩阵G各行本身就是一个码组。加例题！二元域上只有两种运算：加和乘。运算规则如下：加乘0000 111 011 10 0 000 101 001 11 3.监督矩阵
17、和生成矩阵的关系 ,TrkH=PIQPGI Q 例例10-3（课后练习）某（7,4）线性分组码，监督方程如下，求监督矩阵H和典型的生成矩阵G。如信息码为0010，求整个码组。265316430543aaaaaaaaaaaa 654321065432106543210110110001011010001110010aaaaaaaaaaaaaaaaaaaaa 监督方程改写为得监督矩阵：110110010110100111001rHP I 110101011111TQP 典型生成矩阵：1000110010010100100110001111 kGI Q 如信息码为0010，则整个码组为 0010AG
18、 10001100100101001000100110001111 0010011 4.线性分组码的主要性质 (1)封闭性封闭性 是指一种线性分组码中的任意两个码组之逐位模是指一种线性分组码中的任意两个码组之逐位模2和仍为这种和仍为这种 码中的另一个许用码组。码中的另一个许用码组。(2)码的最小距离等于非零码的最小重量。码的最小距离等于非零码的最小重量。5.线性分组码的纠错能力 10.4 循环码循环码是一种线性分组码。10.4.1 循环码的循环特性表表10.4.1（7,3）循环码的一种码组）循环码的一种码组 P328 码组编号码组编号信息位信息位监督位监督位码组编号码组编号信息位信息位监督位监
19、督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010 循环码的循环特性是指在循环码中任一许用码组经过循环移位后所得到的码组仍为它的一个许用码组。第2码组右移1位得到第5码组；第5码组右移1位得到第7码组。12101210()nnnnA xaxaxa xa x1210(,)nnAaaa a2.码多项式的表示及运算规则 6431A xxxxx 1011011A 例如，码组为 则码多项式为：码多项式的运算：加、减、乘、除运算1）码多项式的加法运算：同幂次相加，系数进
20、行异或运算）码多项式的加法运算：同幂次相加，系数进行异或运算kkkkkkkkkkkcbabaxcxbxa 2）码多项式的减法运算：同加法运算）码多项式的减法运算：同加法运算kkkkxaxa-码组为码组为则码多项式为：则码多项式为：A B C0000111011103）异或运算（逻辑加和逻辑减）的真值表）异或运算（逻辑加和逻辑减）的真值表CBABABA4）码多项式的乘法运算：服从一般的代数规律）码多项式的乘法运算：服从一般的代数规律123xxx)1()1(2xxx)1)(1(2xx5）码多项式的除法运算：服从一般的代数规律）码多项式的除法运算：服从一般的代数规律11112223xxxxxx6）码
21、多项式的除法运算简化表示）码多项式的除法运算简化表示)1(1223xxxx模余式（模除式）被除式 例如例如上式还可表示为上式还可表示为10.4.2 循环码的生成多项式和生成矩阵 1.生成多项式 g(x)生成多项式的寻找方法：（n,k）循环码的 个码组中，有一个码组前k-1位码元均为0，第k位码元为1，最后一位为1，此码组对应的多项式为生成多项式。2k例例10-5 求表10.4.1所示的（7,3）循环码的生成多项式。码组编号码组编号信息位信息位监督位监督位码组编号码组编号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a010000000510010112001011
22、16101110030101110711001014011100181110010 421g xxxx 2.生成矩阵G 12kkxg xxg xG xxg xg x 典型的生成矩阵kGI Q 通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵单位方阵例例10-5（续）（续）求表10-6所示的（7,3）循环码的典型生成矩阵G。421g xxxx 生成矩阵多项式 2x g xG xxg xg x 6432532421xxxxxxxxxxx 生成矩阵101110001011100010111G 100101101011100010111 311 行行行行取取代代第第 行行 3.生成多项式的另一种求
23、法 （n,k）循环码的生成多项式是 的一个（n-k）次因式。1nx 例例 求（7,3）循环码的生成多项式。73231111xxxxxx 生成多项式有两个：3242111g xxxxxxx 3432111g xxxxxxx 表10.4.1循环码用生成多项式不同，产生出的循环码码组也不同。10.4.3 循环码的编码方法 1211210nnn kn kkkm xmxmxm xm x 信息位对应的码多项式：循环码的码多项式 1n kxm x 求求 2n kxm xr xq xg xg x 3n kA xxm xr x 下一页上一页10.4 循环码的编码当M=110，所以 即所得的码字为A=110010
24、1。xxxM2)(5624)()(xxxxxxMxkn)(111)()(222456xgxxxxxxxxxgxMxkn1)(2xxr1)()()(256xxxxrxMxxAkn10.4.4 循环码的解码方法1.检错的实现无差错 A x，发送码组 R x，接收码组 若码组无错 A xR x，R xrxQxg xg x A xR x 若码组有错，则 接收码组 若码组无错 0rx 0rx 检测到差错解码器的核心：除法器下一页上一页10.4 循环码r级线性移位寄存器的初始状态为全零，所有开关均向下连通；在寄存器时钟的控制下进行k次移位，输出M(x)的系数(即信息 码组)，同时实现除法电路的功能；编码器
25、工作过程下一页上一页10.4 循环码所有开关向下连通，输入下一组信息重复上述过程。实例分析所有开关均倒向上方连通，在寄存器时钟的控制下再经过r=n-k 次移位，将监督元输出到信道；本节前面给出的(7，3)循环码生成多项式：g(x)=x4+x2+x+1 由其可得编码电路如下图所示：下一页上一页10.4 循环码假设M=110，编码器工作过程如下表所示 输入移位寄存器状态反馈输出R1R2R3R4f0000000m2m1m0110111100101010111110信息元0000000010000100001001010101监督元a6a5a4a3a2a1a0循环码的编码器电路设计1)(245810
26、xxxxxxxg2.纠错的实现概念：错误图样 1210,nnAaaa a 发送码组接收码组 1210,nnRrrr r 1210,nnEeee e 2RAE 模模错误码组 错误码组的各种不同的具体采样称错误图样纠错的步骤：1,;g xR xA xE xrx 用用除除得得出出余余式式 2,rxE 按按余余式式用用查查表表或或算算得得到到可可确确定定位位置置；3A xR xE x 。得原发送码组。下一页上一页10.4 循环码 纠错译码原理确定循环码的纠错能力;根据 模g(x)计算伴随式，若S(x)0则判定传输出错。)()(xBxS根据 模g(x)找到校正子对应的错误图样)()(xExS由A(x)=
27、B(x)+E(x)纠错。下一页上一页10.4 循环码检错译码原理图：P334，335下一页上一页10.4 循环码寄存器置零，开关S向下连通；在寄存器时钟的控制下经n次移位后将接收码字B输入，此时寄存器中存储的即校正子(n，k)循环码校正子计算电路 其工作过程如下：),.,(011ssssSrr将开关向上打开，经r=n-k次移位读出校正子。121132121CRCxxxxx 国际通信中常用的是循环冗余校验（CRC）生成多项式为：16152161CRCxxx 161251CRCITUxxx 1245781011121622232632xxxxxxxxxxxxxxCRC-32CRC IS-95 CD
28、MA126781112131520212930 xxxxxxxxxxxxx10.6 卷积码下一页上一页本节内容提要：卷积码是一类非线性有记忆编码，本节将简要介绍卷积码的编 译码原理。10.6.1 卷积码编码器 10.6.2 卷积码的解析描述 10.6.3 卷积码的图解描述 10.6.4 维特比译码原理 10.6 卷积码卷积码又称连环码，是非分组码。没有严格的代数结构10.6.1 卷积码的基本概念 卷积码的监督位不仅取决于这段时间的k个信息位，还取决于前N-1段规定时间内的信息位。1.卷积码的概念编码效率：即卷积码的监督位不仅对本码组起监督作用，对前即卷积码的监督位不仅对本码组起监督作用，对前N
29、-1个码组个码组也起监督作用。也起监督作用。这这N段时间内的码元数目段时间内的码元数目nN称为约束长度。称为约束长度。卷积码的表示方式：(n,k,N)kRn 下一页上一页10.6.1 卷积编码器(n，k，N)卷积编码器结构 下一页上一页10.6.1 卷积编码器(3，1，3)卷积码的两种等效编码器 实例分析 3级编码器 n=3,k=1:每输入一个信息比特，产生3个输出比特；S1、S2、S3：移存器321331211ssscsscsc下一页上一页10.6.2 卷积码的解析描述仍然以上图中的(3，1，3)卷积码为例，由其单位冲击响应可构造生成矩阵为：生成矩阵法 其中未写出的元素为0。和分组码不同，卷
30、积码并不以块的形式出现，即其码字可能无限长，故上式所示的矩阵称为半无限矩阵 011001111011001111011001111011001111321321321321VVVVVVVVVVVVg下一页上一页此时卷积码可由C=MG得到，例如M=11101时01100110001010111011101100111101100111101100111101100111101100111111101C10.6.2 卷积码的解析描述下一页上一页卷积编码器也可以用n个生成多项式来描述，分别对应n个输出支路。生成多项式法 (3，1，3)卷积码编码器 上图所示的卷积编码器可以用以下所示的3个生成多项式描
31、述 232211)(1)(1)(xxxgxxgxg10.6.2 卷积码的解析描述下一页上一页则对应的码多项式为所以对应的码字是：C=111 110 101 010 100 001 011输入信息为M=11101，对应的多项式为 则各支路码多项式分别为：421)(xxxxM65233632242111)()()(1)()()(1)()()(xxxxgxMxcxxxxgxMxcxxxxgxMxc65432321110100001010101011111)()()()(xxxxxxxcxcxcxC10.6.2 卷积码的解析描述下一页上一页10.6.3 卷积码的图解描述 实例分析以下图所示的(3，1，
32、3)卷积码器mj、mj-1、mj-2：移存器；y1、y2、y3：3个输出比特。实线虚线000111110 001011010100101 状态图法 10.6.3 卷积码的图解描述 假设初始状态为a，输入序列为M=110101，则有状态图很容易得到编码序列为C=111 110 010 100 001 100。下一页上一页10.6.3 卷积码的图解描述 树图法 输入为110101时，编码输出为111 110 010 100 001 100，如图中虚线所示 下一页上一页10.6.3 卷积码的图解描述 网格图法 实线：传 0虚线：传 1粗实线：编码过程下一页上一页10.6.4 维特比译码原理（有错）收码：1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1红线：码距最小的幸存路径通信理论教研室 518
