信息论与编码第六章.ppt

信息论与编码第六章现在学习的是第1页，共55页信息论与编码-线性分组码 最优译码与最大似然译码 最优译码： 最大似然译码： 汉明距离、码字重量)/(max2 , 2 , 1RCpCiiik)/(max2, 2, 1iiiCRpCk现在学习的是第2页，共55页信息论与编码-线性分组码一、线性分组码的基本概念分组码是建立在码的代数结构基础上的，所以对分组码的讨论和分析需要一定的代数基础。在这里我们不准备系统地学习代数知识，只介绍一些相关的内容。现在学习的是第3页，共55页信息论与编码-线性分组码域（Field）的概念域是定义了两种代数运算的系统。所谓代数系统，是指满足一定规律或定律的系统，系统中有一群元素构成的集合、定义了一些运算等。在域中定义的两种算术运算是：现在学习的是第4页，共55页信息论与编码-线性分组码（i）加法：o 集合F在加法运算下是封闭的，即如果 必有 。o 满足加法结合率，即o 集合中一定包含一个零元素，满足o 集合中每个元素都有其逆元素，元素a的逆记为-a，有a+(-a)=a-a=0,FbaFbaabbaaa0现在学习的是第5页，共55页信息论与编码-线性分组码（ii）乘法：o 集合F在乘法运算下是封闭的，即如果 ，则必有o 满足乘法结合率，即o 满足乘法交换率，即o 满足乘法分配率，即o 集合中一定有一个单位元I，对任何 有o 除零元素外，集合中每一个元素都有逆元素。,FbaFabcabbca)()(baab bcaccba )(,FaaaI 现在学习的是第6页，共55页信息论与编码-线性分组码当域由有限个元素组成时，叫做有限域，也称为伽罗华（Galois Field）域，记为GF(q)，其中q是域中元素的个数。例如，集合0，1对加法和乘法（不包含零元）都是模2的运算构成一个域GF（2）。 集合0，1，2，3，4对加法和乘法（不包含零元）都是模5的运算构成一个域GF（5）。现在学习的是第7页，共55页信息论与编码-线性分组码（2）矢量空间由初等数学可知，平面上的二维矢量的全体构成一个二维的矢量空间，空间的三维矢量全体构成三维矢量空间。推广可以得到一般的n维矢量空间。nRV现在学习的是第8页，共55页信息论与编码-线性分组码在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重线性无关的矢量可以构成一个n维矢量空间。取其中的k个可以张成n维空间的一个子空间。例如：由（1，0，0）， （0，1，0），（0，0，1）为基底可以张成一个三维三重空间，取其中的两个为基底可以构成一个二维三重空间。以互相正交的基底张成的两个空间也正交，并互称为另一个空间的零空间。这两个空间对偶。现在学习的是第9页，共55页信息论与编码-线性分组码线性分组码一个n，k分组码，是把信息划成k个为一段（称为信息组），通过编码器变成长为n个码元的一组，作为n，k分组码的一个码字。则共可能有 个码字。如果这些码字集合组成一个k维线性空间，则称它是一个n，k线性分组码。k2现在学习的是第10页，共55页信息论与编码-线性分组码 对于线性分组码，如果 是码字，则 必定也是码字。其中 是码元字符集里的任意两个元素。因为一个定义了加法的域一定有零元素，如果取 ，则得到的码字一定是全零码。因此，线性分组码一定包含全零码。因此：jiCC、jiCC2121、021),()()(),(0kkjijiCdisCWCCWCCdisd现在学习的是第11页，共55页信息论与编码-线性分组码也就是说：（i）两个码字之间的距离必定等于另一个码字的重量，所以线性分组码的最小码距 等于码集中非零码字的最小重量：（ii）研究两两码字之间的距离，可用码字与全零码的距离，或各码字自身的重量来代替。mindmin0,miniCCCCWdii现在学习的是第12页，共55页信息论与编码-线性分组码对于n，k二进制分组码，共有 个码字，可以看成是n维n重空间S的一个子空间。这个子空间是由k个基底张成的，记作码空间C，它是一个k维n重空间。n维n重空间的另外n-k个基底则张成一个n-k维的子空间，称为校验空间H。分组编码器的工作，就是要把k维k重的信息组空间的 个矢量一一对应到k维n重码空间C。因此，编码算法就要研究两个问题：（i）如何确定码空间C，和（ii）如何映射。k2k2现在学习的是第13页，共55页信息论与编码-线性分组码二、生成矩阵和校验矩阵n，k分组码的编码问题就是要在n维线性空间中，找出满足一定要求的由 个矢量组成的k维n重线性子空间，或者说，要由k个信息码元得到n-k个冗余码元。设 是一组k个信息组，可以写成矢量形式 。编码器输出的是k维n重码空间C的一个矢量，记为 。因此有k2kmmm,21),(21kmmmm),(21iniiiCCCCnjgmgmgmCkjkjjij, 2 , 1,2211现在学习的是第14页，共55页信息论与编码-线性分组码对二进制分组码来说， 。上式也可以写成矩阵形式：其中， 均为一个含有n个元素的行向量。所以有1 , 0ijgTkiniimmmccc),(),(),(2121k21igggmGCk21ggg,knknggggG1111现在学习的是第15页，共55页信息论与编码-线性分组码G是一个k行n列的矩阵，给定任何k码元的信息比特，都可以由G利用公式 求出对应的码字，因此，G被称为码的生成矩阵。可以看出，任何码子都是G的行矢量的线性组合，即从矢量空间的角度来说，G的k个行矢量相当于k维n重码字矢量空间的一组基底，该空间的任何矢量（码字）都可以由这组基底的线性组合得到。并且这组基底本身也是一组码字。mGCik21igggCkmmm21现在学习的是第16页，共55页信息论与编码-线性分组码一般形式的G，得到的码字前k位的信息位也发生了变化，而一般来说，我们只是希望在信息位后加上冗余比特，所以，可以对生成矩阵通过行运算（以及列置换）作适当的变换，变成“系统形式”，即这样生成的（n，k）码是系统码。)()(2)( 12221212111100010001)(knkknknkkpppppppppGPIk现在学习的是第17页，共55页信息论与编码-线性分组码与码空间C相对应，一定存在一个对偶空间H。对偶空间H的基底，是n维n重矢量空间的基底中，除去张成k维码字空间C的k个基底，而剩下的n-k个基底。因此，H空间和C空间一定正交。即生成矩阵的每一行，都是一个码字，所以有0HCTi0GHT现在学习的是第18页，共55页信息论与编码-线性分组码因此H叫做码字空间C的校验矩阵，可以利用 是否等于零矢量，来判断一个 是不是码字。例题：对一个（7，4）码，其生成矩阵为)(knTIPHTiHCiC1101000011010011100101010001G现在学习的是第19页，共55页信息论与编码-线性分组码（1）对于信息组(1 0 1 1 )，对应码字是什么？（2）设计一个（7，4）分组编码器原理图。（3）若接收到一个7位码r=（1 0 0 1 1 0 1），判断它是否是码字。解：（1）由生成矩阵可知，得到的一定是系统码。由 得mGCi421743263215mmmcmmmcmmmciii现在学习的是第20页，共55页信息论与编码-线性分组码将信息位的值代入，得： ，因此，编得的码字为 。注意加法是模2加。（2）由编码后冗余位与信息位的关系，可得编码器的原理图如图所示：0, 0, 0765iiiccc)1011000(iC1m2m3m4m7ic6ic5ic输入输出现在学习的是第21页，共55页信息论与编码-线性分组码（3）要检验一个码序列R是否是码字，可以使用校验矩阵H，如果 ，则一定是码字，否则一定不是码字。因此， 就产生三个方程，只有第一个为零，另两个不为零，所以R不是码字。系统码的前k位为信息位，后n-k位为校验位。0TRH100101101011100010111)(knTIPHTRH现在学习的是第22页，共55页信息论与编码-线性分组码校验矩阵H除了可以用来检验码字外，还与码的最小距离（也就和码的检错纠错能力）有关。因为其中， 是H矩阵的列向量。),()(2)(1 )(2222111211n21hhhHnknknknnnhhhhhhhhhn21hhh,现在学习的是第23页，共55页信息论与编码-线性分组码因此，也就是说，n个矢量 一定是线性相关的。如果分组码的最小距离为 ，则根据线性码的特点，码集里面一定有一个码字其重量最小为 ，即有 个非零元素。将其代入校验矩阵的方程，左边就有 个 项，而右边为零。也就是说， 个 是线性相关的。 而TnT2T1TihhhHCiniiccc21ThjmindmindmindmindThjmindThj现在学习的是第24页，共55页信息论与编码-线性分组码 个 一定是线性无关的（反证法：如果 个 列矢量是线性相关的，则可以把其对应的系数当成码字，而该码字的重量为 ，这与码字的最小重量为 相矛盾）。由于H是 的矩阵，其秩最大为n-k，也就是说，最多有n-k个列矢量线性无关。所以1mindThj1mindThj1mindmindnkn )(1,1minminkndknd即现在学习的是第25页，共55页信息论与编码-线性分组码在编码的时候，我们希望 越大越好。二进制（n，k）线性码的最小码距的上界是n-k+1。称这样的码为极大最小距离码（MDC:Maximized minimum Distance Code）。mind现在学习的是第26页，共55页信息论与编码-线性分组码 本节讨论如何用伴随式译码 伴随式设发送的码字为 通过有扰信道传输，信道产生的错误图样为收端译码器收到的n重矢量为 ),(110NcccC),(110NeeeE),(110NrrrR现在学习的是第27页，共55页信息论与编码-线性分组码 R=C+E，译码器的任务就是要从收到的R中得出 ，或者由R中解出错误图样 ，从而得到 ，并使译码错误概率最小。对于二进制码字，模2减与模2加等同。对于n，k分组码C，满足 ，因此若E=0，则 ，若 ，并且仅与错误图样E有关，而与发送什么码字无关。EERC0CHTTTTEHHECRH)(0RHT0RH0ET则,C现在学习的是第28页，共55页信息论与编码-线性分组码令S称为接收矢量R的伴随式（校正子）。伴随式完全由E决定，它充分反映了信道的干扰情况。译码器的主要任务就是如何从S中得到最象E的错误图样 ，从而译出 。S与E是否有一一对应的关系？如果一个n，k译码器要纠正t个错误，则要求对于错误个数 的所有可能组合的错误图样，都应该有不同的伴随式与之对应。EERCtTTEHRHS现在学习的是第29页，共55页信息论与编码-线性分组码2. 标准阵列由前面的讨论可知，n，k分组码的译码步骤可归结为以下三步：（1）由接收到的R，计算伴随式 ；（2）若S=0，则认为接收无误。若 ，则由 S找出错误图样 ；（3）由 和R找出 。这里最关键的是由S找出E，只要找出的E是正确的，译出的码也是正确的。TRHS 0S EEERC现在学习的是第30页，共55页信息论与编码-线性分组码由S的定义式， ，即共有n-k个方程，但有n个未知量，所以解不唯一。对于二进制，少一个方程导致两个解，少两个方程导致四个解，少k个方程导致有 个解，也就是说，可以解出 个不同的错误图样，从而对应了 个码字（码字的全部可能）。根据最大似然译码规则，应该译成可能性最大的那个码字。Tnknnknnknhhhheeesss)(11 )(112121),(),(k2k2k2TEHS 现在学习的是第31页，共55页信息论与编码-线性分组码对于二进制对称信道，若差错概率为p，则错一个比特的概率（ ）大于错两个比特的概率（ ），。所以，应该译成所有 个差错图样中重量最小的那一个。但如果每接收一个R就要解一次方程组，显然太麻烦了。可以预先把不同S下的方程组解出来，并得到最大概率的那个错误图样，和错误图样对应的R，存成一个表格，译码的时候，只要根据不同的R查表，就可以得到对应的最大可能的码字。1)1 (npp22)1 (nppk2现在学习的是第32页，共55页信息论与编码-线性分组码下表就是一个这样的表，叫做标准阵列译码表。表中有 列，每一列的头一个元素对应的是一个码字，所以共对应 个不同的码字；每一列的列首元素下，是 个禁用码字（即n维空间点中不是码字的那些点），代表该列首元素（码字）在不同差错图样下偏移后所对应的空间点，正好对应了 个不同的伴随式。全部的元素个数是 ，正好是n维矢量空间中总的点数，也就是说，每一个空间点k2k2kn2kn2nkkn222现在学习的是第33页，共55页信息论与编码-线性分组码都有其所对应的码字，这样，在译码的时候，当接收到一个R后，只要在标准阵列表中找到该R的位置，这一列的列首元素就是它应该译成的码字。现在学习的是第34页，共55页信息论与编码-线性分组码 标准阵列译码表11ES 22ES jjES knkn22ES00011 CE212ECEjjECE1knknECE212221CCE22CE 2CEj22CEkniCE 2ijCE iCEkn2iiCCE1kkCCE221kCE22kCEj2kknCE22现在学习的是第35页，共55页信息论与编码-线性分组码表中第一行对应的是 个码字，相当于差错为零；第二行到第n+1行分别对应n个差错为1的差错图样；。每一行的行首元素叫做陪集首，是该行所对应的错误图样。但是，错误图样数有 个，标准阵列译码表只有 行，代表 个伴随式和错误图样。那么，怎么从 个错误图样中选择 个，作为陪集首？n2k2n2kn2kn2kn2现在学习的是第36页，共55页信息论与编码-线性分组码原则当然是要使得译码的错误概率最小。前面已经说过，对BSC信道，当错误概率p0.5时，产生一个错误的概率比产生两个错误的概率要大，产生两个错误的概率比产生3个错误的概率要大，。总之，错误图样重量越小，产生的可能性就越大。因此，译码器必须首先保证能正确纠正这些出现可能性比较大的错误图样，这相当于构造标准阵列译码表时，要求按照错误图样重量从轻到重的顺序挑选为陪首集。现在学习的是第37页，共55页信息论与编码-线性分组码例题：某（5，2）系统线性码的生成矩阵是设收到的码是R=(10101)，请先构造该码的标准阵列译码表，然后译出发码的估值C。1101111001G现在学习的是第38页，共55页H=PTI3=100110100100111=hhhhhhhhhhhhhhh353433323125242322211514131211 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)四种错误图样信息论与编码-线性分组码现在学习的是第39页，共55页信息论与编码-线性分组码标准阵列译码表 n-k=3， ，即标准阵列译码表共有8行，每行代表一种错误图样。按照错误图样重量从轻到重的顺序，无差错（错误图样重量为0）的有一种，重量为1的有 种，重量为2的有 种。我们挑选的陪首集是1种无错误（重量为0），5种有一个错误（重量为1）和重量为2的10 种里面的2种。8231025515现在学习的是第40页，共55页信息论与编码-线性分组码码字共有 种，将信息组的可能组合(00)、(01)、(10)、(11)代入生成矩阵，得到四个码字为：(00000)、(10111)、(01101)、(11010)。得到的标准阵列译码表如下图所示：4222k现在学习的是第41页，共55页信息论与编码-线性分组码标准阵列译码表 S1=000E1=00000C2=10111C3=01101C4=11010 S2=111E2=10000 00111 11101 01010 S3=101E3=01000 11111 00101 10010 S4=100E4=00100 10011 01001 11110 S5=010E5=00010 10101 01111 11000 S6=001E6=00001 10110 01100 11011 S7=011E7=00011 10100 01110 11001 S8=110E8=00110 10001 01011 11100现在学习的是第42页，共55页信息论与编码-线性分组码当然，上述的标准阵列译码表不是唯一的，因为从10种重量为2的错误图样中选择两种，可以是任意选的。标准阵列译码表需要把 个n重存储在译码器中。其复杂性随n的增大指数增长，当n比较大时很不实用。n2现在学习的是第43页，共55页信息论与编码-线性分组码可以把标准阵列译码表进行简化，即只存储伴随式和错误图样的对应关系，译码时先计算得到伴随式，再查表得到错误图样，从而得到译码码字。这样码表可以简化，但译码时的计算量增加了。并且当n和k都比较大时，即使采用这种简化的码表，译码器的复杂性还是很高。因此在线性分组码理论中，如何简化译码器是最中心的研究课题之一。现在学习的是第44页，共55页信息论与编码-线性分组码 完备码 对于纠错能力为t的（n，k）分组码，重量小于等于t的错误图样共有因此，要想纠正t个错误，必须有tnnninti100tnnnintikn1020现在学习的是第45页，共55页信息论与编码-线性分组码如果伴随式的数目刚好等于重量小于等于t的错误图样的数目，即则称这样的（n，k）分组码为完备码。这样每一个错误图样，都有一个不同的伴随式与之对应，每一个伴随式都对应一个不同的错误图样。tiknin02现在学习的是第46页，共55页信息论与编码-线性分组码o 从多维矢量空间的角度来看完备码 o 假定我们围绕每一个码字ci放置一个半径为t的球，每个球内包含了与该码字汉明距离小于、等于t的所有收码R的集合，这样在半径为t(dmin-1)/2的球内的收码数是 tiin0现在学习的是第47页，共55页信息论与编码-线性分组码因为有2k个可能发送的码字，也就有2k个不相重叠的半径为t的球。包含在2k个球中的码字总数不会超过2n个可能的接收码字。于是一个纠t差错的码必然满足不等式 2k 2n即 2n-k tiin0tiin0现在学习的是第48页，共55页信息论与编码-线性分组码如果等号成立，表示所有的收码都落在2k个球内，而球外没有一个码，这就是完备码。完备码具有下述特性：围绕个码字、汉明距离为t=（dmin-1）/2的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码离发码的距离至多为t，这时所有的重量t的差错图案都能用最佳（最小距离）译码器得到纠正，而所有重量t+1的差错图案都不能纠正。 现在学习的是第49页，共55页信息论与编码-线性分组码o 完备码并不多见，迄今发现的完备码有t=1的汉明码，t=3的高莱码，以及长度n为奇数、由两个码字组成、满足dmin=n的任何二进制码，还有三进制t=3的（11，6）码。现在学习的是第50页，共55页信息论与编码-线性分组码 汉明码是一类码的总称。汉明码的纠错能力t=1。对于二进制汉明码，码长n和信息位k满足其中，m=n-k是正整数。汉明码是完备码。 汉明码校验矩阵H具有特殊的性质。一个（n，k）码的校验矩阵有n-k行和n列，二进制时n-k个校验码元能够组成的列矢量总数为（全零矢量除外） ，对于二进制汉明码，恰好等于校验矩阵的列数 。12kn12mn)12 , 12(),(mknmm现在学习的是第51页，共55页信息论与编码-线性分组码例题：构造一个m=3的二元汉明码。所谓构造一个码，就是求出其生成矩阵G。m=3时，n=7，n-k=4,即（7，4）汉明码，所以汉明码的校验矩阵H为即各列均不相等，一个错误时，伴随式与列对应，从而可知错误的位置。101100111010101110100H现在学习的是第52页，共55页信息论与编码-线性分组码经列置换化成系统形式为所以生成矩阵G为)(100101101011100010111IPHT1101000011010011100101010001)(PIG现在学习的是第53页，共55页信息论与编码-线性分组码 二进制汉明码的概念也可以扩展到多进制，即GF（q）域上的汉明码。在q进制中，一个码元上的差错位置就可以有（q-1）种，n个码元上的差错位置有n（q-1）种。而（n-k）个校验位可以表达 个不同的意思，由汉明码定义，它应该恰好等于所有的单个差错图案加上1（无差错），即 =n(q-1)+1。令n-k=m，则q进制汉明码的n，k应服从qknmqqkqqnmm）（）（及1/1) 1/() 1(qkn现在学习的是第54页，共55页信息论与编码-线性分组码 高莱高莱（Golay）码码是二进制（23，12）线性码，其最小距离 纠错能力t=3。由于满足 因此它也是完备码。，7mind3232231231204821223现在学习的是第55页，共55页