信息论与编码第二讲

1、信息论与编码第二讲第1页，共84页，2022年，5月20日，1点16分，星期一主要内容1234信道编码定理线性分组码的编译码码的检、纠错能力信道编码概念第2页，共84页，2022年，5月20日，1点16分，星期一一、信道编码概念第3页，共84页，2022年，5月20日，1点16分，星期一 1.1 通信系统模型第4页，共84页，2022年，5月20日，1点16分，星期一信源编码器 把消息转换成为二进制形式的信息序列，并且为了使传输有效，去掉了与传输信息无关的多余度。纠错编码器 为了抗击传输过程中各种干扰，要人为地增加一些多余度，使其具有自动检错或纠错能力。纠错码译码器 由于信道干扰，该信息序列中

2、可能有错误，经过纠错码译码器，对错误进行纠正。第5页，共84页，2022年，5月20日，1点16分，星期一 信源指原来的信源和信源编码器，其输出是二(多)进制信息序列。 信道包括发射机、实际信道（或称传输媒质）和接收机在内的广义信道，它的输入是二（多）进制数字序列，输出是二（多）进制数字序列。 1.2 编码信道第6页，共84页，2022年，5月20日，1点16分，星期一第7页，共84页，2022年，5月20日，1点16分，星期一二、信道编码定理第8页，共84页，2022年，5月20日，1点16分，星期一2.1 信道编码理论 每个信道具有确定的信道容量C，对任何小于C的码率Rs，存在有速率为Rs

3、、码长为n的编码方法，若用最大似然译码，则随着码长的n增加其译码错误概率Pe可任意小， 即 ：第9页，共84页，2022年，5月20日，1点16分，星期一式中，E(RS)为正实函数，称为误差指数，它与RS、C的关系如下图所示。图中，C1、C2为信道容量，且C1C2。第10页，共84页，2022年，5月20日，1点16分，星期一2.2 信道编码基本思想 第11页，共84页，2022年，5月20日，1点16分，星期一第12页，共84页，2022年，5月20日，1点16分，星期一第13页，共84页，2022年，5月20日，1点16分，星期一第14页，共84页，2022年，5月20日，1点16分，星期

4、一第15页，共84页，2022年，5月20日，1点16分，星期一2.3译码平均错误概率 第16页，共84页，2022年，5月20日，1点16分，星期一第17页，共84页，2022年，5月20日，1点16分，星期一第18页，共84页，2022年，5月20日，1点16分，星期一2.4 译码规则 第19页，共84页，2022年，5月20日，1点16分，星期一2.4.1 最大后验概率译码准则第20页，共84页，2022年，5月20日，1点16分，星期一例 题第21页，共84页，2022年，5月20日，1点16分，星期一第22页，共84页，2022年，5月20日，1点16分，星期一2.4.2 极大似然译

5、码准则第23页，共84页，2022年，5月20日，1点16分，星期一例 题第24页，共84页，2022年，5月20日，1点16分，星期一第25页，共84页，2022年，5月20日，1点16分，星期一两种译码准则比较第26页，共84页，2022年，5月20日，1点16分，星期一2.4.3 最小码距译码准则第27页，共84页，2022年，5月20日，1点16分，星期一第28页，共84页，2022年，5月20日，1点16分，星期一最小码距第29页，共84页，2022年，5月20日，1点16分，星期一最小码距对错误概率的影响第30页，共84页，2022年，5月20日，1点16分，星期一最小距离译码准则

6、第31页，共84页，2022年，5月20日，1点16分，星期一最小距离准则与最大似然准则关系第32页，共84页，2022年，5月20日，1点16分，星期一例：重复码早期的检错码为重复码。该码用000代表信息“0”，用111代表信息“1”。显然所增加的2个码元并不增多信息，是多余的,使传信率降低。此外，除去传送信息的000和111这2种组合外,还有001,010,011,100,101,110等6种组合没采用。当信道上信噪比足够大时,可认为000和111中产生的错误一般不会多于一个码元。如接收到001,010,100,在接收端怎么译码呢？根据最小码距译码准则，可判定实际上是000,即信息为0；同

