1、第9章 差错控制编码 第第9 章章 差错控制编码差错控制编码 9.1概述概述 9.2检错与纠错检错与纠错 9.3常用差错控制码常用差错控制码 9.4线性分组码线性分组码 9.5循环码循环码 9.6卷积码卷积码*9.7 网格编码调制网格编码调制 第9章 差错控制编码 9.1 概概 述述 9.1.1 信道编码信道编码 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发
2、射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。第9章 差错控制编码 9.1.2 差错控制方式差错控制方式 图9-1 差错控制方式 第9章 差错控制编码 1.检错重发方式检错重发方式 检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效，但实时性差，主要在计算机数据通信中
3、得到应用。第9章 差错控制编码 2.前向纠错方式前向纠错方式 前向纠错方式记作FEC(Forword ErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。第9章 差错控制编码 3.混合纠错方式混合纠错方式 混合纠错方式记作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和
4、检错重发的优点，可达到较低的误码率，因此，近年来得到广泛应用。第9章 差错控制编码 另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道，错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。第9章 差错控制编码 9.2.1纠错码的分类纠错码的分类 (1)根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关
5、系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。(2)根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。(3)根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。9.2检错与纠错检错与纠错 第9章 差错控制编码 9.2.2 纠错编码的基本原理纠错编码的基本原理 1.分组码分组码 分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元
6、数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。第9章 差错控制编码 在分组码中，非零码元的数目称为码字的汉明重量，简称码重。例如，码字 10110，码重w=3。两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离，简称码距。例如 11000 与 10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用d表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。第
7、9章 差错控制编码 2.检错和纠错能力检错和纠错能力 若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。它是一种简单实用的检错码，并有一定的纠错能力。例如(2,1)重复码，两个许用码组是 00 与 11，d0=2，收端译码，出现 01、10 禁用码组时，可以发现传输中的一位错误。如果是(3,1)重复码，两个许用码组是 000 与111,d0=3;当收端出现两个或三个 1 时，判为 1，否则判为 0。此时，可以纠正单个错误，或者该码可以检出两个错误。第9章 差错控制编码 码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内:(1)检测e
8、个随机错误，则要求码的最小距离d0e+1;(2)纠正t个随机错误，则要求码的最小距离d02t+1;(3)纠正t个同时检测e(t)个随机错误，则要求码的最小距离d0t+e+1。第9章 差错控制编码 3.编码效率编码效率 用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性:其中,k是信息元的个数，n为码长。对纠错码的基本要求是:检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。nkR(9-1)第9章 差错控制编码 9.3 常用的几种简单分组码常用的几种简单分组码9.3.1 奇偶
9、监督码奇偶监督码 奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的(n,n-1)系统分组码。奇偶监督码又分为奇监督码和偶监督码。第9章 差错控制编码 设码字A=an-1,an-2,a1,a0，对偶监督码有 00121aaaann 奇监督码情况相似，只是码组中“1”的数目为奇数，即满足条件 1021aaann而检错能力与偶监督码相同。奇偶监督码的编码效率R为 nnR/)1(9-2)(9-3)第9章 差错控制编码 9.3.2水平奇偶监督码水平奇偶监督码为了提高奇偶监督码的检错能力,特别是克服其不能检测突发错误的缺点,可以将经
10、过奇偶监督的码元序列按行排成方阵,每行为一组奇偶监督码,如表91所示。发送时按列的顺序传输,接收时仍将码元序列还原为发送时的方阵形式,然后按行进行奇偶校验。第9章 差错控制编码 表91水平奇偶监督码 信息码元 监督码元 1110011000 1101001101 1000011101 0001000010 1100111011 1 0 1 0 1 第9章 差错控制编码 9.3.3 9.3.3 行列监督码行列监督码 奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列监督码。这种码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施奇偶监督。这种码既可以逐行传输，也可以逐列传输。一般地
11、，LM个信息元附加L+M+1个监督元，组成(LM+L+M+1,LM)行列监督码的一个码字(L+1行，M+1列)。表92是(66,50)行列监督码的一个码字。这种码具有较强的检测能力，适于检测突发错误，还可用于纠错。第9章 差错控制编码 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 表92(66,50)行列监督码 第9章 差错控制编码 9.3.4群计数码群计数码把信息码元中“1”的
12、个数用二进制数字表示,并作为监督码元放在信息码元的后面,这样构成的码称为群计数码。例如,一码组的信息码元为1010111,其中“1”的个数为5,用二进制数字表示为“101”,将它作为监督码元附加在信息码元之后,即传输的码组为1010111 101。群计数码有较强的检错能力,除了同时出现码组中“1”变“0”和“0”变“1”的成对错误外,它还能纠正所有形式的错误。第9章 差错控制编码 9.3.5 恒比码恒比码 码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的 1 和 0，因此恒比码又称等重码，定 1 码。这种码在检测时，只要计算接收码元中 1 的数
13、目是否正确，就知道有无错误。目前我国电传通信中普遍采用 3 2 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。这时可能编成的不同码组数目等于从 5 中取 3 的组合数 10，这 10 个许用码组恰好可表示 10 个阿拉伯数字，如表 7-1 所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。第9章 差错控制编码 表表9-3 3 2 恒比码恒比码 第9章 差错控制编码 9.4 线线 性性 分分 组组 码码 9.4.1基本概念基本概念在(n,k)分组码中,若每一个监督元都是码组中某些信息元按模二和而得到的,即监督元是按线
14、性关系相加而得到的,则称线性分组码。或者说,可用线性方程组表述码规律性的分组码称为线性分组码。线性分组码是一类重要的纠错码,应用很广泛。第9章 差错控制编码 现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是监督元，可用下列线性方程组来描述该分组码，产生监督元。(9-4)4445556660123aaaaaaaaaaaaa第9章 差错控制编码 表 9-4（7，3）分组码 码 元 序号 信息元 监督元 0 000 0000 1 001 1101 2 010 0111 3 011 1010 4 100 111
15、0 5 101 0011 6 110 1001 7 111 0100 第9章 差错控制编码 我们可以把(n,k)线性分组码看成一个n维线性空间,每一个码字就是这个空间的一个矢量。n维线性空间长度为n的码组共有2n个,但线性分组码的码字共有2k个,kd1d0。102dd第9章 差错控制编码 图912 8PSK信号星座图的分割原理 第9章 差错控制编码 上述TCM系统的例子中,需要根据已编码的3个比特来选择信号点,即选择波形的相位。这个系统中卷积码编码器的方框图如图913所示。由图可见,这个卷积码的约束长度等于3。编码器输出的前两个比特c1和c2用来选择星座图划分的路径,最后1个比特c3用于选定星
16、座图第3级(最低级)中的信号点。在图912中,c1,c2,c3表示已编码的3个码元,图中最下一行注明了c1c2c3的值。第9章 差错控制编码 图913一种TCM编码器方框图 第9章 差错控制编码 一般来说,TCM编码器结构如图914所示,它将k比特输入信息分为k1和k2两段,前k1比特通过一个(n1,k1,K)卷积码编码器,产生n1比特输出,用于选择信号星座图中2n1个划分之一,后面的k2比特用于选定星座图中的信号点。这表明星座图被划分为2n1个子集,每个子集中含有2n2个信号点。在图913中,k1=k2=1。第9章 差错控制编码 图914TCM编码器的一般结构图 第9章 差错控制编码 图91
17、5给出了这个8PSK系统的网格图。由于未编码比特有两种取值,所以每个状态下有两根线。例如,设初始状态b1b2=00,k1=k2=0。当输入信号序列k1为“0110100”时,移存器状态以及输出c1c2之间的关系如表912所示。第9章 差错控制编码 图915 8PSK编码器网格图 第9章 差错控制编码 表表 9-12 移存器状态移存器状态 b1b2与输出码与输出码 c1c2之间的关系之间的关系 k1 b1 b2 状态状态 c1 c2 0 0 a 0 0 0 0 0 a 0 0 1 0 0 a 0 1 1 1 0 b 1 1 0 1 1 d 1 1 1 0 1 c 0 0 0 1 0 b 1 0
18、0 0 1 c 0 1 0 0 0 a 0 0 第9章 差错控制编码 在第1 个输入码元“1”到达后，输出码元 c1和 c2由“00”变成“01”，但是这时的输入信息位k2可能是“0”或“1”，所以输出 c1c2c3可能是“010”或“011”；当第 1 个输入码元“1”进入 b1后，b1b2的状态由“00”变到“10”，即由状态 a 变为状态b，输出c1c2c3可能是“110”或“111”，b1b2的状态由 b 变到 d，如图中虚线所示，依此类推。图中虚线表示输入比特为“1”的状态转移；实线表示输入比特为“0”的状态转移。第9章 差错控制编码 为了得到最佳的纠错效果，Ungerboeck 通
19、过研究得出上述网格图和星座图之间的对应关系符合下列规则：每对平行转移必须对应最下一级划分同一子集中的两个信号点。例如，图9-15 中的“000”和“001”同属于图 9-12 中的子集 C0，“010”和“011”同属于子集C1，等等。这些信号点对具有最大的欧氏距离（d2=2)。从某一状态出发的所有转移，或到达某一状态的所有转移，必须属于同一上级子集。例如，图 9-15 中从状态 a 出发的转移000，001，010 和 011 都属于图 9-12中的子集 B0。或者说，此两对平行转移应具有最大可能的欧氏距离，例如图 9-12 中的 dl=2。第9章 差错控制编码 9.7.2TCM信号的解调信
20、号的解调TCM信号的解调通常都采用维特比算法,但是现在的网格图表示的状态是波形,而不是码组。解码器的任务是计算接收信号序列路径和各种可能的编码网格路径(简称可能路径)间的距离。若所有发送信号序列是等概率的,则判定与接收序列距离最小的可能路径(又称为最大似然路径)为发送序列。第9章 差错控制编码 假若选用全“0”序列作为测试序列,如图916中虚线路径U所示。图中还用实线给出另一许用波形序列路径V,它从全“0”序列路径分开,又回到全“0”序列路径。若发送序列是全“0”序列,但是接收序列中有错误,使接收序列路径离开全“0”路径,然后又回到全“0”序列,且中间没有返回状态a,则解码器需要比较此接收序列
21、路径和U的距离与接收序列路径和V的距离之大小。若后者小,则将发生一次错误判决。这里的距离指欧氏距离。第9章 差错控制编码 图9168PSK解码路径示意图 第9章 差错控制编码 这里,我们将引入自由欧氏距离Fed(FreeEuclideanDistance)的概念。自由欧氏距离是指许用波形序列集合中各元素之间的最小距离,它决定了产生错误判决的概率。自由欧氏距离越大,错误判决的概率越小。在上例中,按照在欧氏空间求矢量和的方法,U和V两条路径间的欧氏距离d为 d2d2(Ul，V1)+d2(U2，V2)+d2(U3，V3)d2(000，010)+d2(000，100)+d2(000，010)2)2(0
22、.765)22)2(4.585 第9章 差错控制编码 因此 4.5852.14d(942)另外一种许用波形序列的路径是U1WU3,如图916的上端所示。它和V序列相似,从状态a开始,离开U,再回到状态a。这个路径和U的距离为 d2=d2(U1,U1)+d2(U2,W)+d2(U3,U3)d2(000,000)+d2(000,001)+d2(000,010)0(2)20=4 即 d=2(943)第9章 差错控制编码 比较式(942)和式(943)可见,路径U1WU3和路径V相比,前者和路径U的距离更小。并且可以逐个验证,这是和路径U距离最小的许用序列的路径。因此,按照上述定义,式(943)中的距离就是这种编码的自由欧氏距离。故可以将其写为dFed2(944)另一方面,未编码的QPSK信号的码元之间没有约束,将其自由欧氏距离作为参考距离dRef,则由图912可知 Ref12Dd(945)第9章 差错控制编码 由此可见,与未编码QPSK系统相比,8PSK的TCM系统可以获得的渐近编码增益为 30.1(dB)lg20GRefFedPSK/QPSK8dd(946)
