信息论与编码第二讲精选PPT.ppt

信息论与编码第二讲第1页，此课件共84页哦主要内容主要内容1234信道编码定理信道编码定理信道编码定理信道编码定理线性分组码的编译码线性分组码的编译码线性分组码的编译码线性分组码的编译码码的检、纠错能力码的检、纠错能力码的检、纠错能力码的检、纠错能力信道编码概念信道编码概念信道编码概念信道编码概念第2页，此课件共84页哦一、信道编码概念一、信道编码概念第3页，此课件共84页哦 1.1 通信系统模型通信系统模型第4页，此课件共84页哦信源编码器信源编码器 把消息转换成为二进制形式的信息序列，并且为了把消息转换成为二进制形式的信息序列，并且为了使传输有效，去掉了与传输信息无关的多余度。使传输有效，去掉了与传输信息无关的多余度。纠错编码器纠错编码器 为了抗击传输过程中各种干扰，要人为地增加一些多为了抗击传输过程中各种干扰，要人为地增加一些多余度，使其具有自动检错或纠错能力。余度，使其具有自动检错或纠错能力。纠错码译码器纠错码译码器 由于信道干扰，该信息序列中可能有错误，经过纠由于信道干扰，该信息序列中可能有错误，经过纠错码译码器，对错误进行纠正。错码译码器，对错误进行纠正。第5页，此课件共84页哦 信信源源指指原原来来的的信信源源和和信信源源编编码码器器，其其输输出出是是二二(多多)进进制制信信息息序序列。列。信信道道包包括括发发射射机机、实实际际信信道道（或或称称传传输输媒媒质质）和和接接收收机机在在内内的的广广义义信信道道，它它的的输输入入是是二二（多多）进进制制数数字字序序列列，输输出出是是二二（多多）进进制制数字序列。数字序列。1.2 编码信道编码信道第6页，此课件共84页哦第7页，此课件共84页哦二、信道编码定理二、信道编码定理第8页，此课件共84页哦2.1 信道编码理论信道编码理论 每每个个信信道道具具有有确确定定的的信信道道容容量量C，对对任任何何小小于于C的的码码率率Rs，存存在在有有速速率率为为Rs、码码长长为为n的的编编码码方方法法，若若用用最最大大似似然然译译码码，则则随随着着码码长长的的n增增加加其其译译码码错错误误概概率率Pe可可任任意小，意小，即即：第9页，此课件共84页哦式中，式中，E(RS)为正实函数，称为误差指数，它与为正实函数，称为误差指数，它与RS、C的关的关系如下图所示。图中，系如下图所示。图中，C1、C2为信道容量，且为信道容量，且C1C2。第10页，此课件共84页哦2.2 信道编码基本思想信道编码基本思想 第11页，此课件共84页哦第12页，此课件共84页哦第13页，此课件共84页哦第14页，此课件共84页哦第15页，此课件共84页哦2.3译码平均错误概率译码平均错误概率 第16页，此课件共84页哦第17页，此课件共84页哦第18页，此课件共84页哦2.4 译码规则译码规则 第19页，此课件共84页哦2.4.1 最大后验概率译码准则最大后验概率译码准则第20页，此课件共84页哦例例 题题第21页，此课件共84页哦第22页，此课件共84页哦2.4.2 极大似然译码准则极大似然译码准则第23页，此课件共84页哦例例 题题第24页，此课件共84页哦第25页，此课件共84页哦两种译码准则比较两种译码准则比较第26页，此课件共84页哦2.4.3 最小码距译码准则最小码距译码准则第27页，此课件共84页哦第28页，此课件共84页哦最小码距最小码距第29页，此课件共84页哦最小码距对错误概率的影响最小码距对错误概率的影响第30页，此课件共84页哦最小距离译码准则最小距离译码准则第31页，此课件共84页哦最小距离准则与最大似然准则关系最小距离准则与最大似然准则关系第32页，此课件共84页哦例：重复码例：重复码v早期的检错码为重复码。该码用早期的检错码为重复码。该码用000000代表信息代表信息“0 0”，用，用111111代表信息代表信息“1 1”。v显然所增加的显然所增加的2 2个码元并不增多信息，是多余的个码元并不增多信息，是多余的,使传信率降低。此外，除使传信率降低。此外，除去传送信息的去传送信息的000000和和111111这这2 2种组合外种组合外,还有还有001,010,011,100,101,110001,010,011,100,101,110等等6 6种种组合没采用。组合没采用。v当信道上信噪比足够大时当信道上信噪比足够大时,可认为可认为000000和和111111中产生的错误一般不会多于一中产生的错误一般不会多于一个码元。个码元。v如接收到如接收到001,010,100,001,010,100,在接收端怎么译码呢？根据最小码距译码准则，可在接收端怎么译码呢？根据最小码距译码准则，可判定实际上是判定实际上是000,000,即信息为即信息为0 0；同理；同理,如接收到如接收到011,110,101,011,110,101,在接收端也可在接收端也可判定判定111,111,即信息为即信息为1 1。v 可见可见,多余码元可检出并纠正一个错误，这样就提高了传信的可靠性。多余码元可检出并纠正一个错误，这样就提高了传信的可靠性。第33页，此课件共84页哦三、线性分组码三、线性分组码第34页，此课件共84页哦第35页，此课件共84页哦m2m1m0C5C4C3C0C1C23.1 生成矩阵生成矩阵第36页，此课件共84页哦m2 m1 m0100111010110001011=c5 c4 c3 c2 c1 c0 m G =C100111010110001011张成码空间的三个基，张成码空间的三个基，本身也是码字。本身也是码字。第37页，此课件共84页哦第38页，此课件共84页哦信息空间到码空间的线性映射信息空间到码空间的线性映射信息组信息组(m2 m1 m0)码字码字(c5 c4 c3 c2 c1c0)000000000001001011010010110011011101100100111101101100110110001111 111010 k维维k重重k维维n重重 信息空间信息空间 码字空间码字空间第39页，此课件共84页哦 gk-1G=g1 g0c=m G=mk-1,m1 m0 gk-1 g1 g0 T =mk-1 gk-1+m1 g1+m0 g0 第40页，此课件共84页哦 生成矩阵生成矩阵G 是由是由k个行矢量组成的，其中的每个个行矢量组成的，其中的每个行矢量行矢量g i既是一个基底，也是一个码字。既是一个基底，也是一个码字。任何码字都是生成矩阵任何码字都是生成矩阵G的的k个行矢量的线性组合。个行矢量的线性组合。只要这只要这k个行矢量线性无关，就可以作为个行矢量线性无关，就可以作为k个基个基底张成一个底张成一个k维维n重空间，它是重空间，它是n维维n重空间的一个子重空间的一个子空间，子空间的所有空间，子空间的所有2k个矢量构成个矢量构成码集码集C。第41页，此课件共84页哦不同的生成矩阵产生不同的码，生成矩阵的特点决不同的生成矩阵产生不同的码，生成矩阵的特点决定了码的特点。定了码的特点。由于构成同一空间的基底不是唯一的，所以不同的由于构成同一空间的基底不是唯一的，所以不同的基底或生成矩阵可能生成同一码集。基底或生成矩阵可能生成同一码集。码集相同，编码不一定相同，因为编码涉及码集和映码集相同，编码不一定相同，因为编码涉及码集和映射两个因素，码集一样而映射方法不同不能说是同样射两个因素，码集一样而映射方法不同不能说是同样的编码。的编码。第42页，此课件共84页哦 由于基底不是唯一的，因此允许将基底线性组合后挑由于基底不是唯一的，因此允许将基底线性组合后挑出其中出其中k个线性无关的矢量作为新的基底，依然可以张成个线性无关的矢量作为新的基底，依然可以张成同一个码空间。同一个码空间。对应到生成矩阵，等效于允许对应到生成矩阵，等效于允许通过行运算（行交换、通过行运算（行交换、行的线性组合）改变生成矩阵的行而不改变码集，只要保行的线性组合）改变生成矩阵的行而不改变码集，只要保证矩阵的秩仍是证矩阵的秩仍是k（k行线性无关行线性无关)。所以，任何生成矩阵可通过行运算转化成所以，任何生成矩阵可通过行运算转化成“系统码系统码”形式形式。第43页，此课件共84页哦3.2 系统码 把信息组原封不动搬到码字前把信息组原封不动搬到码字前k位的位的(n,k)码，码，其码字具有如下形式：其码字具有如下形式：c=(cn-1,cn-k,cn-k-1,c0)=(mk-1,m1,m0,cn-k-1,c0)其生成矩阵具有如下形式：其生成矩阵具有如下形式：G=Ik P =第44页，此课件共84页哦3.3 校验矩阵校验矩阵 对对于于kn矩矩阵阵G，存存在在一一个个(n-k)n矩矩阵阵H，使使得得G的的行行空空间间和和H正正交。交。基基底底数数k的的码码空空间间C是是n维维n重重空空间间的的子子空空间间，若若能能找找出出全全部部n个个基基底底的的另另外外n-k个个基基底底，也也就就找找到到了了对对偶偶空空间间D。将将D空空间间的的n-k个个基基底底排排列列起起来来可可构构成成一一个个(n-k)n矩矩阵阵，称称为为是是码码空空间间C的的校校验验矩矩阵阵H，它与所有码字正交。，它与所有码字正交。既既然然用用k个个基基底底能能产产生生一一个个(n,k)线线性性码码，那那么么也也能能用用其其余余n-k个个基基底底产产生生一一个个(n,n-k)线线性性码码，称称（n,n-k）线线性性码码是是(n,k)线线性性码码的的对对偶偶码码。C和和D的的对对偶偶是是相相互互的的，G是是C的的生生成成矩矩阵阵又又是是D的的校校验验矩矩阵阵，而而H是是D的生成矩阵又是的生成矩阵又是C的校验矩阵。的校验矩阵。第45页，此课件共84页哦 n维维n重空间重空间R k维维k重重 k维维n重重 n-k维维n重重 信息组信息组 码空间码空间C 对偶空间对偶空间D 空间空间m G H 图图3-1 码空间与映射码空间与映射第46页，此课件共84页哦 c是是G空间的一个码字，那么由正交性得到：空间的一个码字，那么由正交性得到：c HT=00代表零阵，它是代表零阵，它是1nn(n-k)=1(n-k)矢量。矢量。上上式式可可以以用用来来检检验验一一个个n重重矢矢量量是是否否为为码码字字：若若等等式式成成立立，该该n重是码字，否则不是码字。重是码字，否则不是码字。由于生成矩阵的每行都是一个码字，因此有：由于生成矩阵的每行都是一个码字，因此有：GHT=0这里这里0代表一个代表一个 knn(n-k)=k(n-k)的零矩阵。的零矩阵。第47页，此课件共84页哦对于系统码，其校验矩阵也是规则的，必为：对于系统码，其校验矩阵也是规则的，必为：HPT In-k 因为：因为：GHT=IkP PTIn-k T =Ik P+P In-k =P+P =0 第48页，此课件共84页哦例例3.1 考虑一个考虑一个(7，4)码，其生成矩阵是：码，其生成矩阵是：G=I4 P 对于信息组对于信息组m=(1 0 1 1),编出的码字是什么？编出的码字是什么？画一个（画一个（7，4）分组码编码器原理图。）分组码编码器原理图。若接收到一个若接收到一个7位码位码r=(1 0 0 1 1 0 1),检验它是否码字？检验它是否码字？第49页，此课件共84页哦3.3 伴随式与译码伴随式与译码 线性分组码线性分组码 C=(cn-1,c1,c0)，接收码接收码 R=(rn-1,r1,r0)，差错图案差错图案:E=(e n1,，e 1,e0)=R C 对于二进制码，有对于二进制码，有E=RC 及及R=CE RHT=(CE)HT=C HTE HT=0E HT=EHT 如收码无误，必有如收码无误，必有R=C 即即RHT=0,如信道差错如信道差错E 0，必有，必有RHT=EHT 0。定义定义伴随式伴随式S S：S=(s n-k-1,，s1,s0)=RHT=EHT S仅与仅与E有关，而与有关，而与C无关。无关。第50页，此课件共84页哦从物理意义看，伴随式从物理意义看，伴随式S并不反映发送的码字是什么，而只反映信道并不反映发送的码字是什么，而只反映信道对码字造成了怎样的干扰。对码字造成了怎样的干扰。伴随式伴随式S是一个是一个(n-k)重矢量，只有重矢量，只有2n-k种可能的组合；而差错图案种可能的组合；而差错图案E是是n重矢量，共有重矢量，共有2n个可能的组合。因此，同一伴随式可能对个可能的组合。因此，同一伴随式可能对应若干个不同的差错图案。应若干个不同的差错图案。在接收端我们并不知道发码在接收端我们并不知道发码C究竟是什么，但可以知道究竟是什么，但可以知道HT和接收和接收码是码是R什么，从而算出什么，从而算出S是什么。是什么。译码最重要的任务：从伴随式译码最重要的任务：从伴随式S找出找出C的估值。的估值。第51页，此课件共84页哦 一般的译码思路一般的译码思路 RHT=S E C=RE E m 编码 C R S=no 计算 输出 mG RH T=0？E R+E yes 输出R 图3-3 译码过程框图 第52页，此课件共84页哦S=(s n-k-1,，s1,s0)=E HT=(e n1,e 1,e0)(3-18)展开成线性方程组形式，为：展开成线性方程组形式，为：sn-k-1=en-1h(n-k-1)(n-1)+e1 h(n-k-1)1+e0 h(n-k-1)0 s1 =en-1h1(n-1)+e1 h11+e0 h10s0 =en-1h0(n-1)+e1 h01+e0 h00方程组中有方程组中有n个未知数个未知数en1,e1,e0，却只有，却只有n-k个方程。个方程。第53页，此课件共84页哦 在二元域中，少一个方程导致两个解，少两个方程在二元域中，少一个方程导致两个解，少两个方程导致四个解导致四个解少少n-(n-k)=k个方程导致有个方程导致有2k个解。个解。在在E的的2k个解中选一，最合理的方法是个解中选一，最合理的方法是概率译码概率译码，它把所有，它把所有2k个解个解的重量的重量(差错图案差错图案E中中1的个数的个数)作比较，选择其中最轻者作作比较，选择其中最轻者作为为E的估值。的估值。该算法的理论根据该算法的理论根据就是最小汉明距离译码。就是最小汉明距离译码。第54页，此课件共84页哦3.4 3.4 标准阵列标准阵列第55页，此课件共84页哦某一个某一个(5,2)系统线性码的生成矩阵：系统线性码的生成矩阵：G=码集：码集：00000,10111,01101,11010S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第56页，此课件共84页哦E2n-k+C2kE2n-k+CiE2n-k-1+C1E2n-k+C0=E2n-k Ej+C2k1Ej+CiEj+C1Ej+C0=Ej E1+C2k1E1+CiE1+C1E1+C0=E1E0+C2k1=C2k1E0+Ci=CiE0+C1=C1E0+C0=0+0=0表表3-2 标准阵列译码表标准阵列译码表第57页，此课件共84页哦对于对于(6,3)码的码的8个码矢：个码矢：v1=(0 0 0 0 0 0),v2=(0 0 1 1 1 0),v3=(0 1 0 1 0 1),v4=(1 0 0 0 1 1),v5=(0 1 1 0 1 1),v6=(1 0 1 1 0 1),v7=(1 1 0 1 1 0),v8=(1 1 1 0 0 0)。其标准阵列：其标准阵列：第58页，此课件共84页哦例：某一个(5,2)系统线性码的生成矩阵是G=，设收码是R=(10101),请先构造该码的标准阵列译码表，然后译出发码的估值。分析：H=PT I3 =，由S=(E+C)HT=EHT得：s2 =e4+e3+e2s1 =e4+e1 5个未知数，3个方程s0 =e4+e3+e0 必有4组解令S0=000,并分别令e4e3=00、01、10、11,解得E0的4组解是(00000)(01101)(10111)(11010)，取E0=(00000)再依次令S=001,010,011每次有4组解，取最轻者为“解”。其中有的组最轻解是唯一的，有的却不是，比如伴随式S=(011)的4个解是(00011)、(10100)、(01110)、(11001)，其中(00011)和(10100)并列最小重量，任取其中一个？第59页，此课件共84页哦S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第60页，此课件共84页哦第61页，此课件共84页哦查表译码方法查表译码方法1 计计算算R的伴随式的伴随式S=RHT；2 找出伴随式找出伴随式S等于等于RHT的陪集首的陪集首el；3 码码矢矢v=R+el就是就是发发送送码码矢。矢。第62页，此课件共84页哦例例3.3对对于于(6,3)码码，校，校验验矩矩阵为阵为：S=EHT第63页，此课件共84页哦 如果如果发发送的送的码码矢矢为为v=(111000)，接收的矢量，接收的矢量r=(111001)，怎，怎样样来来译码译码？第64页，此课件共84页哦四、码的纠、检错能力四、码的纠、检错能力第65页，此课件共84页哦4.1 计算最小距离的方法计算最小距离的方法1 直直接接计计算算。含含2k个个码码字字的的码码集集需需计计算算2k(2 k-1)/2个个距距离离后后才才能能找找出出dmin。2 利用利用群码封闭性群码封闭性两码字之和仍是码字两码字之和仍是码字：d(C1,C2)=w(C1 C2)=w(C3)可得可得定理定理3.1:线性分组码的最小距离等于码集中非零码字的最小重量线性分组码的最小距离等于码集中非零码字的最小重量：dmin=min w(Ci)C i C 及及Ci 0于于是是最最小小距距离离问问题题转转化化为为寻寻找找最最轻轻码码字字问问题题，含含2k个个码码字字的的码码集集仅需计算仅需计算2k次。次。第66页，此课件共84页哦3 利用校验矩阵利用校验矩阵H的秩的秩定定理理3.4：(n,k)线线性性分分组组码码最最小小距距离离等等于于dmin的的充充要要条条件件是是校校验验矩矩阵阵H中有（中有（dmin-1)列线性无关。换言之，列线性无关。换言之，dmin=校验矩阵校验矩阵H的秩的秩+1。第67页，此课件共84页哦定理定理3.2:任何最小距离任何最小距离dmin的线性分组码，其检测随机差错的能力为的线性分组码，其检测随机差错的能力为（dmin1）。）。定定理理3.3:任任何何最最小小距距离离等等于于d dminmin的的线线性性分分组组码码，其其纠纠正正随随机机差差错错的的能能力力t t为：为：t=INT 若最小距离为若最小距离为dmin的码同时能检的码同时能检ed个、纠个、纠ec个差错个差错,则则edec dmin1 ec ed。抑制纠错能力才能提高检错能力。抑制纠错能力才能提高检错能力。第68页，此课件共84页哦第69页，此课件共84页哦例：每个分例：每个分组码组码dmin=7，那么怎么来，那么怎么来纠错纠错和和检错检错？（1）纠错纠错 t=3；（2）2重重纠错纠错，并且，并且4重重错误检测错误检测 t=2,D=4；（3）6重重错误检测错误检测 D=6。第70页，此课件共84页哦定定理理3.5：(n,k)线线性性分分组组码码的的最最小小距距离离必必定定小小于于等等于于(n-k+1)即即 dmin (n-k+1)因为因为H是是(n-k)n矩阵，该矩阵的秩最大不会超过矩阵，该矩阵的秩最大不会超过(n-k)，即线性无关的列不会超过即线性无关的列不会超过(n-k)。第71页，此课件共84页哦 4.2 完备码完备码如如果果某某码码的的伴伴随随式式组组合合数数目目恰恰好好和和不不大大于于t个个差差错错的的图图案案数数目目相相等等，相相当当于于在在标标准准阵阵列列中中能能将将所所有有重重量量不不大大于于t的的差差错错图图案案选选作作陪陪集集首首而而没没有有一一个个陪陪集集首首的的重重量量大大于于t，这这时时的的伴伴随随式式就就能能和和可可纠纠差差错错图图案案实实现一一对应，校验位得到最合理的利用。现一一对应，校验位得到最合理的利用。满足方程：满足方程：的二元的二元(n,k)线性分组码称为线性分组码称为完备码完备码。t=1的完备码叫汉明码。的完备码叫汉明码。第72页，此课件共84页哦4.3 汉明码汉明码纠错能力纠错能力t=1的完备码称为的完备码称为汉明码汉明码。汉汉明明码码指指一一类类码码，既既可可以以是是二二进进制制的的，也也可可以以是是非非二进制的。二进制的。二进制汉明码应满足条件：二进制汉明码应满足条件：2n-k=1+n。令令r=n-k，汉明码，汉明码n和和k服从以下关系服从以下关系 码长：码长：n=2r-1 信息位：信息位：k=2r-1-r 最小距离最小距离 d min=3当当r3、4、5、6、7、8时，有以下汉明码：时，有以下汉明码：(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)。第73页，此课件共84页哦 从从n n维维矢矢量量空空间间的的角角度度看看(n,k)完完备备码码，假假定定每每个个码码字字为为中中心心放放置置一一个个半半径径t t的的球球，与与该该码码汉汉明明距距离离小小于于等等于于t t的的所所有有接接收收矢矢量量均均包包含含在在此此球球内内，每每球包含的矢量点数是球包含的矢量点数是 。以码集。以码集2 2k k个码字为中个码字为中心、半径心、半径t t(不相重叠不相重叠)的球共可包含的球共可包含 2 2k k 点。点。由由于于n n重重矢矢量量的的总总数数是是2 2n n个个，包包含含在在2 2 k k个个球球中中的的点点数数不不可可能能多多于于总总点点数数，所所以下列不等式必定成立：以下列不等式必定成立：第74页，此课件共84页哦如果上式等号成立，表示全部如果上式等号成立，表示全部2 2n n个接收矢量等分地落在个接收矢量等分地落在2 2k k个半径个半径t t的的球内，而没有一个矢量落在球外，这就是完备码。球内，而没有一个矢量落在球外，这就是完备码。围绕完备码围绕完备码2 2k k个码字、汉明距离为个码字、汉明距离为t t的所有球都是不相交的、不相切的所有球都是不相交的、不相切的，每一个接收矢量不是落在这个球、就是落在那个球内，没有一的，每一个接收矢量不是落在这个球、就是落在那个球内，没有一点是在球外。这样，接收矢量离码字的距离至多为点是在球外。这样，接收矢量离码字的距离至多为t t，所有重量，所有重量W t的差错图案都能通过最小距离译码得到纠正，而所有重量的差错图案都能通过最小距离译码得到纠正，而所有重量W t+1的差错图案都不能纠正。的差错图案都不能纠正。第75页，此课件共84页哦例例3.4:构造一个构造一个m=3的二元的二元(7，4)汉明码。汉明码。0 0 0 1 1 1 1 列置换1 1 1 0 1 0 0 H=0 1 1 0 0 1 1 0 1 1 1 0 1 01 0 1 0 1 0 1 1 1 0 1 0 0 1那么系统汉明码的生成矩阵G为：1 0 0 0 1 0 1 G =I4 P =0 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1第76页，此课件共84页哦 4.4 高莱码高莱码高莱码是二进制（高莱码是二进制（23，12）线性码，其最小距离）线性码，其最小距离dmin7，纠错能力，纠错能力t=3。由于满足：。由于满足：223-12=2048=它也是完备码。它也是完备码。在在(23,12)码上添加一位奇偶位即得二进制线性码上添加一位奇偶位即得二进制线性(24,12)扩展高莱码，其最扩展高莱码，其最小距离小距离dmin8。第77页，此课件共84页哦 4.5 扩展码扩展码(n,k)分组码分组码+1位奇偶校验位奇偶校验=(n1,k)扩展码扩展码校验位校验位c校校的选择应满足校验方程的选择应满足校验方程 c n1 c1 c0 c 校校0矩阵矩阵H与与H扩扩的关系如下：的关系如下：0k0 H 个个0H扩扩 0 (n+1)1 1 1 1 1 个个1离离距距小小最最的的码码原原前前展展扩扩若若，看看度度角角离离距距小小最最从从dmin数数奇奇是是,最最的的后后展展扩扩则则成成变变离离距距小小dmin+1变变改改不不验验校校偶偶则则，数数偶偶是是离离距距小小最最的的码码原原若若；其最小距离其最小距离。第78页，此课件共84页哦 4.6 缩短码缩短码(n,kn,k)分组码分组码 缩短缩短i i位位=(=(n-i,k-in-i,k-i)缩短码缩短码如如果果缩缩短短1 1位位,可可在在码码集集中中去去掉掉所所有有第第1 1位位是是0 0的的码码字字,剩剩下下的的码码组组成成一一个个新的码集，其最小码重不变；新的码集，其最小码重不变；如如果果缩缩短短2 2位位,可可在在码码集集中中去去掉掉所所有有前前2 2位位是是0 0的的码码字字,剩剩下下的的码码组组成成一一个个新新的的码码集集，其其最最小小码码重重仍仍不不变变；以以此此类类推推，缩缩短短i i位位，在在码码集集中中去去掉所有前掉所有前i i位是位是0 0的码字，剩下码集的的码字，剩下码集的d dminmin与缩短前一样。与缩短前一样。因因此此,（n n-i i,k k-i i,d dminmin）缩缩短短码码与与原原（n n,k k,d dminmin）码码具具有有相相同同的的纠纠检错能力。检错能力。第79页，此课件共84页哦缩短后的生成矩阵缩短后的生成矩阵Gs(删除前删除前i行、前行、前i列）列）g(k-1)(n-1)g(k-1)(n-2)g(k-1)(n-i)g(k-1)(n-i-1)g(k-1)0 g(k-2)(n-1)g(k-2)(n-2)g(k-2)(n-i)g(k-2)(n-i-1)g(k-2)0 Gs=g(k-i)(n-1)g(k-i)(n-2)g(k-i)(n-i)g(k-i)(n-i-1)g(k-i)0 g(k-i-1)(n-1)g(k-i-1)(n-2)g(k-i-1)(n-i)g(k-i-1)(n-i-1)g(k-i-1)0 g0(n-1)g0(n-2)g0(n-i)g0(n-i-1)g00缩短后的校验矩阵缩短后的校验矩阵Hs。删除原校验矩阵删除原校验矩阵H的前的前i列。列。第80页，此课件共84页哦4.7 分组码的性能限分组码的性能限为了揭示冗余度为了揭示冗余度(n-k)与纠错能力与纠错能力 t 或或dmin之间的关系，通常可以之间的关系，通常可以用极限值、渐近线或解析公式三种描述方式。极限方式过于粗用极限值、渐近线或解析公式三种描述方式。极限方式过于粗糙，解析公式又难以寻找，因此以下将扼要叙述几个重要的渐糙，解析公式又难以寻找，因此以下将扼要叙述几个重要的渐近公式，也叫性能限。近公式，也叫性能限。第第一一个个性性能能限限叫叫汉汉明明限限(H限限)，它它给给出出了了n-k与与t的的关关系系。汉汉明明限限可可这样推出：这样推出：第81页，此课件共84页哦第二个性能限叫普洛特金第二个性能限叫普洛特金(Plotkin)限限(P限限):在在一一个个q进进制制(n,k)线线性性分分组组码码中中，为为了了达达到到最最小小距距离离dmin所需的校验位所需的校验位n-k数目必须满足不等式数目必须满足不等式 (3-41)对二进制码来说，上式简化为对二进制码来说，上式简化为 (3-42)第82页，此课件共84页哦第第三三个个性性能能限限是是沃沃尔尔沙沙莫莫夫夫(Varsharmov)吉吉尔尔伯伯特特(Gilbert)限限（V-G限限）：对对于于q进进制制(n,k)线线性性分分组组码，若校验位码，若校验位n-k数目满足不等式数目满足不等式 (3-43)则则一一定定可可以以构构造造出出一一个个最最小小距距离离为为dmin的的(n,k)线线性性分分组组码。码。在二进制在二进制q=2情况下，上式两边取对数并简化为情况下，上式两边取对数并简化为(3-44)第83页，此课件共84页哦 dmin/n 1.0-0.8-0.6-0.4-0.2-0 0 0.2 0.4 0.6 0.8 1.0 Rc 图图3-5 3-5 归一化的上、下性能限归一化的上、下性能限 Plotkin限 V-G限 汉明限 n=31 BCH码 n=63 BCH码第84页，此课件共84页哦