信道编码纠错码基础幻灯片.ppt

《信道编码纠错码基础幻灯片.ppt》由会员分享，可在线阅读，更多相关《信道编码纠错码基础幻灯片.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信道编码纠错码基础第1页，共99页，编辑于2022年，星期五课程概况目的目的：了解信道编码的作用与意义作用与意义，对信道编码的研究方法和成果研究方法和成果有广泛的基本认识，学会应用信道编码应用信道编码，为进一步研究打下基础特点特点：以概念和物理意义为主，数学推导尽量放到课外第2页，共99页，编辑于2022年，星期五教材及参考书“纠错码纠错码原理与方法原理与方法”，王新梅，西安电子科技大学出版社，高等学校教材“差错控制编码差错控制编码”，ShuLin等著，晏坚等译，机械工业出版社，电子与电气工程图书“Digital Modulation and Coding”,S.G.Wilson,Prenti

2、ce Hall（“数字调制与编码”影印版，电子工业出版社，通信与信息科学教育丛书）第3页，共99页，编辑于2022年，星期五作业及考试作业：每章布置课后练习，20%。项目：二至四人为一组，选择一篇或两篇相关论文精读，模拟论文作者写一份国家自然科学基金申请书和答辩ppt，组长代表全组作报告；用C语言、Java或Matlab实现其中一篇论文的算法，20%。考试：基本概念、计算和简单证明，60%。第4页，共99页，编辑于2022年，星期五“通信的基本问题就是在一点重新准确地或近似地再现另一点所选择的消息”。烽火狼烟、摔杯为号、铜镜反光、鸣金收兵、集结号C.E.Shannon（1916-2001）第5

3、页，共99页，编辑于2022年，星期五第6页，共99页，编辑于2022年，星期五为什么需要信道编码？第7页，共99页，编辑于2022年，星期五信道编码发展简史（1）1948年C.E.Shannon信道编码定理20世纪四十年代,Hamming码、Golay码1954年，Reed-Muller码1955年Elias提出卷积码循环码（CRC,CyclicRedundancyCheck)1959年BCH码（Bose,Ray-Chaudhuri,Hocquuenghem)1960年RS码(Reed-Solomon)第8页，共99页，编辑于2022年，星期五信道编码发展简史（2）序列译码算法：1961年，

4、Wozencraft,Reiffen,1963Fano，1969，Jelinek.1963年Massy门限译码算法1966年Forney级联编码概念同年Forney提出GMD算法1967年viterbi算法1967年Berlekmp译码算法第9页，共99页，编辑于2022年，星期五信道编码发展简史（3）1974年BCJR算法1976年HR算法（Hartman和Rudoolph)1971年WeldonWED算法1972年Chase算法1982年Ungerbock提出TCM概念1993年，Turbo码，ClaudeBerrou,AlainGlavieux和PunyaThitimajshima第10

5、页，共99页，编辑于2022年，星期五信道编码在GSM中应用信道编码是提高通信系统可靠性的最主要手段，它不仅成功地用于典型的加性高斯噪声AWGN信道，也成功的用于各类变参量的衰落信道，前者主要是卫星通信。信道编码在数字蜂窝移动通信中最典型的应用是在全球移动通信系统GSM中的应用。在GSM中无线信道按其功能可分为业务信道(TCH)和控制信道(CCH)，其中业务信道用于传送话音与数据，控制信道用于传送信令和同步。GSM的信道编码系统总体框图如图所示。第11页，共99页，编辑于2022年，星期五GSM编、译码器方框图第12页，共99页，编辑于2022年，星期五图解GSM语音信道编码第13页，共99页

6、，编辑于2022年，星期五CDMA(IS-95)CDMA2000(IS-2000)、WCDMA中的信道编码IS-95是高高通通公司基于CDMA技术发展出来的2G移移动动通通信信标准：检错码、卷积码、交织编码。CDMA2000：检错码、卷积码、Turbo码、交织编码。WCDMA：检错码、卷积码、Turbo码、交织编码。第14页，共99页，编辑于2022年，星期五第一章 纠错码的基本概念Basic Concepts of Error Control Coding 1.1 数字通信系统的组成及信道模型数字通信系统的组成及信道模型 1.2 差错控制系统和纠错码分类差错控制系统和纠错码分类 1.3 最大

7、似然译码和纠错码的基本概念最大似然译码和纠错码的基本概念 1.4 信道编码定理信道编码定理 第15页，共99页，编辑于2022年，星期五1.1 数字通信系统的组成及信道模型数字通信系统的组成及信道模型 一、一、数字通信系统的组成数字通信系统的组成通信的目的是要把对方不知道的消息及时可靠地(有时还须秘密地)传送给对方，因此，要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加，传送消息的可靠性减低。若要求可靠，则使得传送消息的速率变慢。因此，如何较合理地解决可靠

