第三章 信道编码技术

1、在数字通信中，根据不同的目的，编码可分为在数字通信中，根据不同的目的，编码可分为信源编码和信道信源编码和信道编码编码。 信源编码信源编码是为了提高数字通信的有效性以及使模拟信号数字是为了提高数字通信的有效性以及使模拟信号数字化而采取的编码技术。化而采取的编码技术。 信道编码信道编码是为了降低误码率，提高数字通信的可靠性而采取是为了降低误码率，提高数字通信的可靠性而采取的编码。的编码。v 一类信道编码是对传输信号的一类信道编码是对传输信号的码型进行转换码型进行转换，使之更适，使之更适合于信道特性或满足接收端对恢复信号的要求，从而减少信合于信道特性或满足接收端对恢复信号的要求，从而减少信息损失；息

2、损失；v 另一类信道编码是在信息序列中人为的另一类信道编码是在信息序列中人为的增加冗余位增加冗余位，使，使之具有相关特性，在接收端利用相关性进行检错或纠错，从之具有相关特性，在接收端利用相关性进行检错或纠错，从而达到可靠通信的目的。而达到可靠通信的目的。差错（纠错）控制差错（纠错）控制信道编码技术信道编码技术 信道分类：从差错控制角度看信道分类：从差错控制角度看随机信道随机信道：错码的出现是随机的：错码的出现是随机的 差错是差错是相互独立相互独立的的, ,不相关不相关，如白噪声，如白噪声突发信道突发信道：错码是成串集中出现的：错码是成串集中出现的错误与错误间有相关性错误与错误间有相关性, ,一

3、个差错往往要影响到后面一串一个差错往往要影响到后面一串字字，如脉冲干扰，如脉冲干扰 E: 0 0 1 0 0 1 0 0 0 0 0 00 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 01 0 0 1 1 1 0 0 0 0 0 0 0 混合信道混合信道：既存在随机错码又存在突发错码：既存在随机错码又存在突发错码 对于不同类型的信道应采用不同的差错控制技术对于不同类型的信道应采用不同的差错控制技术信道分类信道分类 突发长度= 4突发长度= 6本章内容本章内容v 差错控制v 线性分组码v 循环码v 卷积码第一节差错控制第一节差错控制v 差错控制技术

4、v差错编码的基本原理v 码距与纠检错能力的关系v差错控制编码的分类差错控制差错控制技术技术 自动请求重发自动请求重发(ARQ)(ARQ)：发端发送发端发送检错码检错码，收端译码器判断当前码字传输是否出错；收端译码器判断当前码字传输是否出错；当有错时按某种协议通过一个当有错时按某种协议通过一个反向信道反向信道请求请求发送端重传已发送的码字发送端重传已发送的码字( (全部或部分全部或部分) )。差错控制差错控制技术技术 优点：译码设备简单优点：译码设备简单缺点：缺点：系统是工作在半双工状态，系统是工作在半双工状态，时间没有得到充分利用，传输效率时间没有得到充分利用，传输效率较低较低，只有检错能力而

5、无纠错能力只有检错能力而无纠错能力差错控制差错控制技术技术 前向纠错前向纠错(FEC)(FEC)：发送端的信道编码器将信息码组编成具有一发送端的信道编码器将信息码组编成具有一定定纠错能力纠错能力的码。的码。接收端信道译码器对接收码字进行译码接收端信道译码器对接收码字进行译码, ,若传若传输中产生的差错数目在码的纠错能力之内时输中产生的差错数目在码的纠错能力之内时, ,译码器对差错进行定位并加以纠正。译码器对差错进行定位并加以纠正。差错控制差错控制技术技术 优点：不会因反复重发延误时间优点：不会因反复重发延误时间缺点：译码设备比较复杂缺点：译码设备比较复杂差错控制差错控制技术技术 信息反馈信息反

6、馈(IRQ)(IRQ)：收端把收到的数据收端把收到的数据, ,原封不动地通过反馈信道送回到发端原封不动地通过反馈信道送回到发端, ,发发端比较发的数据与反馈来的数据端比较发的数据与反馈来的数据, ,从而发现错误从而发现错误, ,并且把错误并且把错误的消息再次传送的消息再次传送, ,直到发端没有发现错误为止。直到发端没有发现错误为止。效率低效率低混合纠错混合纠错(HEC)(HEC)：是是FECFEC与与ARQARQ方式的结合。方式的结合。发端发送同时具有自动纠错和检测能力的码组发端发送同时具有自动纠错和检测能力的码组, ,收端收到码收端收到码组后组后, ,检查差错情况检查差错情况, ,如果差错在