7、理,如接收到011,110,101,在接收端也可判定111,即信息为1。 可见,多余码元可检出并纠正一个错误，这样就提高了传信的可靠性。 第33页，共84页，2022年，5月20日，1点16分，星期一三、线性分组码第34页，共84页，2022年，5月20日，1点16分，星期一第35页，共84页，2022年，5月20日，1点16分，星期一m2m1m0C5C4C3C0C1C23.1 生成矩阵第36页，共84页，2022年，5月20日，1点16分，星期一m2 m1 m0100111010110001011=c5 c4 c3 c2 c1 c0 m G = C100111010110001011张成码空

8、间的三个基，本身也是码字。第37页，共84页，2022年，5月20日，1点16分，星期一第38页，共84页，2022年，5月20日，1点16分，星期一信息空间到码空间的线性映射信息组(m2 m1 m0 ) 码字(c5 c4 c3 c2 c1c0 )000000000001001011010010110011011101100100111101101100110110001111 111010 k维k重k维n重 信息空间 码字空间第39页，共84页，2022年，5月20日，1点16分，星期一 gk-1G = = g1 g0c = m G = mk-1,m1 m0 gk-1 g1 g0 T = m

9、k-1 gk-1 + + m1 g1 + m0 g0 第40页，共84页，2022年，5月20日，1点16分，星期一 生成矩阵G 是由k个行矢量组成的，其中的每个行矢量g i既是一个基底，也是一个码字。 任何码字都是生成矩阵G的k个行矢量的线性组合。 只要这k个行矢量线性无关，就可以作为k个基底张成一个k维n重空间，它是n维n重空间的一个子空间，子空间的所有2k个矢量构成码集C。第41页，共84页，2022年，5月20日，1点16分，星期一不同的生成矩阵产生不同的码，生成矩阵的特点决定了码的特点。由于构成同一空间的基底不是唯一的，所以不同的基底或生成矩阵可能生成同一码集。码集相同，编码不一定相

10、同，因为编码涉及码集和映射两个因素，码集一样而映射方法不同不能说是同样的编码。第42页，共84页，2022年，5月20日，1点16分，星期一 由于基底不是唯一的，因此允许将基底线性组合后挑出其中k个线性无关的矢量作为新的基底，依然可以张成同一个码空间。 对应到生成矩阵，等效于允许通过行运算（行交换、行的线性组合）改变生成矩阵的行而不改变码集，只要保证矩阵的秩仍是k（k行线性无关)。 所以，任何生成矩阵可通过行运算转化成“系统码”形式。第43页，共84页，2022年，5月20日，1点16分，星期一3.2 系统码 把信息组原封不动搬到码字前k位的(n,k)码，其码字具有如下形式： c = (cn-

11、1,cn-k , cn-k-1 ,c0) = ( mk-1 ,m1, m0 , cn-k-1 ,c0 )其生成矩阵具有如下形式：G = Ik P =第44页，共84页，2022年，5月20日，1点16分，星期一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

12、)线性码，称（n,n-k）线性码是(n,k)线性码的对偶码。C和D的对偶是相互的，G是C的生成矩阵又是D的校验矩阵，而H是D的生成矩阵又是C的校验矩阵。第45页，共84页，2022年，5月20日，1点16分，星期一 n维n重空间R k维k重 k维n重 n-k维n重 信息组 码空间C 对偶空间D 空间m G H 图3-1 码空间与映射第46页，共84页，2022年，5月20日，1点16分，星期一 c是G空间的一个码字，那么由正交性得到： c HT= 00代表零阵，它是1nn(n-k)=1(n-k)矢量。 上式可以用来检验一个n重矢量是否为码字：若等式成立，该n重是码字，否则不是码字。 由于生成矩

