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

《信息论与编码第6章(2)》由会员分享，可在线阅读，更多相关《信息论与编码第6章(2)（50页珍藏版）》请在装配图网上搜索。

1、信道编码信道编码16.3 线性分组码线性分组码2线性分组码线性分组码3G gk 1,gk 2 1 0 ,.g ,g T线性分组码的码空间线性分组码的码空间C 是由是由 k 个线性无关个线性无关的的基底基底 gk-1,，g1，g0 张成的张成的k维维n重重子空间子空间，所有码字都可写成，所有码字都可写成k个个基底的线性组合，即基底的线性组合，即 c=mk-1 gk-1+m1 g1+m0 g0如果如果gi表示第表示第i个基底，并写成行矩阵的形式个基底，并写成行矩阵的形式gi gi(n 1),gi(n 2),.gi1,gi0,k个基底可以排列成个基底可以排列成k行行n列的形式，如下所示：列的形式，如

2、下所示：.g(k 1)1.g11.g01 g(k 1)(n 1).g1(n 1)g0(n 1)g(k 1)0.g10 g00 6.3.1生成矩阵和校验矩阵生成矩阵和校验矩阵4码空间中任何一个码字都可以写成基底的线性组合，即：码空间中任何一个码字都可以写成基底的线性组合，即：C cn 1,cn 2,.,c1,c0 mk 1gk 1 mk 2gk 2 .m1g1 m0g0 mG 当信息元确定后，码字仅由当信息元确定后，码字仅由G矩阵决定，因此我们称这矩阵决定，因此我们称这kn 矩阵矩阵G为该为该(n,k)线性分组码的线性分组码的生成矩阵生成矩阵。如果已知线性分组码的生成矩阵，则任何一个如果已知线性

3、分组码的生成矩阵，则任何一个k位信息位信息组对应的码字都可以由组对应的码字都可以由mG运算得到。运算得到。生成矩阵生成矩阵5 (n,k)线性分组码共有多少个码字线性分组码共有多少个码字?问题问题答：答：2k个码字。个码字。6 想要保证想要保证(n,k)线性分组码能够构成线性分组码能够构成k维维n重子空间，重子空间，G 的的k 个行矢量个行矢量gk-1,g1,g0必须是必须是线性无关线性无关的，只有这的，只有这样样才符合作为基底的条件。才符合作为基底的条件。由于由于k个基底即个基底即G的的k个行矢量线性无关，矩阵个行矢量线性无关，矩阵G的的秩一定秩一定等于等于k。由于由于基底不是唯一基底不是唯一

4、的，所以的，所以G也就不是唯一的。也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说映射两个因素，码集一样而映射方法不同也不能说是同是同 样的码。样的码。生成矩阵生成矩阵G(kn)的特点的特点7已知已知(7,4)线性分组码的生成矩阵为线性分组码的生成矩阵为如果输入的四位信息组为如果输入的四位信息组为m 0,1,1,0时，其对应的时，其对应的码码字为字为：举例举例8(n,k)码的任何生成矩阵都可以通过码的任何生成矩阵都可以通过行运算行运算（不改变码集，（不改变码集，只改变映射规则）简化成只改

5、变映射规则）简化成“系统形式系统形式”。Ik是是kk单位矩阵，单位矩阵，P是是k(n-k)矩阵。矩阵。系统形式的生成矩阵系统形式的生成矩阵 G=Ik P =1 0 0p(k 1)0 p10p00 p(k 1)(n k 1)p1(n k 1)p0(n k 1)0 01 0 0 0 1 p(k 1)1 p11 p019 前前k位由单位矩阵位由单位矩阵Ik决定，等于把信息组决定，等于把信息组m原封不原封不动搬到码字的前动搬到码字的前k位；位；其余的其余的n-k位叫冗余位或位叫冗余位或一致校验位一致校验位，是前，是前k个信个信息位的线性组合。息位的线性组合。这样生成的（这样生成的（n,k）码叫做）码叫

