差错控制编码基础课件

1、第一章第一章纠错编码技术目的目的：提高抗干扰能力，使差：提高抗干扰能力，使差错率最小错率最小实质实质：增加冗余度，扩大信号：增加冗余度，扩大信号空间，增大信号间距离空间，增大信号间距离意义意义：通过纠错编码方法，可：通过纠错编码方法，可以用不可靠的信道实现可靠的以用不可靠的信道实现可靠的传输传输第一章第一章第一章 纠错编码的基本概念1.1纠错编码的理论基础纠错编码的理论基础1.2纠错编码的分类纠错编码的分类1.3纠错编码的基本概念纠错编码的基本概念1.4有噪信道编码定理有噪信道编码定理1.5译码规则和编码规则译码规则和编码规则1.6纠错编码的本质纠错编码的本质1.7纠错编码方法的性能纠错编码方

2、法的性能1.8纠错编码系统的性能纠错编码系统的性能第一章第一章 香农第二定理指出，当信息香农第二定理指出，当信息传输速率低于信道容量时，通传输速率低于信道容量时，通过某种编译码方法，就能使错过某种编译码方法，就能使错误概率为任意小。目前已有了误概率为任意小。目前已有了许多有效的编译码方法，并形许多有效的编译码方法，并形成了一门新的技术成了一门新的技术纠错编纠错编码技术。码技术。第一章第一章 编码有编码有信源编码信源编码和和信道编码信道编码。 纠错编码即信道编码。纠错编码即信道编码。 信源编码的目的是压缩冗余度，信源编码的目的是压缩冗余度，提高信息的传输速率。提高信息的传输速率。 信道编码的目的

3、是提高信息传信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输输时的抗干扰能力以增加信息传输的可靠性的可靠性。 第一章第一章 有实用价值的码应该具备良好有实用价值的码应该具备良好的结构特性，这样可保证译码简单的结构特性，这样可保证译码简单易行。香农在证明有噪声信道编码易行。香农在证明有噪声信道编码定理时提出定理时提出随机编码随机编码方法，这不过方法，这不过是一种为避免寻找好码而采取的权是一种为避免寻找好码而采取的权宜之计，有理论意义而无实用价值。宜之计，有理论意义而无实用价值。真正实用的信道编码还须用适当的真正实用的信道编码还须用适当的数学工具来构造，使得构造出的码数学工具来构造，使得构

4、造出的码具有很好的结构特性，以便译码。具有很好的结构特性，以便译码。第一章第一章1.1纠错编码的理论基础 通信的目的是要把消息及时可靠地传送通信的目的是要把消息及时可靠地传送给对方。给对方。 若要求若要求快速快速，则必然使得每个数据码元，则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少，从所占的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加，传而在受到干扰后产生错误的可能性增加，传送消息的可靠性减低。送消息的可靠性减低。 若要求若要求可靠可靠，则使得传送消息的速率变，则使得传送消息的速率变慢。慢。 在数字通信系统中可靠与快速往往是一在数字通信系统中可靠与快速往往是一

5、对矛盾。对矛盾。 通信理论本身通信理论本身( (包括纠错码包括纠错码) )也正是在解决也正是在解决这对矛盾中不断发展起来的。这对矛盾中不断发展起来的。 第一章第一章 香农第二定理是有噪信道编码定理，香农第二定理是有噪信道编码定理，作为一个作为一个存在性存在性定理，指出可以用任意接定理，指出可以用任意接近信道容量的信息传输速率传送消息，且近信道容量的信息传输速率传送消息，且出错的概率可以任意小，这就引发了人们出错的概率可以任意小，这就引发了人们对纠错码的研究。纠错码理论的中心任务对纠错码的研究。纠错码理论的中心任务就是要针对具有不同干扰特性的各种信道就是要针对具有不同干扰特性的各种信道设计出编码

