差错控制编码

1、第三章第三章差错控制编码差错控制编码 教学重点教学重点1理解差错控制编码的基本原理理解差错控制编码的基本原理; ;2理解理解三种差错控制方式三种差错控制方式; ;3了解简单检纠错码、常用检纠错码差错控制的编码方了解简单检纠错码、常用检纠错码差错控制的编码方 法。法。 掌握掌握差错控制编码的基本原理差错控制编码的基本原理序号序号 内内 容容学时学时1 1 3.1 3.1概述概述 2 22 2 3.2 3.2 简单的纠、检错编码简单的纠、检错编码 1.51.53 3 3.3 3.3 常用的纠错编码常用的纠错编码 2 25 5 习题和小结习题和小结 0.50.56 6 本章总学时本章总学时 6 6学

2、时分配学时分配教学难点教学难点第三章差错控制编码第三章差错控制编码 3.1 概述概述3.2 简单的纠、检错编码简单的纠、检错编码 3.3 常用的纠错编码常用的纠错编码 本章小结本章小结3.1概述概述一、差错类型一、差错类型 二、差错控制方式二、差错控制方式三、纠错编码的基本原理三、纠错编码的基本原理 2信源编码和信道编码信源编码和信道编码 的区别的区别： 信源编码是为了提高数字信号的信源编码是为了提高数字信号的有效性有效性以及为了使模拟以及为了使模拟信号信号数字化数字化而采取的编码。而采取的编码。1差错控制编码差错控制编码又称又称信道编码信道编码、抗干扰编码抗干扰编码或或纠错码纠错码，它是提高

3、数字信号传输可靠性的有效方法之一。它是提高数字信号传输可靠性的有效方法之一。 信道编码是为了信道编码是为了降低误码率降低误码率，提高提高数字通信的数字通信的可靠性可靠性而而采取的编码。采取的编码。(1)(1)目的目的 信源编码是信源编码是去掉去掉信源的多余度；信源的多余度；信道编码是按一定的规则信道编码是按一定的规则加入加入多余度。多余度。 信道编码是在发送端的信息码元序列中，以某种确定的编信道编码是在发送端的信息码元序列中，以某种确定的编码规则，加入码规则，加入监督码元监督码元，以便在接收端利用该规则进行解码，以便在接收端利用该规则进行解码，从而发现错误、纠正错误。从而发现错误、纠正错误。

4、(2) (2) 方式：方式： 1 1 差错类型差错类型造成这种差错的类型有三种造成这种差错的类型有三种: : 一、一、差错类型差错类型 (1) 随机错误随机错误，也称独立错误，其特点是发生错误的码元互，也称独立错误，其特点是发生错误的码元互相独立，大多不会成片出现。相独立，大多不会成片出现。 (2) 突发错误突发错误，即一个错误出现往往影响后面的数据也出现，即一个错误出现往往影响后面的数据也出现错误，误码成片出现，错误之间有相关性。错误，误码成片出现，错误之间有相关性。 (3) 混合错误混合错误，随机错误和突发错误都占有相当的比例。，随机错误和突发错误都占有相当的比例。 2 2 纠检错码分类纠

5、检错码分类 (1) (1)根据编码的用途，可分成根据编码的用途，可分成检错码检错码和和纠错码纠错码。检错。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能纠错。一定能纠错。 (2) (2)按对信息码元处理的方法不同，又可分成按对信息码元处理的方法不同，又可分成分组码分组码和和卷积码卷积码。 分组码的各码元仅与本组的信息元有关；卷积码中码分组码的各码元仅与本组的信息元有关；卷积码中码元不仅与本组的信息元有关，而且还与前面若干组的信息元不仅与本组的信息元有关，而且还与前面若干组的信息码元有关。其中分组码又还可分成码元有关。其中分组码

6、又还可分成汉明码汉明码和和循环码循环码。 常用的差错控制方式有常用的差错控制方式有3 3种：检错重发、前向纠错和混合种：检错重发、前向纠错和混合纠错。纠错。 1 1检错重发方式检错重发方式（ARQ）二、二、差错控制方式差错控制方式 检错重发检错重发又称自动请求重传方式，记作又称自动请求重传方式，记作ARQ。由发端送。由发端送出能够发现错误的码，由收端判决传输中有无错误产生，如出能够发现错误的码，由收端判决传输中有无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确然后，发端把收

7、端认为错误的信息再次重发，从而达到正确传输的目的。传输的目的。 检错重发特点是检错重发特点是需要反馈信道需要反馈信道，译码设备简单，对突发，译码设备简单，对突发错误和信道干扰较严重时有效，但错误和信道干扰较严重时有效，但实时性差实时性差，主要应用在计，主要应用在计算机数据通信中。算机数据通信中。 2 2前向纠错方式前向纠错方式（FEC） 前向纠错前向纠错方式记作方式记作FEC。发端发送能够纠正错误的码，。发端发送能够纠正错误的码，收端收到解码之后，不仅可以发现错误，而且能够判断错误收端收到解码之后，不仅可以发现错误，而且能够判断错误码元所在的位置，并自动纠正。码元所在的位置，并自动纠正。 前向