8、性与速度这一对矛盾，是正确设计一个通信系统关键问题之一。通信理论本身(包括纠错码)也正是在解决这对矛盾中不断发展起来的。第16页，共99页，编辑于2022年，星期五图1-1数字通信系统模型第17页，共99页，编辑于2022年，星期五图中，信源编码器是把信源发出的消息如语言、图像、文字等转换成为二进制(也可转换成为多进制)形式的信息序列，并且为了使传输有效，还去掉了一些与传输信息无关的多余度(有时为了保密，信源编码器后还可接上加密器)。为了抗击传输过程中的各种干扰，往往要人为地增加一些多余度，使其具有自动检错或纠错能力，这种功能由图中的信道编码器即纠错编码器完成。发射机(调制器)的功用是把纠错码

9、送出的信息序列通过调制器变换成适合于信道传输的信号。数字信号在信道传输过程中，总会遇到各种干扰而使信号失真，这种失真信号传输到接收端的接收机，进行解调，变成二进制(或多进制)信息序列。由于信道干扰的影响，该信息序列中可能已有错误，经过信道译码器即纠错码译码器，对其中的错误进行纠正，再通过信源译码器恢复成原来的消息送给用户。第18页，共99页，编辑于2022年，星期五本课程研究的是图中的信道编、译码器即纠错编、译码器两个方框，为了研究方便，将上述模型再进一步简化成图-所示的模型。在此模型中，信源是指原来的信源和信源编码器，其输出是二(多)进制信息序列。信道是包括发射机、实际信道(或称传输媒质)和

10、接收机在内的广广义义信信道道(又称编编码码信信道道)，它的输入是二(多)进制数字序列，输出一般也是二(多)进制数字序列，而图中的信宿可以是人或计算机。第19页，共99页，编辑于2022年，星期五图1-2数字通信系统简化模型第20页，共99页，编辑于2022年，星期五二、信道模型回顾：编码是消息到信道波形或矢量的一种映射关系从数学上看，信道实际上也是从发空间X到收空间Y一个概率映射函数第21页，共99页，编辑于2022年，星期五收发集合可以以符号集的多重形式表示，相当于多维空间。发空间的维数n与收空间的维数m可以不等例如当发送波形x(t)通过一个滤波器h(t)时，输出y(t)=x(t)*h(t)

11、，如果x(t)只在0,T内有值，而当h(t)有一定的宽度t时，输出的非零长度变成了T+t，也就是说当接收采样率等于或高于发送采样率时，接收的维数增加了。而如果接收时采用了较低的采样率，则有效维数就减低了。第22页，共99页，编辑于2022年，星期五根据收发空间中每一维所取的数域有限或无限可分为离散信道和连续信道这里借用了空间的名称，但只用到了它的集合概念而没有用到空间中的运算，只有线性信道才可以直接用线性运算构成一个线性空间。离散信道可用转移概率律描述：P(y=b|x=a),a=(a1,a2,.aK)X（发空间）（发空间）,b=(b1,b2,.bJ)Y（收空间）（收空间）,均为矢量（或K(J)

12、重符号）第23页，共99页，编辑于2022年，星期五信道特性：信道译码：发送ak,收到bj的概率为，接收端不唯一，以什么准则译码，使差错可接受？第24页，共99页，编辑于2022年，星期五例：二元对称信道正确的传递概率分别为1/3和1/3。第25页，共99页，编辑于2022年，星期五译码器1：译码性能分析：则在此译码器下，平均错误概率为（设输入为等概）第26页，共99页，编辑于2022年，星期五译码器2：第27页，共99页，编辑于2022年，星期五关于译码准则的结论第28页，共99页，编辑于2022年，星期五现在以图1-2的模型来讨论二进制数字序列通过该系统时所发生的情况。设从信源送出字母A，

13、它的二进制序列为11000，以基带信号传送，经发射机调制后，送往信道的已调信号如图1-3所示。由于信道的干扰，从信道输出端的信号产生了失真，如图1-4所示。这些失真信号送入接收机进行判决时，由于第一、二、四、五码元的波形失真不大，容易正确地判为1、1和0、0；但对第三个码元来说，由于失真严重而难于判决。这时有以下三种判决方法：一是勉强作出是0还是1的判决，即所谓硬硬判判决决；另一种是对该码元暂且不作判决，而输出一个未知或待定的信号“x”，称其为删删除除符符号号；第三种方法是输出一种有关该码元的信息，例如关于0和1的后验概率或似然函数，这种作法称为软软判判决决。当然软判决的性能较好，但实现起来较

