差错控制解析

会计学1差错控制解析学习要求1.理解差错控制的基本概念及其原理等；2.掌握信道编码的基本原理；3.了解常用检错码的特性；4.掌握线性分组码的一般特性；5.掌握汉明码以及循环码的编译码及其实现原理；6.掌握卷积码的编译码基本原理。第1页/共72页

10.1

差错控制的基本概念及原理1.差错分类10.1.1差错控制的基本概念随机差错：又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。

突发差错：是指一串串，甚至成片出现的差错，差错之间有相关性。目的：提高通信系统的可靠性噪声分类：随机噪声和脉冲噪声。误码产生原因：信道不理想造成的符号间干扰；噪声对信号的干扰。重点讨论由随机噪声引起由脉冲噪声引起第2页/共72页2.错误图样E中，“0”表示正确，“1”表示错误第3页/共72页

随机错误错误图样错误图样

突发错误错误图样第4页/共72页2.差错控制的基本思路

发送端：将被传送的信息码（无规律）按照一定的规则加入监督码元后进行传输，加入的监督码元与信息码元存在某种确定的约束关系。

接收端：检验信息码元与监督码元之间的既定的约束关系，如关系被破坏，则传输中有错。差错控制也称纠错编码，信道编码。

信息码(k)+监督码(r)=码组(n)第5页/共72页

信息码元(k)+监督码元(r)=码组(n)第6页/共72页3.差错控制方式（1）检错重发（ARQ）

优缺点——所需的监督码位数少，编码效率比较高；——译码设备较简单；——接收端检测到差错后，要通过反向信道发回NAK，要求发端重发，所以需要反向信道，实时性差ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。第7页/共72页a）停发等候重发b）返回重发c）选择重发第8页/共72页（2）前向纠错（FEC）

优缺点——

不需要反向信道，自动纠错，不要求重发，因而实时性好；——

缺点是所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；——

要纠正较多的错码，译码设备复杂，且要求附加的监督码较多，编码效率低。第9页/共72页（3）混合纠错检错（HEC）是ARQ和FEC方式的折衷方案

优缺点——

集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性，但需要反向信道。第10页/共72页（4）信息反馈（IRQ）数据信息

数据信息

（d）信息反馈

优缺点优点是不需要纠错、检错，设备简单；缺点是需要和前向信道相同的反向信道，实时性差，且发送端需要一定容量的存储器。第11页/共72页10.1.2差错控制的基本原理1.差错控制的原理AB0

01

1010110准用码组禁用码组无检错能力无纠错能力可检测1位错码举例说明信息位1无监督位信息位1监督位1方案1方案2第12页/共72页10.1.2差错控制的基本原理（续）1.差错控制的原理（续）AB0

001

11001010100011101110准用码组禁用码组可检测1到2位错码，或纠1位错码要想具有检错和纠错能力，必须有禁用码组。禁用码组的获得方法：加监督位。方案3信息位1监督位2第13页/共72页码长：码组或码字中编码的总位数为码组的长度。2.汉明距离与检错和纠错能力的关系（1）几个概念码重：码组中非零码元的数目为码组的重量。例如“11010”的码长为5，码重为3。码距：两个等长码组中对应码位上具有不同二进制码的数目称为码距。例如：码组111010

码组201101码距：d0

=4汉明距离（最小码距）：dmin

在一种编码中，任意两个许用码组间距离的最小值。000001010100111011101110dmin

=1第14页/共72页（2）汉明距离和检错和纠错能力的关系a)为了检测e位错码，要求最小码距b)为了纠正t位错码，要求最小码距c)为了纠正t位错码，同时检测e(e>t)位错码，要求最小码距第15页/共72页3.纠错编码的分类(1)按码组的功能分，有检错码和纠错码两类。(2)按码组中监督码元与信息码元之间的关系分，有线性码和非线性码两类。(3)按照信息码元与监督码元的约束关系，可分为分组码和卷积码。(4)按照信息码元在编码前后是否保持原来的形式不变，可分为系统码和非系统码。(5)按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码。(6)按照每个码元取值来分，可分为二进制码与多进制码。第16页/共72页10.2.1奇偶监督码

10.2简单的差错控制编码特点：只有一个监督位。偶监督：码组中“1”的个数为偶数。信息位监督位奇监督：码组中“1”的个数为奇数。只能检出奇数位错码。第17页/共72页10.2.2水平奇偶监督码

思想方法：将信息码序列按行排成方阵，每行后面加一个奇或偶监督码，即每行为一个奇（偶）监督码组，但发送时则按列的顺序传输：111011100110000…10101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。

信息码元

监督码元11100110001101001101100001110100010000101100111011

