信息论与编码-第6章-信道编码

第1章：概述第2章：信源熵第3章：信道容量第4章：信息率失真函数第5章：信源编码第6章：信道编码第7章：密码体制的安全性测度§6.1信道编码的概念§6.2线形分组码§6.3循环码§6.4卷积码§6.1.1信道编码的作用和分类§6.1.2：编码信道§6.1.3：检错和纠错原理§6.1.4：检错和纠错方式和能力信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号－－线路编码如何避免少量差错信号对信息内容的影响－－纠错编码广义信道编码=特定信道上传输信息而进行的传输信号或信号格式的设计与实现描述编码用于对特定数据信号的描述约束编码用于对特定信号特性的约束扩频编码用于扩展信号频谱为近似白噪声谱并满足某些相关特性纠错编码用于检测与纠正信号传输过程中因噪声干扰导致的差错1234§6.1.1：信道编码的作用和分类§6.1.2编码信道§6.1.3：检错和纠错原理§6.1.4：检错和纠错方式和能力011011,,,,0,1,,,,0,1ninicccccrrrrr消息crmˆ信道编码编码信道信道译码m码字接收向量消息编码信道模型当码字C和接受向量R均由二元序列表时，称编码信道为二进制信道C=(c0,c1,…cn-1)如果对于任意的n都有：则称此二进制信道为无记忆二进制信道。p(0/1)=p(1/0)=p0则称此信道为无记忆二进制对称信道BSC10)/()/(niiicrpcrpBSC转移概率BSC编码信道mod2(1),(0)1bbrcepeppepBSC输入输出关系等效为差错图案：随机序列或，ie110,,,neeeei第i位上的一个随机错误：1ie长的突发错误：第至第位之间有很多错误1ijiijj对于一个BSC信道总有转移概率1/2，比特传输中发生差错数目越少，概率越大，即bpnnbtnbtbnbbnbpppppp1111从而总认为发生差错的图案是差错数目较少的图案二元软判决信道用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出信道干扰z为零均值正态分布的随机变量，噪声干扰功率为均方差，z的概率分布为。对于BPSK调制，二元输入符号为二元符号取值为+1或-12)(zpzcr2221(),2zpzez§6.1.1：信道编码的作用和分类§6.1.2：编码信道§6.1.3检错和纠错原理§6.1.4：检错和纠错方式和能力检纠错是根据信道输出序列自身判断是否可能是发送的，或纠正导致不等于的错误。冗余编码：码字的长度一定大于消息的长度rrcrccnm110,,,kmmmm110,,,ncccc纠错编码编码码率：每个码字的序列符号（或码元）平均传送的消息比特数RnkR/偶（或奇）校验方法：实现检纠错目的的一个基本方法。一个偶校验位是对消息使得如下校验方程成立的二进制符号，即pm2mod01210pmmmmk2mod110kmmmp一个偶校验码码字pmmmmck,,,,,1210c一个码率为的偶校验码，所有可能的的全体)1/(kkkk,1Cc校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错m0+m1+m2+…+mk－1+p=0（mod2）称c=(m0,m1,m2…mk-1,p)为一个偶校验字确定校验位P的编码方程为：P=m0+m1+…+mk-1编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部按某种校验方程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字和其码率分别为ctstsststssttppppmmpmmc,1,0,,11,10,1,01,00,0,,,,,,,,,sttstsststR11112mod1,,1,02,mod1,,1,02,mod10,10,,10,,10,,tjjssititssijijstjjitimmptjmpsimp重复消息位：实现检纠错目的第二个基本方法一个重复码是一个码率为的码，仅有两个码字和，传送1比特（）消息。nn/10c1c1k111,00010cc重复码可以检测出任意小于个差错的错误图案，纠正任意小于个差错的错误图案。nn/2n纠1位差错的3重复码等重码或定比码：实现检纠错的第三个方法。设计码字重量恒为常数，即cwmcwcC例如一种用于表示0至9数字的5中取3等重码如下表所示，其码率R为22log15log0.6635nmRn5中取3等重码1234567890010111100110110110100011110101111000111010011011015中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错§6.1.1：信道编码的作用和分类§6.1.2：编码信道§6.1.3：检错和纠错原理§6.1.4检错和纠错方式和能力纠错码的应用方式：前向纠错方式（FEC），自动请求重发（ARQ）方式，混合纠错（HEC）方式以及信息反馈（IRQ方式）FEC与ARQ纠错应用方式常用汉明距离来描述检纠差错的数目，对于两n长向量u、v，汉明距离为：最小汉明距离（最小码距d）：任意两码字之间的汉明距离的最小值mind',min'minccddcc1,1ni,iiduvuv定理对一个最小距离为纠错码，如下三个结论仅有其中任意一个结论成立：mind（1）可以检测出任意小于等于个差错；1mindl（2）可以纠正任意小于等于个差错；21mindt（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足ltdtl1min最小码距与检纠错能力差错概率：通信作为一个统计过程时，纠检错能力的统计特性。FEC方式纠错码的码字差错概率wepcwerccpcppˆ)(：发送码字的先验概率cpc：码字数，对于充分随机的消息源MMcp/1对BSC信道crdbbnbcrdbcrdnbpppppcrp,,,111/最大化等价于最小化，最小差错概率译码等价为使接收向量与输出码字距离最小的最小距离译码，即crp/crd,crdcrdciicˆ,,min:ˆ信息比特信噪比：传输一个比特信息所需的最小信噪比obNE/比特差错概率（又称误码率）与信噪比的关系如下图所示，采用纠错码后，达到同样比特差错概率实际需要的信噪比减小量称为编码增益。bepobNE/编码增益§6.2线性码§6.2.1线性分组码的描述§6.2.2线性分组码的译码§6.2.3码例与码的重构§6.2.1线性分组码的描述§6.2.2线性分组码的译码§6.2.3码例与码的重构一个（n,k）线形分组码C是称为码字c的n维向量的集合C={c|c=mG}其中m为任意的k维向量并称为消息向量。G是k行n行列秩为k（n≥k）的矩阵并称为生成矩阵，000,11,01,1nkknggGgg对于二元编码，和是二元向量，是一个二元矩阵，，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算。cmG1,0ijg表6.2.1模二加/乘法表例6.2.13重复码是一个（3，1）线性分组码111G0000210,,111,,mmmmccc例6.2.2（4，3）偶校验码是一个（4，3）线性分组码110010101001G2102102103210,,,110010101001,,,,,mmmmmmmmmcccccwcdminmin当生成矩阵给定时线性分组码有如下性质：(1)零向量一定是一个码字，称为零码字；(2)任意两码字的和仍是一个码字；(3)任意码字是的行向量的线性组合；（4）线性分组码的最小距离等于最小非零码字重量。cG110,,,kgggG0,,0,0r由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为0来判断传输是否可能有错，那么必有一个矩阵满足HTcH显然的每一列或的每一行确定了一个可能的分组码的校验方程，的线性不相关行数最少要等于该码的所有可能的校验方程数，称这样的矩阵为线性分组码的一致校验矩阵。THHrnrHkn,H1,10,11,00,0nrrnhhhhH由的每一行都是一个码字有GrkTGH0knr其中G是k行、n列；H是r行、n列。由线性空间的理论，当H的行秩为r时，H作为一个(n,r)线性分组码的生成矩阵所生成的码是与G对应空间正交的r维线性子空间，称为(n,k)线性分组码的对偶码或对偶空间，并且有如下的维数关系成立定理：任何满足下式的n维向量a均是一（n,k）线性分组码的码字其中满足公式的H矩阵形式不唯一，但一个线性码的对偶码是惟一的。TaH系统码：生成矩阵具有如下形式GrkksQIGG在码字集合不变的情况下，任何一个线性分组码都可以一对一的去对应一个系统码。对于系统码相应的一致校验矩阵sH],[rTrksIQHH注意与仍然满足。GsH0TSGH以线性分组码的一致校验矩阵为生成矩阵产生的线性分组码称为原线性分组码的对偶码。例6.2.3一个（5，3）线性分组码的ssHGG,,010111101001101G1011101110,,,111001101010001IQHQIGTss其中到的行初等变换过程为（表示第i行）GsGiR31123313331311233,,,,RRRRRRRRRRRRRRRRR或（5，3）线性分组码码例消息mG生成码字Gs生成码字对偶码码字0000010100111001011101110000011010010111000110110011001110100111000000011101011011001000110110110101110100000111010111010011ssHGG,,由一致校验矩阵可以比较容易确定线性分组码的最小码距mind定理线性分组码的最小码距为，当且仅当其一致校验矩阵H中任意列线性无关，某列线性相关。ddmin1dd该定理实际给出了计算线性分组码最小码距的一种方法。§6.2.1线性分组码的描述§6.2.2线性分组码的译码§6.2.3码例与码的重构译码的概念检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即。sry,r=c-e=c+e纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。cˆcyˆ纠错译码的译码失败状态：译码器不能输出一个确切的码字，通常此时的输出y与检错译码输出相同。cˆ定义：(n,k）线形分组码的伴随式是一个r(r=n-k)维向量s0121eeeeenn110,,,rTsssrHsTTeHHces)(，则传输中一定有错误发生s，则传输中要么无差错发生，要么差错图案恰好为一个码字。s码组在传输中可能由于干扰而出错，例如发送码组为c，接收到的码组却是r，它们都是n位码的行向量，我们就定义e＝r－c为错码向量，错误图案。其中iiiiicrcre10定理可纠t错的q元线性分组码满足0(1)triinqqi当q=2，即二元码时：tirin02当取等号时称为完备码。伴随式纠错译码的通用译码方法（1）按最可能出现的个差错图案e，计算相应的伴随式s，并构造伴随式—差错图案表