7、码的纠错能力以内如果差错在码的纠错能力以内, ,则自动则自动进行纠正。进行纠正。如果信道干扰很严重如果信道干扰很严重, ,错误很多错误很多, ,超过了码的纠错能力超过了码的纠错能力, ,但能但能检测出来检测出来, ,则经反馈信道请求发端重发这组数据。则经反馈信道请求发端重发这组数据。差错控制差错控制技术技术 从理论上讲，差错控制是以降低信息传从理论上讲，差错控制是以降低信息传输速率为代价换取提高传输可靠性输速率为代价换取提高传输可靠性纠错编码的基本原理纠错编码的基本原理分组码基本原理：举例说明如下。分组码基本原理：举例说明如下。设有一种由设有一种由3位二进制数字构成的码组，它共有位二进制数字构

8、成的码组，它共有8种不同的可能组合。若种不同的可能组合。若将其全部用来表示天气，则可以表示将其全部用来表示天气，则可以表示8种不同天气，种不同天气， 例如：例如：“000”（晴），（晴），“001”（云），（云）， “010”（阴），（阴），“011”（雨），（雨）， “100”（雪），（雪），“101”（霜），（霜）， “110”（雾），（雾），“111”（雹）。（雹）。其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。组。这时，接收端将无法发现错误。13纠错编码的基本原理纠错编码的基本

9、原理若在上述若在上述8种码组中只准许使用种码组中只准许使用4种来传送天气，例如：种来传送天气，例如：“000”晴晴 “011”云云 “101”阴阴 “110”雨雨这时，虽然只能传送这时，虽然只能传送4种不同的天气，但是接收端却有可能发现码组中种不同的天气，但是接收端却有可能发现码组中的一个错码。的一个错码。例如，若例如，若“000”（晴）中错了一位，则接收码组将变成（晴）中错了一位，则接收码组将变成“100”或或“010”或或“001”。这。这3种码组都是不准使用的，称为种码组都是不准使用的，称为禁用码组。接收端在收到禁用码组时，就认为发现了错码。当发生接收端在收到禁用码组时，就认为发现了错码

10、。当发生3个错码时，个错码时，“000”变成了变成了“111”，它也是禁用码组，故这种编码也能检测，它也是禁用码组，故这种编码也能检测3个错码。个错码。但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是的是许用码组。14纠错编码的基本原理纠错编码的基本原理检错和纠错检错和纠错上面这种编码上面这种编码只能检测错码，不能纠正错码只能检测错码，不能纠正错码。例如，当接收码组为禁用。例如，当接收码组为禁用码组码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、时，接收端将无法判断是哪一位码发生了错误，因为晴、

11、阴、雨三者错了一位都可以变成雨三者错了一位都可以变成“100”。要能够纠正错误，还要增加多余度要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：。例如，若规定许用码组只有两个：“000”（晴），（晴），“111”（雨），其他都是禁用码组，则能够检测两个以下（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。错码，或能够纠正一个错码。例如，当收到禁用码组例如，当收到禁用码组“100”时，时，若当作仅有一个错码若当作仅有一个错码，则可以判断此，则可以判断此错码发生在错码发生在“1”位，从而纠正为位，从而纠正为“000”（晴）。因为（晴）。因为“111”（雨）发生任（雨

12、）发生任何一位错码时都不会变成何一位错码时都不会变成“100”这种形式。这种形式。 但是，这时若假定错码数不超过两个，则存在两种可能性：但是，这时若假定错码数不超过两个，则存在两种可能性：“000”错一错一位和位和“111”错两位都可能变成错两位都可能变成“100”，因而只能检测出存在错码而无法纠因而只能检测出存在错码而无法纠正错码正错码。分组码的结构分组码的结构将信息码分组，为每组信息码附加若干监督码的编码称为将信息码分组，为每组信息码附加若干监督码的编码称为分组码 。在分组码中，在分组码中，监督码元仅监督本码组中的信息码元监督码元仅监督本码组中的信息码元。 信息位和监督位的关系：举例如下信