13、阵的每行都是一个码字，因此有： GHT=0这里0代表一个 knn(n-k)= k(n-k)的零矩阵。第47页，共84页，2022年，5月20日，1点16分，星期一对于系统码，其校验矩阵也是规则的，必为：HPT In-k 因为： GHT= IkP PTIn-k T =Ik P + P In-k = P + P = 0 第48页，共84页，2022年，5月20日，1点16分，星期一例3.1 考虑一个(7，4) 码，其生成矩阵是： G = = I4 P 对于信息组m= (1 0 1 1), 编出的码字是什么？ 画一个（7，4）分组码编码器原理图。 若接收到一个7位码r = (1 0 0 1 1 0

14、1), 检验它是否码字？ 第49页，共84页，2022年，5月20日，1点16分，星期一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 n-k-1,，s1, s0) = RHT = EHT S仅与E有关，而与C无关。 第50页，共84

15、页，2022年，5月20日，1点16分，星期一从物理意义看，伴随式S并不反映发送的码字是什么，而只反映信道对码字造成了怎样的干扰。伴随式S是一个(n-k)重矢量，只有2n-k种可能的组合；而差错图案E是n重矢量，共有2n个可能的组合。因此，同一伴随式可能对应若干个不同的差错图案。在接收端我们并不知道发码C究竟是什么，但可以知道HT和接收码是R什么，从而算出S是什么。译码最重要的任务：从伴随式S找出C的估值。第51页，共84页，2022年，5月20日，1点16分，星期一 一般的译码思路 RHT = S E C = RE E m 编码 C RS= no 计算 输出 mG RH T=0？ E R+E

16、 yes 输出R 图3-3 译码过程框图 第52页，共84页，2022年，5月20日，1点16分，星期一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页，2022年，5月20日，1点

17、16分，星期一 在二元域中，少一个方程导致两个解，少两个方程导致四个解少n-( n-k) = k个方程导致有2k个解。在E的2k个解中选一，最合理的方法是概率译码，它把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。 该算法的理论根据就是最小汉明距离译码。 第54页，共84页，2022年，5月20日，1点16分，星期一3.4 标准阵列第55页，共84页，2022年，5月20日，1点16分，星期一某一个(5,2)系统线性码的生成矩阵：G = 码集： 00000, 10111, 01101, 11010S0=000E0+C0=00000C1=10111C2=01101

18、C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第56页，共84页，2022年，5月20日，1点16分，星期一E2n-k +C2kE2n-k+ CiE2n-k-1 + C1E2n-k+C0 = E2n-kEj+C2k1Ej+C