6、效率高、抗干扰性能好而编译设计出编码效率高、抗干扰性能好而编译设备又较简单的纠错码。设备又较简单的纠错码。第一章第一章 纠错编码，顾名思义，是当消息经纠错编码，顾名思义，是当消息经过有噪声信道传输或要恢复储存的数据过有噪声信道传输或要恢复储存的数据时用来纠正错误的。时用来纠正错误的。 用来传输消息的物理介质叫做信道用来传输消息的物理介质叫做信道（如电话线、卫星连接、用于移动通信（如电话线、卫星连接、用于移动通信的无线信道等）。的无线信道等）。 不同种类的信道易产生不同种类的不同种类的信道易产生不同种类的噪声，对传输的数据造成不同的损害。噪声，对传输的数据造成不同的损害。纠错编码就是试图克服信道

7、中噪声造成纠错编码就是试图克服信道中噪声造成的损害。的损害。 第一章第一章 纠错编码的纠错编码的基本思想基本思想是在消息通过一个是在消息通过一个有噪声信道传输前以多余符号的形式在消息有噪声信道传输前以多余符号的形式在消息中增添冗余度，这种冗余度是在一定的规则中增添冗余度，这种冗余度是在一定的规则控制下添加的。编码后的消息在传输时可能控制下添加的。编码后的消息在传输时可能还会遭到信道中噪声的损害。在接收端，如还会遭到信道中噪声的损害。在接收端，如果错误数在该码的设计限度内，则原始消息果错误数在该码的设计限度内，则原始消息可以从受损的消息中恢复。可以从受损的消息中恢复。 纠错编码就是靠增加纠错编码

8、就是靠增加“冗余冗余”码元来克码元来克服或减轻噪声影响的。这里的服或减轻噪声影响的。这里的“冗余冗余”是相是相对于信息的表示而言，对提高传送可靠性来对于信息的表示而言，对提高传送可靠性来说，说，“冗余冗余”码元却提供了极宝贵的可靠性码元却提供了极宝贵的可靠性信息。信息。第一章第一章例例1.1 1.1 我们来看看冗余度是怎样同噪声做我们来看看冗余度是怎样同噪声做“斗争斗争”的。我们用来交流的语言通常有的。我们用来交流的语言通常有很大的冗余度。考虑下面的句子：很大的冗余度。考虑下面的句子： 星期一上午星期一上午2 2点在点在24052405教师开会。教师开会。 我们看到，在这个句子中有几处错我们看

9、到，在这个句子中有几处错误。但由于对这种语言的熟悉我们可以猜误。但由于对这种语言的熟悉我们可以猜到原来的句子应该是到原来的句子应该是 星期一下午星期一下午2 2点在点在24052405教室开会教室开会。第一章第一章图图1-1 数字通信系统框图数字通信系统框图第一章第一章 可以把纠错编码（即差错可以把纠错编码（即差错控制编码）看成是为提高通信控制编码）看成是为提高通信系统的性能而设计的信号变换，系统的性能而设计的信号变换，其目的是提高通信的可靠性，其目的是提高通信的可靠性，使传输的消息更好地抵抗各种使传输的消息更好地抵抗各种信道损伤的影响，如噪声、干信道损伤的影响，如噪声、干扰、以及衰落等。扰、

10、以及衰落等。第一章第一章1.2纠错编码的分类1.2.1差错控制编码的分类差错控制编码的分类1.2.2差错控制系统分类差错控制系统分类1.2.3纠错编码的分类纠错编码的分类第一章第一章1.2.1差错控制编码的分类 从差错控制码功能的角度，可以分为以下从差错控制码功能的角度，可以分为以下3 3类：类：1. 1.检错码（检错码（error detection codeerror detection code） 只能发现错误，不只能发现错误，不能纠正错误能纠正错误。在一些仅需要给出错误提示以及。在一些仅需要给出错误提示以及ARQARQ（自动请求重发，（自动请求重发，automatic repeat r

11、equestautomatic repeat request）系）系统中使用这类码。统中使用这类码。2. 2.纠错码（纠错码（error correcting codeerror correcting code） 能够发现错误也能能够发现错误也能纠正错误纠正错误。FECFEC（前向纠错，（前向纠错，feed-forward error feed-forward error correctioncorrection）和）和HECHEC（混合纠错，（混合纠错，hybrid-error-hybrid-error-correctioncorrection）系统都使用这类码。）系统都使用这类码。3. 3

