信息论与编码-第六章2.ppt

《信息论与编码-第六章2.ppt》由会员分享，可在线阅读，更多相关《信息论与编码-第六章2.ppt（58页珍藏版）》请在三一文库上搜索。

1、信息论与编码-线性分组码,上次课小结： 信道编码定理： 差错控制的途径 增加码长、增加带宽、提高信噪比、噪声均化 码距与检错纠错的关系,信息论与编码-线性分组码,最优译码与最大似然译码 最优译码： 最大似然译码： 汉明距离、码字重量,信息论与编码-线性分组码,一、线性分组码的基本概念 分组码是建立在码的代数结构基础上的，所以对分组码的讨论和分析需要一定的代数基础。在这里我们不准备系统地学习代数知识，只介绍一些相关的内容。,信息论与编码-线性分组码,域（Field）的概念 域是定义了两种代数运算的系统。 所谓代数系统，是指满足一定规律或定律的系统，系统中有一群元素构成的集合、定义了一些运算等。

2、在域中定义的两种算术运算是：,信息论与编码-线性分组码,（i）加法： 集合F在加法运算下是封闭的，即如果 必有 。 满足加法结合率，即 集合中一定包含一个零元素，满足 集合中每个元素都有其逆元素，元素a的逆记为-a，有a+(-a)=a-a=0,信息论与编码-线性分组码,（ii）乘法： 集合F在乘法运算下是封闭的，即如果 ，则必有 满足乘法结合率，即 满足乘法交换率，即 满足乘法分配率，即 集合中一定有一个单位元I，对任何 有 除零元素外，集合中每一个元素都有逆元素。,信息论与编码-线性分组码,当域由有限个元素组成时，叫做有限域，也称为伽罗华（Galois Field）域，记为GF(q)，其中q

3、是域中元素的个数。 例如，集合0，1对加法和乘法（不包含零元）都是模2的运算构成一个域GF（2）。 集合0，1，2，3，4对加法和乘法（不包含零元）都是模5的运算构成一个域GF（5）。,信息论与编码-线性分组码,（2）矢量空间 由初等数学可知，平面上的二维矢量的全体构成一个二维的矢量空间，空间的三维矢量全体构成三维矢量空间。推广可以得到一般的n维矢量 空间。,信息论与编码-线性分组码,在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重线性无关的矢量可以构成一个n维矢量空间。 取其中的k个可以张成n维空间的一个子空间。例如：由（1，0，0）， （0，1，0），（0，0，1）

4、为基底可以张成一个三维三重空间，取其中的两个为基底可以构成一个二维三重空间。 以互相正交的基底张成的两个空间也正交，并互称为另一个空间的零空间。这两个空间对偶。,信息论与编码-线性分组码,线性分组码 一个n，k分组码，是把信息划成k个为一段（称为信息组），通过编码器变成长为n个码元的一组，作为n，k分组码的一个码字。则共可能有 个码字。 如果这些码字集合组成一个k维线性空间，则称它是一个n，k线性分组码。,信息论与编码-线性分组码,对于线性分组码，如果 是码字，则 必定也是码字。其中 是码元字符集里的任意两个元素。 因为一个定义了加法的域一定有零元素，如果取 ，则得到的码字一定是全零码。因此，

5、线性分组码一定包含全零码。 因此：,信息论与编码-线性分组码,也就是说： （i）两个码字之间的距离必定等于另一个码字的重量，所以线性分组码的最小码距 等于码集中非零码字的最小重量： （ii）研究两两码字之间的距离，可用码字与全零码的距离，或各码字自身的重量来代替。,信息论与编码-线性分组码,对于n，k二进制分组码，共有 个码字，可以看成是n维n重空间S的一个子空间。这个子空间是由k个基底张成的，记作码空间C，它是一个k维n重空间。n维n重空间的另外n-k个基底则张成一个n-k维的子空间，称为校验空间H。分组编码器的工作，就是要把k维k重的信息组空间的 个矢量一一对应到k维n重码空间C。因此，编

6、码算法就要研究两个问题： （i）如何确定码空间C，和（ii）如何映射。,信息论与编码-线性分组码,二、生成矩阵和校验矩阵 n，k分组码的编码问题就是要在n维线性空间中，找出满足一定要求的由 个矢量组成的k维n重线性子空间，或者说，要由k个信息码元得到n-k个冗余码元。 设 是一组k个信息组，可以写成矢量形式 。编码器输出的是k维n重码空间C的一个矢量，记为 。因此有,信息论与编码-线性分组码,对二进制分组码来说， 。上式也可以写成矩阵形式： 其中， 均为一个含有n个元素的行向量。所以有,信息论与编码-线性分组码,G是一个k行n列的矩阵，给定任何k码元的信息比特，都可以由G利用公式 求出对应的码