8、纠错的特点是前向纠错的特点是单向传输单向传输，实时性好实时性好，传输效率高传输效率高，但但译码设备较复杂译码设备较复杂。这种纠错方式广泛应用于移动通信设备。这种纠错方式广泛应用于移动通信设备中（例如中（例如BP机、手机等）。机、手机等）。 3 3混合纠错方式混合纠错方式（HEC） 混合纠错混合纠错方式记作方式记作HEC，是，是ARQ和和FEC方式的混合。发方式的混合。发送端同时送出具有检错和纠错能力的码，接收端收到信码之送端同时送出具有检错和纠错能力的码，接收端收到信码之后，检查错误情况。如果误码较少，且在码的纠错能力以内，后，检查错误情况。如果误码较少，且在码的纠错能力以内，则自动进行纠正。

9、如果超过了码的纠错能力，则经过反馈信则自动进行纠正。如果超过了码的纠错能力，则经过反馈信道请求发送端重发。道请求发送端重发。HEC方式具有方式具有自动纠错自动纠错和和检错重发检错重发的优点，可达到较低的优点，可达到较低的误码率，特别适合于高速传输系统（例如卫星通信中）。的误码率，特别适合于高速传输系统（例如卫星通信中）。三、纠错编码的基本原理三、纠错编码的基本原理 下面我们以分组码为例说明纠错码检错和纠错的基本原理。下面我们以分组码为例说明纠错码检错和纠错的基本原理。 分组码的结构如图分组码的结构如图3.13.1所示。所示。 1 1分组码分组码 图图 3.1 分组码分组码 分组码用（分组码用（

10、n,k）表）表示示。其中。其中k k是每组信息码元是每组信息码元的数目的数目，n n是编码码组的码是编码码组的码元总位数，又称为码组长元总位数，又称为码组长度，简称度，简称码长码长。n k = = r为每个码组中的监督码元为每个码组中的监督码元数目。数目。 简单地说，分组码是对每段简单地说，分组码是对每段k位长的信息组以一定的规位长的信息组以一定的规则增加则增加r r个监督元，组成长度为个监督元，组成长度为n的码字。的码字。 在二进制情况下，共有在二进制情况下，共有2 2k个不同的信息组，相应地可得到个不同的信息组，相应地可得到2 2k个不同的码字，称为许用码组。其余个不同的码字，称为许用码组

11、。其余2 2n-2-2k个码字未被选用，个码字未被选用，称为禁用码组。称为禁用码组。 两个等长码组之间相应位取值不同的数目称为这两个码两个等长码组之间相应位取值不同的数目称为这两个码组的汉明距离，简称组的汉明距离，简称码距码距。 例如码字例如码字11000与与10011之间的码距之间的码距d=3，码字，码字11011与与11000之间的码距之间的码距d=2。 码组中任意两个码字之间距离的最小值称为码的码组中任意两个码字之间距离的最小值称为码的最小码最小码距距，用，用d0表示。最小码距是码的一个重要参数，它是表示。最小码距是码的一个重要参数，它是衡量码衡量码检错检错、纠错能力的依据纠错能力的依据

12、。 例如左边的三个码字：例如左边的三个码字： 则三个码字的最小码距则三个码字的最小码距 d0=1。 2 2检错和纠错的基本原理检错和纠错的基本原理 以重复编码为例说明：为什么纠错码能检错和纠错，检纠以重复编码为例说明：为什么纠错码能检错和纠错，检纠错能力与最小码距错能力与最小码距d0的关系。的关系。 假如要发送天气预报的消息，且天气只有晴、阴两种状态，假如要发送天气预报的消息，且天气只有晴、阴两种状态，可用表可用表3.1中的中的3种编码来讨论它的编码方法和纠错能力。种编码来讨论它的编码方法和纠错能力。a序序号编码用号编码用1位二进制表示阴晴二种状态，位二进制表示阴晴二种状态，b、c序号是各用二

13、位序号是各用二位二进制，三位二进制表示二种状态，故二进制，三位二进制表示二种状态，故b、c序号为序号为重复编码重复编码。 晴晴阴阴a1 10 0b11110 0c1111110 0序号序号检、纠错能力检、纠错能力不能发现和纠正错误不能发现和纠正错误能发现一位错，不能纠正能发现一位错，不能纠正能发现两位错或纠正一个错能发现两位错或纠正一个错天气天气 表表3.1 重复码的简单例子重复码的简单例子 在编码在编码a中，两个码字中只有一位差别，即最小码距中，两个码字中只有一位差别，即最小码距d0=1。若。若“1”（晴）误传为（晴）误传为“0”（阴）或（阴）或“0”（阴）误（阴）误传为传为“1”（晴），则