14、复杂。第29页，共99页，编辑于2022年，星期五图1311000发送的已调信号波形第30页，共99页，编辑于2022年，星期五图1-4接收端收到的失真信号波形第31页，共99页，编辑于2022年，星期五在二进制硬判决情况下，信道可用图1-5所示的简单模型表示。图中，p01和p10分别是0错成1和1错成0的概率，称信信道道转转移移概概率率。该信道的信道转移概率矩阵可用描述。如果p01=p10=pe，则称这种信道为二二进进制制对对称称信信道道，简称BSC(Binary Symmetric Channel)。否则，称为不不对对称称信信道道。若p01或p10等于零，则称为Z Z信信道道。通常BSC是

15、一种无无记记忆忆信信道道，所以也称随随机机信道信道，它说明数据序列中出现的错误彼此无关。第32页，共99页，编辑于2022年，星期五图15二进制信道第33页，共99页，编辑于2022年，星期五如果信道的输入是二进制符号，而输出是离散的q(qpm2)进制符号，如图1-6所示，且p(i0)p(q-1-i1)，i0，1，q-1，则这种信道称为离离散散无无记记忆忆信信道道(Discrete Memoryless Channel,DMC)DMC)，显然BSC是DMC的一种特殊情况。DMC的信道转移概率矩阵第34页，共99页，编辑于2022年，星期五图1-6DMC第35页，共99页，编辑于2022年，星期

16、五在作删除判决情况下，信道可用图1-7所示的模型表示，称为二二进进制制删删除除信信道道，简称BEC(Binary Erasure Channel)，一般它也是对称信道。图中，pe为信道的转移概率，q为删除概率，在有删除处理情况下，信道的转移概率pe一般很小，可忽略，因此把图1-7所示的模型用图1-8代替，称为二进制纯删除信道。以后所说的BEC都是指这种信道。应当指出，当码元作删除处理时，它在序列中的位置是已知的，仅不知其值是0还是1，故对这种BEC信道的纠错要比BSC信道容易。第36页，共99页，编辑于2022年，星期五图图 1-7 二进制删除信道二进制删除信道 第37页，共99页，编辑于20

17、22年，星期五图图 1-8 二进制纯删除二进制纯删除 第38页，共99页，编辑于2022年，星期五上述三种信道模型只是为了讨论问题方便而简化成理想的情况，它们表达了某些实际信道传送信号的主要特征。例如，卫星信道或深空信道，可近似看成是BSC。但有很多实际信道如高频、散射、有线等信道，由于各种干扰所造成的错误，往往不是单个地而是成群成串地出现的，也就是一个错误的出现，往往引起其前后码元的错误(突突发发错错误误)，表现为错误之间的相关性。产生这种错误的信道称有记记忆忆信信道道或突突发发信信道道。在计算机存贮系统中，磁带的缺陷或读写头接触不良所引起的错误，也属于这种类型。但由于实际信道干扰的复杂性，

18、所引起的错误往往不是单纯的一种，而是两种错误形式并存，只不过有的信道以某种错误形式为主罢了。第39页，共99页，编辑于2022年，星期五像这种随机错误与突发错误并存的信道，称为组合信道或复合信道。作为检错与纠错用的抗干扰码，必须针对这几类信道，设计能纠正随机错误或纠正突发错误的码，或者设计既能纠正随机错误又能纠正突发错误的码。我们将首先讨论BSC和BEC(包括多进制)的纠错编码问题。第40页，共99页，编辑于2022年，星期五由于目前在信道中传输或计算机内部运算的数据序列，大部分是二进制数字序列，因此以后主要讨论二进制数字通信中的纠错码，当然这些纠错码往往可以推广到q(素数或素数的幂)进制情况

19、，这将在以后具体讨论时予以说明。二进制情况下，序列之间0、1两个符号按下列规则进行运算：+01001110模2相加模2相乘01000101为了简便，今后用+和表示模2相加和相乘。在模2情况下，加和减是一回事。第41页，共99页，编辑于2022年，星期五 三、三、错误图样错误图样设发送的是n个码元长的序列C：(cn-1,cn-2,c1,c0)，通过信道传输到达接收端(纠错码译码器输入端)的序列为R：(rn-1,rn-2,r1,r0)。由于信道中存在干扰，R序列中的某些码元可能与C序列中对应码元的值不同，也就是说产生了错误。由于二进制序列中的错误不外乎是1错成0或0错成1，因此，如果把信道中的干扰

