《信息论与编码第二讲.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第二讲.ppt（84页珍藏版）》请在三一办公上搜索。
1、第二讲 信道编码理论和线性分组码,主要内容,1,2,3,4,信道编码定理,线性分组码的编译码,码的检、纠错能力,信道编码概念,一、信道编码概念,1.1 通信系统模型,信源编码器 把消息转换成为二进制形式的信息序列，并且为了使传输有效，去掉了与传输信息无关的多余度。纠错编码器 为了抗击传输过程中各种干扰，要人为地增加一些多余度，使其具有自动检错或纠错能力。纠错码译码器 由于信道干扰，该信息序列中可能有错误，经过纠错码译码器，对错误进行纠正。,信源指原来的信源和信源编码器，其输出是二(多)进制信息序列。信道包括发射机、实际信道（或称传输媒质）和接收机在内的广义信道，它的输入是二（多）进制数字序列，
2、输出是二（多）进制数字序列。,1.2 编码信道,二、信道编码定理,2.1 信道编码理论,每个信道具有确定的信道容量C，对任何小于C的码率Rs，存在有速率为Rs、码长为n的编码方法，若用最大似然译码，则随着码长的n增加其译码错误概率Pe可任意小，即：,式中，E(RS)为正实函数，称为误差指数，它与RS、C的关系如下图所示。图中，C1、C2为信道容量，且C1C2。,2.2 信道编码基本思想,2.3译码平均错误概率,2.4 译码规则,2.4.1 最大后验概率译码准则,例 题,2.4.2 极大似然译码准则,例 题,两种译码准则比较,2.4.3 最小码距译码准则,最小码距,最小码距对错误概率的影响,最小
3、距离译码准则,最小距离准则与最大似然准则关系,例：重复码,早期的检错码为重复码。该码用000代表信息“0”，用111代表信息“1”。显然所增加的2个码元并不增多信息，是多余的,使传信率降低。此外，除去传送信息的000和111这2种组合外,还有001,010,011,100,101,110等6种组合没采用。当信道上信噪比足够大时,可认为000和111中产生的错误一般不会多于一个码元。如接收到001,010,100,在接收端怎么译码呢？根据最小码距译码准则，可判定实际上是000,即信息为0；同理,如接收到011,110,101,在接收端也可判定111,即信息为1。可见,多余码元可检出并纠正一个错误
4、，这样就提高了传信的可靠性。,三、线性分组码,3.1 生成矩阵,m G=C,100111010110001011,张成码空间的三个基，本身也是码字。,信息空间到码空间的线性映射,信息组(m2 m1 m0)码字(c5 c4 c3 c2 c1c0)000000000001001011010010110011011101100100111101101100110110001111 111010 k维k重k维n重 信息空间 码字空间,gk-1G=g1 g0c=m G=mk-1,m1 m0 gk-1 g1 g0 T=mk-1 gk-1+m1 g1+m0 g0,生成矩阵G 是由k个行矢量组成的，其中的每个
5、行矢量g i既是一个基底，也是一个码字。任何码字都是生成矩阵G的k个行矢量的线性组合。只要这k个行矢量线性无关，就可以作为k个基底张成一个k维n重空间，它是n维n重空间的一个子空间，子空间的所有2k个矢量构成码集C。,不同的生成矩阵产生不同的码，生成矩阵的特点决定了码的特点。由于构成同一空间的基底不是唯一的，所以不同的基底或生成矩阵可能生成同一码集。码集相同，编码不一定相同，因为编码涉及码集和映射两个因素，码集一样而映射方法不同不能说是同样的编码。,由于基底不是唯一的，因此允许将基底线性组合后挑出其中k个线性无关的矢量作为新的基底，依然可以张成同一个码空间。对应到生成矩阵，等效于允许通过行运算
6、（行交换、行的线性组合）改变生成矩阵的行而不改变码集，只要保证矩阵的秩仍是k（k行线性无关)。所以，任何生成矩阵可通过行运算转化成“系统码”形式。,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=,3.3 校验矩阵 对于kn矩阵G，存在一个(n-k)n矩阵H，使得G的行空间和H正交。基底数k的码空间C是n维n重空间的子空间，若能找出全部n个基底的另外n-k个基底，也就找到了对偶空间D。将D空间的n-k个基底排列起来可构成一个(n-
7、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的校验矩阵。,n维n重空间R k维k重 k维n重 n-k维n重 信息组 码空间C 对偶空间D 空间m G H 图3-1 码空间与映射,c是G空间的一个码字，那么由正交性得到：c HT=00代表零阵，它是1nn(n-k)=1(n-k)矢量。上式可以用来检验一个n重矢量是否为码字：若等式成立，该n重是码字，否则不是码
8、字。由于生成矩阵的每行都是一个码字，因此有：GHT=0这里0代表一个 knn(n-k)=k(n-k)的零矩阵。,对于系统码，其校验矩阵也是规则的，必为：HPT In-k 因为：GHT=IkP PTIn-k T=Ik P+P In-k=P+P=0,例3.1 考虑一个(7，4)码，其生成矩阵是：G=I4 P 对于信息组m=(1 0 1 1),编出的码字是什么？画一个（7，4）分组码编码器原理图。若接收到一个7位码r=(1 0 0 1 1 0 1),检验它是否码字？,3.3 伴随式与译码 线性分组码 C=(cn-1,c1,c0)，接收码 R=(rn-1,r1,r0)，差错图案:E=(e n1,，e
9、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 n-k-1,，s1,s0)=RHT=EHT S仅与E有关，而与C无关。,从物理意义看，伴随式S并不反映发送的码字是什么，而只反映信道对码字造成了怎样的干扰。伴随式S是一个(n-k)重矢量，只有2n-k种可能的组合；而差错图案E是n重矢量，共有2n个可能的组合。因此，同一伴随式可能对应若干个不同的差错图案。在接收端我们并不知道发码C究竟是什么，但可以知道HT和接收码是R什么，从
10、而算出S是什么。译码最重要的任务：从伴随式S找出C的估值。,一般的译码思路 RHT=S E C=RE,E m 编码 C RS=no 计算 输出 mG RH T=0？E R+E yes 输出R 图3-3 译码过程框图,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个方程
11、。,在二元域中，少一个方程导致两个解，少两个方程导致四个解少n-(n-k)=k个方程导致有2k个解。在E的2k个解中选一，最合理的方法是概率译码，它把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该算法的理论根据就是最小汉明距离译码。,3.4 标准阵列,某一个(5,2)系统线性码的生成矩阵：G=码集：00000,10111,01101,11010,E2n-k+C2k,E2n-k+Ci,E2n-k-1+C1,E2n-k+C0=E2n-k,Ej+C2k1,Ej+Ci,Ej+C1,Ej+C0=Ej,E1+C2k1,E1+Ci,E1+C1,E1+C0=E1,E0+C2k
12、1=C2k1,E0+Ci=Ci,E0+C1=C1,E0+C0=0+0=0,表3-2 标准阵列译码表,对于(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)。其标准阵列：,例：某一个(5,2)系统线性码的生成矩阵是G=，设收码是R=(10101),请先构造该码的标准阵列译码表，然后译出发码的估值。分析：H=PT I3=，由S=(E+C)HT=EHT得：s2
13、=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)并列最小重量，任取其中一个？,查表译码方法,1 计算R的伴随式S=RHT；2 找出伴随式S等于RHT的陪集首el；3
14、码矢v=R+el就是发送码矢。,例3.3对于(6,3)码，校验矩阵为：S=EHT,如果发送的码矢为v=(111000)，接收的矢量r=(111001)，怎样来译码？,四、码的纠、检错能力,4.1 计算最小距离的方法1 直接计算。含2k个码字的码集需计算2k(2 k-1)/2个距离后才能找出dmin。2 利用群码封闭性两码字之和仍是码字：d(C1,C2)=w(C1C2)=w(C3)可得定理3.1:线性分组码的最小距离等于码集中非零码字的最小重量：dmin=min w(Ci)C iC 及Ci 0于是最小距离问题转化为寻找最轻码字问题，含2k个码字的码集仅需计算2k次。,3 利用校验矩阵H的秩定理3
15、.4：(n,k)线性分组码最小距离等于dmin的充要条件是校验矩阵H中有（dmin-1)列线性无关。换言之，dmin=校验矩阵H的秩+1。,定理3.2:任何最小距离dmin的线性分组码，其检测随机差错的能力为（dmin1）。定理3.3:任何最小距离等于dmin的线性分组码，其纠正随机差错的能力t为：t=INT 若最小距离为dmin的码同时能检ed个、纠ec个差错,则edec dmin1 ec ed。抑制纠错能力才能提高检错能力。,例：每个分组码dmin=7，那么怎么来纠错和检错？（1）纠错 t=3；（2）2重纠错，并且4重错误检测 t=2,D=4；（3）6重错误检测 D=6。,定理3.5：(n
16、,k)线性分组码的最小距离必定小于等于(n-k+1)即 dmin(n-k+1)因为H是(n-k)n矩阵，该矩阵的秩最大不会超过(n-k)，即线性无关的列不会超过(n-k)。,4.2 完备码如果某码的伴随式组合数目恰好和不大于t个差错的图案数目相等，相当于在标准阵列中能将所有重量不大于t的差错图案选作陪集首而没有一个陪集首的重量大于t，这时的伴随式就能和可纠差错图案实现一一对应，校验位得到最合理的利用。满足方程：的二元(n,k)线性分组码称为完备码。t=1的完备码叫汉明码。,4.3 汉明码纠错能力t=1的完备码称为汉明码。汉明码指一类码，既可以是二进制的，也可以是非二进制的。二进制汉明码应满足条
17、件：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)。,从n维矢量空间的角度看(n,k)完备码，假定每个码字为中心放置一个半径t的球，与该码汉明距离小于等于t的所有接收矢量均包含在此球内，每球包含的矢量点数是。以码集2k个码字为中心、半径t(不相重叠)的球共可包含 2k 点。由于n重矢量的总数是2n个，包含在2 k个球中的点数不可能多于总点数，所以下列不等式必定成立：,如果上
18、式等号成立，表示全部2n个接收矢量等分地落在2k个半径t的球内，而没有一个矢量落在球外，这就是完备码。围绕完备码2k个码字、汉明距离为t的所有球都是不相交的、不相切的，每一个接收矢量不是落在这个球、就是落在那个球内，没有一点是在球外。这样，接收矢量离码字的距离至多为t，所有重量Wt的差错图案都能通过最小距离译码得到纠正，而所有重量Wt+1的差错图案都不能纠正。,例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 11 1 0 1 0 0 1那么系统汉明码的
19、生成矩阵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,4.4 高莱码高莱码是二进制（23，12）线性码，其最小距离dmin7，纠错能力t=3。由于满足：223-12=2048=它也是完备码。在(23,12)码上添加一位奇偶位即得二进制线性(24,12)扩展高莱码，其最小距离dmin8。,4.5 扩展码(n,k)分组码+1位奇偶校验=(n1,k)扩展码校验位c校的选择应满足校验方程 c n1 c1 c0 c 校0矩阵H与H扩的关系如下：0 H 0 k个0H扩 0 1 1 1 1 1(n+1)个1从最小距离角度看，若
20、扩展前原码的最小距离dmin是奇数,则扩展后的最小距离变成dmin+1；若原码的最小距离是偶数，则偶校验不改变其最小距离。,4.6 缩短码(n,k)分组码 缩短i位=(n-i,k-i)缩短码如果缩短1位,可在码集中去掉所有第1位是0的码字,剩下的码组成一个新的码集，其最小码重不变；如果缩短2位,可在码集中去掉所有前2位是0的码字,剩下的码组成一个新的码集，其最小码重仍不变；以此类推，缩短i位，在码集中去掉所有前i位是0的码字，剩下码集的dmin与缩短前一样。因此,（n-i,k-i,dmin）缩短码与原（n,k,dmin）码具有相同的纠检错能力。,缩短后的生成矩阵Gs(删除前i行、前i列）g(k
21、-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列。,4.7 分组码的性能限为了揭示冗
22、余度(n-k)与纠错能力 t 或dmin之间的关系，通常可以用极限值、渐近线或解析公式三种描述方式。极限方式过于粗糙，解析公式又难以寻找，因此以下将扼要叙述几个重要的渐近公式，也叫性能限。第一个性能限叫汉明限(H限)，它给出了n-k与t的关系。汉明限可这样推出：,第二个性能限叫普洛特金(Plotkin)限(P限):在一个q进制(n,k)线性分组码中，为了达到最小距离dmin所需的校验位n-k数目必须满足不等式(3-41)对二进制码来说，上式简化为(3-42),第三个性能限是沃尔沙莫夫(Varsharmov)吉尔伯特(Gilbert)限（V-G限）：对于q进制(n,k)线性分组码，若校验位n-k数目满足不等式(3-43)则一定可以构造出一个最小距离为dmin的(n,k)线性分组码。在二进制q=2情况下，上式两边取对数并简化为(3-44),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 归一化的上、下性能限,Plotkin限,V-G限,汉明限,n=31 BCH码,n=63 BCH码,