10101水平偶监督码可以检出奇数位错误和长度不大于方阵中行数的突发错误。第18页/共72页10.2.3二维奇偶监督码（水平垂直奇偶监督码）

思想方法：在水平监督基础上对方阵中的每一列再进行奇偶校验。发送时按行或按列的顺序传输，接收端重新将码元排成与发送时的方阵形式，然后每行、每列都进行奇偶校验。二维偶监督码

信息码元

监督码元1110011000110100110110000111010001000010110011101110101监督码元01101100011可以纠1位错码；可以检出某行或某列上的奇数位错码和长度不大于方阵中行数(列数)的突发错码；可以检出一部分偶数位错码；不能检出错码恰好分布在矩阵4个顶点上的偶数位错码。第19页/共72页

10.3

汉明码及线性分组码汉明码特点

可以纠正一位错码，且d0=310.3.1汉明码

1.码长和监督位的关系：若使用偶监督：只有一位监督位接收端译码时，实际上就是计算：若无错；有错。奇监督相反校正子1位监督位，有1个校正子。只能表示有错和无错，不能指示错码位置。第20页/共72页

码长和监督位的关系2位监督位，就有2个监督关系式，也有2个校正子。如果无错指示错码位置（n,k）汉明码，监督位r=n-k，可构造出r个监督关系式来指示一位错码的n种可能位置，要求若为：第21页/共72页1.（7,4）汉明码a6

a5

a4

a3：信息码元；a2

a1

a0：监督码元信息码元与监督码元的关系：第22页/共72页表10.3.1（7,4）汉明码的许用码组P322——假设发送端的码字是A15=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

a0000000010010001101000101011001110000

0000001

0110010

1010011

1100100

110010

1

1010110

0110111

000100010011010101111001101111011111000

1111001

1001010

0101011

0011100

0011101

0101110

1001111

111第23页/共72页1.（7,4）汉明码

s1s2s3

错码位置

000

无错001a0

010a1

100a2

011a3

101a4

110a5

111a6

校正子与错码位置的关系有3个校正子第24页/共72页例10-1

接收端收到某（7,4）汉明码为1001010，问：此（7,4）汉明码是否有错？错码位置如何？解：计算校正子得校正子为110，码组有错。正确码组：1101010第25页/共72页2）（7,4）汉明码的产生由监督关系式：发端无错移项，解出监督位：解决问题：由信息位计算监督位第26页/共72页例10-2

已知信息码为1101，求所对应的（7,4）汉明码。解：计算监督位汉明码码组：1101010监督位3）编码效率（7,4）汉明码的编码效率：第27页/共72页10.3.2线性分组码线性码：监督码元与信息码元之间满足一组线性方程。分组码：监督码元仅对本码组中的码元起监督作用。1.监督矩阵以（7,4）汉明码为例改写为简写为+线性分组码：既是线性码又是分组码。。第28页/共72页写成矩阵形式监督矩阵简写为单位方阵P第29页/共72页用矩阵表示为

其中：

监督位

信息位

监督位与信息位的关系（矩阵表示）第30页/共72页2.生成矩阵用途：由信息位和生成矩阵可得出整个码组。生成矩阵：以（7,4）汉明码为例生成矩阵第31页/共72页如（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

a0000000010010001101000101011001110000

0000001

0110010

1010011

1100100

110010

1

1010110

0110111

000100010011010101111001101111011111000

1111001

1001010

0101011

0011100

0011101

0101110

1001111

111第32页/共72页求整个码组注意：生成矩阵G各行本身就是一个码组。加例题！二元域上只有两种运算：加和乘。运算规则如下：加乘第33页/共72页3.监督矩阵和生成矩阵的关系例10-3

（课后练习）某（7,4）线性分组码，监督方程如下，求监督矩阵H和典型的生成矩阵G。如信息码为0010，求整个码组。解：监督方程改写为第34页/共72页得监督矩阵：典型生成矩阵：如信息码为0010，则整个码组为第35页/共72页4.线性分组码的主要性质(1)封闭性是指一种线性分组码中的任意两个码组之逐位模2和仍为这种码中的另一个许用码组。(2)码的最小距离等于非零码的最小重量。

5.线性分组码的纠错能力第36页/共72页

10.4

循环码循环码是一种线性分组码。10.4.1

循环码的循环特性表10.4.1（7,3）循环码的一种码组P328

码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010

循环码的循环特性是指在循环码中任一许用码组经过循环移位后所得到的码组仍为它的一个许用码组。

第2码组右移1位得到第5码组；

第5码组右移1位得到第7码组。第37页/共72页2.码多项式的表示及运算规则例如，码组为则码多项式为：