20、也用二进制序列E：(en-1,en-2,e1,e0)表示，则相应有错误的各位ei取值为1，无错的各位取值为0，而R就是C与E序列模2相加的结果，称E为信道的错错误误图图样样或干干扰扰矢矢量量。例如，发送序列C：(1111100000)，收到的序列R：(1001010000)，第二、三、五、六位产生了错误，因此信道的错误图样E的二、三、五、六位取值为1，其它各位取值为0，即E：(0110110000)。用式子可表示成：第42页，共99页，编辑于2022年，星期五发送序列C:1111100000错误图样E：0110110000接收序列R：1001010000+即RC+E，或E=R-C。信道干扰所造

21、成的错误可在序列中的任一位出现，且也可以在n长序列中同时出现一位、二位，甚至n位错误。因此，若发送的C序列长为n，则信道中可能产生的错误图样E共有2n种。若为突发信道，则在错误图样E中，第一个1与最后一个1之间的长度称为突突发发长长度度，其图样称为突发图样。在该例中，突发图样是(11011)，突发长度为5。第43页，共99页，编辑于2022年，星期五1.2 差错控制系统和纠错码分类差错控制系统和纠错码分类(1)重重传传反反馈馈方方式式(Automatic(Automatic Repeat Repeat reQuest,reQuest,ARQ)ARQ)，（自自动动请请求求重重传传、或或检检错错重

22、重发发）。应用ARQ方式纠错的通信系统如图1-9所示。发送端发出能够发现(检测)错误的码，接收端收到通过信道传来的码后，在译码器根据该码的编码规则，判决收到的码序列中有无错误产生，并通过反馈信道把判决结果用判决信号告诉发端。发端根据这些判决信号，把接收端认为有错的消息再次传送，直到接收端认为正确接收为止。第44页，共99页，编辑于2022年，星期五图1-9ARQ通信系统第45页，共99页，编辑于2022年，星期五应用ARQ方式必须有一反馈信道，一般较适用于一个用户对一个用户（点对点)的通信，且要求信源能够控制，系统收发两端必须互相配合、密切协作，因此这种方式的控制电路比较复杂。由于反馈重发的次

23、数与信道干扰情况有关，若信道干扰很频繁，则系统经常处于重发消息的状态，因此这种方式传送消息的连贯性和实时性较差。该方式的优点是：编译码设备比较简单；在一定的多余度码元下，检错码的检错能力比纠错码的纠错能力要高得多，因而整个系统的纠错能力极强，能获得极低的误码率；由于检错码的检错能力与信道干扰的变化基本无关，因此这种系统的适应性很强，特别适应于短波、散射、有线等干扰情况特别复杂的信道中。第46页，共99页，编辑于2022年，星期五(2)前前向向纠纠错错方方式式(Forward Error Correction,FEC)FEC)。数字通信系统如图1-2所示。发送端发送能够被纠错的码，接收端通过纠错

24、译码器不仅能自动地发现错误，而且能自动地纠正接收码字传输中的错误。其优点是不需要反馈信道，适用于一对多的广播通信，译码实时性较好。其缺点是译码设备复杂，所选用的纠错码必须与信道的干扰情况相匹配，因而对信道的适应性较差。为了要获得比较低的误码率，必须以最坏的信道条件来设计纠错码，所需的冗余码元比检错码要多得多，从而编码效率低。特别适用于军用通信，并且随着编码理论的发展和编译码设备所需的大规模集成电路成本的不断降低，译码设备有可能更简单，成本更低，在实际的数字通信中逐渐得到应用。主要用于语音，广播，TV等通信。第47页，共99页，编辑于2022年，星期五(3)混混合合纠纠错错方方式式(Hybrid

25、 Error Correction,HEC)HEC)。这种方式是发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错能力。接收端收到码序列以后，首先检验错误情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果错误很多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消息。这种方式在一定程度上避免了FEC方式要求用复杂的译码设备和ARQ方式信息连贯性差的缺点，并能达到较低的误码率，因此在实际中的应用越来越广。第48页，共99页，编辑于2022年，星期五除了上述三种主要方式以外，还有所谓狭狭义义信信息息反反馈馈系系统统(InformationRepeatreQu

26、est,IRQ)，或信信息息反反馈馈重重发发。这种方式是接收端把收到的消息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的消息，从而发现错误，并且把传错的消息再次传送，最后达到使对方正确接收消息的目的。为了便于比较，我们把上述几种方式用图1-10所示的框图表示。在实际系统设计中，如何根据实际情况选择哪种差错控制方式是一个比较复杂的问题。第49页，共99页，编辑于2022年，星期五检错重发(ARQ)前向纠错混合纠错图图 1-10 差错控制的基本方式差错控制的基本方式 第50页，共99页，编辑于2022年，星期五二、二、纠错码的分类纠错码的分类上述各种差错控制系统中所用到的码，不外乎

