信道编码纠错码基础.ppt

,信道编码基础Fundamentals of Channel Coding陈德元,OH:周五15:0017:00,地点:科研楼206,课程概况,目的：了解信道编码的作用与意义，对信道编码的研究方法和成果有广泛的基本认识，学会应用信道编码，为进一步研究打下基础特点：以概念和物理意义为主，数学推导尽量放到课外,教材及参考书,“纠错码原理与方法”，王新梅，西安电子科技大学出版社，高等学校教材“差错控制编码”，Shu Lin等著，晏坚等译，机械工业出版社，电子与电气工程图书“Digital Modulation and Coding”,S.G.Wilson,Prentice Hall（“数字调制与编码”影印版，电子工业出版社，通信与信息科学教育丛书）,作业及考试,作业：每章布置课后练习，20%。项目：二至四人为一组，选择一篇或两篇相关论文精读，模拟论文作者写一份国家自然科学基金申请书和答辩ppt，组长代表全组作报告；用C语言、Java或Matlab实现其中一篇论文的算法，20%。考试：基本概念、计算和简单证明，60%。,“通信的基本问题就是在一点重新准确地或近似地再现另一点所选择的消息”。烽火狼烟、摔杯为号、铜镜反光、鸣金收兵、集结号,（1916-2001）,为什么需要信道编码？,信道编码发展简史（1）,1948年信道编码定理20世纪四十年代,Hamming码、Golay码1954年，Reed-Muller码1955年Elias提出卷积码循环码（CRC,Cyclic Redundancy Check)1959年BCH码（Bose,Ray-Chaudhuri,Hocquuenghem)1960年RS码(Reed-Solomon),信道编码发展简史（2）,序列译码算法：1961年，Wozencraft,Reiffen,1963 Fano，1969，Jelinek.1963 年Massy门限译码算法1966年Forney级联编码概念同年Forney提出GMD算法1967年viterbi算法1967年Berlekmp译码算法,信道编码发展简史（3）,1974年BCJR算法1976年HR算法（Hartman和Rudoolph)1971年WeldonWED算法1972年Chase算法1982年Ungerbock提出TCM概念1993年，Turbo码，Claude Berrou,Alain Glavieux 和 Punya Thitimajshima,信道编码在GSM中应用 信道编码是提高通信系统可靠性的最主要手段，它不仅成功地用于典型的加性高斯噪声AWGN信道，也成功的用于各类变参量的衰落信道，前者主要是卫星通信。信道编码在数字蜂窝移动通信中最典型的应用是在全球移动通信系统GSM中的应用。在GSM中无线信道按其功能可分为业务信道(TCH)和控制信道(CCH)，其中业务信道用于传送话音与数据，控制信道用于传送信令和同步。GSM的信道编码系统总体框图如图所示。,GSM编、译码器方框图,图解GSM语音信道编码,CDMA(IS-95)CDMA2000(IS-2000)、WCDMA中的信道编码 IS-95是高通公司基于CDMA技术发展出来的2G移动通信标准：检错码、卷积码、交织编码。CDMA2000：检错码、卷积码、Turbo码、交织编码。WCDMA：检错码、卷积码、Turbo码、交织编码。,第一章 纠错码的基本概念Basic Concepts of Error Control Coding,1.1 数字通信系统的组成及信道模型 1.2 差错控制系统和纠错码分类 1.3 最大似然译码和纠错码的基本概念 1.4 信道编码定理,1.1 数字通信系统的组成及信道模型,一、数字通信系统的组成 通信的目的是要把对方不知道的消息及时可靠地(有时还须秘密地)传送给对方，因此，要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占的时间缩短、波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加，传送消息的可靠性减低。若要求可靠，则使得传送消息的速率变慢。因此，如何较合理地解决可靠性与速度这一对矛盾，是正确设计一个通信系统关键问题之一。通信理论本身(包括纠错码)也正是在解决这对矛盾中不断发展起来的。,图 1-1 数字通信系统模型,图中，信源编码器是把信源发出的消息如语言、图像、文字等转换成为二进制(也可转换成为多进制)形式的信息序列，并且为了使传输有效，还去掉了一些与传输信息无关的多余度(有时为了保密，信源编码器后还可接上加密器)。为了抗击传输过程中的各种干扰，往往要人为地增加一些多余度，使其具有自动检错或纠错能力，这种功能由图中的信道编码器即纠错编码器完成。发射机(调制器)的功用是把纠错码送出的信息序列通过调制器变换成适合于信道传输的信号。数字信号在信道传输过程中，总会遇到各种干扰而使信号失真，这种失真信号传输到接收端的接收机，进行解调，变成二进制(或多进制)信息序列。由于信道干扰的影响，该信息序列中可能已有错误，经过信道译码器即纠错码译码器，对其中的错误进行纠正，再通过信源译码器恢复成原来的消息送给用户。,本课程研究的是图中的信道编、译码器即纠错编、译码器两个方框，为了研究方便，将上述模型再进一步简化成图-所示的模型。在此模型中，信源是指原来的信源和信源编码器，其输出是二(多)进制信息序列。信道是包括发射机、实际信道(或称传输媒质)和接收机在内的广义信道(又称编码信道)，它的输入是二(多)进制数字序列，输出一般也是二(多)进制数字序列，而图中的信宿可以是人或计算机。,图 1-2 数字通信系统简化模型,二、信道模型回顾：编码是消息到信道波形或矢量的一种映射关系,从数学上看，信道实际上也是从发空间X到收空间Y一个概率映射函数,收发集合可以以符号集的多重形式表示，相当于多维空间。发空间的维数n与收空间的维数m可以不等例如当发送波形x(t)通过一个滤波器h(t)时，输出y(t)=x(t)*h(t)，如果x(t)只在0,T内有值，而当h(t)有一定的宽度t时，输出的非零长度变成了T+t，也就是说当接收采样率等于或高于发送采样率时，接收的维数增加了。而如果接收时采用了较低的采样率，则有效维数就减低了。,根据收发空间中每一维所取的数域有限或无限可分为离散信道和连续信道这里借用了空间的名称，但只用到了它的集合概念而没有用到空间中的运算，只有线性信道才可以直接用线性运算构成一个线性空间。离散信道可用转移概率律描述：P(y=b|x=a),a=(a1,a2,.aK)X（发空间）,b=(b1,b2,.bJ)Y（收空间）,均为矢量（或K(J)重符号）,信道特性：信道译码：发送ak,收到bj的概率为，接收端不唯一，以什么准则译码，使差错可接受？,例：二元对称信道,正确的传递概率分别为1/3和1/3。,译码器1：,译码性能分析：,则在此译码器下，平均错误概率为（设输入为等概）,译码器2：,关于译码准则的结论,现在以图1-2的模型来讨论二进制数字序列通过该系统时所发生的情况。设从信源送出字母A，它的二进制序列为11000，以基带信号传送，经发射机调制后，送往信道的已调信号如图1-3所示。由于信道的干扰，从信道输出端的信号产生了失真，如图1-4所示。这些失真信号送入接收机进行判决时，由于第一、二、四、五码元的波形失真不大，容易正确地判为1、1和0、0；但对第三个码元来说，由于失真严重而难于判决。这时有以下三种判决方法：一是勉强作出是0还是1的判决，即所谓硬判决；另一种是对该码元暂且不作判决，而输出一个未知或待定的信号“x”，称其为删除符号；第三种方法是输出一种有关该码元的信息，例如关于0和1的后验概率或似然函数，这种作法称为软判决。当然软判决的性能较好，但实现起来较复杂。,图 1 3 11000发送的已调信号波形,图 1-4 接收端收到的失真信号波形,在二进制硬判决情况下，信道可用图1-5所示的简单模型表示。图中，p01和p10分别是0错成1和1错成0的概率，称信道转移概率。该信道的信道转移概率矩阵可用,描述。如果p01=p10=pe，则称这种信道为二进制对称信道，简称BSC(Binary Symmetric Channel)。否则，称为不对称信道。若p01或p10等于零，则称为Z信道。通常BSC是一种无记忆信道，所以也称随机信道，它说明数据序列中出现的错误彼此无关。,图 1 5 二进制信道,如果信道的输入是二进制符号，而输出是离散的q(qpm2)进制符号，如图1-6所示，且p(i0)p(q-1-i1)，i0，1，q-1，则这种信道称为离散无记忆信道(Discrete Memoryless Channel,DMC)，显然BSC是DMC的一种特殊情况。DMC的信道转移概率矩阵,图 1-6 DMC,在作删除判决情况下，信道可用图1-7所示的模型表示，称为二进制删除信道，简称BEC(Binary Erasure Channel)，一般它也是对称信道。图中，pe为信道的转移概率，q为删除概率，在有删除处理情况下，信道的转移概率pe一般很小，可忽略，因此把图1-7所示的模型用图1-8代替，称为二进制纯删除信道。以后所说的BEC都是指这种信道。应当指出，当码元作删除处理时，它在序列中的位置是已知的，仅不知其值是0还是1，故对这种BEC信道的纠错要比BSC信道容易。,图 1-7 二进制删除信道,图 1-8 二进制纯删除,上述三种信道模型只是为了讨论问题方便而简化成理想的情况，它们表达了某些实际信道传送信号的主要特征。例如，卫星信道或深空信道，可近似看成是BSC。但有很多实际信道如高频、散射、有线等信道，由于各种干扰所造成的错误，往往不是单个地而是成群成串地出现的，也就是一个错误的出现，往往引起其前后码元的错误(突发错误)，表现为错误之间的相关性。产生这种错误的信道称有记忆信道或突发信道。在计算机存贮系统中，磁带的缺陷或读写头接触不良所引起的错误，也属于这种类型。但由于实际信道干扰的复杂性，所引起的错误往往不是单纯的一种，而是两种错误形式并存，只不过有的信道以某种错误形式为主罢了。,像这种随机错误与突发错误并存的信道，称为组合信道或复合信道。作为检错与纠错用的抗干扰码，必须针对这几类信道，设计能纠正随机错误或纠正突发错误的码，或者设计既能纠正随机错误又能纠正突发错误的码。我们将首先讨论BSC和BEC(包括多进制)的纠错编码问题。,三、错误图样 设发送的是n个码元长的序列C：(cn-1,cn-2,c1,c0)，通过信道传输到达接收端(纠错码译码器输入端)的序列为R：(rn-1,rn-2,r1,r0)。由于信道中存在干扰，R序列中的某些码元可能与C序列中对应码元的值不同，也就是说产生了错误。由于二进制序列中的错误不外乎是1错成0或0错成1，因此，如果把信道中的干扰也用二进制序列E：(en-1,en-2,e1,e0)表示，则相应有错误的各位ei取值为1，无错的各位取值为0，而R就是C与E序列模2相加的结果，称E为信道的错误图样或干扰矢量。例如，发送序列C：(1111100000)，收到的序列R：(1001010000)，第二、三、五、六位产生了错误，因此信道的错误图样E的二、三、五、六位取值为1，其它各位取值为0，即E：(0110110000)。用式子可表示成：,即RC+E，或E=R-C。,信道干扰所造成的错误可在序列中的任一位出现，且也可以在n长序列中同时出现一位、二位，甚至n位错误。因此，若发送的C序列长为n，则信道中可能产生的错误图样E共有2n种。若为突发信道，则在错误图样E中，第一个1与最后一个1之间的长度称为突发长度，其图样称为突发图样。在该例中，突发图样是(11011)，突发长度为5。,1.2 差错控制系统和纠错码分类,(1)重传反馈方式(Automatic Repeat reQuest,ARQ)，（自动请求重传、或检错重发）。应用ARQ方式纠错的通信系统如图1-9所示。发送端发出能够发现(检测)错误的码，接收端收到通过信道传来的码后，在译码器根据该码的编码规则，判决收到的码序列中有无错误产生，并通过反馈信道把判决结果用判决信号告诉发端。发端根据这些判决信号，把接收端认为有错的消息再次传送，直到接收端认为正确接收为止。,图 1-9 ARQ通信系统,应用ARQ方式必须有一反馈信道，一般较适用于一个用户对一个用户（点对点)的通信，且要求信源能够控制，系统收发两端必须互相配合、密切协作，因此这种方式的控制电路比较复杂。由于反馈重发的次数与信道干扰情况有关，若信道干扰很频繁，则系统经常处于重发消息的状态，因此这种方式传送消息的连贯性和实时性较差。该方式的优点是：编译码设备比较简单；在一定的多余度码元下，检错码的检错能力比纠错码的纠错能力要高得多，因而整个系统的纠错能力极强，能获得极低的误码率；由于检错码的检错能力与信道干扰的变化基本无关，因此这种系统的适应性很强，特别适应于短波、散射、有线等干扰情况特别复杂的信道中。,(2)前向纠错方式(Forward Error Correction,FEC)。数字通信系统如图1-2所示。发送端发送能够被纠错的码，接收端通过纠错译码器不仅能自动地发现错误，而且能自动地纠正接收码字传输中的错误。其优点是不需要反馈信道，适用于一对多的广播通信，译码实时性较好。其缺点是译码设备复杂，所选用的纠错码必须与信道的干扰情况相匹配，因而对信道的适应性较差。为了要获得比较低的误码率，必须以最坏的信道条件来设计纠错码，所需的冗余码元比检错码要多得多，从而编码效率低。特别适用于军用通信，并且随着编码理论的发展和编译码设备所需的大规模集成电路成本的不断降低，译码设备有可能更简单，成本更低，在实际的数字通信中逐渐得到应用。主要用于语音，广播，TV等通信。,(3)混合纠错方式(Hybrid Error Correction,HEC)。这种方式是发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错能力。接收端收到码序列以后，首先检验错误情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果错误很多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消息。这种方式在一定程度上避免了FEC方式要求用复杂的译码设备和ARQ方式信息连贯性差的缺点，并能达到较低的误码率，因此在实际中的应用越来越广。,除了上述三种主要方式以外，还有所谓狭义信息反馈系统(Information Repeat reQuest,IRQ)，或信息反馈重发。这种方式是接收端把收到的消息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的消息，从而发现错误，并且把传错的消息再次传送，最后达到使对方正确接收消息的目的。为了便于比较，我们把上述几种方式用图1-10所示的框图表示。在实际系统设计中，如何根据实际情况选择哪种差错控制方式是一个比较复杂的问题。,检错重发(ARQ)前向纠错混合纠错,图 1-10 差错控制的基本方式,二、纠错码的分类 上述各种差错控制系统中所用到的码，不外乎是能在译码器自动发现错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者能纠正删除错误的纠删码。但这三类码之间没有明显区分，以后将看到，任何一类码，按照译码方法不同，均可作为检错码、纠错码或纠删码来使用。除了上述的划分方法以外，通常还按以下方式对纠错码进行分类：,(1)按照对信息元处理方法的不同，分为分组码与卷积码两大类。分组码是把信源输出的信息序列，以k个码元划分为一段，通过编码器把这段k个信息元按一定规则产生r个校验(监督)元，输出长为nk+r的一个码组。因此每一码组的校验元仅与本组的信息元有关，而与别组无关。分组码用(n，k)表示，n表示码长，k表示信息位。卷积码是把信源输出的信息序列，以k0个(k0通常小于k)码元分为一段，通过编码器输出长为n0(k0)一段的码段。但是该码段的n0-k0个校验元不仅与本组的信息元有关，而且也与其前m段的信息元有关，称m为编码存贮。因此卷积码用(n0，k0，m)表示。,(2)根据校验元与信息元之间的关系分为线性码与非线性码。若校验元与信息元之间的关系是线性关系(满足线性叠加原理)，则称为线性码;否则，称为非线性码。由于非线性码的分析比较困难，实现较为复杂，故今后仅讨论线性码。(3)按照纠正错误的类型可分为纠正随机(独立)错误的码、纠正突发错误的码和纠正同步错误的码，以及既能纠正随机错误又能纠正突发错误的码。,(4)按照每个码元取值来分，可分为二进制码与q进制码(q=pm，p为素数，m为正整数)。(5)按照对每个信息元保护能力是否相等可分为等保护纠错码与不等保护(UEP)纠错码。除非特别说明，今后讨论的纠错码均指等保护能力的码。此外，在分组码中按照码的结构特点，又可分为循环码与非循环码。为了清楚起见，我们把上述分类用图 1-11表示。,图 1-11 纠错码分类,1.3 最大似然译码和纠错码的基本概念,一、基本定义 利用纠错码进行差错控制的数字通信系统如图1-12所示，由此可如下定义分组码。定义1.3.1 分组码是对每段k位长的信息组，以一定规则增加r=n-k个校验元，组成长为n的序列：(cn-1,cn-2,c1,c0)，称这个序列为码字(码组、码矢)。在二进制情况下，信息组总共有2k(q进制为qk)个，因此通过编码器后，相应的码字也有2k个，称这2k个码字集合为(n，k)分组码。,图 1-12 分组码的数字通信模型,n长序列的可能排列总共有2n种(每一n长序列称为n重)，而(n，k)分组码的码字集合只有2k种。所以，分组码的编码问题就是定出一套规则（映射），以便从2n个n重中选出2k个码字，不同的选取规则就得到不同的码。我们称被选取的2k个n重为许用码组，其余的2n-2k个为禁用码组。称Rkn为码率，表示(n，k)分组码中，信息位在码字中所占的比重。R是衡量分组码有效性的一个基本参数。,图 1-13是一个(2,1,2)卷积码编码器。若输入的信息序列以k01个码元分段输入，则输出以n02个码元为一段输出，如输入的信息序列M(1 1 0 1 0 0)，输出的码序列为C(11，10，10，00，01，11，00，)。可知随着信息元的不断输入，输出的是一个半无限长的码序列，由此可如下定义卷积码。,图 1-13 一个(2，1，2)卷积码编码器,定义(n0，k0，m)卷积码是对每段k0长的信息组以一定的规则增加r0n0-k0个校验元，组成长为n0的码段。n0-k0个校验元不仅与本段的信息元有关，且与前m段的信息元有关，当信息元不断输入时，输出的码序列是一个半无限长序列。(n0，k0，m)卷积码的码率Rk0/n0。与分组码的码长n相对应，在卷积码中称nck0(m+1)为编码约束长度，说明k0个信息元从输入编码器到离开时在码序列中影响的码元数目，如图1-13中(2，1，2)卷积码的nc 3。,二、最大似然译码 由图1-2可知，信道输出的R是一个2(或q)进制序列，而译码器的输出是一个信息序列M的估值序列。译码器的基本任务就是根据一套译码规则，由接收序列R给出与发送的信息序列M最接近(最好是相同)的估值序列。由于M与码字C之间存在一一对应关系，所以这等价于译码器根据R产生一个C的估值序列。显然，当且仅当 C时，M，这时译码器正确译码。,如果译码器输出的 C，则译码器产生了错误译码。之所以产生错误译码是由于：信道干扰很严重，超过了码本身的纠错能力；其次，由于译码设备的故障(不讨论)。当给定接收序列R时，译码器的条件译码错误概率定义为,所以译码器的错误译码概率,P(R)是接收R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使,因此，如果译码器对输入的R，能在2k个码字中选择一个使 最大的码字Ci作为C的估值序列，则这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验概率译码（理想译码器）。,（）,由贝叶斯公式,可知，若发端发送每个码字的概率P(Ci)均相同，且由于P(R)与译码方法无关，所以,对DMC而言,（）,（）,这里码字Ci(ci1，ci2，cin)，i1，2，2k。,一个译码器的译码规则若能在2k个码字C中选择某一个Ci使式(1.3.2)成为最大，则这种译码规则称为最大似然译码(MLD)，P(R|C)称为似然函数，相应的译码器称为最大似然译码器。由于logbx与x是单调关系，因此式(1.3.2)与式(1.3.3)可写成,称logbP(R|C)为对数似然函数或似然函数。对于DMC信道，MLD是使译码错误概率最小的一种最佳译码准则或方法，但此时要求发端发送每一码字的概率P(Ci)(i1,2,2k)均相等，否则MLD不是最佳的。以后都认为P(Ci)均近似相等。,三、汉明(Hamming)距离与重量 定义1.3.3 两个n重x、y之间，对应位取值不同的个数，称为它们之间的汉明距离，用d(x，y)表示。例如，若x:(10101)，y:(01111)，则d(x，y)3。定义 n重x中非零码元的个数，称为它的汉明重量，简称重量，用w(x)表示。例如，若x:(10101)，则w(x)3。若y:(01111)，则w(y)4，等等。,定义(n，k)分组码中，任两个码字之间距离的最小值，称为该分组码的最小汉明距离d0，简称最小距离 例如(3,2)码，n3，k2，共有224个码字：000，011，101，110，显然d02。d0是(n，k)分组码的另一个重要参数。它表明了分组码抗干扰能力的大小：d0越大，码的抗干扰能力越强，在同样译码方法下它的译码错误概率越小。由上可知，R和d0是(n，k)分组码的两个最重要参数。纠错编码的基本任务之一就是构造出R一定、d0尽可能大的码，或d0一定、R尽可能高的码。下面用几个具体例子说明码的R、d0以及译码错误概率之间的关系。,例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，因此在传输中没有错误的可能性比出现一个错误的可能性大，出现一个错误的可能性比出现两个错误的大，等等。也就是说信道错误图样E中，出现重量最轻的图样可能性最大。,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。这种译码方案就是大数准则译码。,当n是奇数时，按照这种大数准则译码方法，译码器总可以很快地作出是0还是1的判决。当n是偶数时可能出现以下情况，即接收序列中“1”的个数和“0”的个数刚好相等，此时若按大数准则无法作出判断，造成译码失败，这种译码称为不完备译码。而n为奇数情况下的译码(即译码器一定作出是哪一个信息组的判决)称为完备译码。译码失败只表明译码器无法给出明确判断，但并不等于译码错误，而仅表明接收序列中存在有错误。此时，如果我们与ARQ系统相结合，则可以利用此信息要求对方重发该组信息，直到译码器作出明确判决为止。下面几个具体例子说明重复码的抗干扰能力。,(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)不是许用码字，不会造成译码错误。因此，这个码能发现传输中的一个错误，但不能自动纠正。,(3)(3，1)重复码。显然，它的两个码字是(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。,(4)(4，1)重复码。显然，该码的d04，R14。由于n是偶数，故只能采取不完备译码。它的纠错能力如下：能纠正一个错误同时发现两个错误。若发送的是(0000)，则错一个时，根据大数准则可正确判断发送的是0信息组。若错两个变成(0011)，(1100)，(1010)，(0101)，(1001)，(0110)之一时，则译码器无法作出判决，而指出发生了两个错误。仅在变成(1110)，(0111)，(1011)，(1101)和(1111)时，译码器才作出错误译码。因此，这时的译码错误概率,若仅用来检错，则可检测ed0-13个错误。显然，若发送的是(0000)，则仅在变成(1111)时，才产生错误译码，而其它情况均能正确译码或发现错误。因此，此时的译码错误概率pp4e10-4=0.0001。,(5)(5，1)重复码。(5，1)码的d05，R15。它的纠错能力如下：能纠正两个随机错误，这时的译码错误概率,因此，传送信息组0、1的错误概率从0.1降至千分之七，约降低了两个量级。,若仅用来检错，则能发现ed0-14个错误。若与ARQ系统结合进行纠错，则译码错误概率大约为10-5。由上面有关重复码的一系列例子可以看到：(1)随着码长n的增加，重复码的d0n越来越大，抗干扰能力越来越强，即dn1，误码率也越来越小，但码率R1n却越来越低，并随着n的增加而趋近于零。(2)在用同样的(n，k)码下，应用非完备译码并与ARQ系统相结合，译码器所给出的误码率比完备译码所产生的要低得多。还可看出，(n，k)分组码的最小距离d0(今后简称d)与纠错能力有如下关系：,定理1.3.1 任一(n，k)分组码，若要在码字内：(1)检测e个随机错误，则要求码的最小距离de+1；(2)纠正t个随机错误，则要求d2t+1;(3)纠正t个随机错误，同时检测e(t)个错误，则要求dt+e+1。(4)纠正t个错误和个删除，则要求d2t+1。(证明见板书)。,图 1-14 纠错码纠错能力的几何解释,例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+c00 cn-1+cn-2+c1+c00(1.3.5)该式保证每个码字中“1”的个数为偶数，所以称这种校验关系为奇偶校验。由于分组码中的每一个码字均按同一规则构成，故称这种分组码为一致校验码。显然，码中的码字数目M2k2n-1。,(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个二进制三重中，把重量为偶数的4个三重挑选为许用码字，重量为奇数的其它4个为禁用码组。显然，该码的d2，也只能发现码元中的一个错误。译码误码率大约为,(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，后者抗干扰能力接近于零，或d/n0，都不理想。那么是否存在有一种码，随着n的增加。其纠错能力和传信率都保持一定呢？换言之，在R一定时，随着n，d/n0，从而使p0的码是否存在？1949年香农(Shannon)的信道编码定理对此作了肯定的回答。,1.4 信道编码定理,有噪信道编码定理(香农第二定理)：信道具有确定的信道容量C，对任何小于C的码率R，存在有速率为R码长为n的分组码及(n0，k0，m)卷积码，若用最大似然译码，则随着码长的增加其译码错误概率p可任意小，即,和,(1.4.1),式中，Ab和Ac为大于0的系数，Eb(R)和Ec(R)为正实函数，称为误差指数，它与R、C的关系如图1-15所示。图中，C1、C2为信道容量，且C1C2。由信息论的基本知识可知，在高斯白噪声信道时，信道容量,式中，W是信道所能提供的带宽，PSES/T是信号功率，ES是信号能量，T是分组码信号的持续时间即信号宽度，PS/W是单位频带的信号功率，N0是单位频带的噪声功率，PS/(WN0)是信噪比。,图 1-15 信道容量C、码长n和错误概率p之间的转换关系,香农第一定理(无失真信源编码定理)：当用J个码字对熵率为H(U)的离散无记忆平稳信源进行变长编码时，若概率为p(ak)的源字所对应的码字长度为lk，则前缀码的平均码长 必须满足,另一方面，必可构造前缀码，使,保真度准则下的信源编码定理(香农第三定理)：设R(D)为某离散无记忆信源的率失真函数，对任意允许失真度D0，和任意小的正数(0)，以及足够长的码字长度N，则必存在一种信源编码W，其码字个数 MexpNR(D)+编码后的平均失真度满足,三大定理的联合结论,如果不等式CRR(D)成立，根据定理3总可以找到一种编码方法，使其平均失真度D，输出信息率降为R、再根据定理1（冗余编码）和定理2（有噪信道编码），总能得到既有效、又可靠的通信系统；反之，不等式不成立，则在信宿端失真或错误不可避免。,由式(1.4.1)和图 1-15可看出，信道容量C、码长n和错误概率p之间的转换关系。为了满足一定误码率p的要求，可用以下两类方法实现。一是增加信道容量C，从而使E(R)增加。由C的表示式(1.4.2)可知，增加C的方法可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、调相等宽带调制方法；增加发射机的功率；应用高增益天线；采用分集接收及低噪声器件等方法。这些措施是从根本上改善信道、增加信道容量、减少误码率的方法，是通信设计工作者经常采用的传统方法。,另一种方法是在R一定下，增加分组码长n(也就是增加分组信号持续时间T)，可使p随n的增加而呈指数下降。但由于码长n的增加，当R保持一定时，可能发送的码字数2k指数增加，从而增加了译码设备的复杂性。这种方法就是信道编码定理所指出减少误码率的另一方向，它为通信设计工作者提供了一条新的途径。下面通过几个具体例子说明R保持一定时，随着n的增加，可使p下降。,例1.3 设有一个随机产生二进制序列的信源和一个转移概率pe0.1的BSC。如果不编码，则传送消息的误码率仍为0.1。现以R12的码率进行编码，考察一下编码效果。首先，按k2分组，则编出码的长度n4，构成一个(4，2)分组码。编码规则如下：设两个信息元为c3、c2，两个校验元为c1、c0，则c1c2 c0c3+c2 编出的4个许用码组为:(0000)，(1001)，(0111)，(1110)。其余12个四重为禁用码组。译码按表1-1所示的译码表进行。译码表的第一行是许用码组，禁用码组则在其它行，列于许用码组之下，接收到的四重落在哪一列就相应地译为最上面一行所对应的信息码。每一种可能接收的四重，在译码表中仅出现一次。,表1-1(4，2)码译码表,由译码表可知，若发送码字在传送过程中前三位的任一位发生错误，接收的四重必位于该码字所在列中，因而正确译码。因此正确译码概率,码字的错误译码概率,由此可得译码后的误码率,可以看到，编码使误码率由0.1下降到0.063。,如果保持传信率R1/2不变，把信息组的长度k加大到3，构成一个(6,3)码。设信息组为c5、c4、c3，相应地3个校验元为c2、c1、c0，按下述校验规则求校验元：,c2c3+c4，c1=c3+c5，c0=c4+c5，,得到8个码字及其译码表，如表1-2所示。由该译码表知，发送码字的六位码元中，任一位出现错误均可纠正。第一位和第四位同时出现错误时也能正确译码。故三位信息组完全正确译出的概率为,表1-2(6，3)码编译码表,相应的信息元误码率,由此可见，随着n的增加，在保持R12不变时，可使误码率越来越小，这正是信道编码定理指出的结果。但也必须看到，随着n的增加，其译码设备的复杂性成指数增加。我们研究纠错编码的意义就在于：保持一定的信息传输效率条件下，通过编译码来降低误码率以实现可靠通信，并且要求译码器尽可能简单。,应用纠错码后，若仍要求传输信息的速率不变，则必然使信道的带宽W增加。设原来的信息传输速率为600bit/s，如用R1/2码，则要求信道传输速率为1200bit/s，一般要求信道带宽增加一倍(通常增加(n-k)/k倍)。因此，纠错码主要应用于功率受限而带宽不太受限的信道中。,在极限情况n时，要求带宽W。此时只要求信噪比Eb/N0-1.6dB，就可实现高斯白噪声信道下的无误传输。这就是带宽无限高斯白噪声信道的极限传输能力，称为Shannon限。图1-16给出了未编码的PSK与应用各类纠错码后，误码率与信噪比之间的关系曲线。由此图看到：应用R1/2的(24,12)分组码后，在误码率为10-5时比未编码的大约可节省3dB的功率(称编码增益)；而用R=1/2，约束度N为8的卷积码软判决维特比(Viterbi)译码，在误码率为10-5时，大约可节省5dB的功率。一般情况下，应用纠错码后，大约能得到从零点几到几个dB程度不等的编码增益。,图 1-16 各种码的性能比较,