通信原理精品课--第八章 差错控制编码

1、电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课通信原理通信原理主讲人：吴海涛主讲人：吴海涛 副教授副教授TEL:mail:第第1页，共页，共61页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课第第8 8章章 差错控制编码差错控制编码8.1 概述概述8.2 常用的几种简单分组码常用的几种简单分组码8.3 线性分组码线性分组码8.4 循环码循环码8.5 小结小结第第2页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1

2、 概述概述8.1.1 信道编码信道编码在数字通信中，根据不同的目的，编码可分为在数字通信中，根据不同的目的，编码可分为信源编码信源编码和和信信道编码道编码。信源编码是为了提高数字信号的有效性以及为了使。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率，模拟信号数字化而采取的编码。信道编码是为了降低误码率， 提高数字通信的可靠性而采取的编码。数字信号在传输过程提高数字通信的可靠性而采取的编码。数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接

3、收设备本身的噪声，抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。码技术。第第3页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.1 信道编码信道编码另外，按照噪声或干扰的变化规律，可把信道分为三类：另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是恒参高斯白噪声信道是典型的随机

4、信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道，是典型的突发信道， 错误是成串成群出现的，即在短时间内错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。型的信道，应采用不同的差错控制方式。 第第4页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理

5、精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.2 差错控制方式差错控制方式 发端纠错码收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号图8-1 差错控制方式 第第5页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.2 差错控制方式差错控制方式 1. 前向纠错方式前向纠错方式(80年代年代) 前向纠错方式记作前向纠错方式记作FEC (Forward Error Correction)。发。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输端发

6、送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。在二进制码元的情况下，能够确定错码的位置，中的错误。在二进制码元的情况下，能够确定错码的位置，就相当于能够纠正错码。将错码就相当于能够纠正错码。将错码“0”改为改为“1”或或“1”改为改为“0”即可。其特点是单向传输，实时性好，但译码设备较复即可。其特点是单向传输，实时性好，但译码设备较复杂。杂。 第第6页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.2 差错控制方式差错控制方式 2. 检错重发方式（书上检错重发方式（书上3种方式）种方式） 检错

7、重发又称自动请求重传方式，记作检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat reQuest)。 由发端送出能够发现错误的码，由收端判决传输中由发端送出能够发现错误的码，由收端判决传输中有无错误产生，如果发现错误，则通过反向信道把这一判决结有无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效，简单，对突发错误和信道

8、干扰较严重时有效， 但实时性差，主但实时性差，主要在计算机数据通信与深空通信中得到应用。要在计算机数据通信与深空通信中得到应用。 第第7页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.2 差错控制方式差错控制方式 图8-2 CFDP协议ARQ-延迟NAK模式 第第8页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.2 差错控制方式差错控制方式 3. 混合纠错方式混合纠错方式 混合纠错方式记作混合纠错方式记作HEC(

9、Hybrid Error Correction)是是FEC和和ARQ方式的结合。发端发送具有自动纠错同时又具有检错方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但能检测出来，则经过反馈信道请求发端重发。这种方式具但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此，有自动纠错和检错重发的优点，可达到较低的误码率，因此， 近年来得到广

10、泛应用。近年来得到广泛应用。 第第9页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.3 纠错码的分类纠错码的分类 (1) 根据纠错码各码组信息元和监督元的函数关系，可分为根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。性方程式，则称为线性码，否则为非线性码。(2) 根据上述关系涉及的范围，可分为分组码和卷积码。分组根据上述关系涉及的范围，可分为分组码和卷积码。分

11、组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。本组的信息元有关，而且还与前面若干组的信息元有关。(3) 根据码的用途，可分为检错码和纠错码。检错码以检错为根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。 第第10页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编

12、码的基本原理 无论是具有检错能力还是纠错功能的编码，统称为纠错编码。无论是具有检错能力还是纠错功能的编码，统称为纠错编码。现在用一个例子说明其原理。设有一种由现在用一个例子说明其原理。设有一种由3 个二进制码元构个二进制码元构成的编码，共有成的编码，共有8种不同的可能码组。若将其全部用来表示种不同的可能码组。若将其全部用来表示天气，则可以表示天气，则可以表示8种不同的天气。例如（种不同的天气。例如（1）：）： 000晴晴 001云云 010阴阴 011雨雨 100雪雪 101霜霜 110雾雾 111雹雹这时，若一个码组在传输中发生错码，则因接收端无法发现这时，若一个码组在传输中发生错码，则因接