7、字，因此，G被称为码的生成矩阵。 可以看出，任何码子都是G的行矢量的线性组合，即 从矢量空间的角度来说，G的k个行矢量相当于k维n重码字矢量空间的一组基底，该空间的任何矢量（码字）都可以由这组基底的线性组合得到。并且这组基底本身也是一组码字。,信息论与编码-线性分组码,一般形式的G，得到的码字前k位的信息位也发生了变化，而一般来说，我们只是希望在信息位后加上冗余比特，所以，可以对生成矩阵通过行运算（以及列置换）作适当的变换，变成“系统形式”，即 这样生成的（n，k）码是系统码。,信息论与编码-线性分组码,与码空间C相对应，一定存在一个对偶空间H。对偶空间H的基底，是n维n重矢量空间的基底中，除

8、去张成k维码字空间C的k个基底，而剩下的n-k个基底。因此，H空间和C空间一定正交。即 生成矩阵的每一行，都是一个码字，所以有,信息论与编码-线性分组码,因此 H叫做码字空间C的校验矩阵，可以利用 是否等于零矢量，来判断一个 是不是码字。 例题：对一个（7，4）码，其生成矩阵为,信息论与编码-线性分组码,（1）对于信息组(1 0 1 1 )，对应码字是什么？ （2）设计一个（7，4）分组编码器原理图。 （3）若接收到一个7位码r=（1 0 0 1 1 0 1），判断它是否是码字。 解：（1）由生成矩阵可知，得到的一定是系统码。由 得,信息论与编码-线性分组码,将信息位的值代入，得： ，因此，编

9、得的码字为 。注意加法是模2加。 （2）由编码后冗余位与信息位的关系，可得编码器的原理图如图所示：,输入,输出,信息论与编码-线性分组码,（3）要检验一个码序列R是否是码字，可以使用校验矩阵H，如果 ，则一定是码字，否则一定不是码字。 因此， 就产生三个方程，只有第一个为零，另两个不为零，所以R不是码字。 系统码的前k位为信息位，后n-k位为校验位。,信息论与编码-线性分组码,校验矩阵H除了可以用来检验码字外，还与码的最小距离（也就和码的检错纠错能力）有关。 因为 其中， 是H矩阵的列向量。,信息论与编码-线性分组码,因此， 也就是说，n个矢量 一定是线性相关的。 如果分组码的最小距离为 ，则

10、根据线性码的特点，码集里面一定有一个码字其重量最小为 ，即有 个非零元素。将其代入校验矩阵的方程，左边就有 个 项，而右边为零。也就是说， 个 是线性相关的。 而,信息论与编码-线性分组码,个 一定是线性无关的（反证法：如果 个 列矢量是线性相关的，则可以把其对应的系数当成码字，而该码字的重量为 ，这与码字的最小重量为 相矛盾）。 由于H是 的矩阵，其秩最大为n-k，也就是说，最多有n-k个列矢量线性无关。所以,信息论与编码-线性分组码,在编码的时候，我们希望 越大越好。 二进制（n，k）线性码的最小码距的上界是n-k+1。称这样的码为极大最小距离码（MDC:Maximized minimum

11、 Distance Code）。,信息论与编码-线性分组码,本节讨论如何用伴随式译码 伴随式 设发送的码字为 通过有扰信道传输，信道产生的错误图样为 收端译码器收到的n重矢量为,信息论与编码-线性分组码,R=C+E，译码器的任务就是要从收到的R中得出 ，或者由R中解出错误图样 ，从而得到 ，并使译码错误概率最小。对于二进制码字，模2减与模2加等同。 对于n，k分组码C，满足 ，因此 若E=0，则 ，若 ，并且仅与错误图样E有关，而与发送什么码字无关。,信息论与编码-线性分组码,令 S称为接收矢量R的伴随式（校正子）。伴随式完全由E决定，它充分反映了信道的干扰情况。译码器的主要任务就是如何从S中