12、.纠删码纠删码 能够发现并纠正或删除错误能够发现并纠正或删除错误。第一章第一章1.2.2差错控制系统分类1. 1.前向纠错前向纠错(FEC)(FEC)方式方式 FEC (Forward Error Control)FEC (Forward Error Control)方式是，发方式是，发端发送有纠错能力的码（纠错码），接收端发送有纠错能力的码（纠错码），接收端收到这些码后，通过纠错译码器自动地端收到这些码后，通过纠错译码器自动地纠正传输中的错误。纠正传输中的错误。 这种方式的这种方式的优点优点是不需要反馈信道；能是不需要反馈信道；能进行一个用户对多个用户的同时通信（如进行一个用户对多个用户的同

13、时通信（如广播），特别适合于移动通信；译码实时广播），特别适合于移动通信；译码实时性较好，控制电路也比较简单。性较好，控制电路也比较简单。缺点缺点是译是译码设备较复杂；编码效率较低。码设备较复杂；编码效率较低。第一章第一章2. 2.重传反馈重传反馈(ARQ)(ARQ)方式方式 ARQ (Automatic Repeat Request)ARQ (Automatic Repeat Request)方式是，发端发方式是，发端发出能够发现错误的码（检错码），收端译码器收到出能够发现错误的码（检错码），收端译码器收到后，判断在传输中有无错误产生，并通过反馈信道后，判断在传输中有无错误产生，并通过反馈信

14、道把捡测结果告诉发端。发端把收端认为有错的消息把捡测结果告诉发端。发端把收端认为有错的消息再次传送，直到收端认为正确接收为止。再次传送，直到收端认为正确接收为止。 缺点缺点是必须有一条从收端至发端的反馈信道。是必须有一条从收端至发端的反馈信道。并要求信源产生信息的速率可以进行控制，收、发并要求信源产生信息的速率可以进行控制，收、发两端必须互相配合，其控制电路比较复杂，传输信两端必须互相配合，其控制电路比较复杂，传输信息的连贯性和实时性也较差。该方式的息的连贯性和实时性也较差。该方式的优点优点是译码是译码设备简单，在多余度一定的情况下，码的检错能力设备简单，在多余度一定的情况下，码的检错能力比纠

15、错能力要高得多，因而整个系统能获得极低的比纠错能力要高得多，因而整个系统能获得极低的误码率。误码率。第一章第一章3. 3.混合纠错混合纠错(HEC)(HEC)方式方式 HEC (Hybrid Error Control)HEC (Hybrid Error Control)方式是上述方式是上述两种方式的结合。发端发送的码既能检错、两种方式的结合。发端发送的码既能检错、又有一定的纠错能力。接收端译码时若发又有一定的纠错能力。接收端译码时若发现错误个数在码的纠错能力以内，则自动现错误个数在码的纠错能力以内，则自动进行纠错；若错误个数超过了码的纠错能进行纠错；若错误个数超过了码的纠错能力，但能检测出来

16、，则通过反馈信道告知力，但能检测出来，则通过反馈信道告知发方重发。这种方式在一定程度上避免了发方重发。这种方式在一定程度上避免了FECFEC方式译码设备复杂和方式译码设备复杂和ARQARQ方式信息连方式信息连贯性差的缺点，因此得到了较为广泛的应贯性差的缺点，因此得到了较为广泛的应用。用。 第一章第一章第一章第一章 在设计差错控制系统时，选择何在设计差错控制系统时，选择何种实现方式，应综合考虑各方面的因种实现方式，应综合考虑各方面的因素。主要有：素。主要有：（1 1）满足用户对误码率的要求；）满足用户对误码率的要求；（2 2）有尽可能高的信息传输速率；）有尽可能高的信息传输速率；（3 3）有尽可