14、收端都不可能判别是否有错。因为所（晴），则收端都不可能判别是否有错。因为所收到的码字都是预先约定好的码（允许用码）在这种情况收到的码字都是预先约定好的码（允许用码）在这种情况下误码下误码只能产生错误的预报只能产生错误的预报。 晴晴阴阴a1 10 0b11110 0c1111110 0序号序号检、纠错能力检、纠错能力不能发现和纠正错误不能发现和纠正错误能发现一位错，不能纠正能发现一位错，不能纠正能发现两位错或纠正一个错能发现两位错或纠正一个错天气天气 在编码在编码b中，将中，将a中代码再加一位重复监督码元，即晴中代码再加一位重复监督码元，即晴用用“11”、阴用、阴用“00”表示。这两个码字的差别

15、是两位不表示。这两个码字的差别是两位不同，即许用码组中的最小码距同，即许用码组中的最小码距d0=2。如果干扰使码字中仅。如果干扰使码字中仅一位传错，即出现一位传错，即出现“01”或或“10”码，收端译码时，可发码，收端译码时，可发现在预约的二位编码中，并不存在这样的码字（这就是禁现在预约的二位编码中，并不存在这样的码字（这就是禁用码），这时收端认为传输过程中出现错误。这是用码），这时收端认为传输过程中出现错误。这是“11”或是或是“00”中一位出错造成的。但错码到底是由哪个码字中一位出错造成的。但错码到底是由哪个码字造成的，难以判断。可见，这种具有两位差别的码字具有造成的，难以判断。可见，这种

16、具有两位差别的码字具有检测一个错误的能力检测一个错误的能力，但不能纠正但不能纠正。 在编码在编码c中，将中，将b中编码再增加一位重复监督位，构成中编码再增加一位重复监督位，构成三位码三位码“111”和和“000”。显然，这两个码字的差别是。显然，这两个码字的差别是3位位不同，即许用码组中的最小码距不同，即许用码组中的最小码距d0 =3。当传输中码字受干。当传输中码字受干扰而将扰而将“111”或或“000”误传为误传为“110”，“101”、“011”，“001”、“010”、“100”时，接收端认为是时，接收端认为是都传错了。因为这些码字都不是许用码字而是禁用码字。都传错了。因为这些码字都不是

17、许用码字而是禁用码字。这些错误的码字可能是由于错一位造成的，也可能是由于这些错误的码字可能是由于错一位造成的，也可能是由于错两位造成的，所以它可以发现两位错误。如果把出现的错两位造成的，所以它可以发现两位错误。如果把出现的二个二个1或三个或三个1时，判为时，判为1，否则判为，否则判为0。此时该编码可以。此时该编码可以纠纠正单个错误码正单个错误码，检查出二个错误码检查出二个错误码。 从例中可以看出，码的从例中可以看出，码的最小距离最小距离d0直接关系着码的检直接关系着码的检错和纠错能力错和纠错能力。任一（。任一（n,k）分组码，若要在码字内：）分组码，若要在码字内： (1) 检测检测e个随机错误

18、，则要求最小距码个随机错误，则要求最小距码 d0e e+1;+1; ( (2) ) 纠正纠正t t个随机错误，则要求最小码距个随机错误，则要求最小码距 d d022t t+1;+1; ( (3) ) 纠正纠正t t个同时检测个同时检测e e(t t) )个随机错误，则个随机错误，则要求最小要求最小码距码距 d d0t t+ +e e 最小码距最小码距d0越大，纠、检错能力越强。越大，纠、检错能力越强。 3 3 编码效率编码效率 我们定义我们定义编码效率编码效率R来衡量有效性来衡量有效性： nkR 其中，其中，k k是信息元的个数，是信息元的个数，n n为码长。为码长。 对纠错码的基本要求是：对

19、纠错码的基本要求是： 检错和纠错能力尽量强，编码效率尽量高，编码规律尽量检错和纠错能力尽量强，编码效率尽量高，编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。力和编码效率，并且易于实现。 3.2 简单的纠、检错编码简单的纠、检错编码 一、奇偶校验码一、奇偶校验码 二、行列校验码二、行列校验码三、恒比码三、恒比码一、奇偶校验码一、奇偶校验码 奇偶校验码奇偶校验码是在原信息码后面附加一个监督元，使得码是在原信息码后面附加一个监督元，使得码组中组中“1”的个数是的个数是奇数或偶数奇数或偶数。 奇偶校验码又