码多项式的运算：加、减、乘、除运算1）码多项式的加法运算：同幂次相加，系数进行异或运算2）码多项式的减法运算：同加法运算码组为则码多项式为：第38页/共72页ABC0000111011103）异或运算（逻辑加和逻辑减）的真值表4）码多项式的乘法运算：服从一般的代数规律5）码多项式的除法运算：服从一般的代数规律6）码多项式的除法运算简化表示例如上式还可表示为第39页/共72页10.4.2

循环码的生成多项式和生成矩阵

1.生成多项式g(x)

生成多项式的寻找方法：

（n,k）循环码的个码组中，有一个码组前k-1位码元均为0，第k位码元为1，最后一位为1，此码组对应的多项式为生成多项式。例10-5

求表10.4.1所示的（7,3）循环码的生成多项式。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010解：生成多项式第40页/共72页

2.生成矩阵G

典型的生成矩阵

通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵单位方阵第41页/共72页例10-5（续）

求表10-6所示的（7,3）循环码的典型生成矩阵G。解：

生成矩阵多项式

生成矩阵非典型矩阵典型矩阵第42页/共72页

3.生成多项式的另一种求法

（n,k）循环码的生成多项式是的一个（n-k）次因式。例

求（7,3）循环码的生成多项式。解：生成多项式有两个：表10.4.1循环码用生成多项式不同，产生出的循环码码组也不同。第43页/共72页10.4.3

循环码的编码方法步骤：信息位对应的码多项式：循环码的码多项式第44页/共72页10.4循环码的编码——当M=110，所以——即所得的码字为A=1100101。第45页/共72页10.4.4

循环码的解码方法1.检错的实现无差错发送码组接收码组若码组无错判别方法若码组有错，则接收码组若码组无错检测到差错解码器的核心：除法器第46页/共72页10.4循环码——r级线性移位寄存器的初始状态为全零，所有开关均向下连通；——在寄存器时钟的控制下进行k次移位，输出M(x)的系数(即信息码组)，同时实现除法电路的功能；

编码器工作过程第47页/共72页10.4循环码——所有开关向下连通，输入下一组信息重复上述过程。

实例分析——所有开关均倒向上方连通，在寄存器时钟的控制下再经过r=n-k

次移位，将监督元输出到信道；——本节前面给出的(7，3)循环码生成多项式：g(x)=x4+x2+x+1

由其可得编码电路如下图所示：第48页/共72页10.4循环码——假设M=110，编码器工作过程如下表所示输入移位寄存器状态反馈输出R1R2R3R4f0000000m2m1m0110111100101010111110信息元0000000010000100001001010101监督元a6a5a4a3a2a1a0第49页/共72页循环码的编码器电路设计第50页/共72页2.纠错的实现概念：错误图样发送码组接收码组错误码组错误码组的各种不同的具体采样称错误图样纠错的步骤：得原发送码组。第51页/共72页10.4循环码

纠错译码原理——确定循环码的纠错能力;——根据[模g(x)]计算伴随式，若S(x)≠0则判定传输出错。——根据[模g(x)]找到校正子对应的错误图样——由A(x)=B(x)+E(x)纠错。第52页/共72页10.4循环码——检错译码原理图：P334，335第53页/共72页10.4循环码——寄存器置零，开关S向下连通；——在寄存器时钟的控制下经n次移位后将接收码字B输入，此时寄存器中存储的即校正子(n，k)循环码校正子计算电路

其工作过程如下：

——将开关向上打开，经r=n-k次移位读出校正子。第54页/共72页国际通信中常用的是循环冗余校验（CRC）生成多项式为：CRC--32CRCIS-95CDMA第55页/共72页10.6卷积码本节内容提要：——卷积码是一类非线性有记忆编码，本节将简要介绍卷积码的编译码原理。

10.6.1卷积码编码器

10.6.2卷积码的解析描述

10.6.3卷积码的图解描述

10.6.4维特比译码原理第56页/共72页

10.6

卷积码卷积码又称连环码，是非分组码。没有严格的代数结构10.6.1

卷积码的基本概念

卷积码的监督位不仅取决于这段时间的k个信息位，还取决于前N-1段规定时间内的信息位。1.卷积码的概念编码效率：

即卷积码的监督位不仅对本码组起监督作用，对前N-1个码组也起监督作用。这N段时间内的码元数目nN称为约束长度。卷积码的表示方式：(n,k,N)第57页/共72页10.6.1卷积编码器(n，k，N)卷积编码器结构第58页/共72页10.6.1卷积编码器——(3，1，3)卷积码的两种等效编码器

实例分析3级编码器n=3,k=1:每输入一个信息比特，产生