17、能简单的编译码算法且易）有尽可能简单的编译码算法且易于实现；于实现；（4 4）可接受的成本。）可接受的成本。第一章第一章1.2.3纠错编码的分类1. 1.根据对信息元的处理方法不同，可以根据对信息元的处理方法不同，可以将纠错码分为分组码与卷积码。将纠错码分为分组码与卷积码。（1 1）分组码是把信源输出的信息序列，）分组码是把信源输出的信息序列，以以k k个码元划分为一段，通过编码器个码元划分为一段，通过编码器把这段把这段k k个信息元按一定规则产生个信息元按一定规则产生r个个校验（监督）元，输出码长为校验（监督）元，输出码长为n=k+r的一个码组。的一个码组。第一章第一章 这种编码中每一码组的

18、校验元仅与这种编码中每一码组的校验元仅与本组的信息元有关，而与别组无关。分本组的信息元有关，而与别组无关。分组码用（组码用（n n，k k）表示，）表示，n n表示码长，表示码长，k k表表示信息位。分组码的构成如图示信息位。分组码的构成如图1-31-3所示。所示。第一章第一章第一章第一章第一章第一章2. 2.根据校验元与信息元之间的关系的不根据校验元与信息元之间的关系的不同，可以将纠错码分为为线性码同，可以将纠错码分为为线性码（linear codelinear code）与非线性码。）与非线性码。 若校验元与信息元之间的关系是若校验元与信息元之间的关系是线性关系（满足线性叠加原理），线性关

19、系（满足线性叠加原理），则则称为线性码；否则，称为非线性码。称为线性码；否则，称为非线性码。 由于非线性码的分析比较困难，实由于非线性码的分析比较困难，实现较为复杂，故今后我们仅讨论线性现较为复杂，故今后我们仅讨论线性码。码。第一章第一章3. 3.根据校验元与信息元之间的关系分类根据校验元与信息元之间的关系分类 根据纠正错误的类型不同，可以根据纠正错误的类型不同，可以将纠错码分为纠随机错误的码、纠突将纠错码分为纠随机错误的码、纠突发错误的码、纠同步错误码以及既能发错误的码、纠同步错误码以及既能纠随机错误又能纠突发错误的码。纠随机错误又能纠突发错误的码。4. 4.根据每个码元的取值来分类根据每个

20、码元的取值来分类 按照每个码元取值的不同，可以按照每个码元取值的不同，可以将分为二进制码和将分为二进制码和q q进制码（进制码（q q = = p pm m，p p为素数，为素数，m m为正整数）。为正整数）。第一章第一章5. 5.根据码的结构特点来分类根据码的结构特点来分类 根据码的结构特点的不同，可以根据码的结构特点的不同，可以将纠错码分为循环码、非循环码、系将纠错码分为循环码、非循环码、系统码和完备码等。统码和完备码等。6. 6.根据对每个信息元保护能力是否相等根据对每个信息元保护能力是否相等来分类来分类 根据对每个信息元保护能力是否根据对每个信息元保护能力是否相等来分可分为等保护纠错码

21、与不等相等来分可分为等保护纠错码与不等保护（保护（UEPUEP）纠错码。）纠错码。第一章第一章图图1-2 纠错码的分类示意图纠错码的分类示意图第一章第一章1.3纠错编码的基本概念定义定义1 1 码字码字是一些符号的序列。是一些符号的序列。定义定义2 2 码码是称为码字（是称为码字（codewordcodeword）的向量的）的向量的 集合。集合。第一章第一章第一章第一章例例1.2 1.2 考虑有两个码字考虑有两个码字01000100，11111111的码的码C C。码字的汉明重量为码字的汉明重量为w w(0100)=1(0100)=1和和w w(1111)=4(1111)=4。这两个码字间的汉

22、明距离为这两个码字间的汉明距离为3 3，因为它们在第，因为它们在第1 1、第第3 3和第和第4 4位置上不同。位置上不同。观察到观察到w w(0100-1111)= (0100-1111)= w w(1011)=3=(1011)=3=d d(0100,1111) (0100,1111) 。 一般而言，对于任意一种编码，其中各一般而言，对于任意一种编码，其中各码组之间的距离不一定都相等。码组之间的距离不一定都相等。第一章第一章定义定义4 4 一个分组码由具有固定长度的码字集合一个分组码由具有固定长度的码字集合构成。这些码字的固定长度称为分组长度构成。这些码字的固定长度称为分组长度（block L