13、息位和监督位的关系：举例如下纠错编码的基本原理纠错编码的基本原理分组码的一般结构分组码的一般结构分组码的符号：分组码的符号：(n, k)N 码组的总位数，又称为码组的长度（码码组的总位数，又称为码组的长度（码长），长），k 码组中信息码元的数目，码组中信息码元的数目，n k r 码组中的监督码元数目，或称监码组中的监督码元数目，或称监督位数目。督位数目。 纠错编码的基本原理纠错编码的基本原理 v 码重码重：码字中非零码元的个数定义为该码字的重量，：码字中非零码元的个数定义为该码字的重量，简称码重。如简称码重。如“10011”码字的码重为码字的码重为3。v 码距码距：两个等长码字之间对应码元不同

14、的两个等长码字之间对应码元不同的数目，数目，即即两个码组之间对应位置上两个码组之间对应位置上1、0不同的位数，又叫汉明不同的位数，又叫汉明(Hamming)距通常用距通常用d表示。表示。10 1 1 0 码重：码重：301 1 0 0 2 距离：距离：3 纠错编码的基本原理纠错编码的基本原理码距的几何意义码距的几何意义对于对于3 3位的编码组，可以在位的编码组，可以在3 3维空间中说明码距的几何意义。维空间中说明码距的几何意义。 每个码组的每个码组的3 3个码元的值个码元的值( (a a1 1, , a a2 2, , a a3 3) )就是此立方体各顶点的坐标。就是此立方体各顶点的坐标。而上

15、述而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离几何距离。由此图可以直观看出，上例中由此图可以直观看出，上例中4 4个准用码组之间的距离均为个准用码组之间的距离均为2 2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1纠错编码的基本原理纠错编码的基本原理v 最小码距最小码距：在一个码字集合中，任意两个码字间距：在一个码字集合中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，离的最小值，即码字集合中任意两元素间的最小距离，记为记为

16、d dminmin或或d d0 0，例如例如11101110、10101010、10001000v 编码效率：编码效率：信息码元数与码长之比，通常用信息码元数与码长之比，通常用 表示，其中表示，其中k k为信息码元的数目，为信息码元的数目，n n为码长为码长。纠错码的抗干扰能力完全取决于许用码字之间的距纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。大，抗干扰能力就越强。nk纠错编码的基本原理纠错编码的基本原理码距和检纠错能力的关系码距和检纠错能力的关系一种编码的最小码距一种编码的最小码距

17、d0的大小直接关的大小直接关系着这种编码的检错和纠错能力系着这种编码的检错和纠错能力 为检测为检测e个错码，要求最小码距个错码，要求最小码距 d0 e + 1码距和检纠错能力的关系码距和检纠错能力的关系【证】设一个码组【证】设一个码组A A位于位于OO点。若码组点。若码组A A中发生一个错码中发生一个错码，则我们可以认为，则我们可以认为A A的位置将移动至以的位置将移动至以O O点为圆心，点为圆心，以以1 1为半径的圆上某点，但其位置不会超出此圆。为半径的圆上某点，但其位置不会超出此圆。 若码组若码组A A中发生两位错码，则其位置不会超出以中发生两位错码，则其位置不会超出以O O点为圆心，以点

18、为圆心，以2 2为半径的圆。因此，为半径的圆。因此，只要最小码距只要最小码距不小于不小于3 3，码组，码组A A发生两位以下错码时，发生两位以下错码时，不可能变成另一个准用不可能变成另一个准用码组，因而能检测错码码组，因而能检测错码的位数等于的位数等于2 2。 0123BA汉明距离ed00 0: :晴晴, ,1 1: :雨雨若若10,0110,01。收端无法发现错误。收端无法发现错误00晴1001110011雨能发现一个错误禁用码组插入插入1 1位监督码位监督码后具有后具有检出检出1 1位错码位错码的能的能力力, ,但不能予以纠正。但不能予以纠正。码距和检纠错能力的关系码距和检纠错能力的关系同

19、理，若一种编码的最小码距为同理，若一种编码的最小码距为d d0 0，则将能检测，则将能检测( (d d0 0 - 1) - 1)个个错码。反之，若要求检测错码。反之，若要求检测e e个错码，则最小码距个错码，则最小码距d d0 0至少应不至少应不小于小于( ( e e + 1)+ 1)。为了纠正为了纠正t t个错码，要求最小码距个错码，要求最小码距d d0 0 2 2t t + 1 + 1【证】图中画出码组【证】图中画出码组A A和和B B的距离为的距离为5 5。码组。码组A A或或B B若发生不多若发生不多于两位错码，则其位置均不会超出半径为于两位错码，则其位置均不会超出半径为2 2以原位置