27、是能在译码器自动发现错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者能纠正删除错误的纠删码。但这三类码之间没有明显区分，以后将看到，任何一类码，按照译码方法不同，均可作为检错码、纠错码或纠删码来使用。除了上述的划分方法以外，通常还按以下方式对纠错码进行分类：第51页，共99页，编辑于2022年，星期五(1)按照对信息元处理方法的不同，分为分分组组码码与与卷卷积积码码两两大大类类。分分组组码码是把信源输出的信息序列，以k个码元划分为一段，通过编码器把这段k个信息元按一定规则产生r个校验(监督)元，输出长为nk+r的一个码组。因此每一码组的校验元仅与本组的信息元有关，而与别组无关。

28、分组码用(n，k)表示，n表示码长，k表示信息位。卷卷积积码码是把信源输出的信息序列，以k0个(k0通常小于k)码元分为一段，通过编码器输出长为n0(k0)一段的码段。但是该码段的n0-k0个校验元不仅与本组的信息元有关，而且也与其前m段的信息元有关，称m为编码存贮编码存贮。因此卷积码用(n0，k0，m)表示。第52页，共99页，编辑于2022年，星期五(2)根据校验元与信息元之间的关系分为线线性性码码与与非非线线性性码码。若校验元与信息元之间的关系是线性关系(满足线性叠加原理)，则称为线性码;否则，称为非线性码。由于非线性码的分析比较困难，实现较为复杂，故今后仅讨论线性码。(3)按照纠正错误

29、的类型可分为纠纠正正随随机机(独独立立)错错误误的的码码、纠纠正正突突发发错错误误的的码码和纠纠正正同同步步错错误误的的码码，以及既既能能纠正随机错误又能纠正突发错误的码纠正随机错误又能纠正突发错误的码。第53页，共99页，编辑于2022年，星期五(4)按照每个码元取值来分，可分为二二进进制制码码与q进制码(q=pm，p为素数，m为正整数)。(5)按照对每个信息元保护能力是否相等可分为等等保保护护纠纠错错码码与不不等等保保护护(UEP)(UEP)纠纠错错码码。除非特别说明，今后讨论的纠错码均指等保护能力的码。此外，在分组码中按照码的结构特点，又可分为循环码与非循环码。为了清楚起见，我们把上述分

30、类用图1-11表示。第54页，共99页，编辑于2022年，星期五图1-11纠错码分类第55页，共99页，编辑于2022年，星期五1.3 最大似然译码和纠错码的基本概念最大似然译码和纠错码的基本概念 一、一、基本定义基本定义利用纠错码进行差错控制的数字通信系统如图1-12所示，由此可如下定义分组码。定定义义1.3.1 分分组组码码是对每段k位长的信息组，以一定规则增加r=n-k个校验元，组成长为n的序列：(cn-1,cn-2,c1,c0)，称这个序列为码码字字(码码组组、码矢)。在二进制情况下，信息组总共有2k(q进制为qk)个，因此通过编码器后，相应的码字也有2k个，称这2k个码字集合为(n，

31、k)分组码分组码。第56页，共99页，编辑于2022年，星期五图1-12分组码的数字通信模型第57页，共99页，编辑于2022年，星期五 n长序列的可能排列总共有2n种(每一n长序列称为n n重重)，而(n，k)分组码的码字集合只有2k种。所以，分组码的编码问题就是定出一套规规则则（映映射射），以便从2n个n重中选出2k个码字，不同的选取规则就得到不同的码。我们称被选取的2k个n重为许用码组许用码组，其余的2n-2k个为禁用码组禁用码组。称Rkn为码码率率，表示(n，k)分组码中，信息位在码字中所占的比重。R是衡量分组码有效性的一个基本参数。第58页，共99页，编辑于2022年，星期五图1-1

32、3是一个(2,1,2)卷积码编码器。若输入的信息序列以k01个码元分段输入，则输出以n02个码元为一段输出，如输入的信息序列M(110100)，输出的码序列为C(11，10，10，00，01，11，00，)。可知随着信息元的不断输入，输出的是一个半无限长的码序列，由此可如下定义卷积码。第59页，共99页，编辑于2022年，星期五图1-13一个(2，1，2)卷积码编码器第60页，共99页，编辑于2022年，星期五定定义义1.3.2(n0，k0，m)卷卷积积码码是对每段k0长的信息组以一定的规则增加r0n0-k0个校验元，组成长为n0的码段。n0-k0个校验元不仅与本段的信息元有关，且与前m段的信