12、得到最象E的错误图样 ，从而译出 。 S与E是否有一一对应的关系？ 如果一个n，k译码器要纠正t个错误，则要求对于错误个数 的所有可能组合的错误图样，都应该有不同的伴随式与之对应。,信息论与编码-线性分组码,2. 标准阵列 由前面的讨论可知，n，k分组码的译码步骤可 归结为以下三步： （1）由接收到的R，计算伴随式 ； （2）若S=0，则认为接收无误。若 ，则由 S找出错误图样 ； （3）由 和R找出 。 这里最关键的是由S找出E，只要找出的E是正确的，译出的码也是正确的。,信息论与编码-线性分组码,由S的定义式， ，即 共有n-k个方程，但有n个未知量，所以解不唯一。对于二进制，少一个方程导

13、致两个解，少两个方程导致四个解，少k个方程导致有 个解，也就是说，可以解出 个不同的错误图样，从而对应了 个码字（码字的全部可能）。根据最大似然译码规则，应该译成可能性最大的那个码字。,信息论与编码-线性分组码,对于二进制对称信道，若差错概率为p，则错一个比特的概率（ ）大于错两个比特的概率（ ），。所以，应该译成所有 个差错图样中重量最小的那一个。 但如果每接收一个R就要解一次方程组，显然太麻烦了。可以预先把不同S下的方程组解出来，并得到最大概率的那个错误图样，和错误图样对应的R，存成一个表格，译码的时候，只要根据不同的R查表，就可以得到对应的最大可能的码字。,信息论与编码-线性分组码,下表

14、就是一个这样的表，叫做标准阵列译码表。表中有 列，每一列的头一个元素对应的是一个码字，所以共对应 个不同的码字；每一列的列首元素下，是 个禁用码字（即n维空间点中不是码字的那些点），代表该列首元素（码字）在不同差错图样下偏移后所对应的空间点，正好对应了 个不同的伴随式。全部的元素个数是 ，正好是n维矢量空间中总的点数，也就是说，每一个空间点,信息论与编码-线性分组码,都有其所对应的码字，这样，在译码的时候，当接收到一个R后，只要在标准阵列表中找到该R的位置，这一列的列首元素就是它应该译成的码字。,信息论与编码-线性分组码,标准阵列译码表,信息论与编码-线性分组码,表中第一行对应的是 个码字，相

15、当于差错为零；第二行到第n+1行分别对应n个差错为1的差错图样；。每一行的行首元素叫做陪集首，是该行所对应的错误图样。 但是，错误图样数有 个，标准阵列译码表只有 行，代表 个伴随式和错误图样。那么，怎么从 个错误图样中选择 个，作为陪集首？,信息论与编码-线性分组码,原则当然是要使得译码的错误概率最小。前面已经说过，对BSC信道，当错误概率p0.5时，产生一个错误的概率比产生两个错误的概率要大，产生两个错误的概率比产生3个错误的概率要大，。总之，错误图样重量越小，产生的可能性就越大。因此，译码器必须首先保证能正确纠正这些出现可能性比较大的错误图样，这相当于构造标准阵列译码表时，要求按照错误图

16、样重量从轻到重的顺序挑选为陪首集。,信息论与编码-线性分组码,例题：某（5，2）系统线性码的生成矩阵是 设收到的码是R=(10101)，请先构造该码的标准阵列译码表，然后译出发码的估值C。,H=PTI3=,=,s1e1h11+e2h12+e3h13+e4h14+e5h15 = e1+e2+e3 s2 = e1h21+e2h22+e3h23+e4h24+e5h25= e1+e4 s3 = e1h31+e3h32+e3h33+e4h34+e5h35= e1+e2+e5,解：,对应（s1,s2,s3）=(111),e=(10000),(01010),(00111)和 (11101)四种错误图样,信息

17、论与编码-线性分组码,信息论与编码-线性分组码,标准阵列译码表 n-k=3， ，即标准阵列译码表共有8行，每行代表一种错误图样。 按照错误图样重量从轻到重的顺序，无差错（错误图样重量为0）的有一种，重量为1的有 种，重量为2的有 种。 我们挑选的陪首集是1种无错误（重量为0），5种有一个错误（重量为1）和重量为2的10 种里面的2种。,信息论与编码-线性分组码,码字共有 种，将信息组的可能组合(00)、(01)、(10)、(11)代入生成矩阵，得到四个码字为：(00000)、(10111)、(01101)、(11010)。 得到的标准阵列译码表如下图所示：,信息论与编码-线性分组码,标准阵列译