20、为圆心以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以以A A为圆心的圆上就判决收到的是码组为圆心的圆上就判决收到的是码组A A，若落于以，若落于以B B为圆为圆心的圆上就判决为码组心的圆上就判决为码组B B。这样，就能够纠这样，就能够纠正两位错码。正两位错码。 BtA汉明距离012345td0码距和检纠错能力的关系码距和检纠错能力的关系000晴晴010001111000111雨雨晴晴在只有在只有1 1位错码位错码的情况下的情况下, ,可以判决哪位是错码可以判决哪位是错码并予以并予以纠正纠正, ,可以可以检出检出2 2位位

21、或或2 2位以下的错码。位以下的错码。100011101110雨雨码距和检纠错能力的关系码距和检纠错能力的关系若这种编码中除码组若这种编码中除码组A和和B外，还有许多种不同码外，还有许多种不同码组，但任两码组之间的码距均不小于组，但任两码组之间的码距均不小于5，则以各码，则以各码组的位置为中心以组的位置为中心以2为半径画出之圆都不会互相重为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距将能被纠正。因此，当最小码距d05时，能够纠时，能够纠正正2个错码，且最多能纠正个错码，且最多能纠正2个。若错码达到个。若

22、错码达到3个，个，就将落入另一圆上，从而发生错判。故一般说来就将落入另一圆上，从而发生错判。故一般说来，为纠正，为纠正t个错码，最小码距应不小于个错码，最小码距应不小于(2t + 1)。码距和检纠错能力的关系码距和检纠错能力的关系为纠正为纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个错码，要求最小码距在解释此式之前，先来分析下图所示的例子。图中码组在解释此式之前，先来分析下图所示的例子。图中码组A和和B之之间距离为间距离为5。按照检错能力公式，最多能检测。按照检错能力公式，最多能检测4个错码，即个错码，即e = d0 1 = 5 1 = 4，按照纠错能力公式纠错时，能纠正，按照

23、纠错能力公式纠错时，能纠正2个错码。但是个错码。但是，不能同时作到两者，因为当，不能同时作到两者，因为当错码位数超过纠错能力错码位数超过纠错能力时，该码组时，该码组立即进入另一码组的圆内而被错误地立即进入另一码组的圆内而被错误地“纠正纠正”了。例如，码组了。例如，码组A若错了若错了3位，就会被误认为码组位，就会被误认为码组B错了错了2位造成的结果，从而被位造成的结果，从而被错错“纠纠”为为B。这就。这就是说，检错和纠错是说，检错和纠错公式不能同时成立公式不能同时成立或同时运用。或同时运用。 )(10tetedBtA汉明距离012345td0码距和检纠错能力的关系码距和检纠错能力的关系所以，为了

24、在可以纠正所以，为了在可以纠正t个错码的同时，能够检个错码的同时，能够检测测e个错码，就需要像下图所示那样，使某一码个错码，就需要像下图所示那样，使某一码组（譬如码组组（譬如码组A）发生发生e个错误之后所处的位置个错误之后所处的位置，与其他码组（譬如码组，与其他码组（譬如码组B）的纠错圆圈至少）的纠错圆圈至少距离等于距离等于1，不然将落在该纠错圆上从而发生，不然将落在该纠错圆上从而发生错误地错误地“纠正纠正”。因此，由此图可以直观看出。因此，由此图可以直观看出，要求最小码距，要求最小码距ABe1tt汉明距离)(10teted码距和检纠错能力的关系码距和检纠错能力的关系一个码能检测一个码能检测e个错码，则要求其最小码个错码，则要求其最小码dmine+1一个码能纠正一个码能纠正t个错码，则要求其最小个错码，则要求其最小dmin2t+1一个码能纠正一个码能纠正t个错码，同时能检测个错码，同时能检测e个错码，则要个错码，则要求其最小码距求其最小码距 dmine+t+1 (et)码距和检纠错能力的关系码距和检纠错能力的关系差错控制编码差错控制编码分类分类 从功能角度讲从功能角度讲, ,差错码分为检错码和差错码分为检错码和纠错码纠错码检错码检错码：用于发现差错：用于发现差错纠错码纠错码：能自动纠正差错：能自动纠正差错按照对信息序列的处理方法按照对信息序列的处