33、息元有关，当信息元不断输入时，输出的码序列是一个半无限长序列。(n0，k0，m)卷积码的码率Rk0/n0。与分组码的码长n相对应，在卷积码中称nck0(m+1)为编编码码约约束束长长度度，说明k0个信息元从输入编码器到离开时在码序列中影响的码元数目，如图1-13中(2，1，2)卷积码的nc3。第61页，共99页，编辑于2022年，星期五二、二、最大似然译码最大似然译码由图1-2可知，信道输出的R是一个2(或q)进制序列，而译码器的输出是一个信息序列M的估值序列。译码器的基本任务就是根据一套译码规则，由接收序列R给出与发送的信息序列M最接近(最好是相同)的估值序列。由于M与码字C之间存在一一对应

34、关系，所以这等价于译码器根据R产生一个C的估值序列。显然，当且仅当C时，M，这时译码器正确译码。第62页，共99页，编辑于2022年，星期五如果译码器输出的C，则译码器产生了错误译码。之所以产生错误译码是由于：信道干扰很严重，超过了码本身的纠错能力；其次，由于译码设备的故障(不讨论)。当给定接收序列R时，译码器的条件译码错误概率定义为所以译码器的错误译码概率第63页，共99页，编辑于2022年，星期五P(R)是接收R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使因此，如果译码器对输入的R，能在2k个码字中选择一个使最大的码字Ci作为C的估值序列，则这种译码规则一定使译码器输出错

35、误概率最小，称这种译码规则为最最大大后后验验概概率率译译码码（理理想想译译码器）码器）。（1.3.1）第64页，共99页，编辑于2022年，星期五由贝叶斯公式可知，若发端发送每个码字的概率P(Ci)均相同，且由于P(R)与译码方法无关，所以对DMC而言（1.3.2）（1.3.3）这里码字Ci(ci1，ci2，cin)，i1，2，2k。第65页，共99页，编辑于2022年，星期五一个译码器的译码规则若能在2k个码字C中选择某一个Ci使式(1.3.2)成为最大，则这种译码规则称为最最大大似似然然译译码码(MLD)，P(R|C)称为似然函数，相应的译码器称为最最大大似似然然译译码码器器。由于logb

36、x与x是单调关系，因此式(1.3.2)与式(1.3.3)可写成称logbP(R|C)为对对数数似似然然函函数数或似似然然函函数数。对于DMC信道，MLD是使译码错误概率最小的一种最佳译码准则或方法，但此时要求发端发送每一码字的概率P(Ci)(i1,2,2k)均相等，否则MLD不是最佳的。以后都认为P(Ci)均近似相等。第66页，共99页，编辑于2022年，星期五三、三、汉明汉明(Hamming)距离与重量距离与重量定义1.3.3两个n重x、y之间，对应位取值不同的个数，称为它们之间的汉明距离汉明距离，用d(x，y)表示。例如，若x:(10101)，y:(01111)，则d(x，y)3。定定义义

37、1.3.4n重x中非零码元的个数，称为它的汉汉明明重重量量，简称重量重量，用w(x)表示。例如，若x:(10101)，则w(x)3。若y:(01111)，则w(y)4，等等。第67页，共99页，编辑于2022年，星期五定定义义 1.3.5(n，k)分组码中，任两个码字之间距离的最小值，称为该分组码的最小汉明距离最小汉明距离d0，简称最小距离最小距离例如(3,2)码，n3，k2，共有224个码字：000，011，101，110，显然d02。d0是(n，k)分组码的另一个重要参数。它表明了分组码抗干扰能力的大小：d0越大，码的抗干扰能力越强，在同样译码方法下它的译码错误概率越小。由上可知，R和d0

38、是(n，k)分组码的两个最重要参数。纠错编码的基本任务之一就是构造出R一定、d0尽可能大的码，或d0一定、R尽可能高的码。下面用几个具体例子说明码的R、d0以及译码错误概率之间的关系。第68页，共99页，编辑于2022年，星期五例例1.1 重复码重复码是k1的(n，1)码，它的编码规则(即在2n个n重中挑选2k21个码字的规则)是(n-1)个校验元是信息元的重复，设信息元为cn-1，则校验元cicn-1(i=0，1，2，n-2)。由于信息组只有2k2组：0和1，因此相应的许用码字只有两个(000)和(111)。设它们通过BSC传输，信道的转移概率为pe。通常情况下，pe0.5，因此在传输中没有

