信息论与编码 第6章(1)

1、2021-11-291第六章第六章信道编码信道编码 2021-11-292数字通信系统的一般模型数字通信系统的一般模型 等效信道等效信道 干扰源干扰源 物理信道物理信道 解调器解调器 编码器编码器 译码器译码器 信宿信宿 信源信源 调制器调制器 实际信道实际信道 编码信道编码信道 2021-11-293将模拟信号变为13比特线性码声电输出RPE-LTP编码器RPE-LTP译码器将13比特线性码变换为8比特A律码无线子系统将13比特线性码变为模拟信号电声输出RPE-LTP译码器13 kb / sRPE-LTP编码器将8比特A律码变换为13比特线性码移动交换中心公用电话交换网(PSTN/ISDN)

2、模拟语音8000样本/秒13比特线性码8000样本/秒13比特线性码8000样本/秒8比特A律50帧260比特/帧无线接入和GMSK调制前向纠错编码交织话音编码456比特/帧无线解调去交织纠错编码无线GMSK解调纠错编码去交织无线接入及调制交织前向纠错编码双工器语音编码456比特/帧104 kb / s移动台MS基站系统BSSGSM系统的话音和信道编码系统的话音和信道编码2021-11-294语音编码器（260bits）3bit奇偶校验奇偶校验半速卷积编码器半速卷积编码器8时隙交织时隙交织Ia类（50bit） Ib类（132bit） 类（78bit）53bit378编码比特456bit（8个子

3、块，57bit/子块）4尾比特GSM语音编解码的前向纠错（全速业务信道）语音编解码的前向纠错（全速业务信道）2021-11-2952021-11-296香农编码定理香农编码定理n信息通过信道传输到信宿的过程即为信息通过信道传输到信宿的过程即为通信通信。要做到。要做到既不失真又快速地通信，需要解决两个问题：既不失真又快速地通信，需要解决两个问题：n在不失真或允许一定失真条件下，在不失真或允许一定失真条件下，如何提高信息传输如何提高信息传输速度速度-这是第这是第5 5章要讨论的章要讨论的信源编码信源编码问题问题. .n在信道受到干扰的情况下，在信道受到干扰的情况下，如何增加信号的抗干扰能如何增加信

4、号的抗干扰能力，同时又使得信息传输率最大力，同时又使得信息传输率最大-这是本章要讨论的这是本章要讨论的信道编码信道编码问题问题. .n信源编码的基础是信息论中的两个编码定理信源编码的基础是信息论中的两个编码定理n无失真信源编码无失真信源编码 第一极限定理第一极限定理 n限失真信源编码限失真信源编码 第三极限定理第三极限定理n信道编码定理（离散和连续信道）信道编码定理（离散和连续信道） 第二极限定理第二极限定理2021-11-297 XNUUY2021-11-298n信源编码信源编码n提高数字信号提高数字信号n将信源的模拟信号转变为数字信号将信源的模拟信号转变为数字信号n降低数码率降低数码率,