19、iEj+C1Ej +C0= EjE1+C2k1E1+CiE1 +C1E1+C0= E1E0+C2k1= C2k1E0+Ci= CiE0 +C1= C1E0 +C0= 0+0= 0表3-2 标准阵列译码表第57页，共84页，2022年，5月20日，1点16分，星期一对于(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页，共

20、84页，2022年，5月20日，1点16分，星期一例：某一个(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组解，取最轻者为“解”。其中

21、有的组最轻解是唯一的，有的却不是，比如伴随式S=(011)的4个解是(00011)、(10100)、(01110)、(11001)，其中(00011)和(10100)并列最小重量，任取其中一个？第59页，共84页，2022年，5月20日，1点16分，星期一S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=000011

22、01100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100第60页，共84页，2022年，5月20日，1点16分，星期一第61页，共84页，2022年，5月20日，1点16分，星期一查表译码方法1 计算R的伴随式S=RHT；2 找出伴随式S等于RHT的陪集首el；3 码矢v=R+el就是发送码矢。第62页，共84页，2022年，5月20日，1点16分，星期一例3.3对于(6,3)码，校验矩阵为： S=EHT第63页，共84页，2022年，5月20日，1点16分，星期一 如果发送的码矢为v=(111000)，接

23、收的矢量r =(111001)，怎样来译码？第64页，共84页，2022年，5月20日，1点16分，星期一四、码的纠、检错能力第65页，共84页，2022年，5月20日，1点16分，星期一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次。第66页，共8

24、4页，2022年，5月20日，1点16分，星期一3 利用校验矩阵H的秩定理3.4： (n,k) 线性分组码最小距离等于dmin的充要条件是校验矩阵H中有（dmin-1)列线性无关。换言之，dmin=校验矩阵H的秩+1。第67页，共84页，2022年，5月20日，1点16分，星期一定理3.2: 任何最小距离dmin的线性分组码，其检测随机差错的能力为（dmin1）。 定理3.3: 任何最小距离等于dmin的线性分组码，其纠正随机差错的能力t为： t =INT 若最小距离为dmin的码同时能检ed个、纠ec个差错,则edec dmin1 ec ed。抑制纠错能力才能提高检错能力。第68页，共84页

25、，2022年，5月20日，1点16分，星期一第69页，共84页，2022年，5月20日，1点16分，星期一例：每个分组码dmin=7，那么怎么来纠错和检错？（1）纠错 t=3；（2）2重纠错，并且4重错误检测 t=2, D=4；（3）6重错误检测 D=6。第70页，共84页，2022年，5月20日，1点16分，星期一定理3.5：(n,k) 线性分组码的最小距离必定小于等于 (n-k+1)即 dmin (n-k+1)因为H是(n-k)n矩阵，该矩阵的秩最大不会超过(n-k)，即线性无关的列不会超过(n-k) 。第71页，共84页，2022年，5月20日，1点16分，星期一 4.2 完备码如果某码

26、的伴随式组合数目恰好和不大于t个差错的图案数目相等，相当于在标准阵列中能将所有重量不大于t的差错图案选作陪集首而没有一个陪集首的重量大于t，这时的伴随式就能和可纠差错图案实现一一对应，校验位得到最合理的利用。满足方程：的二元(n,k)线性分组码称为完备码。t = 1的完备码叫汉明码。第72页，共84页，2022年，5月20日，1点16分，星期一4.3 汉明码纠错能力t = 1的完备码称为汉明码。汉明码指一类码，既可以是二进制的，也可以是非二进制的。二进制汉明码应满足条件： 2n-k=1+n。令r= n-k，汉明码n和k服从以下关系 码长：n=2r - 1 信息位：k=2r-1-r 最小距离 d

27、 min = 3当r3、4、5、6、7、8时，有以下汉明码：(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)。第73页，共84页，2022年，5月20日，1点16分，星期一 从n维矢量空间的角度看(n,k)完备码，假定每个码字为中心放置一个半径t的球，与该码汉明距离小于等于t的所有接收矢量均包含在此球内，每球包含的矢量点数是 。以码集2k个码字为中心、半径t (不相重叠) 的球共可包含 2k 点。由于n重矢量的总数是2n个，包含在2 k个球中的点数不可能多于总点数，所以下列不等式必定成立： 第74页，共84页，2022年，5月20日，1点16分

28、，星期一如果上式等号成立，表示全部2n个接收矢量等分地落在2k个半径t的球内，而没有一个矢量落在球外，这就是完备码。围绕完备码2k个码字、汉明距离为t的所有球都是不相交的、不相切的，每一个接收矢量不是落在这个球、就是落在那个球内，没有一点是在球外。这样，接收矢量离码字的距离至多为t，所有重量Wt的差错图案都能通过最小距离译码得到纠正，而所有重量Wt+1的差错图案都不能纠正。 第75页，共84页，2022年，5月20日，1点16分，星期一例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

29、 0 1 01 0 1 0 1 0 11 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页，2022年，5月20日，1点16分，星期一 4.4 高莱码高莱码是二进制（23，12）线性码，其最小距离dmin7，纠错能力t=3。由于满足： 223-12 = 2048 = 它也是完备码。在(23,12)码上添加一位奇偶位即得二进制线性(24,12)扩展高莱码，其最小距离dmin8。 第77页，共84页，2022年，5月20日，1点16分，星期一 4.5

30、扩展码(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从最小距离角度看，若扩展前原码的最小距离dmin是奇数, 则扩展后的最小距离变成dmin+1；若原码的最小距离是偶数，则偶校验不改变其最小距离。第78页，共84页，2022年，5月20日，1点16分，星期一 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）码具有相同的纠检错能力。 第79页，共84页，2022年，5月20日，1