数字通信原理与技术7差错控制编码课件

第7章差错控制编码7.1概述7.2常用的几种简单分组码7.3线性分组码7.4循环码7.5卷积码*7.6网格编码调制第7章差错控制编码7.1概述17.1概述7.1.1信道编码在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。7.1概述7.1.1信道编码27.1.2差错控制方式图7-1差错控制方式7.1.2差错控制方式图7-1差错控制方式3

1.检错重发方式检错重发又称自动请求重传方式，记作ARQ(AutomaticRepeatRequest)。由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效，但实时性差，主要在计算机数据通信中得到应用。1.检错重发方式42.前向纠错方式前向纠错方式记作FEC(ForwordErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。2.前向纠错方式53.混合纠错方式混合纠错方式记作HEC(HybridErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此，近年来得到广泛应用。3.混合纠错方式6另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道，错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。另外，按照噪声或干扰的变化规律，可把信道分为77.1.3纠错码的分类(1)根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。(2)根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。(3)根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。7.1.3纠错码的分类87.1.4纠错编码的基本原理1.分组码分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字未被选用，称为禁用码组。7.1.4纠错编码的基本原理1.分组码9在分组码中，非零码元的数目称为码字的汉明重量，简称码重。例如，码字10110，码重w=3。两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离，简称码距。例如11000与10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用d０表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。在分组码中，非零码元的数目称为码字的汉明重量102.检错和纠错能力若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。它是一种简单实用的检错码，并有一定的纠错能力。例如(2,1)重复码，两个许用码组是00与11，d0=2，收端译码，出现01、10禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是000与111,d0=3;当收端出现两个或三个1时，判为1，否则判为0。此时，可以纠正单个错误，或者该码可以检出两个错误。2.检错和纠错能力若分组码码字中的监督11码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内:(1)检测e个随机错误，则要求码的最小距离d0≥e+1;(2)纠正t个随机错误，则要求码的最小距离d0≥2t+1;(3)纠正t个同时检测e(≥t)个随机错误，则要求码的最小距离d0≥t+e+1。码的最小距离d0直接关系着码的检错和纠错能力123.编码效率用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:R=k/n其中,k是信息元的个数，n为码长。对纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。3.编码效率137.2常用的几种简单分组码7.2.1奇偶监督码奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。7.2常用的几种简单分组码7.2.1奇偶监督码14设码字A=［an-1,an-2,…,a1,a0］，对偶监督码有奇监督码情况相似，只是码组中“1”的数目为奇数，即满足条件而检错能力与偶监督码相同。奇偶监督码的编码效率R为设码字A=［an-1,an-2,…,a1,a0］，对偶监督码157.2.2行列监督码图7-2(66,50)行列监督码7.2.2行列监督码图7-2(66,50)行列监督码167.2.3恒比码码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的数目是否正确，就知道有无错误。

目前我国电传通信中普遍采用3∶2码，又称“5中取3”的恒比码，即每个码组的长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字，如表7-1所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。7.2.3恒比码码字中1的数目与017表7-13∶2恒比码表7-13∶2恒比码187.3线性分组码现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是监督元，可用下列线性方程组来描述该分组码，产生监督元。7.3线性分组码现以(7,4)分19表7-2(7,4)码的码字表表7-2(7,4)码的码字表207.3.2监督矩阵H和生成矩阵G

7.3.2监督矩阵H和生成矩阵G21其中,P为r×k阶矩阵，Ir为r×r阶单位矩阵。可以写成H=［PIr］形式的矩阵称为典型监督矩阵。HAT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。并简记为其中,P为r×k阶矩阵，Ir为r×r阶单位矩22若把监督方程补充为下列方程若把监督方程补充为下列方程23可改写为矩阵形式可改写为矩阵形式24数字通信原理与技术7差错控制编码课件257.3.3伴随式(校正子)S

设发送码组A=［an-1,an-2,…,a1,a0］，在传输过程中可能发生误码。接收码组B=［bn-1,bn-2,…,b1,b0］，则收发码组之差定义为错误图样E，也称为误差矢量，即其中E=［en-1,en-2,…,e1,e0］，且当bi=ai

当bi≠ai

(7-15)7.3.3伴随式(校正子)S设发送码组A=26式(7-15)也可写作令S=BHT，称为伴随式或校正子。式(7-15)也可写作令S=BHT，称为伴随式或校正子27表7-3(7,4)码S与E的对应关系表7-3(7,4)码S与E的对应关系287.4循环码表7-4(7,3)循环码7.4循环码表7-4(7,3)循环码29在代数理论中，为了便于计算，常用码多项式表示码字。(n,k)循环码的码字，其码多项式(以降幂顺序排列)为在代数理论中，为了便于计算，常用码多项式表示307.4.1生成多项式及生成矩阵如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如表7-4的(7,3)循环码中，7.4.1生成多项式及生成矩阵如果一种码的31其它码多项式都是g(x)的倍式，即其它码多项式都是g(x)的倍式，即32循环码的生成矩阵常用多项式的形式来表示循环码的生成矩阵常用多项式的形式来表示33例如(7,3)循环码，n=7,k=3,r=4,其生成多项式及生成矩阵分别为例如(7,3)循环码，n=7,k=3,r=4,其生成多347.4.2监督多项式及监督矩阵为了便于对循环码编译码，通常还定义监督多项式，令

其中g(x)是常数项为1的r次多项式，是生成多项式；h(x)是常数项为1的k次多项式，称为监督多项式。同理，可得监督矩阵H

7.4.2监督多项式及监督矩阵其中g(x)是常数项为135是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+x3+x2+1，则其中是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+36数字通信原理与技术7差错控制编码课件377.4.3编码方法和电路在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为循环码的码多项式可表示为7.4.3编码方法和电路在编码时，首先要38图7-3(7,3)循环码编码电路图7-3(7,3)循环码编码电路39表7-5(7,3)循环码的编码过程表7-5(7,3)循环码的编码过程407.4.4译码方法和电路图7-4(7,3)循环码译码电路7.4.4译码方法和电路图7-4(7,3)循环码译码417.5卷积码7.5.1基本概念图7-5卷积码(2,1,2)编码器7.5卷积码7.5.1基本概念图7-5卷积码42起始状态，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定表7-6(2,1,2)编码器的工作过程起始状态，各级移位寄存器清零，即S1S2S3437.5.2卷积码的描述1.树图图7-6(2,1,2)码的树图7.5.2卷积码的描述1.树图图7-6(2,1,442.状态图图7-7(2,1,2)码的状态图2.状态图图7-7(2,1,2)码的状态图453.格图图7-8(2,1,2)码的格图3.格图图7-8(2,1,2)码的格图467.5.3卷积码的译码1.维特比译码图7-9维特比译码格图7.5.3卷积码的译码1.维特比译码图7-9维特472.序列译码当m很大时，可以采用序列译码法。其过程如下：译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较，沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后得到一条路径。若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门限值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。2.序列译码48*7.6网格编码调制(TCM)网络编码调制(TrellisCodedModulation,缩写为TCM)技术。它是利用编码效率为n/(n+1)的卷积码，并将每一码段映射为2n+1个调制信号集中的一个信号。在收端信号解调后经反映射变换为卷积码，再送入维特比译码器译码。它有两个基本特点：(1)在信号空间中的信号点数目比无编码的调制情况下对应的信号点数目要多，这些增加的信号点使编码有了冗余，而不牺牲带宽。(2)采用卷积码的编码规则，使信号点之间引入相互依赖关系。仅有某些信号点图样或序列是允许用的信号序列，并可模型化成为网格状结构，因此又称为“格状”编码。*7.6网格编码调制(TCM)网络编码调制49图7–108PSK信号空间的集合划分图7–108PSK信号空间的集合划分50图7-10画出了一种8PSK信号空间的集合划分，所有8个信号点分布在一个圆周上，都具有单位能量。连续3次划分后，分别产生2,4,8个子集，最小欧氏距离逐次增大，即图7-10画出了一种8PSK信号空间的51图7–11TCM编码调制器方框图图7–11TCM编码调制器方框图52图7-124状态编码方案图7-124状态编码方案53第7章差错控制编码7.1概述7.2常用的几种简单分组码7.3线性分组码7.4循环码7.5卷积码*7.6网格编码调制第7章差错控制编码7.1概述547.1概述7.1.1信道编码在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。7.1概述7.1.1信道编码557.1.2差错控制方式图7-1差错控制方式7.1.2差错控制方式图7-1差错控制方式56

1.检错重发方式检错重发又称自动请求重传方式，记作ARQ(AutomaticRepeatRequest)。由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效，但实时性差，主要在计算机数据通信中得到应用。1.检错重发方式572.前向纠错方式前向纠错方式记作FEC(ForwordErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。2.前向纠错方式583.混合纠错方式混合纠错方式记作HEC(HybridErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此，近年来得到广泛应用。3.混合纠错方式59另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道，错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。另外，按照噪声或干扰的变化规律，可把信道分为607.1.3纠错码的分类(1)根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。(2)根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。(3)根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。7.1.3纠错码的分类617.1.4纠错编码的基本原理1.分组码分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码字未被选用，称为禁用码组。7.1.4纠错编码的基本原理1.分组码62在分组码中，非零码元的数目称为码字的汉明重量，简称码重。例如，码字10110，码重w=3。两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离，简称码距。例如11000与10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用d０表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。在分组码中，非零码元的数目称为码字的汉明重量632.检错和纠错能力若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。它是一种简单实用的检错码，并有一定的纠错能力。例如(2,1)重复码，两个许用码组是00与11，d0=2，收端译码，出现01、10禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是000与111,d0=3;当收端出现两个或三个1时，判为1，否则判为0。此时，可以纠正单个错误，或者该码可以检出两个错误。2.检错和纠错能力若分组码码字中的监督64码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内:(1)检测e个随机错误，则要求码的最小距离d0≥e+1;(2)纠正t个随机错误，则要求码的最小距离d0≥2t+1;(3)纠正t个同时检测e(≥t)个随机错误，则要求码的最小距离d0≥t+e+1。码的最小距离d0直接关系着码的检错和纠错能力653.编码效率用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:R=k/n其中,k是信息元的个数，n为码长。对纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。3.编码效率667.2常用的几种简单分组码7.2.1奇偶监督码奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。7.2常用的几种简单分组码7.2.1奇偶监督码67设码字A=［an-1,an-2,…,a1,a0］，对偶监督码有奇监督码情况相似，只是码组中“1”的数目为奇数，即满足条件而检错能力与偶监督码相同。奇偶监督码的编码效率R为设码字A=［an-1,an-2,…,a1,a0］，对偶监督码687.2.2行列监督码图7-2(66,50)行列监督码7.2.2行列监督码图7-2(66,50)行列监督码697.2.3恒比码码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，只要计算接收码元中1的数目是否正确，就知道有无错误。

目前我国电传通信中普遍采用3∶2码，又称“5中取3”的恒比码，即每个码组的长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字，如表7-1所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。7.2.3恒比码码字中1的数目与070表7-13∶2恒比码表7-13∶2恒比码717.3线性分组码现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是监督元，可用下列线性方程组来描述该分组码，产生监督元。7.3线性分组码现以(7,4)分72表7-2(7,4)码的码字表表7-2(7,4)码的码字表737.3.2监督矩阵H和生成矩阵G

7.3.2监督矩阵H和生成矩阵G74其中,P为r×k阶矩阵，Ir为r×r阶单位矩阵。可以写成H=［PIr］形式的矩阵称为典型监督矩阵。HAT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。并简记为其中,P为r×k阶矩阵，Ir为r×r阶单位矩75若把监督方程补充为下列方程若把监督方程补充为下列方程76可改写为矩阵形式可改写为矩阵形式77数字通信原理与技术7差错控制编码课件787.3.3伴随式(校正子)S

设发送码组A=［an-1,an-2,…,a1,a0］，在传输过程中可能发生误码。接收码组B=［bn-1,bn-2,…,b1,b0］，则收发码组之差定义为错误图样E，也称为误差矢量，即其中E=［en-1,en-2,…,e1,e0］，且当bi=ai

当bi≠ai

(7-15)7.3.3伴随式(校正子)S设发送码组A=79式(7-15)也可写作令S=BHT，称为伴随式或校正子。式(7-15)也可写作令S=BHT，称为伴随式或校正子80表7-3(7,4)码S与E的对应关系表7-3(7,4)码S与E的对应关系817.4循环码表7-4(7,3)循环码7.4循环码表7-4(7,3)循环码82在代数理论中，为了便于计算，常用码多项式表示码字。(n,k)循环码的码字，其码多项式(以降幂顺序排列)为在代数理论中，为了便于计算，常用码多项式表示837.4.1生成多项式及生成矩阵如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如表7-4的(7,3)循环码中，7.4.1生成多项式及生成矩阵如果一种码的84其它码多项式都是g(x)的倍式，即其它码多项式都是g(x)的倍式，即85循环码的生成矩阵常用多项式的形式来表示循环码的生成矩阵常用多项式的形式来表示86例如(7,3)循环码，n=7,k=3,r=4,其生成多项式及生成矩阵分别为例如(7,3)循环码，n=7,k=3,r=4,其生成多877.4.2监督多项式及监督矩阵为了便于对循环码编译码，通常还定义监督多项式，令

其中g(x)是常数项为1的r次多项式，是生成多项式；h(x)是常数项为1的k次多项式，称为监督多项式。同理，可得监督矩阵H

7.4.2监督多项式及监督矩阵其中g(x)是常数项为188是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+x3+x2+1，则其中是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+89数字通信原理与技术7差错控制编码课件907.4.3编码方法和电路在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为循环码的码多项式可表示为7.4.3编码方法和电路在编码时，首先要91图7-3(7,3)循环码编码电路图7-3(7,3)循环码编码电路92表7-5(7,3)循环码的编码过程表7-5(7,3)循环码的编码过程937.4.4译码方法和电路图7-4(7,3)循环码译码电路7.4.4译码方法和电路图7-4(7,3)循环码译码947.5卷积码7.5.1基本概念图7-5卷积码(2,1,2)