20、分为奇偶校验码又分为奇校验码奇校验码和和偶校验码偶校验码。 设码字设码字A=A=a an-1n-1, ,a an-2n-2,a a1 1, ,a a0 0 ，对偶校验码有：，对偶校验码有：00121aaaann 式中，式中，a an-1n-1, ,a an-2n-2,a a1 1为信息元，为信息元，a a0 0为监督元。接收端为监督元。接收端译码时，按译码时，按上上式将码组中的码元式将码组中的码元模二相加模二相加，若结果为，若结果为“0”0”，就认为无错。结果为就认为无错。结果为“1”1”，就可断定该码组经传输后有奇，就可断定该码组经传输后有奇数个错误。数个错误。 奇校验码情况相似，只是码组中

21、奇校验码情况相似，只是码组中“1”的数目为的数目为奇数奇数，即，即满足条件满足条件 ：1021aaann 奇校验码奇校验码检错能力与偶校验码相同。检错能力与偶校验码相同。 奇偶校验码只能用来奇偶校验码只能用来检查错码检查错码，无纠正错码的能力无纠正错码的能力。00121aaaann二、行列校验码二、行列校验码 行列校验码行列校验码不仅对水平（行）方向的码元，而且对垂直不仅对水平（行）方向的码元，而且对垂直（列）方向的码元也实施奇偶校验。这种码既可以（列）方向的码元也实施奇偶校验。这种码既可以逐行传输逐行传输，也可以也可以逐列传输逐列传输。 图图3.2是行列校验码的一个例子，行和列均用偶校码，第

22、是行列校验码的一个例子，行和列均用偶校码，第6行，行，11列为校验位。列为校验位。 如对应第如对应第4行第行第6列出错，列出错，“1”变为变为“0”，则所对应的，则所对应的行列不能满足偶校验的关系，从而知其是错码。行列不能满足偶校验的关系，从而知其是错码。 行列校验码行列校验码具有较强的具有较强的检测能力检测能力，适于检测，适于检测突发错误突发错误，还可用于还可用于纠错纠错。它应用于。它应用于CD、VCD数字信号的差错控制编数字信号的差错控制编码中。码中。图图3.2 3.2 行列校验码行列校验码 三、三、 恒比码恒比码 码字中码字中1 1的数目与的数目与0 0的数目保持恒定比例的码称为的数目保

23、持恒定比例的码称为恒比码恒比码。又称等重码又称等重码，定定1码码。 恒比码在检测时，只要计算接收码元中恒比码在检测时，只要计算接收码元中1 1的数目是否正的数目是否正确，就知道有无错误。确，就知道有无错误。 目前我国电传通信中普遍采用目前我国电传通信中普遍采用3:2码，又称码，又称“5 5中取中取3”3”的恒比码，即每个码组的长度为的恒比码，即每个码组的长度为5 5，其中，其中3 3个个“1”1”。这时可。这时可能编成的不同码组数目等于从能编成的不同码组数目等于从5 5中取中取3 3的组合数的组合数1010，这，这1010个许个许用码组恰好可表示用码组恰好可表示1010个阿拉伯数字，如表个阿拉

24、伯数字，如表3.23.2所示。所示。 表表3.2 3：2恒比码恒比码 每个汉字以每个汉字以四位十进制数四位十进制数来代表的，采用检错重传来代表的，采用检错重传ARQ的差错控制方式。使用这种码后，我国汉字电报的差错率大的差错控制方式。使用这种码后，我国汉字电报的差错率大为降低。为降低。 数字数字0 00 01 11 10 01 11 10 01 10 01 11 12 21 11 10 00 01 13 31 10 01 11 10 04 41 11 10 01 10 05 50 00 01 11 11 16 61 10 01 10 01 17 71 11 11 10 00 08 80 01 1

25、1 11 10 09 91 10 00 01 11 1数码数码3.3 常用的纠错编码常用的纠错编码 一、线性分组码一、线性分组码 二、循环码二、循环码 四、码元交织四、码元交织 三、卷积码三、卷积码一、线性分组码一、线性分组码 在（在（n,k）分组码中，若每一个监督码元都是码组中某些）分组码中，若每一个监督码元都是码组中某些信息码元按模信息码元按模2加而得到，即监督码元是按线性关系相加得到加而得到，即监督码元是按线性关系相加得到的，则称为的，则称为线性分组码线性分组码。 在这里以在这里以(7，4)分组码为例说明编码过程。分组码为例说明编码过程。 1.基本概念基本概念 设有设有n = 7的码字，