6、做系统码系统码。若生成矩阵若生成矩阵G不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做非系统码非系统码。系统化系统化不改变码集不改变码集，只是改变了，只是改变了映射规则映射规则。系统系统码码10已知已知(7,3)线性分组码的生成矩阵为线性分组码的生成矩阵为如果输入的三位信息组为如果输入的三位信息组为m 0,1,1时，其对应的时，其对应的码码字为：字为：特点：特点：码字的前面码字的前面k位就是信息组中的位就是信息组中的k位，而后面的校验位，而后面的校验 位为位为信息组的线性组合信息组的线性组合。系统系统码码11 n维维n重空间有相互正重空间有相互正交的交的n个基底个基底 选择选择k个

7、基底构成码个基底构成码空间空间C 选择另外的选择另外的(n-k)个基个基底构成空间底构成空间D C和和D是对偶的是对偶的n维维n重空间重空间Vk维维k重重信息组信息组空间空间mk维维n重重 n-k维维码空间码空间 n重重DC HG空间构成空间构成12 将将D空间的空间的n-k个基底排列起来可构成一个个基底排列起来可构成一个(n-k)n矩矩阵，称为阵，称为校验矩阵校验矩阵H，也称，也称监督矩阵监督矩阵。用来校验接收。用来校验接收到的码字是否是正确的；到的码字是否是正确的；即：若即：若c为码空间为码空间C中的任意码字，则中的任意码字，则若不满足此等式，则若不满足此等式，则c必定不是码空间必定不是码

8、空间C中的码字。中的码字。校验矩阵校验矩阵13 G是是(n,k)码的码的生成矩阵生成矩阵，H是它的是它的校验矩阵校验矩阵；H是是(n,n-k)对偶码的对偶码的生成矩阵生成矩阵，它的每一行是，它的每一行是对偶码的一个码字。对偶码的一个码字。G则是它的则是它的校验矩阵校验矩阵。GHT=0，H PT In-k，二进制时，负号可，二进制时，负号可省略。省略。校验矩阵校验矩阵14校验矩阵与生成矩阵的关系校验矩阵与生成矩阵的关系15某线性分组码，其生成矩阵是某线性分组码，其生成矩阵是求：求：(1)计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统

9、码码集并列出映射将该码系统化处理后，计算系统码码集并列出映射关系。关系。(3)计算系统码的校验矩阵计算系统码的校验矩阵H。若收码。若收码r=100110,检检验它是否码字？验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。1 1 1 0 1 0 G=1 1 0 0 0 1 0 1 1 1 0 1 例例6-26-216码集与映射关系码集与映射关系信息信息000001010011100101110111码字码字000000011101110001101100111010100111001011010110系统码字系统码字0000000010110101

10、10011101100111101100110001111010例例6-26-217二元二元(6,3)线性分组码编码器线性分组码编码器输入输入输出输出m0 m1 m2 c0 c1 c2例例6-26-218 下面是某线性二元码的全部码字：下面是某线性二元码的全部码字：求求n,k的值；的值；构造这码的生成矩阵构造这码的生成矩阵G；构成这码的一致校验矩阵构成这码的一致校验矩阵H。C1 000000 C2 001111C3 010001C4 011110C5 100011C6 101100C7 1110010C8 111101举例举例19mC=(cn-1,c1,c0)R=(rn-1,r1,r0)(n,

11、k)信道信道定义定义差错图案差错图案EE(en1,e1,e0)RC(rn-1cn-1,r1c1,r0c0)二进制码中模二进制码中模2加与模加与模2减是等同的，因此有减是等同的，因此有E=R C 及及R=C E6.3.2伴随式与标准阵列译码伴随式与标准阵列译码20因为因为CHT=0所以所以RHT(CE)HT CHT EHT=EHT如果如果收码无误收码无误：必有：必有RC即即E0，则则EHT=0 RHT=0。如果如果收码有误收码有误：即：即E 0，则则RHT=EHT 0。在在HT固定的前提下，固定的前提下，RHT仅仅与差错图案仅仅与差错图案E有关，有关，而与发送码而与发送码C无关。定义无关。定义