13、收端无法发现错码，而将收到错误信息。错码，而将收到错误信息。第第11页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 假设在此假设在此8种码组中仅允许使用种码组中仅允许使用4种来传送天气。例如（种来传送天气。例如（2）：）：000晴晴 011云云 101阴阴 110雨雨为许用码组，其它为许用码组，其它4种为禁用码组。这时，接收端有可能发种为禁用码组。这时，接收端有可能发现（检测到）码组中的一个错码。例如：若现（检测到）码组中的一个错码。例如：若000中有一个错中有

14、一个错码，则它可能错成码，则它可能错成100、010或或001。但是这。但是这3种码组都是禁用种码组都是禁用码组，所以能够发现错码。不难验证，上面这码组，所以能够发现错码。不难验证，上面这4个码组的任个码组的任一码元出错都将变成禁用码组，所以这种编码能发现一个错一码元出错都将变成禁用码组，所以这种编码能发现一个错码。码。第第12页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 当当000有有3个错码时，它变成个错码时，它变成111，也是禁用码组，其它，也是禁用码组

15、，其它3个码个码组情况也是如此。所以这种编码也能发现组情况也是如此。所以这种编码也能发现3个错码。但是它个错码。但是它不能发现不能发现2个错码，因为发生个错码，因为发生2个错码后得到的仍是许用码组。个错码后得到的仍是许用码组。这种编码只能检错不能纠错。例如，若接收到的码组为这种编码只能检错不能纠错。例如，若接收到的码组为100，它是禁用码组，可以判断其中有错码。若这时只有它是禁用码组，可以判断其中有错码。若这时只有1个错码，个错码，则则000、110、101这这3种许用码错了种许用码错了1个码元后都可能变成个码元后都可能变成100。所以不能判断其中哪个码组是原发送码组，即不能纠正错误。所以不能

16、判断其中哪个码组是原发送码组，即不能纠正错误。要想纠正错误还要增大冗余度。要想纠正错误还要增大冗余度。000晴晴 011云云 101阴阴 110雨雨第第13页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 例如（例如（3）规定）规定 只许用两个码组：只许用两个码组：000晴晴 111雨雨其它都是禁用码组。这种编码能检测出两个以下的错码，或其它都是禁用码组。这种编码能检测出两个以下的错码，或纠正一个错码。例如当收到纠正一个错码。例如当收到“100”时，若采用的是纠错

17、技术，时，若采用的是纠错技术，则认为它是由则认为它是由“000（晴）（晴）”中第一位出错造成的，故纠正中第一位出错造成的，故纠正为为“000（晴）（晴）”；若采用的是检错技术，它可以发现两个；若采用的是检错技术，它可以发现两个以下的错码，即以下的错码，即“000”错一位，或错一位，或“111”错两位都可能变成错两位都可能变成“100”，故能发现此码组有错，但是不能纠错。从上面的例，故能发现此码组有错，但是不能纠错。从上面的例子可以建立子可以建立“分组码分组码”的概念。的概念。第第14页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.

18、1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 用例（用例（2）的例子，由于）的例子，由于4种信息用种信息用2比特就能代表，现在为比特就能代表，现在为了纠错用了了纠错用了3比特，加了一位监督位构成可一个具有纠错功比特，加了一位监督位构成可一个具有纠错功能的独立码组，并且监督位仅监督本组中的信息码元，则称能的独立码组，并且监督位仅监督本组中的信息码元，则称这种编码为这种编码为分组码分组码。第第15页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理

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

20、码字，称为许用码组许用码组。其余。其余 2n-2k个个码字未被选用，称为码字未被选用，称为禁用码组禁用码组。 第第16页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 1. 分组码分组码在分组码中，非零码元的数目称为码字的汉明重量，在分组码中，非零码元的数目称为码字的汉明重量， 简称简称码码重重。例如，码字。例如，码字 10110，码重，码重w=3。两个等长码组之间对应位取值不同的数目称为这两个码组的两个等长码组之间对应位取值不同的数目称为这两个码组的汉明汉明(H

21、amming)距离距离， 简称简称码距码距。例如。例如 11000 与与 10011之间之间的距离的距离d=3。码组集中任意两个码字之间距离的最小值称为。码组集中任意两个码字之间距离的最小值称为码的最小距离，用码的最小距离，用d0表示。表示。最小码距最小码距是码的一个重要参数，是码的一个重要参数， 它是衡量码检错、纠错能力的依据。它是衡量码检错、纠错能力的依据。第第17页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 2. 检错和纠错能力检错和纠错能力若分组码码字