23、engthblock Length），通常记为），通常记为n n。因此一个分组。因此一个分组长度为长度为n n的码由一组有的码由一组有n n个分量的码字的集合个分量的码字的集合构成。构成。 定义在定义在q q个符号的字母集上的大小为个符号的字母集上的大小为MM的的分组码是分组码是MM个个q q元序列的集合，每个序列的长元序列的集合，每个序列的长度为度为n n。对。对q q=2=2的特殊情况，那些符号称为比的特殊情况，那些符号称为比特，而码称为二元码。通常对某个整数特，而码称为二元码。通常对某个整数k k有有MM= =q qk k，我们称这样的码为（，我们称这样的码为（n n, , k k）码。

24、）码。第一章第一章例例1.3 1.3 码码C=C=0000000000，1010010100，1111011110，1100111001是分组长度等于是分组长度等于5 5的一个分组码。的一个分组码。该码可用来表示两个比特的二元数字，该码可用来表示两个比特的二元数字，如表如表1-11-1所示：所示：第一章第一章 这里这里MM=4=4，k k=2=2且且n n=5=5。假设我们要用上述。假设我们要用上述编码方案传输由编码方案传输由0 0和和1 1构成的一个序列，如，要编构成的一个序列，如，要编码的序列为码的序列为10010100111001010011。第一步是把这个序列。第一步是把这个序列分成两

25、个比特一组（因为我们要每次编码两个比分成两个比特一组（因为我们要每次编码两个比特），那么我们做如下分割特），那么我们做如下分割 10 01 01 00 1110 01 01 00 11 接下来把每个组用它们对应的码字代换：接下来把每个组用它们对应的码字代换： 11110 10100 10100 00000 1100111110 10100 10100 00000 11001 因此对每两个比特未编码的消息，我们发送因此对每两个比特未编码的消息，我们发送5 5比特（编码后）。应该观察到对每比特（编码后）。应该观察到对每2 2比特的信息，比特的信息，我们发送我们发送3 3个额外比特（冗余度）。个额外

26、比特（冗余度）。第一章第一章定义定义5 5 一个（一个（n, k）码的码率（编码效率，）码的码率（编码效率，coding efficiencycoding efficiency）定义为比率（）定义为比率（k/n, ,），它），它表示码字所含信息符号的分数（比例），表示码字所含信息符号的分数（比例），是衡量编码有效性的基本参数。编码效率是衡量编码有效性的基本参数。编码效率与抗干扰能力这两个参数是相互矛盾的。与抗干扰能力这两个参数是相互矛盾的。 码率总是小于码率总是小于1 1。码率越小，冗余度就。码率越小，冗余度就越大，即在一个码字中添加给每个信息符越大，即在一个码字中添加给每个信息符号的冗余符号

27、越多。一个码有越多的冗余号的冗余符号越多。一个码有越多的冗余度，就有检测和纠正更多错误码符号的能度，就有检测和纠正更多错误码符号的能力，但也降低了传输信息的实际速率。力，但也降低了传输信息的实际速率。第一章第一章第一章第一章第一章第一章 对于二进制系数，上两式中对于二进制系数，上两式中的加、减运算均为模的加、减运算均为模2 2加运算，因加运算，因此加运算和减运算是等效的。对于此加运算和减运算是等效的。对于长为长为n n的码字，信道的错误图样的码字，信道的错误图样E E也称为干扰矢量，共有也称为干扰矢量，共有2 2n n种，实用种，实用中只需讨论那些可以检测或可能纠中只需讨论那些可以检测或可能纠

28、正的部分。正的部分。第一章第一章定义定义9 9 在错误图样中，若在错误图样中，若“1”1”集中于某个长集中于某个长度度b b内，则称该种错误为长度为内，则称该种错误为长度为b b的的突发错突发错误误，其中，其中b b称为突发错误长度，该图样称为称为突发错误长度，该图样称为突发错误图样。突发错误图样。 典型的突发错误图样为：典型的突发错误图样为： 中间含有中间含有b b个连续的个连续的1 1，对于一些编码，对于一些编码（如循环码），突发错误图样也包括首位（如循环码），突发错误图样也包括首位相连的错误，其错误图样为：相连的错误，其错误图样为： 其中两段分别连续的其中两段分别连续的1 1的个数总共为