12、RHT的运算结果为的运算结果为伴随式伴随式SS=(sn-k-1,s1,s0)=RHT=EHT伴随式伴随式的定义的定义21?RHT =SR SC=REE C只要只要E正确，译出的码也就是正确的。正确，译出的码也就是正确的。从物理意义上看，伴随式从物理意义上看，伴随式S并不反映发送的码字是什并不反映发送的码字是什么，而只是么，而只是反映信道对码字造成怎样的干扰反映信道对码字造成怎样的干扰。差错图案差错图案E是是n重矢量重矢量，共有，共有2n个可能的组合，而伴随个可能的组合，而伴随式式S是是(n-k)重矢量重矢量，只有，只有 2n-k 个可能的组合，因此不同个可能的组合，因此不同的差错图案可能有相同

13、的伴随式。的差错图案可能有相同的伴随式。接收端收到接收端收到R后，因为已知后，因为已知HT，可求出，可求出 SRHT；如；如果能知道对应的果能知道对应的E，则通过，则通过C=RE而求得而求得C。伴随式伴随式的意义的意义22译码过程框图译码过程框图译码过程译码过程23差错图案差错图案E E的求解的求解(1)(1)24 上述方程组中有上述方程组中有n个未知数个未知数en1,e1,e0，却只有，却只有n-k 个方程，可知方程组有多解。个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多在有理数或实数域中，少一个方程就可能导致无限多 个解，而在二元域中，少一个方程导致两个解，少两个