26、编为的码字，编为 (7，4) 分组码，其中分组码，其中4个信息码元个信息码元为为a6a5a4a3，3个监督码元为个监督码元为a2a1a0。根据模根据模2和关系和多重监和关系和多重监督原则，列出督原则，列出(7,4)(7,4)线性分组码的一致监督关系。由于线性分组码的一致监督关系。由于r =7- 4 =3, , 显然这个一致监督关系是显然这个一致监督关系是3 3个线性方程组，三个监督码个线性方程组，三个监督码元由下式产生：元由下式产生： 4位信息码分别取不同的组合，经上面位信息码分别取不同的组合，经上面3个线性方程组计个线性方程组计算，可得到算，可得到(7.4)线性分组码的全部码字，如表线性分组

27、码的全部码字，如表3.3所示。所示。 356034514562aaaaaaaaaaaa信息码监督码 信息码 监督码a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111 表表3.3 (7.4)线性分组码码字表线性分组码码字表 从上表可看出，上述从上表可看出，上述(7.4)分组码分组码16个许用码组中的最小个许用码组中的最小码距码距d0=3, , 因此它能因此它能纠正一位错

28、码或检查出二位错码纠正一位错码或检查出二位错码。 2.纠错原理纠错原理 分组码能实现纠检错的原理分组码能实现纠检错的原理： 分组码是通过附加分组码是通过附加监督码监督码元实现对元实现对信息码元信息码元的监督，的监督，两者之间存在由监督方程组建立的两者之间存在由监督方程组建立的相互制约相互制约关系。当信息关系。当信息码元或监督码元在传输过程中发生错误时，方程组中与这码元或监督码元在传输过程中发生错误时，方程组中与这些码元对应的相互制约的关系就会被破坏，于是在接收端些码元对应的相互制约的关系就会被破坏，于是在接收端很容易通过检验监督方程来发现错误。另外，由于分组码很容易通过检验监督方程来发现错误。

29、另外，由于分组码的一致监督关系是的一致监督关系是多重监督多重监督，每个信息码元都受到两个或，每个信息码元都受到两个或两个以上监督元的监督，故不仅能够发现传输中的错误，两个以上监督元的监督，故不仅能够发现传输中的错误，当只有单个错误时，还能知道错误的位置并给以纠正。当只有单个错误时，还能知道错误的位置并给以纠正。 举例说明：举例说明： 令校验子令校验子s s1 1、s s2 2、s s3 3 分别为分别为: :035631345224561aaaasaaaasaaaas 根据一致监督关系，如果接收的码组没有错误，则根据一致监督关系，如果接收的码组没有错误，则s1 =s2 =s3 = 0；当码组在

30、传输过程中发生单个错误时，在；当码组在传输过程中发生单个错误时，在s1、s2、s3的的计算结果中，将有一个或几个不为零。这样根据计算结果中，将有一个或几个不为零。这样根据s1、s2、s3的不的不同数值，就可唯一地确定错误的位置。为此我们把同数值，就可唯一地确定错误的位置。为此我们把s1、s2、s3称称作作校验子校验子。 以以 (7,4) (7,4) 码为例，根码为例，根据据s s1 1、s s2 2、s s3 3的不同结果，的不同结果，可判断出具体的错误位置，可判断出具体的错误位置，如表如表3.43.4所示。所示。035631345224561aaaasaaaasaaaass s1 1、s、s

31、2 2、s、s3 3错码位置错码位置0 0 0无错无错0 0 1a a0 00 1 0a a1 11 0 0a a2 20 1 1a31 0 1a41 1 0a a51 1 1a a6 表表3.4 3.4 校验子和错码位置关系校验子和错码位置关系 例如接收到的码字例如接收到的码字=0000011=0000011，按校验子方程有：，按校验子方程有：s s1 1=0=0、s s2 2 =1 =1、s s3 3=1=1，从表，从表3.43.4可查出错码位置为可查出错码位置为a a3 3 。 在二进制系统中，能准确地知道错码的位置，就等于能在二进制系统中，能准确地知道错码的位置，就等于能纠正错码，这是

32、因为错码位置确定之后，只要把所在位置的纠正错码，这是因为错码位置确定之后，只要把所在位置的码元经过一个逻辑码元经过一个逻辑“非非”电路，就能把电路，就能把“0”0”变成变成“1”1”或把或把“1”1”变变“0”0”，从而完成，从而完成纠错纠错的任务。的任务。 二、循环码二、循环码 循环码循环码是一种码字间具有循环性质的码组。是一种码字间具有循环性质的码组。 循环循环是指将任一码字的各位闭合左移或右移后，生成的是指将任一码字的各位闭合左移或右移后，生成的新码字仍是该码组中的另一个码字。新码字仍是该码组中的另一个码字。 循环码仍由循环码仍由信息码信息码和和监督码监督码两部分组成，它也是一种线两部分