22、中的监督元在信息元之后，而且是信息元的简单若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复，则称该分组码为重复码重复码。它是一种简单实用的检错码，。它是一种简单实用的检错码， 并有一定的纠错能力。例如并有一定的纠错能力。例如(2,1)重复码，两个许用码组是重复码，两个许用码组是 00 与与 11，d0=2，收端译码，出现，收端译码，出现 01、10 禁用码组时，可以发现禁用码组时，可以发现传输中的一位错误。如果是传输中的一位错误。如果是(3,1)重复码，两个许用码组是重复码，两个许用码组是 000 与与111, d0=3; 当收端出现两个或三个当收端出现两个或三个

23、 1 时，判为时，判为 1，否则判为，否则判为 0。此时，可以纠正单个错误，或者该码可以检出两个错误。此时，可以纠正单个错误，或者该码可以检出两个错误。 第第18页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 3.码距的几何意义码距的几何意义(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一般而言，码距是一般而言，码距是 n 维空间中单位正多面维空间中单位正多面体顶点间的汉明距离。体顶点

24、间的汉明距离。第第19页，共页，共68页页3位码组位码组3维空间顶点坐维空间顶点坐标（标（a0,a1,a2 ）各顶点之间沿立各顶点之间沿立方体各边行走的方体各边行走的几何距离。几何距离。电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 4. 纠检错能力纠检错能力一种编码的纠检错能力：一种编码的纠检错能力：决定于最小码距决定于最小码距d0的值。的值。为了能检测为了能检测e个错码，个错码，要求最小码距要求最小码距10 ed0123BA汉明距离ed0码距等于3的两个码组设有一个码组A，它位

25、于0点，若A中发生一个错码，则A的位置将移动到以0为中心，以1为半径的圆上。若A中发生2个错码，则。因此，若最小码距不小于3，例如图中B点为最小码距的码组，则当发生不多于两个错码时，码组A的位置就不会移动到另一个许用码组B的位置上。P332第第20页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 4. 纠检错能力纠检错能力一种编码的纠检错能力：一种编码的纠检错能力：决定于最小码距决定于最小码距d0的值。的值。为了能纠正为了能纠正 t 个错码，个错码，要求最小码距要

26、求最小码距 120 tdBtA汉明距离012345td0码距等于5的两个码组若A和B中的错码不多于两个，其位置均不会超出以2为半径的圆，因而不会错到另一个码组的范围内。若此编码中任意两个码组之间的码距都不小于5，则只要错码不超过两个就能够纠正。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。第第21页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 4. 纠检错能力纠检错能力一种编码的纠

27、检错能力：一种编码的纠检错能力：决定于最小码距决定于最小码距d0的值。的值。为了能纠正为了能纠正t个错码，个错码，同时检测同时检测e个错码，个错码，要求最小码距要求最小码距 在解释公式之前，先来分析上图所示的例子。在解释公式之前，先来分析上图所示的例子。 )(10tetedBtA汉明距离012345td0第第22页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 4. 纠检错能力纠检错能力BtA汉明距离012345td0图中码组图中码组A和和B之间距离为之间距离为5

28、。按照。按照检错能力公式，最多能检测检错能力公式，最多能检测4个错码，个错码，即即e = d0 1 = 5 1 = 4，按照纠错能，按照纠错能力公式纠错时，能纠正力公式纠错时，能纠正2个错码。但个错码。但是，不能同时做到两者，因为当错是，不能同时做到两者，因为当错码位数超过纠错能力时，该码组立码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地即进入另一码组的圆内而被错误地“纠正纠正”了。例如，码组了。例如，码组A若错了若错了3位，就会被误认为码组位，就会被误认为码组B错了错了2位造位造成的结果，从而被错成的结果，从而被错“纠纠”为为B。这。这就说，检错和纠错公式不能同时成就说，检错和

29、纠错公式不能同时成立或同时运用。立或同时运用。)(10teted第第23页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 4. 纠检错能力纠检错能力所以，为了在可以纠正所以，为了在可以纠正t个错码的同个错码的同时，能检测时，能检测e个错码，需要码组个错码，需要码组A发发生生e个错码的位置与码组个错码的位置与码组B的纠错范的纠错范围至少距离为围至少距离为1，否则落在该纠错范，否则落在该纠错范围内就会被错误地围内就会被错误地“纠正纠正”。纠检结合工作方式：纠检结合工作

30、方式：当错码数量少时，系统按前向纠错当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高方式工作，以节省重发时间，提高传输效率；传输效率；当错码数量多时，系统按反馈重发当错码数量多时，系统按反馈重发的纠错方式工作，以降低系统的总的纠错方式工作，以降低系统的总误码率。误码率。)(10tetedAB1tt汉明距离e码距等于(e+t+1)的两个码组第第24页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编码的基本原理纠错编码的基本原理 n 纠检错能力总结：纠检错能力总结：u 码的最小距离码的最

31、小距离d0直接关系着码的检错和纠错能力；任一直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内分组码，若要在码字内: (1) 检测检测e个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离d0e+1; (2) 纠正纠正t个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离d02t+1; (3) 纠正纠正t个同时检测个同时检测e(t)个随机错误，则要求码的最小个随机错误，则要求码的最小 距离距离d0t+e+1。第第25页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.1 8.1 概述概述8.1.4 纠错编

32、码的基本原理纠错编码的基本原理 5.编码效率编码效率用差错控制编码提高通信系统的可靠性，是以降低有效性为代用差错控制编码提高通信系统的可靠性，是以降低有效性为代价换来的。我们定义编码效率价换来的。我们定义编码效率R来衡量有效性来衡量有效性:R=k/n其中其中, k是信息元的个数，是信息元的个数，n为码长。为码长。对纠错码的基本要求是对纠错码的基本要求是: 检错和纠错能力尽量强；编码效率尽检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。有一定纠、检错能力和编码效

33、率，并且易于实现。 第第26页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.2 8.2 常用的几种简单分组码常用的几种简单分组码8.2.1 奇偶监督码奇偶监督码 奇偶监督码是在原信息码后面附加一个监督元，使得码组中奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的为奇数或偶数的(n,n-1)系统系统分组码。分组码。奇偶监督码又分为奇监督码和偶监督码。奇偶监督码又分为奇监督码和偶监督码。第第27页，共页，共68页

34、页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.2 8.2 常用的几种简单分组码常用的几种简单分组码8.2.1 奇偶监督码奇偶监督码 设码字设码字A=an-1,an-2,a1,a0，对于偶监督码有，对于偶监督码有式中，式中，a0为监督码，其它为信息码。为监督码，其它为信息码。奇监督码情况相似，只是码组中奇监督码情况相似，只是码组中“1”的数目为奇数，即满足的数目为奇数，即满足 而检错能力与偶监督码相同。而检错能力与偶监督码相同。 奇偶监督码的编码效率奇偶监督码的编码效率R为为 00121aaaann1021aaannnnR/ ) 1( 检奇数个错码

35、第第28页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.2 8.2 常用的几种简单分组码常用的几种简单分组码8.2.2 行列监督码行列监督码 110010100000100001101001111000011100111000001010101010111000111100图8-2 (66,50)行列监督码 又叫方阵码或矩形码，它的构造方法是先将若干奇偶监督码组按行排列成矩阵，再按列增加第二维监督位。第第29页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.2 8.2

36、常用的几种简单分组码常用的几种简单分组码8.2.3 恒比码恒比码码字中码字中 1 的数目与的数目与 0 的数目保持恒定比例的码称为的数目保持恒定比例的码称为恒比码恒比码。 由于恒比码中，每个码组均含有相同数目的由于恒比码中，每个码组均含有相同数目的 1 和和 0，因此恒比，因此恒比码又称等重码，定码又称等重码，定 1 码。这种码在检测时，只要计算接收码元码。这种码在检测时，只要计算接收码元中中 1 的数目是否正确，就知道有无错误。的数目是否正确，就知道有无错误。 第第30页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.2 8.2

37、常用的几种简单分组码常用的几种简单分组码8.2.3 恒比码恒比码目前我国电传通信中普遍采用目前我国电传通信中普遍采用 3：2 码，又称码，又称“5 中取中取 3”的恒比码，即每个码组的长度为的恒比码，即每个码组的长度为 5，其中其中 3 个个“1”。这时可能编成的不同码组数目。这时可能编成的不同码组数目等于从等于从 5 中取中取 3 的组合数的组合数 10，这，这 10 个许用码组个许用码组恰好可表示恰好可表示 10 个阿拉伯数字，如表个阿拉伯数字，如表 8-1 所示。所示。而每个汉字（区位码）又是以四位十进制数来而每个汉字（区位码）又是以四位十进制数来代表的（吴代表的（吴 4666 海海 2

38、603 涛涛 4446 ）。）。实践证明，采用这种码后，我国汉字电报的差实践证明，采用这种码后，我国汉字电报的差错率大为降低。错率大为降低。 四码电报四码电报第第31页，共页，共68页页表8-1 3 2 恒比码 电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.2 8.2 常用的几种简单分组码常用的几种简单分组码8.2.3 恒比码恒比码由于汉字结构复杂，字型繁多，一字一由于汉字结构复杂，字型繁多，一字一“面孔面孔”，拍电报不直接，拍电报不直接用电码来表示。因此，采用由四个阿拉伯数字代表一个汉字的用电码来表示。因此，采用由四个阿拉伯数字代表一个汉字的方法

39、，简称方法，简称“四码电报四码电报”，中国汉字多达，中国汉字多达6万字，常用的汉字只万字，常用的汉字只有一万个，所以用有一万个，所以用10的的4次方（次方（10，000）来表示。）来表示。1873年，法年，法国驻华人员威基杰（国驻华人员威基杰（SAViguer）参照）参照康熙字典康熙字典的部首排的部首排列方法，挑选了常用汉字列方法，挑选了常用汉字6800多个，编成了第一部汉字电码本，多个，编成了第一部汉字电码本，名为名为电报新书电报新书。后来，由我国的郑观应将其改编成为。后来，由我国的郑观应将其改编成为中中国电报新编国电报新编，这是中国最早的汉字电码本。，这是中国最早的汉字电码本。 第第32页

40、，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.1 定义及性质定义及性质n 如果信息码元与监督码元之间的关系可以用一组线性方程如果信息码元与监督码元之间的关系可以用一组线性方程来表示，且监督码元仅由本码组的信息码元来确定，而与来表示，且监督码元仅由本码组的信息码元来确定，而与其他码组的码元无关，则称该编码为其他码组的码元无关，则称该编码为线性分组码线性分组码。n 线性分组码中信息码元和监督码元是用线性方程联系起来线性分组码中信息码元和监督码元是用线性方程联系起来的。线性码建立在代数学群论基础上

41、的。线性码建立在代数学群论基础上,线性码各许用码组的线性码各许用码组的集合构成代数学中的群集合构成代数学中的群,因此又称群码。在群中只存在一种因此又称群码。在群中只存在一种运算，即模运算，即模2和，通常四则运算中的加、减法在这里都是模和，通常四则运算中的加、减法在这里都是模2和的关系。所以后面将简化运算符号和的关系。所以后面将简化运算符号 为为“+”。 第第33页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.1 定义及性质定义及性质性质：性质：封闭性：任意两个许用码组相加后（按位进行模封闭性

42、：任意两个许用码组相加后（按位进行模2和，所得和，所得编码仍是许用码组）编码仍是许用码组）1. 最小码距等于非零码的最小码重最小码距等于非零码的最小码重(除全除全0码外码外) 第第34页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.1 定义及性质定义及性质现以现以(7,4)分组码为例来说明线性分组码的特点。设其码字为分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前，其中前 4 位是信息元，后位是信息元，后 3 位是监位是监督元，督元， 可用下列

43、线性方程组来描述该分组码，产生监督元。可用下列线性方程组来描述该分组码，产生监督元。) 18(346035614562aaaaaaaaaaaa注意：注意：+表示表示模模2和和第第35页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码表 8-2 (7,4)码的码字表 最小码最小码距距d0=？第第36页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 8-1第第

44、37页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 并简记为并简记为 H AT = 0T 或或A HT = 0A = a6 a5 a4 a3 a2 a1 a00 = 000右上标右上标“T”表示将矩阵转置。表示将矩阵转置。将将H称为监督矩阵。只要监督矩阵称为监督矩阵。只要监督矩阵H给定，编给定，编码时监督位和信息位的关系就完全确定了。码时监督位和信息位的关系就完全确定了。 101100111010101110100H第第38页，共页，共68页页电

45、子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G H矩阵的性质：矩阵的性质：(1) H的行数就是监督关系式的数目，它等于监督位的数目的行数就是监督关系式的数目，它等于监督位的数目r。H的每行中的每行中“1”的位置表示相应码元之间存在的监督关系。例如，的位置表示相应码元之间存在的监督关系。例如，H的第一行的第一行1110100表示监督位表示监督位a2是由是由a6 a5 a4之和决定的。之和决定的。H矩阵矩阵可以分成两部分，例如可以分成两部分，例如rIPH001101101

46、011011001110第第39页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 其中，其中，P为为rk阶矩阵，阶矩阵，Ir为为rr阶单位矩阵。可以写成阶单位矩阵。可以写成H =P Ir形式的矩阵称为形式的矩阵称为典型监督矩阵典型监督矩阵。HAT=0T，说明，说明H矩阵与码字的转置乘积必为零，可以矩阵与码字的转置乘积必为零，可以用来作为判断接收码字用来作为判断接收码字A是否出错的依据。是否出错的依据。 第第40页，共页，共68页页rIPH00110

47、1101011011001110电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G H矩阵的性质：矩阵的性质：(2) 由代数理论可知，由代数理论可知，H矩阵的各行应该是线性无关的，否则将矩阵的各行应该是线性无关的，否则将得不到得不到 r个线性无关的监督关系式，从而也得不到个线性无关的监督关系式，从而也得不到 r个独立的监个独立的监督位。若一矩阵能写成典型阵形式督位。若一矩阵能写成典型阵形式P Ir，则其各行一定是线性，则其各行一定是线性无关的。因为容易验证无关的。因为容

48、易验证Ir的各行是线性无关的，故的各行是线性无关的，故P Ir的各行的各行也是线性无关的。也是线性无关的。rIPH001101101011011001110第第41页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 若把监督方程补充为下列方程若把监督方程补充为下列方程 第第42页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和

49、生成矩阵和生成矩阵G 可改写为矩阵形式可改写为矩阵形式 第第43页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 1101000101010001100101110001GQIGkTPQ110101011111G为生成矩阵，由由它可以产生整个码它可以产生整个码组，组，具有Ik Q形式的生成矩阵称为典型生成矩阵。各行仍线性无关！各行仍线性无关！由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位的位置不变，中，信息位的位置不变，监督位附加于其

50、后。这种形监督位附加于其后。这种形式的码称为式的码称为系统码系统码。 第第44页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.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，且，且 ABE(8 - 2)

51、 10ie当当bi=ai 当当biai 码元未错码元有错第第45页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.3伴随式伴随式(校正子校正子)S 式式(8 - 2)也可写作也可写作令令S=BHT，称为，称为伴随式或校正子伴随式或校正子。当当H确定后，确定后，S只与只与E有关，而与有关，而与A无关。这意味着无关。这意味着S和错和错码码E之间有确定的线性变换关系。若之间有确定的线性变换关系。若S和和E有一一对应关有一一对应关系，则系，则S将能代表错码位置。将能代表错码位置。EAB表示发送码组A与

52、错码矩阵之和等于接收码组BTTTEHHEABHS)(第第46页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.3伴随式伴随式(校正子校正子)S 线性码有一个重要性质，就是它的封闭性。封闭性是指线性码有一个重要性质，就是它的封闭性。封闭性是指一种线性码中任意两个码组之和仍为这种编码一种线性码中任意两个码组之和仍为这种编码 中的一个中的一个码组。也就是说，若码组。也就是说，若A1和和A2是一种线性码中的两个码组，是一种线性码中的两个码组，则（则（A1+A2）仍是其中的一个码组。（证明）仍是其中的一

53、个码组。（证明）第第47页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.3 8.3 线性分组码线性分组码8.3.3伴随式伴随式(校正子校正子)S 表 8-3 (7,4)码S与E的对应关系 TEHS 第第48页，共页，共68页页检错能力？能纠错两个及以上？检错能力？能纠错两个及以上？电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.4 8.4 循环码循环码 8.4.1 定义定义循环性循环性是指任一码组循环是指任一码组循环（左移或右移）一位后仍（左移或右移）一位后仍然是该编码中的一个码组。然是

54、该编码中的一个码组。（仍属于线性分组码）（仍属于线性分组码）表 8-4 一种(7, 3)循环码的全部码组表中第表中第4码组向右移一位即码组向右移一位即得到第得到第2码组；第码组；第7码组向码组向左移一位即得到第左移一位即得到第6码组。码组。第第49页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.4 8.4 循环码循环码 8.4.1 定义定义循环码的定义：循环码的定义：如果如果 (n,k) 线性分组码的任意码矢线性分组码的任意码矢A=(an1, an2, a0) 的的 i 次循环移位，所得矢量次循环移位，所得矢量A(i)=(an1i

55、, an2i, , a0, an1, , ani) 仍是一个码矢，则称此线性码为仍是一个码矢，则称此线性码为 (n,k) 循环码。循环码。第第50页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.4 8.4 循环码循环码 8.4.1 定义定义在代数理论中，为了便于计算，常用码多项式表示码字。在代数理论中，为了便于计算，常用码多项式表示码字。(n,k)循环码的码字，其码多项式循环码的码字，其码多项式(以降幂顺序排列以降幂顺序排列)为：为：注意：上式中注意：上式中x的值没有任何意义，仅用它的幂代表码元的值没有任何意义，仅用它的幂代表码元

56、的位置。例：码组的位置。例：码组1 1 0 0 1 0 1可以表示为可以表示为 012211)(axaxaxaxAnnnn11010011)(25623456xxxxxxxxxxA第第51页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.4 8.4 循环码循环码 8.4.2 生成多项式及生成矩阵生成多项式及生成矩阵 如果一种码的所有码多项式都是多如果一种码的所有码多项式都是多项式项式g(x)的倍式，则称的倍式，则称g(x)为该码的为该码的生成多项式生成多项式。在。在(n,k)循环码中任意循环码中任意码多项式码多项式A(x)都是最低次

57、码多项式都是最低次码多项式的倍式。如表的倍式。如表 8-4 的的(7,3)循环码中，循环码中，1)()(2341xxxxAxg第第52页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.4 8.4 循环码循环码 8.4.2 生成多项式及生成矩阵生成多项式及生成矩阵 其它码多项式都是其它码多项式都是g(x)的倍式，的倍式， 即即 )()()() 1()()() 1()()() 1()()()()() 1()()(0)(2726254320 xgxxAxgxxAxgxxxAxgxxxAxgxxAxgxxAxgxA)()(1xgxA第第53

58、页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.4 8.4 循环码循环码 8.4.2 生成多项式及生成矩阵生成多项式及生成矩阵 循环码的生成矩阵常用多项式的形式来表示循环码的生成矩阵常用多项式的形式来表示 )()()()()(21xgxxgxgxxgxxGkk在循环码中，一个在循环码中，一个(n, k)码有码有2k个不同个不同的码组。若用的码组。若用g(x)表示其中前表示其中前(k-1)位位皆为皆为“0”的码组，则的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这都是码组，而且这k个码组是线性无关

59、的。因此它们可个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵以用来构成此循环码的生成矩阵G。若前k位为0会怎样？由于由于G是是k行行n列的矩列的矩阵，因此若能找到阵，因此若能找到k个线性无关的已知码个线性无关的已知码组，就能构成矩阵组，就能构成矩阵G。1)(111xgxgxxgrrr为什么？第第54页，共页，共68页页电子信息与机电工程学院电子信息与机电工程学院通信原理通信原理精品资源共享课精品资源共享课8.4 8.4 循环码循环码 8.4.2 生成多项式及生成矩阵生成多项式及生成矩阵 在循环码中除全在循环码中除全“0”码组外，再没有连续码组外，再没有连续k位均为位均为“0”的的码

60、组，即连码组，即连“0”的长度最多只能有的长度最多只能有(k-1)位。否则，在经位。否则，在经过若干次循环移位后将得到一个过若干次循环移位后将得到一个k位信息位全为位信息位全为“0”，但，但监督位不全为监督位不全为“0”的一个码组。这在线性码中显然是不的一个码组。这在线性码中显然是不可能的。因此，可能的。因此，g(x)必须是一个必须是一个常数项不为常数项不为“0”的的(n-k)次次多项式多项式，而且这个，而且这个g(x)还是这种还是这种(n, k)码中次数为码中次数为(nk)的的唯一多项式唯一多项式。为什么常数项不为0？(n-1)-(k-1)=n-k=r第第55页，共页，共68页页电子信息与机