14、解，而在二元域中，少一个方程导致两个解，少两 个方程四个解，以此类推，少个方程四个解，以此类推，少n-(n-k)=k个方程导致个方程导致 每个未知数有每个未知数有2k个解。个解。概率译码：概率译码：把所有把所有 2k 个解的重量个解的重量(差错图案差错图案E中中1的个的个 数数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估值。该方法概的估值。该方法概 念上很简单但计算效率不高。念上很简单但计算效率不高。差错图案差错图案E E的求解的求解(2)(2)25依据：依据：若若BSC信道的差错概率是信道的差错概率是 p，则长度，则长度n的码中错误概率的码中错误概率0个错个错1个错个错2个错

15、个错n个错个错概率概率(1-p)np(1-p)n-1p2(1-p)n-2pn由于由于p p(1-p)n-1 p2(1-p)n-2 pn出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，所以该的重量越轻，所以该译码方法实际上体现了译码方法实际上体现了最小距离译码准则最小距离译码准则，即最大似然译码。，即最大似然译码。显然，在进行概率译码时，每接收一个码字就要解一次线显然，在进行概率译码时，每接收一个码字就要解一次线性方程，非常复杂麻烦。但如果性方程，非常复杂麻烦。但如果nk不太大，我们可以预先不太大，我们可以预先把不同校正子把不同校正子S情况下的所有方程组都预先解出来，将

16、各种情情况下的所有方程组都预先解出来，将各种情况下的最大概率译码输出列成一个况下的最大概率译码输出列成一个标准阵列译码表标准阵列译码表。这样，在。这样，在实际译码时就不必解方程，只要查译码表就可以了。实际译码时就不必解方程，只要查译码表就可以了。差错图案差错图案E E的求解的求解依据依据26 伴随式伴随式S的数目是有限的的数目是有限的2n-k个，如果个，如果n-k不太大不太大，我们可，我们可 以预先把不同以预先把不同S下的方程组解出来，把各种情况下的最大概下的方程组解出来，把各种情况下的最大概 率译码输出率译码输出列成一个码表列成一个码表。这样，在实时译码时就不必再。这样，在实时译码时就不必再

17、 去解方程，而只要象查字典那样查一下码表就可以了。这去解方程，而只要象查字典那样查一下码表就可以了。这 样构造的表格叫做样构造的表格叫做标准阵列译码表标准阵列译码表。表中所列码字是接收到的码字表中所列码字是接收到的码字R；将将没有任何差错没有任何差错时的收码时的收码R放在第一行，放在第一行，收码等于发码收码等于发码R=C(C Ci,i=0,1,2k-1),差错图案为全零差错图案为全零E0=(0,00)，伴随，伴随式为全零式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有 2k 列列。标准阵列译码表标准阵列译码表的构成的构成27 在在第第2到第到第n+1的的n行中差错图案

18、的所有行中差错图案的所有重量为重量为1(共共n个个)。如果如果(1+n)2n-k，再在下面行写出全部带有，再在下面行写出全部带有2个差错的图个差错的图案案(共共 n 个个)。2 如果如果总行数总行数(1+n+差错的图案，以此类推，直到放满差错的图案，以此类推，直到放满2n-k行，每行一个行，每行一个Ej,对应一个不同的伴随式对应一个不同的伴随式Sj。这样，表的。这样，表的行数行数2n-k正好等正好等于伴随式的数目于伴随式的数目。n 2 2 )仍然仍然小于小于2n-k，再列出带有，再列出带有3个个 标准阵列译码表标准阵列译码表的构成的构成28标准阵列译码表标准阵列译码表29解：解：(1)构造标准

19、阵列译码表。分别以信息组构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是设收码设收码R=(10101)，构造，构造标准阵列译码表标准阵列译码表，译出发码，译出发码i的估值的估值 c 求出校验矩阵：求出校验矩阵：例例6-36-330列出方程组：列出方程组：s2 e4h24 e3h23 e2h22 e1h21 e0h20 e4 e3 e2s1 e4h14 e3h13 e2h

20、12 e1h11 e0h10 e4 e1s0 e4h04 e3h03 e2h02 e1h01 e0h00 e4 e3 e0由由RHT确定确定S后，对应的后，对应的E可以有可以有2k(22=4)个解，究竟取哪一个解，究竟取哪一个作为差错图样个作为差错图样E的解的解?最简单明了的处理方法是最简单明了的处理方法是概率译码概率译码，即，即对所有对所有2k个解的重量个解的重量(差错图样差错图样E中中1的个数的个数)进行比较，选择重量进行比较，选择重量最小的作为最小的作为E的估值。由于的估值。由于E=R+C，E重量最小重量最小，就是，就是R和和C的汉的汉明距离最小。明距离最小。例例6-36-331例例6-

21、36-332S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例例6-36-3标准阵列译码表标准阵列译码表33将接收码将接收码R10101译码译码可选以下三种方法

22、之一译码：可选以下三种方法之一译码：直接搜索码表直接搜索码表，查得，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此译码输出取为，因此译码输出取为(10111)。先求先求伴随式伴随式RHT=(10101)HT =(010)=S4，确定，确定S4所所在行，再沿着行对码表作一维搜索找到在行，再沿着行对码表作一维搜索找到(10101),最后最后顺着所在列向上找出码字顺着所在列向上找出码字(10111)。先求出伴随式先求出伴随式RHT=(010)=S4并确定并确定S4所对应的所对应的陪集陪集首首（差错图案差错图案）E4=(00010)，再将，再将陪集首与收码陪集首与收码相加相加得

23、到码字得到码字C=R+E4=(10101)+(00010)=(10111)。例例6-36-334对例对例 6-3的分析的分析在制定标准阵列译码表的过程中，由在制定标准阵列译码表的过程中，由S决定差错图案决定差错图案E时只有前时只有前6行真正体现了最大似然译码准则，而第行真正体现了最大似然译码准则，而第7、8行行的差错图案选择不是唯一的。比如第的差错图案选择不是唯一的。比如第7行可有行可有(00011)和和(10100)两个选择，如果当时选的不是两个选择，如果当时选的不是(00011)而是而是(10100)，那么码表第那么码表第7行就不是现在这样了。那么在译码时最后的行就不是现在这样了。那么在译

24、码时最后的结果也就不一样了。结果也就不一样了。为什么会出现这种情况呢？为什么会出现这种情况呢？伴随式的个数伴随式的个数2n-k与与n、k及纠错能力及纠错能力t 有一定的数量关系。有一定的数量关系。例例6-36-335 N重码矢重码矢c=(cn-1,c n-2,c1,c0)可与可与N维矢量空间维矢量空间XN中的中的一个点对应一个点对应，全体码字所对应的点构成，全体码字所对应的点构成矢量空间里的一个子集矢量空间里的一个子集 发码一定在这个子集里，传输发码一定在这个子集里，传输无误时无误时的收码也的收码也一定位于该子集一定位于该子集 当出现差错时，接收的当出现差错时，接收的N重矢量重矢量:对应到子集

25、对应到子集外空间某一点外空间某一点 对应到该子集，却对应到该子集的对应到该子集，却对应到该子集的另一点上另一点上6.3.3码距码距、纠错能力、纠错能力、MDC码及重量谱码及重量谱36dmin=3td=7d=5C1C2C3C4C5 码集各码字间的距离是码集各码字间的距离是不同的，码距最小者不同的，码距最小者决决定码的特性定码的特性，称之为，称之为最最小距离小距离dmin 这里这里dmin=3，纠错能力，纠错能力是是1，检错能力是，检错能力是2码距码距37dmin=min w(C i)C i C 及及C i 0 定理定理6.1 任何最小距离任何最小距离dmin的线性分组码，其的线性分组码，其检错能

26、力检错能力为为（dmin-1）,纠错能力纠错能力t为为 最小距离最小距离dmin表明码集中各码字差异的程度，差异越大越表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力就越强，是衡量分组码性能的最容易区分，抗干扰能力就越强，是衡量分组码性能的最重要的指标之一。重要的指标之一。定理定理6.2 线性分组码的线性分组码的最小距离最小距离等于码集中等于码集中非零码字非零码字的的最最小重量小重量纠错能力纠错能力38于于(n-k+1),即即dmin (n-k+1)定理定理6.3 (n,k)线性分组码最小距离等于线性分组码最小距离等于dmin的的充充要条件要条件是：校验矩阵是：校验矩阵H中有中有（d

27、min-1)列线性无关。列线性无关。定理定理6.4 (n,k)线性分组码的最小距离必定线性分组码的最小距离必定小于等小于等纠错能力纠错能力39例：例：H(7，4)线性码线性码各列都不相同，任意各列都不相同，任意2列之和不等于列之和不等于0，2列列线性无关线性无关；任意；任意2列之和一定等于矩阵中某一列之和一定等于矩阵中某一列，列，任意任意3列线性相关列线性相关。所以该码的。所以该码的最小距离最小距离为为3，小于，小于n-k+14。纠错能力纠错能力40d0 2t 1(1)为为检测检测e个错码，要求最小码距个错码，要求最小码距d0 e 1(2)为为纠正纠正t个错码，要求最小码距个错码，要求最小码距