33、组成，它也是一种线性分组码，同样用（性分组码，同样用（n，k）来表示其码长和信息位数。）来表示其码长和信息位数。 在表（在表（3.5）所示的循环码组里，若将）所示的循环码组里，若将2号码字向右闭合号码字向右闭合移动一位就得到移动一位就得到5号码字，号码字，5号码字向右闭合移动一位即得到号码字向右闭合移动一位即得到7号码字，等等。号码字，等等。 表表3.5 3.5 循环码循环码 码字编号码字编号 信息码元信息码元a6a5a4监督码元监督码元a3a2a1a0 码字编号码字编号 信息码元信息码元a6a5a4 监督码元监督码元a3a2a1a0100000002101113010111040111001

34、51001011610111007 711001018 81110010 循环码是根据多项式代数运算原理来实现编、解码的。循环码是根据多项式代数运算原理来实现编、解码的。常 用 码 多 项 式 表 示 码 字 ， 如 表 （常 用 码 多 项 式 表 示 码 字 ， 如 表 （ 3 . 5 ） 第） 第 2 号 码 字号 码 字a6a5a4a3a2a1a0=0010111，因为其，因为其a4、a2、a1、a0等于等于1， 则可用则可用码多项式码多项式表示。表示。124)(2xxxCx 循环码也是一种循环码也是一种分组码分组码，由信息位和监督位组成一个，由信息位和监督位组成一个码字，即：码字，即

35、： 1.循环码的编码循环码的编码 )()()(xxknxnRAxC 上式中，上式中， 表示循环码的一个码字。表示循环码的一个码字。 为为信息位，信息位， 为信息码多项式，乘上为信息码多项式，乘上 ，在码多项式，在码多项式运算中表示把码多项式左移（运算中表示把码多项式左移（n n- -k k）位。）位。 )(xnC)(xknAx)(xAknx 例如表例如表(3.5)中的第中的第2号码字，信息码元为号码字，信息码元为A（ x）=001，但，但它们的权重位置在它们的权重位置在a6a5a4位置上，所以应该左移位置上，所以应该左移n-k =7-3=4位。位。R(x)为监督码多项式，第为监督码多项式，第2

36、号码字中的号码字中的R（X）=0111。 如何编出循环码呢如何编出循环码呢 ？ 循环码的编码特点是循环码的编码特点是循环码中的一个码字可以被一个循环码中的一个码字可以被一个xn-k次幂的多项式整除次幂的多项式整除。称这个称这个xn-k次幂的多项式为生成多项次幂的多项式为生成多项式，并用符号式，并用符号G(x)表示。表示。 例例3.13.1 已知信息码元为已知信息码元为110，编一个（，编一个（7，3）循环码字。循环码字。 解：第一步：由信息码元列出对应的解：第一步：由信息码元列出对应的k 1=2k 1=2次幂码多次幂码多项式项式A(x)A(x)，即，即 ：12110)(xxxA第二步：将第二步

37、：将 A(A(x x) ) 左移左移n n k k = 7 3 = 4 = 7 3 = 4位，求出位，求出x x4 4A(x)A(x)1100000)(5624xxxxx第三步：查表并选用下式为生成多项式第三步：查表并选用下式为生成多项式G(x)G(x)1)(24xxxxG第四步：进行第四步：进行 除法运算，求余数除法运算，求余数R(x)。 1)()(24564xxxxxxGxAx1 1 1122442352345234625624xxxxxxxxxxxxxxxxxxxxxxxxx余数01011)( 11) 1()()()(1)()()(224222424xxRxxxxxxxGxRxQxxxx

38、xxxGxAxkn即转换成下面格式：转换成下面格式： 第五步：把信息位第五步：把信息位x4A(X) 与余式与余式R(X) 合并，得合并，得 (7,3) 循环码为循环码为1100101) 1()()()(2564)(xxxxRxAxCXn前三位为信息码元，后四位（前三位为信息码元，后四位（0101）为监督码元。）为监督码元。 利用生成多项式可以方便地生成一利用生成多项式可以方便地生成一个循环码字。因为生成多项式可以对应个循环码字。因为生成多项式可以对应构成一个由移位寄存器和模构成一个由移位寄存器和模2相加器组成相加器组成的运算电路，利用这个电路就可完成循的运算电路，利用这个电路就可完成循环码的编

39、码。环码的编码。 由此可知：由此可知： 从编码原理可知，循环码多项式都可被生成多项式从编码原理可知，循环码多项式都可被生成多项式G(x)整除，因此，只要将接收到的码字除以整除，因此，只要将接收到的码字除以G(x)，观察余式，观察余式R(x)是否为零就可判断出传输中是否发生了错误。当是否为零就可判断出传输中是否发生了错误。当R(x)=0时，时，说明说明传输中无错误传输中无错误；如；如R(x) 0，说明传输中有错误，说明传输中有错误， 2循环码的检错与纠错循环码的检错与纠错 例如上例中，例如上例中，7号码字号码字C7=1100101。由于。由于a2误码，接收的误码，接收的时候时候C7 =11000

40、01，在第，在第3位发生了错码，对应的码多项式位发生了错码，对应的码多项式 。 上例中的生成多项式上例中的生成多项式 。将接收到的。将接收到的码字除以生成多项式码字除以生成多项式G(x)：1)(567xxxC1)(24xxxxG22442352345234625624 )(1 1 11 1xxRxxxxxxxxxxxxxxxxxxxxxxxx余数 得到的余式得到的余式 ， ，说明传输中有，说明传输中有错误。将其与产生误码的码字错误。将其与产生误码的码字 相加相加，便可得到正确的，便可得到正确的7号码字：号码字：从而完成了纠错的目的。从而完成了纠错的目的。 2)(xxR0)(xR11001011

41、) 1()()()(25625677xxxxxxxRxCxC)(7xC在广播电视设备中应用的典型例子是在广播电视设备中应用的典型例子是循环多余校验码循环多余校验码（CRCC）。它是由。它是由k = 82位信息码元和位信息码元和r =8位校验码元组位校验码元组成的（成的（90，82）循环码，主要用于）循环码，主要用于检错检错。 卷积码卷积码是将信息序列分成长度为是将信息序列分成长度为k0的一个一个子组，长的一个一个子组，长为为n0的每个子码组（叫作子码）包括的每个子码组（叫作子码）包括k0个信息位，个信息位，n0-k0个监个监督位。这督位。这n0-k0个监督元，不仅与本组的个监督元，不仅与本组的

42、k0个信息元有关，个信息元有关，而且也与前面若干个子组的信息元有关；本组的信息元不而且也与前面若干个子组的信息元有关；本组的信息元不但决定本组的监督元，而且也参与决定以后若干组的监督但决定本组的监督元，而且也参与决定以后若干组的监督元。元。 三、卷积码三、卷积码 卷积码编码器主要由卷积码编码器主要由移位寄存器移位寄存器构成，如图构成，如图3.33.3所示。所示。1编码器和监督元编码器和监督元 图中图中D0、D1为两级移位寄存器，信息序列由左面输入，为两级移位寄存器，信息序列由左面输入，其顺序是高位在右，低位在左。每一单位时间送入编码器一其顺序是高位在右，低位在左。每一单位时间送入编码器一个信息

43、元个信息元 。图图3.3 (3,1,2)卷积码编码器卷积码编码器图图3.3 (3,1,2)卷积码编码器卷积码编码器 移位寄存器移位寄存器的存储数据每个时刻右移一位。在输入信的存储数据每个时刻右移一位。在输入信息为息为m mj j的第的第j j时刻，时刻，D0的输出是其前一时刻的的输出是其前一时刻的m mj- j-1，D1移出的移出的是再前一个时刻的信息是再前一个时刻的信息m mj- j-2，m mj j 与与m mj- j-1，m mj- j-2经两个模经两个模2加法器加法器后，得到两个监督元后，得到两个监督元Pj, j,1、Pj, j,2，即，即 Pj, j,1m mj jm mj- j-1

44、 Pj,2j,2m mj jm mj j- -2 在输出端，由旋转开关选择输出序列，每一时刻旋转一在输出端，由旋转开关选择输出序列，每一时刻旋转一周，输出一个子码。第周，输出一个子码。第j j时刻输出的子码为时刻输出的子码为Cj j，Cj j(mj j，Pj j1，Pj j2)。对。对j+ j+1时刻，输入信息为时刻，输入信息为m mj j1，相应的监督元为相应的监督元为Pj j+1，1= mj j1+ mj j Pj j+1，2 = mj j1+ mj j-1 输出相应的子码输出相应的子码C Cj j= =（m mj j1，Pj j+1，1，Pj j+1，2）。对于这种编）。对于这种编码器，

45、每个子码的信息位码器，每个子码的信息位k01，码长，码长n n03。 2约束关系约束关系 卷卷积码的一个信息元积码的一个信息元m mj j，不但参与决定本子码的监督元，不但参与决定本子码的监督元，还要参与决定其后续子码的监督元。这表明，信息元使前后还要参与决定其后续子码的监督元。这表明，信息元使前后相继的子码之间产生了约束关系，也就是说，相继的子码之间产生了约束关系，也就是说，子码之间存在子码之间存在相关性相关性。这种相关性是若干信息元通过改变移位寄存器的状。这种相关性是若干信息元通过改变移位寄存器的状态来实现的。态来实现的。 由图由图3.4可看出，一个子码可看出，一个子码j j既与前面既与前

46、面N1个子码发生关个子码发生关联，而且还与其后面联，而且还与其后面N1个子码相关联，就像图中的各个个子码相关联，就像图中的各个虚线方框是一个套着一个的，正如一串不断的连环一样，所虚线方框是一个套着一个的，正如一串不断的连环一样，所以通常又把卷积码称为以通常又把卷积码称为连环码连环码。 图图3.4 卷积码子码之间的约束关系卷积码子码之间的约束关系 卷积码的卷积码的译码和编码过程相类似译码和编码过程相类似。 卷积码接收到的各个子码之间存在着一定的约束关系，卷积码接收到的各个子码之间存在着一定的约束关系，一组信息元不但影响着本子码的监督码元，同时还将影响着一组信息元不但影响着本子码的监督码元，同时还

47、将影响着其后面若干子码的监督码元。即后面（其后面若干子码的监督码元。即后面（N1）个子码都含有）个子码都含有本组的信息。我们可以充分利用后面（本组的信息。我们可以充分利用后面（N1）个子码来帮助）个子码来帮助本组信息的正确译码。这将使译码的正确率大大提高。本组信息的正确译码。这将使译码的正确率大大提高。 3卷积码的译码和纠错卷积码的译码和纠错 码元交织码元交织是将顺序传送的码元序列按一定规律重新进行是将顺序传送的码元序列按一定规律重新进行排列，以使突发误码分散到不相邻的样值中。排列，以使突发误码分散到不相邻的样值中。这样这样使使突发误突发误码变成了随机误码，再用消除随机误码的前向自动纠错码变成

48、了随机误码，再用消除随机误码的前向自动纠错（FECFEC）技术消除随机误码，在接收端再按规定的规律恢复）技术消除随机误码，在接收端再按规定的规律恢复成原来顺序。成原来顺序。 四、四、码元交织码元交织 码元交织的特点是码元交织的特点是不需增加任何码元不需增加任何码元，就可实现对突发，就可实现对突发错误的校正或对突发与随机误码的校正，使用十分广泛。错误的校正或对突发与随机误码的校正，使用十分广泛。 卷积码的卷积码的译码和编码过程相类似译码和编码过程相类似。 以（以（7 7，3 3）线性分组码为例，说明交织编码原理。（）线性分组码为例，说明交织编码原理。（7 7，3 3）分组码每个码字有）分组码每个

49、码字有7 7位，由位，由3 3位信息码和位信息码和4 4位监督码组成，位监督码组成，它的编码矩阵如下：它的编码矩阵如下： 1交织编码原理交织编码原理 2约束关系约束关系 交织编码矩阵中的行为前向自动纠错交织编码矩阵中的行为前向自动纠错FECFEC方式中的一个方式中的一个码字，它由码字，它由3 3位信息位及位信息位及4 4位监督位组成。矩阵中行的数目位监督位组成。矩阵中行的数目M称为称为交织深度交织深度。交织编码的过程是将。交织编码的过程是将FECFEC码字序列按行写入码字序列按行写入而按列读出。其交织编码输出序列为而按列读出。其交织编码输出序列为 a11 b21 c31mM1 a12 b22

50、c32.mM2 a13 b23 c33交织深度交织深度M M越大，离散度越大，抗突发差错能力也越强越大，离散度越大，抗突发差错能力也越强。交织深度交织深度M M越大，交织编码处理时间也越长，即是以时间为越大，交织编码处理时间也越长，即是以时间为代价的。代价的。 本章小结本章小结一、差错控制方式一、差错控制方式 二、反映纠错编码的参数二、反映纠错编码的参数 三、奇偶校验码三、奇偶校验码 四、分组码四、分组码 五、码元交织技术五、码元交织技术 一、差错控制方式一、差错控制方式 信道编码又称为差错控制编码或纠错编码。信道编码又称为差错控制编码或纠错编码。 错码分为三种：一是以随机、个别、独立出现的错

51、码分为三种：一是以随机、个别、独立出现的随机随机错错码；二是短时间内大量出现的码；二是短时间内大量出现的突发突发错码；三是随机错码和突错码；三是随机错码和突发错码的混合称为发错码的混合称为混合混合错码。错码。 差错控制有三种方式：（差错控制有三种方式：（1 1）检错重传）检错重传ARQ，（，（2 2）前向）前向纠错纠错FEC，（，（3 3）混合纠错）混合纠错HEC。在移动通信中用得较多的是。在移动通信中用得较多的是前向纠错前向纠错FCCFCC差错控制方式，它的特点是无需反馈信道，实时差错控制方式，它的特点是无需反馈信道，实时性好，但编解码电路复杂，编码效率低。性好，但编解码电路复杂，编码效率低。 二、反映纠错编码的参数二、反映纠错编码的参数 反映纠错编码的参数有反映纠错编码的参