29、的个数总共为b b。0110011010011001第一章第一章1.4有噪信道编码定理 是否能找到一种信道编码方法能同是否能找到一种信道编码方法能同时保证差错率和信息传输的要求呢？时保证差错率和信息传输的要求呢？ 19481948年，香农从理论上得出结论：年，香农从理论上得出结论：对于有噪信道，只要通过足够复杂的编对于有噪信道，只要通过足够复杂的编码方法，就能使信息率达到信道的极限码方法，就能使信息率达到信道的极限通过能力通过能力信道容量，同时使平均差信道容量，同时使平均差错率逼近零。这一结论称为香农第二编错率逼近零。这一结论称为香农第二编码定理或有噪信道编码定理，是有关信码定理或有噪信道编码

30、定理，是有关信息传输的最基本结论。息传输的最基本结论。第一章第一章定理（香农第二编码定理）定理（香农第二编码定理） 若信道是离散、若信道是离散、无记忆、平稳的，且信道容量为无记忆、平稳的，且信道容量为C C，只要待，只要待传送的信息率传送的信息率RCRC，就一定能找到一种信道，就一定能找到一种信道编码方法，使得码长编码方法，使得码长N N足够大时，平均差错足够大时，平均差错率任意接近于零。率任意接近于零。 香农第二编码定理实际上是一个存在定香农第二编码定理实际上是一个存在定理，它指出：在理，它指出：在RCR33的码组，可以认为，码的码组，可以认为，码距是距是n n维空间中单位正多面体顶点之间维

31、空间中单位正多面体顶点之间的汉明距离。的汉明距离。 可见，一种编码性能的优劣，可可见，一种编码性能的优劣，可以用最小码距以用最小码距d d0 0的大小来表征。下面用的大小来表征。下面用几何关系证明纠几何关系证明纠/ /检错能力和最小码距检错能力和最小码距的关系。的关系。第一章第一章1.为了能检测为了能检测e e个错码，要求最小码个错码，要求最小码距距：)51 (10 ed第一章第一章2. 2.为了能纠正为了能纠正 t t 个错码，要求最小码个错码，要求最小码距：距： )61 (120 td第一章第一章3. 3.为了能纠正为了能纠正t t个错码，同时检测个错码，同时检测e e个个错码，要求最小码

32、距：错码，要求最小码距： )71 (10ted第一章第一章1.8纠错编码系统的性能 由纠错编码原理可知，为了减少错由纠错编码原理可知，为了减少错码，需要在信息码元序列中加入监督码元。码，需要在信息码元序列中加入监督码元。这样做的结果是：这样做的结果是：使序列增长，冗余度增使序列增长，冗余度增大大。若仍须保持信息码元速率不变，则通。若仍须保持信息码元速率不变，则通信系统的传输速率必须增大。因而增大了信系统的传输速率必须增大。因而增大了系统的带宽。系统带宽的增大又引起系统系统的带宽。系统带宽的增大又引起系统噪声功率增大，使信噪比下降。信噪比的噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收

33、码元序列中的错码下降反而又使系统接收码元序列中的错码增多。因此，采用了纠错编码后到底得失增多。因此，采用了纠错编码后到底得失如何，需要进一步的分析。如何，需要进一步的分析。第一章第一章1. 1.误码率性能和带宽的关系误码率性能和带宽的关系 在采用纠错编码后，虽然系统在采用纠错编码后，虽然系统的带宽增大了，但是误码性能还是的带宽增大了，但是误码性能还是能得到很大的改善。改善程度自然能得到很大的改善。改善程度自然和所用的编码体制有关。如图和所用的编码体制有关。如图1-81-8给出某通信系统采用给出某通信系统采用BPSKBPSK调制时调制时的误码率曲线，以及采用某种纠错的误码率曲线，以及采用某种纠错编码后的误码率曲线。编码后的误码率曲线。第一章第一章图图1-8 编码与误码的关系编码