18、码表,信息论与编码-线性分组码,当然，上述的标准阵列译码表不是唯一的，因为从10种重量为2的错误图样中选择两种，可以是任意选的。 标准阵列译码表需要把 个n重存储在译码器中。其复杂性随n的增大指数增长，当n比较大时很不实用。,信息论与编码-线性分组码,可以把标准阵列译码表进行简化，即只存储伴随式和错误图样的对应关系，译码时先计算得到伴随式，再查表得到错误图样，从而得到译码码字。这样码表可以简化，但译码时的计算量增加了。并且当n和k都比较大时，即使采用这种简化的码表，译码器的复杂性还是很高。因此在线性分组码理论中，如何简化译码器是最中心的研究课题之一。,信息论与编码-线性分组码,完备码 对于纠错

19、能力为t的（n，k）分组码，重量小于等于t的错误图样共有 因此，要想纠正t个错误，必须有,信息论与编码-线性分组码,如果伴随式的数目刚好等于重量小于等于t的错误图样的数目，即 则称这样的（n，k）分组码为完备码。 这样每一个错误图样，都有一个不同的伴随式与之对应，每一个伴随式都对应一个不同的错误图样。,信息论与编码-线性分组码,从多维矢量空间的角度来看完备码 假定我们围绕每一个码字ci放置一个半径为t的球，每个球内包含了与该码字汉明距离小于、等于t的所有收码R的集合，这样在半径为t(dmin-1)/2的球内的收码数是,。,信息论与编码-线性分组码,因为有2k个可能发送的码字，也就有2k个不相重

20、叠的半径为t的球。包含在2k个球中的码字总数不会超过2n个可能的接收码字。于是一个纠t差错的码必然满足不等式 2k 2n 即 2n-k,信息论与编码-线性分组码,如果等号成立，表示所有的收码都落在2k个球内，而球外没有一个码，这就是完备码。 完备码具有下述特性：围绕个码字、汉明距离为t=（dmin-1）/2的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码离发码的距离至多为t，这时所有的重量t的差错图案都能用最佳（最小距离）译码器得到纠正，而所有重量t+1的差错图案都不能纠正。,信息论与编码-线性分组码,完备码并不多见，迄今发现的完备码有t=1的汉明码，t=3的高莱码，以及长度

21、n为奇数、由两个码字组成、满足dmin=n的任何二进制码，还有三进制t=3的（11，6）码。,信息论与编码-线性分组码,汉明码是一类码的总称。汉明码的纠错能力t=1。对于二进制汉明码，码长n和信息位k满足 其中，m=n-k是正整数。汉明码是完备码。 汉明码校验矩阵H具有特殊的性质。一个（n，k）码的校验矩阵有n-k行和n列，二进制时n-k个校验码元能够组成的列矢量总数为（全零矢量除外） ，对于二进制汉明码，恰好等于校验矩阵的列数 。,信息论与编码-线性分组码,例题：构造一个m=3的二元汉明码。 所谓构造一个码，就是求出其生成矩阵G。 m=3时，n=7，n-k=4,即（7，4）汉明码，所以汉明码

22、的校验矩阵H为 即各列均不相等，一个错误时，伴随式与列对应，从而可知错误的位置。,信息论与编码-线性分组码,经列置换化成系统形式为 所以生成矩阵G为,信息论与编码-线性分组码,二进制汉明码的概念也可以扩展到多进制，即GF（q）域上的汉明码。在q进制中，一个码元上的差错位置就可以有（q-1）种，n个码元上的差错位置有n（q-1）种。而（n-k）个校验位可以表达 个不同的意思，由汉明码定义，它应该恰好等于所有的单个差错图案加上1（无差错），即 =n(q-1)+1。令n-k=m，则q进制汉明码的n，k应服从,信息论与编码-线性分组码,高莱（Golay）码是二进制（23，12）线性码，其最小距离 纠错能力t=3。由于满足 因此它也是完备码。,信息论与编码-线性分组码,需要指出的是，完备码是标准阵列最规则因而译码最简单的码，但并不一定是纠错能力最强的码。要想使其纠错能力最强，还要保证达到极大最小码距码MDC 的要求。,码重分布及意义 汉明码 （7，4）汉明码,信息论与编码-线性分组码,本课小结： 线性分组码的基本概念 生成矩阵和校验矩阵 译码与伴随式 标准阵列译码表 习题：6-3，6-6,信息论与编码-线性分组码,