39、错误的可能性比出现一个错误的可能性大，出现一个错误的可能性比出现两个错误的大，等等。也就是说信道错误图样E中，出现重量最轻的图样可能性最大。第69页，共99页，编辑于2022年，星期五P(w(E)0)P(w(E)1)P(w(E)2)或由ER-C及式(1.3.2)可知，MLD译码器寻求可能出现的错误图样，就是由接收到的R在2k个码字集中，寻求与R的汉明距离最小的码字Ci，为最可能发送的码字，这就是最最小小汉汉明明距距离离译译码码(或称最最近近临临区区译译码码)。在重复码情况下这种译码方案就是根据收到序列中0和1的多少，来判断信息组是0还是1。若接收序列中1的个数大于n2，则判为1；否则，判为0。

40、这种译码方案就是大数准则译码。第70页，共99页，编辑于2022年，星期五当n是奇数时，按照这种大数准则译码方法，译码器总可以很快地作出是0还是1的判决。当n是偶数时可能出现以下情况，即接收序列中“1”的个数和“0”的个数刚好相等，此时若按大数准则无法作出判断，造成译码失败，这种译译码码称称为为不不完完备备译译码码。而n为奇数情况下的译码(即译码器一定作出是哪一个信息组的判决)称为完完备备译译码码。译码失败只表明译码器无法给出明确判断，但并不等于译码错误，而仅表明接收序列中存在有错误。此时，如果我们与ARQ系统相结合，则可以利用此信息要求对方重发该组信息，直到译码器作出明确判决为止。下面几个具

41、体例子说明重复码的抗干扰能力。第71页，共99页，编辑于2022年，星期五(1)(1，1)码。这种码n1，k1，d1，R1，显然无任何抗干扰能力。设BSC中的pe0.1，则这种码的误码率仍为0.1。(2)(2，1)重复码。该重复码的两个许用码字是(00)和(11)，d02，R12。若用不完备译码(并与ARQ结合)则译码错误概率为p2e10-2。也就是说只有当(00)错成(11)或(11)错成(00)时，才造成译码错误。而(01)和(10)不是许用码字，不会造成译码错误。因此，这个码能发现传输中的一个错误，但不能自动纠正。第72页，共99页，编辑于2022年，星期五(3)(3，1)重复码。显然，

42、它的两个码字是(000)和(111)，d03，R13。设发的是(000)，若收到的是(001)或(010)或(100)，则根据大数译码准则正确地判为(000)，信息组为0。若收到的是(011)，(101)，(110)，(111)中之一，则造成译码错误，错判为信息组是1。因此，该码若用完备译码能纠正序列中的一个错误，此时译码错误概率p1-Q1-(1-pe)3+3pe(1-pe)2=2.810-2也就是误码率由0.1减至2.810-2=0.028。若该码不用作纠错，而采用不完备译码用作检错，则可以发现两个错误，与ARQ系统结合后，译码错误概率减至p3e10-3=0.001。第73页，共99页，编辑

43、于2022年，星期五(4)(4，1)重复码。显然，该码的d04，R14。由于n是偶数，故只能采取不完备译码。它的纠错能力如下：能纠正一个错误同时发现两个错误。若发送的是(0000)，则错一个时，根据大数准则可正确判断发送的是0信息组。若错两个变成(0011)，(1100)，(1010)，(0101)，(1001)，(0110)之一时，则译码器无法作出判决，而指出发生了两个错误。仅在变成(1110)，(0111)，(1011)，(1101)和(1111)时，译码器才作出错误译码。因此，这时的译码错误概率第74页，共99页，编辑于2022年，星期五若仅用来检错，则可检测ed0-13个错误。显然，若

44、发送的是(0000)，则仅在变成(1111)时，才产生错误译码，而其它情况均能正确译码或发现错误。因此，此时的译码错误概率pp4e10-4=0.0001。第75页，共99页，编辑于2022年，星期五(5)(5，1)重复码。(5，1)码的d05，R15。它的纠错能力如下：能纠正两个随机错误，这时的译码错误概率因此，传送信息组0、1的错误概率从0.1降至千分之七，约降低了两个量级。第76页，共99页，编辑于2022年，星期五若仅用来检错，则能发现ed0-14个错误。若与ARQ系统结合进行纠错，则译码错误概率大约为10-5。由上面有关重复码的一系列例子可以看到：(1)随着码长n的增加，重复码的d0n