28、(3)为为纠正纠正t个错码，同时个错码，同时检测检测e个错码，要求最小码距个错码，要求最小码距d0 t e 1最小码距与检错能力图示最小码距与检错能力图示41 （n,k）线性码最小距离）线性码最小距离dmin的上边界是的上边界是n-k我们设计的（我们设计的（n,k）线性码的）线性码的dmin达到了达到了n-k达到了设计性能的极点。因此，达到了设计性能的极点。因此，dmin n-k为为极大最小距离码极大最小距离码 (MDC Maximized+1。如果。如果+1，就是，就是+1的码称的码称minimum Distance Code)。(1)二进制码中，除了将一位信息重复二进制码中，除了将一位信息

29、重复n 次的次的（n,1）码外，不存在其它二进制码外，不存在其它二进制MDC码；码；(2)非二进制码中，非二进制码中，MDC码是存在的，如码是存在的，如RS码码 （reed-solomon)。MDC码码(Maximized minimum Distance Code)42 含义：在码长含义：在码长n的码集里，包含重量为的码集里，包含重量为0的码字的码字A0个，个，重量为重量为1的码字的码字A1个，个，-，重量为，重量为n的码字的码字An个。个。纠错能力纠错能力t只是说明距离只是说明距离t的差错一定能纠，的差错一定能纠，并非说并非说距距离大于离大于t的差错一定不能纠。（除非完备码）的差错一定不能