5、,压缩传输频带压缩传输频带( (数据压缩数据压缩) )n信道编码信道编码n提高数字通信提高数字通信 n数字信号在信道的传输过程中数字信号在信道的传输过程中, ,由于实际由于实际信道信道的的传传输特性不理想输特性不理想以及存在加性以及存在加性噪声噪声, ,在接收端往往会在接收端往往会产生产生误码误码。2021-11-299信道编码信道编码是以信息在信道上的正确传输为目标是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：的编码，可分为两个层次上的问题：n如何正确接收载有信息的信号如何正确接收载有信息的信号线路编码线路编码( (通信原理，基带编码）通信原理，基带编码）n如何避免少量差错

6、信号对信息内容的影响如何避免少量差错信号对信息内容的影响纠错编码纠错编码n纠错编码的理论体系属于信息论，但纠错编码纠错编码的理论体系属于信息论，但纠错编码的实现离不开有形载体的信号理论，因此信息的实现离不开有形载体的信号理论，因此信息的编码与信号的编码有天然的联系。的编码与信号的编码有天然的联系。2021-11-29106.1 有扰离散信道的编码理论有扰离散信道的编码理论6.2 纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法6.3 线性分组码线性分组码6.4 卷积码卷积码6.5 其它信道编码其它信道编码内内 容容2021-11-29116.1 6.1 有扰离散信道的编码定理有扰离

7、散信道的编码定理 6.1 .1 差错和差错控制系统分类差错和差错控制系统分类 6.1 .2 矢量空间与码空间矢量空间与码空间 6.1 .3 随机编码与信道编码定理随机编码与信道编码定理2021-11-29126.1.1 6.1.1 差错和差错控制系统分类差错和差错控制系统分类是衡量传输质量的重要指标之一是衡量传输质量的重要指标之一,它有几种不同它有几种不同的定义。的定义。n码元差错率码元差错率/符号差错率符号差错率n指在传输的指在传输的码元码元总数中发生差错的码元数所占的比总数中发生差错的码元数所占的比例例(平均值平均值),简称简称误码率误码率(Error symbol rate)。n是指是指

8、差错概率差错概率 n比特差错率比特差错率 /比特误码率比特误码率(Error bit rate)：n在传输的在传输的比特比特总数中发生差错的比特数所占比例总数中发生差错的比特数所占比例n是指是指差错概率差错概率 n对对二进制二进制传输系统传输系统,符号差错等效于比特差错符号差错等效于比特差错;对多进制对多进制系统系统,一个符号差错对应多少比特差错却难以确定一个符号差错对应多少比特差错却难以确定2021-11-2913量级量级自然二进制码自然二进制码反射二进制码反射二进制码000000010010012010011301101041001105101111611010171111002021-1

9、1-2914差错率差错率n根据不同的应用场合对差错率有不同的要求根据不同的应用场合对差错率有不同的要求:n在电报传送时在电报传送时,允许的比特差错率约为允许的比特差错率约为: 104105；n计算机数据传输计算机数据传输,一般要求比特差错率小于一般要求比特差错率小于: 108109；n在遥控指令和武器系统的指令系统中在遥控指令和武器系统的指令系统中,要求有要求有更小的误比特率或码组差错率更小的误比特率或码组差错率2021-11-2915差错图样差错图样n为定量地描述信号的差错为定量地描述信号的差错,定义定义差错图样差错图样E E=CR (模模M )n最常用的二进制码可当作特例来研究最常用的二进

10、制码可当作特例来研究,其差错图样等其差错图样等于收码与发码的模于收码与发码的模2加加,即即 E = C R 或或 C = R En设发送的码字设发送的码字C 1 1 1 1 1 1 1 1 1 1 接收的码字接收的码字R 1 0 0 1 0 0 1 1 1 1 差错的图样差错的图样E 0 1 1 0 1 1 0 0 0 0 n差错图样中的差错图样中的“1”既是符号差错也是比特差错既是符号差错也是比特差错,差错差错的个数叫的个数叫汉明距离汉明距离。0:传输中无错1:传输中有错2021-11-2916差错图样类型差错图样类型n随机差错随机差错：n差错是差错是相互独立相互独立的的,不相关不相关n存在

11、这种差错的信道是无记忆信道或随机信道存在这种差错的信道是无记忆信道或随机信道n突发差错突发差错：n指指成串成串出现的错误出现的错误,错误与错误间有相关性错误与错误间有相关性,一个差错一个差错往往要影响到后面一串字往往要影响到后面一串字nE: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 突发长度= 4突发长度= 62021-11-2917纠错码分类纠错码分类 n从功能角度讲从功能角度讲, ,差错码分为检错码和纠错码差错码分为检错码和纠错码n检错码检错码：用于发现差错：用于发现差错n纠错码纠错码：能自动纠正差错：能自动纠正差错n纠错码与检错码在理

12、论上没有本质区别纠错码与检错码在理论上没有本质区别, ,只是只是应用场合不同应用场合不同, ,而侧重的性能参数也不同。而侧重的性能参数也不同。n本章的纠错编码包含检错码本章的纠错编码包含检错码. .2021-11-2918检错与纠错原理检错与纠错原理 n0:晴晴,1:雨雨n若若10,01。收端无法发现错误。收端无法发现错误00晴1001110011雨能发现一个错误禁用码组n插入插入1位监督码位监督码后具有后具有检出检出1位错码位错码的能的能力（力（2位呢？）位呢？）,但不能予以纠正。但不能予以纠正。2021-11-2919检错与纠错原理检错与纠错原理 000晴010001111000111雨晴

13、n在只有在只有1位错码位错码的情况下的情况下,可以判决哪位是错码可以判决哪位是错码并予以并予以纠正纠正,可以可以检出检出2位位或或2位以下的错码。位以下的错码。100011101110雨2021-11-2920检错与纠错原理检错与纠错原理n最大似然译码最大似然译码：n将接收到的码字译码为与它将接收到的码字译码为与它的的许用码字许用码字,并且认为这个许用码字就是它所对应的发送码字并且认为这个许用码字就是它所对应的发送码字,从而在码字的纠错能力内实现自动纠错。从而在码字的纠错能力内实现自动纠错。n纠错编码之所以具有检错、纠错能力纠错编码之所以具有检错、纠错能力,是因为在信息是因为在信息码元之外加入

14、了码元之外加入了监督码监督码。监督码不载信息。监督码不载信息,只是用来只是用来监督信息码在传输中有无差错。监督信息码在传输中有无差错。n纠错编码所提高的可靠性纠错编码所提高的可靠性,是以牺牲信道利用率为代是以牺牲信道利用率为代价换取的。价换取的。n监督码监督码引入引入越多越多,检错、纠错检错、纠错能力能力越强越强,但信道的传输但信道的传输效率下降也越多。效率下降也越多。2021-11-2921n信道编码信道编码n在被传输信息中附加一些冗余码在被传输信息中附加一些冗余码, ,即即监督码元监督码元, ,利用附加码元与信息码元间的利用附加码元与信息码元间的约束关系约束关系加以校加以校验验, ,以以。

15、n信源信源编码编码减少减少了了n冗余度是随机的、无规律的冗余度是随机的、无规律的n信道信道编码编码增加增加了了n冗余度是特定的、有规律的冗余度是特定的、有规律的, ,故可利用其在接收故可利用其在接收端进行检错和纠错。端进行检错和纠错。信道编码信道编码2021-11-2922信道编码的基本思想信道编码的基本思想n信道编码信道编码n按一定规则给数字序列按一定规则给数字序列m增加一些增加一些多余多余的码元的码元,使使不具有规律性的信息序列不具有规律性的信息序列 m 变换为具有某种规律变换为具有某种规律性的数码序列性的数码序列 C；n码序列中的码序列中的信息序列码元信息序列码元与与多余码元多余码元之间

16、是之间是的；的；n信道译码器利用这种信道译码器利用这种预知的预知的编码规则译码。检验编码规则译码。检验接收到的数字序列接收到的数字序列 R 是否符合既定的是否符合既定的 规则规则,从而从而发现发现 R 中是否有错中是否有错,或者纠正其中的差错；或者纠正其中的差错；n根据根据来检测来检测/发现和纠正发现和纠正传输过程中产生的传输过程中产生的差错就是信道编码的基本思想。差错就是信道编码的基本思想。2021-11-2923纠错码分类纠错码分类 n按照对信息序列的处理方法按照对信息序列的处理方法,有有分组码分组码和和卷积码卷积码n分组码分组码：n将将k个信息码元分成一组个信息码元分成一组,由这由这k个

17、码元按照一定规个码元按照一定规则产生则产生r个监督码元个监督码元,组成长度组成长度n = k + r的码字的码字 n卷积码卷积码：n先将信息序列分组先将信息序列分组, ,不同的是编解码运算不仅与不同的是编解码运算不仅与本组信息有关本组信息有关, ,而且还与而且还与前面若干组有关前面若干组有关。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr2021-11-2924纠错码分类纠错码分类 n按照码元与原始信息位的关系按照码元与原始信息位的关系,分为分为n线性码线性码：所有码元均是原始信息元的：所有码元均是原始信息元的线性组合线性组合,编码编码器不

18、带反馈回路。器不带反馈回路。n非线性码非线性码：码元并不都是信息元的线性组合：码元并不都是信息元的线性组合,可能还可能还与前面已编的码元有关与前面已编的码元有关,编码器可能含反馈回路。编码器可能含反馈回路。n由于非线性码的分析比较困难由于非线性码的分析比较困难,早期实用的纠错码多为早期实用的纠错码多为线性码线性码,但当今发现的很多但当今发现的很多好码好码恰恰是非线性码。恰恰是非线性码。n假设假设i，j是某（是某（ n，k）分组码的两个码字，）分组码的两个码字， 是是码元字符集里的任意两个元素，码元字符集里的任意两个元素， 当且仅当当且仅当也是码字时，才称该码是线性码或群码。也是码字时，才称该码

19、是线性码或群码。12, 2021-11-2925纠错码分类纠错码分类 n按照适用的差错类型按照适用的差错类型, ,分成分成: :n纠随机差错码纠随机差错码: :用于随机差错信道用于随机差错信道, ,其纠错能力用其纠错能力用码组内允许的独立差错的个数来衡量。码组内允许的独立差错的个数来衡量。n纠突发差错码纠突发差错码: :针对突发差错而设计针对突发差错而设计, ,其纠错能力其纠错能力主要用可纠突发差错的最大长度来衡量主要用可纠突发差错的最大长度来衡量n 按照构造码的理论：代数码、几何码、算术码和按照构造码的理论：代数码、几何码、算术码和组合码。代数码：近世代数。组合码。代数码：近世代数。 几何码

20、：投影几何。几何码：投影几何。 算术码：数论和高等算术。算术码：数论和高等算术。 组合码：排列组合和数论。组合码：排列组合和数论。2021-11-2926差错控制系统分类差错控制系统分类 n前向纠错前向纠错(FEC(FEC，forward error correction)forward error correction)：n发送端的信道编码器将信息码组编成具有一定发送端的信道编码器将信息码组编成具有一定纠纠错能力错能力的码。的码。n接收端信道译码器对接收码字进行译码接收端信道译码器对接收码字进行译码, ,若传输若传输中产生的差错数目在码的纠错能力之内时中产生的差错数目在码的纠错能力之内时,

21、,译码译码器对差错进行定位并加以纠正。器对差错进行定位并加以纠正。n应用在应用在实时性和容错强实时性和容错强的场合的场合, ,如语音如语音, ,图像图像2021-11-2927差错控制系统分类差错控制系统分类 n自动请求重发自动请求重发(ARQ, automatic repeat request)：n发端发送发端发送检错码检错码, 如如CRC(循环冗余校验码循环冗余校验码)，n收端译码器判断当前码字传输是否出错；收端译码器判断当前码字传输是否出错；n当有错时按某种协议通过一个当有错时按某种协议通过一个反向信道反向信道请求发送端请求发送端重传已发送的码字重传已发送的码字(全部或部分全部或部分)。

22、n应用于数据通信网、计算机网络应用于数据通信网、计算机网络2021-11-2928差错控制系统分类差错控制系统分类 n混合纠错混合纠错(HEC, hybrid error correction)：n是是FEC与与ARQ方式的结合。方式的结合。n发端发送同时具有自动纠错和检测能力的码组发端发送同时具有自动纠错和检测能力的码组,收端收收端收到码组后到码组后,检查差错情况检查差错情况,如果差错在码的纠错能力以内如果差错在码的纠错能力以内,则自动进行纠正。则自动进行纠正。n如果信道干扰很严重如果信道干扰很严重,错误很多错误很多,超过了码的纠错能力超过了码的纠错能力,但但能检测出来能检测出来,则经反馈信

23、道请求发端重发这组数据。则经反馈信道请求发端重发这组数据。n信息反馈信息反馈(IRQ)：n收端把收到的数据收端把收到的数据,原封不动地通过反馈信道送回到发原封不动地通过反馈信道送回到发端端,发端比较发的数据与反馈来的数据发端比较发的数据与反馈来的数据,从而发现错误从而发现错误,并并且把错误的消息再次传送且把错误的消息再次传送,直到发端没有发现错误为止。直到发端没有发现错误为止。只适于低速非实时数据通信，是一种较原始的做法。只适于低速非实时数据通信，是一种较原始的做法。 2021-11-29296.1.2 矢量空间与码空间矢量空间与码空间分组码：把信源输出的信息序列，以分组码：把信源输出的信息序

24、列，以k个码元个码元化分为化分为一段，通过编码器把这段一段，通过编码器把这段k个信息元按照一定的规则个信息元按照一定的规则产生产生 r个校验元个校验元，输出长为，输出长为n=k+r的一个码组。每个码的一个码组。每个码组的校验元仅与本组的信息元有关，而与别组无关。组的校验元仅与本组的信息元有关，而与别组无关。分组码一般用分组码一般用(n,k)来表示，其中来表示，其中n表示码长表示码长，k表示信表示信息位息位。分组码的一个码字可以看作一个分组码的一个码字可以看作一个n重矢量，所以可以用重矢量，所以可以用矢量空间矢量空间来分析和理解分组码。来分析和理解分组码。2021-11-2930线性（矢量）空间

25、的概念线性（矢量）空间的概念F表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，F代表二元域代表二元域0,1。设。设n重有序元素的集合重有序元素的集合V= Vi , n若满足条件：若满足条件：nV中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；nV中矢量元素与数域中矢量元素与数域F元素的标乘封闭在元素的标乘封闭在V中；中；n分配律、结合律成立，分配律、结合律成立， 则称集合则称集合V是数域是数域F上的上的n维维矢量空间矢量空间，或称，或称n维维线线性空间性空间，n维矢量又称维矢量又称n重重(n-tuples)。（关于（关于群，环，域群，环，域的概念）的概念

26、）2021-11-2931矢量的运算规则矢量的运算规则0121012100112211012100112(,.,)(,.,), (1)(,.,) (2)(,.,) (3)(,iiiiinjjjjjnijijijijinjniiiiinijijijiVvvvvVvvvvaFVVvvvvvvvvaVavavavavVVvvvvvv设和标量矢量加标量乘矢量矢量乘矢量2111211221212112212,.,) (4),.,. ,.,., .0,.,jinjnikkiiKiiiiivvFV VVVVaVa VaVVV VVa aaaVa VaVV VV线性相关与线性无关：对于域 上的若干矢量及若，则

27、称是的线性组合。如果存在一组不全为零的使得，则称线性相关。如果不存在一组不全12112212,., .0,.,iiiia aaaVa VaVV VV为零的使得，则称线性无关。2021-11-2932线性空间的基底线性空间的基底空间的基底。为这个线性性空间。称这组矢量的集合就构成了一个线则这些矢量的线性组合的矢量如果存在一组线性无关nnVVVVVV,.,.,2121然基底。，则把这组基底称为自，其余的分量都为分量为且每个元素中只有一个是线性空间的基底，并如果矢量01,.,21nVVV自然基底自然基底子空间子空间的子空间。是，则称也能构成一个矢量空间的一个元素子集若矢量空间VVVVss2021-1

28、1-2933 如在二元域如在二元域GF(2)上上n以（以（100）为基底可张成）为基底可张成一维三重一维三重子空间子空间V1，含，含21 =2 个元素，即个元素，即n以以(010)(001)为基底可张成为基底可张成二维三重二维三重子空间子空间V2，含含 22 =4个元素，即个元素，即n以以(100)(010)(001)为基底可张成为基底可张成三维三重三维三重空间空间V,含含 23 =8个元素，个元素，V1和和V2都是都是V的子空间。的子空间。1(000),(100)V2(000),(001),(010),(011)V“重数重数”：构成矢量的有序元素的个数；：构成矢量的有序元素的个数；“维数维数

29、”：张成矢量空间基底的个数；：张成矢量空间基底的个数；维数不可能大于重数，而当维数小于重数时说明这是个子空间。维数不可能大于重数，而当维数小于重数时说明这是个子空间。2021-11-2934矢量正交矢量正交正交。和则称，即如果两个矢量的点积为2121, 00VVVV矢量空间正交矢量空间正交矢量空间正交。这两个任意元素都正交，则称如果两个矢量空间中的对偶空间对偶空间是对偶空间。、正交，则称、的两个子空间，并且是空间、如果212121VVVVVVV2021-11-2935码空间码空间 消息消息k长长 (n , k) 码字码字n长长 qk 种种 分组编码器分组编码器 qn种种 k维维k重矢量重矢量

30、n维维n重矢量重矢量 通常通常qn qk，分组编码的任务是要在，分组编码的任务是要在n维维n重重矢量空间的矢量空间的qn种可能组合中选择其中的种可能组合中选择其中的qk个构成个构成一个一个码空间码空间，其元素就是许用码的，其元素就是许用码的码集码集。 2021-11-2936分组编码的任务分组编码的任务 n选择一个选择一个维维n重子空间重子空间作为码空间。作为码空间。n确定由确定由k维维k重信息空间到重信息空间到维维n重码空间的重码空间的映映射方法射方法。 码空间的不同选择方法，以及信息组与码组码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。的不同映射算法，就构成了

31、不同的分组码。2021-11-29376.1.3 随机编码与信道编码定理随机编码与信道编码定理 如果不考虑编码的具体方法，而是运用概率统计的方法如果不考虑编码的具体方法，而是运用概率统计的方法在特定信道条件下对编码信号的性能作出统计分析，求出差在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上，下限边界，其中最优码所能达到的差错概率上错概率的上，下限边界，其中最优码所能达到的差错概率上界称为随机码界。界称为随机码界。随机编码的含义随机编码的含义机编码。间，则称这种编码为随果随机的选取一个子空种选法，如该子空间的选取有好多重空间的一个子空间。维成的空间为个码字组由所有重空间中的一个元

32、素，维所以码字为码字的长度为个不同的消息。而总共有元符号组成的码组，则个，由编成长度为种符号。其中每个消息有分组码，设消息组对于NNqNNNqMqNNqmmmmKNkkk,),.,(),(1102021-11-2938n在在(N,k)分组编码器中随机选定的码集有分组编码器中随机选定的码集有qNM种种 n第第m个码集个码集(记作记作cm )被随机选中的概率是被随机选中的概率是n设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是Pe(cm)n全部码集的平均差错概率是全部码集的平均差错概率是()( )NMmPqc11( ) ( )( )NMNMqqNMeemmemmmPPPqPcc

33、c随机编码随机编码2021-11-2939随机编码随机编码n必定存在某些码集必定存在某些码集n某些码集某些码集n若若 ，就必然存在一批码集，就必然存在一批码集 即差错概率趋于零的好码一定存在即差错概率趋于零的好码一定存在 11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc( )emePPc( )emePPc0eP ( )0emPc2021-11-2940随机编码随机编码n码集点数码集点数M=qK占占N维矢量空间总点数维矢量空间总点数qN的比例是的比例是 F =qK / qN = q-(N-K) n当当K和和N的差值拉大即冗余的空间点数增加时，平的差值拉大即冗余的空间点数增

34、加时，平均而言码字的分布将变得稀疏，码字间的平均距离均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。将变大，平均差错概率将变小。 n当当F0 即即(N-K)时，能否让平均差错概时，能否让平均差错概率率 ？ nGallager在在1965年推导了年推导了 的上边界，并证明这个的上边界，并证明这个上边界是按指数规律收敛的。上边界是按指数规律收敛的。 eP0eP 2021-11-2941错误概率的上界错误概率的上界对于离散无记忆信道（对于离散无记忆信道（DMC）。错误平均）。错误平均概率的上界为：概率的上界为：exp( )erPNE RnE(R)为为可靠性函数可靠性函数，也叫

35、误差指数，也叫误差指数 n码率码率：R =( lbM) / N nM是可能的信息组合数，是可能的信息组合数，M=qKnN是每码字的码元数，是每码字的码元数，nR表示每码元携带的信息量，单位是每符号比特表示每码元携带的信息量，单位是每符号比特（bit / symbol）n 是全部码集的平均差错概率是全部码集的平均差错概率eP2021-11-2942可靠性函数可靠性函数Er( R )的曲线的曲线可靠性函数可靠性函数Er( R )与信息传输率与信息传输率R的关系曲线如下图，的关系曲线如下图，是一条下凹的函数曲线。是一条下凹的函数曲线。nR在在0,R0区间时区间时E(R) R曲线是斜率为曲线是斜率为-

36、1（-45 ）的直线，的直线，E(R)反反比于比于R；而当而当R=C时时E(R)=0即可即可靠性为零。靠性为零。 E(R) C 0 R0 -45 R E(R)和和R的关系曲线的关系曲线2021-11-2943n正定理正定理：只要传信率：只要传信率R小于信道容量小于信道容量C，总存在一种信，总存在一种信道码（及解码器），可以以所要求的任意小的差错概道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。率实现可靠的通信。n逆定理逆定理：信道容量：信道容量C是可靠通信系统传信率是可靠通信系统传信率R的上边界，的上边界，如果如果R C，就不可能有任何一种编码能使差错概率任，就不可能有任何一种

37、编码能使差错概率任意小。意小。 n上述两定理统称为有扰或噪声信道的信道编码定理上述两定理统称为有扰或噪声信道的信道编码定理信道编码定理信道编码定理2021-11-29446.2 纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法6.2.1 纠错编码的基本原理纠错编码的基本原理6.2.2 译码方法译码方法-最优译码最优译码 和最大似然译码和最大似然译码2021-11-29456.2.1 纠错编码的基本原理纠错编码的基本原理一、从编码定理出发讨论纠错码的基本原理一、从编码定理出发讨论纠错码的基本原理二、从冗余度和噪声均化讨论纠错码的基本原理二、从冗余度和噪声均化讨论纠错码的基本原理202

38、1-11-2946增大增大Er( R )的途径的途径 Er( R ) R O R1R2 C1C2C2C1R1R2一、从编码定理出发讨论纠错码的基本原理：一、从编码定理出发讨论纠错码的基本原理：)(RNEereP从上可以看出：要减小从上可以看出：要减小 Pe： （1）增大）增大N; （2）增大）增大Er( R )；2021-11-29471 增大信道容量增大信道容量C（1）扩展带宽。）扩展带宽。（2）加大功率。）加大功率。（3）减小噪声功率。）减小噪声功率。2 减小码率减小码率R(=KlbQ /N)（1）Q,N不变，减小不变，减小K,表示降低信息传输速率。表示降低信息传输速率。（2） Q,K不变

39、，增大不变，增大N,表示提高符号速率。表示提高符号速率。（3） N，K不变，减小不变，减小Q,表示减小信道的输入表示减小信道的输入 输出符号集。输出符号集。 3 增大码长增大码长N C,R,K/N不变不变一、从编码定理出发讨论纠错码的基本原理：一、从编码定理出发讨论纠错码的基本原理：2021-11-2948二、从冗余度和噪声均化讨论纠错码的基本原理：二、从冗余度和噪声均化讨论纠错码的基本原理：冗余度：冗余度：就是在信息流中插入冗余比特，插入的冗余比特与就是在信息流中插入冗余比特，插入的冗余比特与 信息比特存在着特定的相关性。这样如果在传输过信息比特存在着特定的相关性。这样如果在传输过 程中有个

40、别信息比特受损，也可以从冗余比特中恢程中有个别信息比特受损，也可以从冗余比特中恢 复或发现受损比特。从而保证了信息传输的可靠性。复或发现受损比特。从而保证了信息传输的可靠性。例如，假定信息为两位共有四种组合（例如，假定信息为两位共有四种组合（00，01，11，10）如果不加冗余位，直接传输，则接收端无法发现传输过程中如果不加冗余位，直接传输，则接收端无法发现传输过程中的错误。但是如果添加一位冗余位，并且有下面的对应关系的错误。但是如果添加一位冗余位，并且有下面的对应关系000000101110101111100000010100111001011101112021-11-2949n 传输传输冗

41、余比特冗余比特 必然要动用必然要动用冗余的资源冗余的资源。n时间时间：比如一个比特重复发几次：比如一个比特重复发几次,或一段消息重复发几遍或一段消息重复发几遍,或或根据收端的反馈重发受损信息组。根据收端的反馈重发受损信息组。n频带频带：插入冗余比特后传输效率下降：插入冗余比特后传输效率下降,若要保持有用信息的若要保持有用信息的速率不变速率不变,方法之一是增大符号传递速率方法之一是增大符号传递速率(波特率波特率),结果就占结果就占用了更大的带宽用了更大的带宽。n功率功率：采用多进制符号：采用多进制符号,用用8进制进制ASK符号代替符号代替4进制进制ASK符符号来传送号来传送2比特信息比特信息,可

42、腾出位置另传可腾出位置另传1冗余比特。冗余比特。8进制进制ASK符号的平均功率肯定比符号的平均功率肯定比4进制时要大（误码率相同时）进制时要大（误码率相同时）,这就是动用冗余的功率资源来传输冗余比特。这就是动用冗余的功率资源来传输冗余比特。n设备复杂度设备复杂度：加大码长：加大码长,采用网格编码调制采用网格编码调制,是在功率、带宽是在功率、带宽受限信道中实施纠错编码的有效方法受限信道中实施纠错编码的有效方法,代价是算法复杂度的代价是算法复杂度的提高提高,需动用设备资源。需动用设备资源。二、从冗余度和噪声均化讨论纠错码的基本原理：二、从冗余度和噪声均化讨论纠错码的基本原理：2021-11-295

43、0噪声均匀化：就是让差错随机化，以便符合编码定理的条件从噪声均匀化：就是让差错随机化，以便符合编码定理的条件从 而得到符合编码定理结果。其基本思想是设法将而得到符合编码定理结果。其基本思想是设法将 危害较大的，较为集中的噪声干扰分摊开来，使危害较大的，较为集中的噪声干扰分摊开来，使 不可恢复的信息损伤最小。不可恢复的信息损伤最小。（1）增加码长。）增加码长。 例如：设例如：设BSC信道的误码率为信道的误码率为Pe=0.01,编码后的纠错能力为编码后的纠错能力为10%，当码长当码长N=10时，码字中多于时，码字中多于1位误码就会产生译码差错，差错概率位误码就会产生译码差错，差错概率为：为： 当码

44、长变为当码长变为40时，则码字中多于时，则码字中多于4个错误时产生差错，其差错概个错误时产生差错，其差错概率为率为（2）卷积。）卷积。（3）交织。）交织。11031001(1)4.27 10mmmeemPC PP 44054001(1)4.92 10mmmeemPC PP 二、从冗余度和噪声均化讨论纠错码的基本原理：二、从冗余度和噪声均化讨论纠错码的基本原理：2021-11-295176543211413 1211 10982120 1918 1716 152827 2625 2423 223534 3332 3130 2976543211413 1211 10982120 1918 1716

45、 152827 2625 2423 223534 3332 3130 29出出入入入入出出222921815交错器交错器去交错器去交错器交错器工作原理图交错器工作原理图2021-11-29526.2.2 译码方法译码方法-最优译码和最大似然译码最优译码和最大似然译码译码器的任务是从受损的信息序列中尽可能正确译码器的任务是从受损的信息序列中尽可能正确的恢复出原始信息。的恢复出原始信息。信息组码字00000000000010011101010010011101101110101001001110101101001111011010011111110100发送码字发送码字接收码字接收码字001110

46、100001012021-11-2953译码算法的已知条件是要求已知：译码算法的已知条件是要求已知：（1）实际接收到的码字序列）实际接收到的码字序列r,r=(r1,r2,.rN)。（2）发送端所采用的编码算法和该算法产生的码集）发送端所采用的编码算法和该算法产生的码集XN,满足满足。NiNiiiXcccc),.,(21（3）信道模型及信道参数。）信道模型及信道参数。消息组消息组m),.,(21kmmm(N,K)编码器编码器NiXC 码字),.,(21iNiiccc信道信道r接收码),.,(21Nrrr最佳最佳/最大最大似然译码似然译码ic码字估值),.,(21iNiiccc消息消息还原还原),

47、.,(21kmmmim消息2021-11-2954XNUUYf1fXFYXY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN2021-11-2955XY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN*:(),1,2,.,jjF BAF baAjs2021-11-2956XY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN*(),1,2,.,jjF baAjs *(|)()|jjjjP XaYbP F bb ()|1()|)|(jjjjjP XF bYbP FPbebb 11()() 1()(|)jssejjjjjjPP bP bbFPPbeb2

48、021-11-2957XY12 ,rAa aa12 ,sBb bbX12 ,rAa aaN*(),1,2,.,jjF baAjs11()() 1()(|)jssejjjjjjPP bP bbFPPbeb111(),1()|()ssejjjjjjjPP F bbP F bP bF b *,( ,)( ) (|)eijijiY XaY XaPP a bP a P ba*1,111|()(|)sejjjijY XaPP bF bP barr 2021-11-29580.80.90.20.12b1b1a2a3113322( ):()F baFF ba1()0.4P a1111121( ):()F ba

49、FF ba4124421( ):()F baFF ba2122222( ):()F baFF ba0.40.6XP1122|0.80.20.10.9Y XaPbba11220.320.080.060.54XYabbaP1111121()1(),1(,)(,)1 (0.320.08)0.6sejjjP FP F bbP a bP a b 2221221()1(),1(,)(,)1 (0.060.54)0.4sejjjP FP F bbP a bP a b 33112210.()1(),1(,)(,)1 (0.320.514)4sejjjP FP F bbP a bP a b 44211210.()1(),1(,)(,)1 (0.080.086)6sejjjP FP F bbP