45、越来越大，抗干扰能力越来越强，即dn1，误码率也越来越小，但码率R1n却越来越低，并随着n的增加而趋近于零。(2)在用同样的(n，k)码下，应用非完备译码并与ARQ系统相结合，译码器所给出的误码率比完备译码所产生的要低得多。还可看出，(n，k)分组码的最小距离d0(今后简称d)与纠错能力有如下关系：第77页，共99页，编辑于2022年，星期五定理定理1.3.1 任一(n，k)分组码，若要在码字内：(1)检测e个随机错误，则要求码的最小距离de+1；(2)纠正t个随机错误，则要求d2t+1;(3)纠正t个随机错误，同时检测e(t)个错误，则要求dt+e+1。(4)纠正t个错误和个删除，则要求d2

46、t+1。(证明见板书)。第78页，共99页，编辑于2022年，星期五图1-14纠错码纠错能力的几何解释第79页，共99页，编辑于2022年，星期五 例例1.2 奇偶校验(监督)码：奇偶校验码是只有一个校验元的(n,n-1)分组码。设给定kn-1位的二进制信息码组为:mk-1,mk-2,m1,m0，则按如下规则完成码中一个码字(cn-1,cn-2,c1,c0)的编码：cn-1mk-1,cn-2mk-2,c2m1,c1m0,而一个校验元c0mk-1+mk-2+m1+m0或mk-1+mk-2+m1+m0+c00cn-1+cn-2+c1+c00(1.3.5)该式保证每个码字中“1”的个数为偶数，所以称

47、这种校验关系为奇奇偶偶校校验验。由于分组码中的每一个码字均按同一规则构成，故称这种分组码为一致校验码一致校验码。显然，码中的码字数目M2k2n-1。第80页，共99页，编辑于2022年，星期五(1)(2，1)奇偶校验码。此码的n=2，k1，按c1+c00求出校验元c0=c1，所以两个许用码组是00和11，此时d2，R1/2，能发现一个错误。若在pe0.1的BSC中传送，则利用不完备译码并与ARQ相结合，可使误码率大约减至p10-2。(2)(3，2)码。此码有224个信息组，由式(1.3.5)求得校验元，得到相应的4个码字为：000，011，101，110。由此看出，这4个信息组就是在8个二进制

48、三重中，把重量为偶数的4个三重挑选为许用码字，重量为奇数的其它4个为禁用码组。显然，该码的d2，也只能发现码元中的一个错误。译码误码率大约为第81页，共99页，编辑于2022年，星期五(3)(4，3)码。该码的8个码字是按照式(1.3.5)的要求，在16个二进制四重中挑选出来的，其重量均为偶数。该码的d2，R3/4，故只能检测码字中的一位错误。其译码误码率约为。由上看出，(n，n-1)奇偶校验码。当它的n时，R1，但d2，d/n0，译码误码率ppe，接近未编码时的情况。即随着码长的增加，抗干扰能力接近于零。上述(n，1)和(n，n-1)码，随着码长n的增加，前者R0，后者抗干扰能力接近于零，或

49、d/n0，都不理想。那么是否存在有一种码，随着n的增加。其纠错能力和传信率都保持一定呢？换言之，在R一定时，随着n，d/n0，从而使p0的码是否存在？1949年香农(Shannon)的信道编码定理对此作了肯定的回答。第82页，共99页，编辑于2022年，星期五1.4 信道编码定理信道编码定理 有有噪噪信信道道编编码码定定理理(香香农农第第二二定定理理)：信道具有确定的信道容量C，对任何小于C的码率R，存在有速率为R码长为n的分组码及(n0，k0，m)卷积码，若用最大似然译码，则随着码长的增加其译码错误概率p可任意小，即和(1.4.1)第83页，共99页，编辑于2022年，星期五式中，Ab和Ac

50、为大于0的系数，Eb(R)和Ec(R)为正实函数，称为误误差差指指数数，它与R、C的关系如图1-15所示。图中，C1、C2为信道容量，且C1C2。由信息论的基本知识可知，在高斯白噪声信道时，信道容量式中，W是信道所能提供的带宽，PSES/T是信号功率，ES是信号能量，T是分组码信号的持续时间即信号宽度，PS/W是单位频带的信号功率，N0是单位频带的噪声功率，PS/(WN0)是信噪比。第84页，共99页，编辑于2022年，星期五图1-15信道容量C、码长n和错误概率p之间的转换关系第85页，共99页，编辑于2022年，星期五香农第一定理香农第一定理(无失真信源编码定理无失真信源编码定理)：当用J