30、纠。（除非完备码）总体的、平均的纠错能力不但与总体的、平均的纠错能力不但与最小距离最小距离有关，而且有关，而且与与其余码距其余码距或者说与码字的或者说与码字的重量分布特性重量分布特性有关。把码有关。把码距（码重）的分布特性称为距（码重）的分布特性称为距离（重量）谱距离（重量）谱，其中最，其中最小重量就是小重量就是dmin。当所有码距相差不大时（重量谱为。当所有码距相差不大时（重量谱为窄谱），性能较好。重量谱多项式表示：窄谱），性能较好。重量谱多项式表示：重量谱重量谱43 任何一个二元任何一个二元(n,k)线性分组码都有线性分组码都有2n-k个伴随式，假如个伴随式，假如该码的纠错能力是该码的纠错

31、能力是t，则对于任何一个重量小于等于，则对于任何一个重量小于等于t的的差错图案，都应有一个伴随式与之对应，也就是说，差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件伴随式的数目满足条件 上式称作上式称作汉明限汉明限，任何一个纠，任何一个纠t码都应满足上述码都应满足上述条件。条件。6.3.4完备码完备码(Perfect code)44 某二元某二元(n,k)线性分组码能使等式线性分组码能使等式成立，成立，即该码的伴随式数目不多不少恰好和不大于即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等个差错的图案数目相等，相当于在标准译码阵列中能，相当于在标准译码阵列中能将所有

32、重量不大于将所有重量不大于t的的差错图案差错图案选作选作陪集首陪集首，而没有一，而没有一个陪集首的重量大于个陪集首的重量大于t，这时的校验位得到最充分的利，这时的校验位得到最充分的利用。这样的二元用。这样的二元(n,k)线性分组码称为线性分组码称为完备码完备码。2n kti 0 n I 完备码完备码45汉明码的汉明码的纠错能力纠错能力t=1，既有二进制的，也有非二进制，既有二进制的，也有非二进制的。二进制时，汉明码码长的。二进制时，汉明码码长n和信息位和信息位k服从以下规律：服从以下规律：(n,k)=(2m-1,2m-1-m)，其中其中m=n-k，是正整数。，是正整数。当当m3、4、5、6、7

33、、8时，有汉明码时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)汉明码是完备码汉明码是完备码，因为它满足上述等式。，因为它满足上述等式。汉明码汉明码(Hamming Code)46汉明码的校验矩阵汉明码的校验矩阵H具有特殊的性质，能使具有特殊的性质，能使构造方法简化。一个构造方法简化。一个(n,k)码的校验矩阵有码的校验矩阵有nk行和行和n列，二进制时列，二进制时n-k个码元所能组成的列矢个码元所能组成的列矢量总数是量总数是2n-k-1=2m-1=n,恰好和校验矩阵的恰好和校验矩阵的列列数相等数相等。只要排列所有列，通过。只要排列所有列，通过列置换列置换将矩阵将矩阵H转换成转换成系统形式系统形式，就可以进一步得到相应的，就可以进一步得到相应的生成矩阵生成矩阵G。汉明码校验矩阵的构成汉明码校验矩阵的构成47例例6-46-448高莱码高莱码49 6-3 6-6作业作业50