信息论与编码第六章

信息论与编码第六章第一页，共五十五页，2022年，8月28日信息论与编码-线性分组码最优译码与最大似然译码最优译码：最大似然译码：汉明距离、码字重量第二页，共五十五页，2022年，8月28日信息论与编码-线性分组码一、线性分组码的基本概念分组码是建立在码的代数结构基础上的，所以对分组码的讨论和分析需要一定的代数基础。在这里我们不准备系统地学习代数知识，只介绍一些相关的内容。第三页，共五十五页，2022年，8月28日信息论与编码-线性分组码域（Field）的概念域是定义了两种代数运算的系统。所谓代数系统，是指满足一定规律或定律的系统，系统中有一群元素构成的集合、定义了一些运算等。在域中定义的两种算术运算是：第四页，共五十五页，2022年，8月28日信息论与编码-线性分组码（i）加法：集合F在加法运算下是封闭的，即如果必有。满足加法结合率，即集合中一定包含一个零元素，满足集合中每个元素都有其逆元素，元素a的逆记为-a，有a+(-a)=a-a=0第五页，共五十五页，2022年，8月28日信息论与编码-线性分组码（ii）乘法：集合F在乘法运算下是封闭的，即如果，则必有满足乘法结合率，即满足乘法交换率，即满足乘法分配率，即集合中一定有一个单位元I，对任何有除零元素外，集合中每一个元素都有逆元素。第六页，共五十五页，2022年，8月28日信息论与编码-线性分组码当域由有限个元素组成时，叫做有限域，也称为伽罗华（GaloisField）域，记为GF(q)，其中q是域中元素的个数。例如，集合｛0，1｝对加法和乘法（不包含零元）都是模2的运算构成一个域GF（2）。集合｛0，1，2，3，4｝对加法和乘法（不包含零元）都是模5的运算构成一个域GF（5）。第七页，共五十五页，2022年，8月28日信息论与编码-线性分组码（2）矢量空间由初等数学可知，平面上的二维矢量的全体构成一个二维的矢量空间，空间的三维矢量全体构成三维矢量空间。推广可以得到一般的n维矢量空间。第八页，共五十五页，2022年，8月28日信息论与编码-线性分组码在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重线性无关的矢量可以构成一个n维矢量空间。取其中的k个可以张成n维空间的一个子空间。例如：由（1，0，0），（0，1，0），（0，0，1）为基底可以张成一个三维三重空间，取其中的两个为基底可以构成一个二维三重空间。以互相正交的基底张成的两个空间也正交，并互称为另一个空间的零空间。这两个空间对偶。第九页，共五十五页，2022年，8月28日信息论与编码-线性分组码线性分组码一个[n，k]分组码，是把信息划成k个为一段（称为信息组），通过编码器变成长为n个码元的一组，作为[n，k]分组码的一个码字。则共可能有个码字。如果这些码字集合组成一个k维线性空间，则称它是一个[n，k]线性分组码。第十页，共五十五页，2022年，8月28日信息论与编码-线性分组码

对于线性分组码，如果是码字，则必定也是码字。其中是码元字符集里的任意两个元素。因为一个定义了加法的域一定有零元素，如果取，则得到的码字一定是全零码。因此，线性分组码一定包含全零码。因此：第十一页，共五十五页，2022年，8月28日信息论与编码-线性分组码也就是说：（i）两个码字之间的距离必定等于另一个码字的重量，所以线性分组码的最小码距等于码集中非零码字的最小重量：（ii）研究两两码字之间的距离，可用码字与全零码的距离，或各码字自身的重量来代替。第十二页，共五十五页，2022年，8月28日信息论与编码-线性分组码对于[n，k]二进制分组码，共有个码字，可以看成是n维n重空间S的一个子空间。这个子空间是由k个基底张成的，记作码空间C，它是一个k维n重空间。n维n重空间的另外n-k个基底则张成一个n-k维的子空间，称为校验空间H。分组编码器的工作，就是要把k维k重的信息组空间的个矢量一一对应到k维n重码空间C。因此，编码算法就要研究两个问题：（i）如何确定码空间C，和（ii）如何映射。第十三页，共五十五页，2022年，8月28日信息论与编码-线性分组码二、生成矩阵和校验矩阵[n，k]分组码的编码问题就是要在n维线性空间中，找出满足一定要求的由个矢量组成的k维n重线性子空间，或者说，要由k个信息码元得到n-k个冗余码元。设是一组k个信息组，可以写成矢量形式。编码器输出的是k维n重码空间C的一个矢量，记为。因此有第十四页，共五十五页，2022年，8月28日信息论与编码-线性分组码对二进制分组码来说，。上式也可以写成矩阵形式：其中，均为一个含有n个元素的行向量。所以有第十五页，共五十五页，2022年，8月28日信息论与编码-线性分组码G是一个k行n列的矩阵，给定任何k码元的信息比特，都可以由G利用公式求出对应的码字，因此，G被称为码的生成矩阵。可以看出，任何码子都是G的行矢量的线性组合，即从矢量空间的角度来说，G的k个行矢量相当于k维n重码字矢量空间的一组基底，该空间的任何矢量（码字）都可以由这组基底的线性组合得到。并且这组基底本身也是一组码字。第十六页，共五十五页，2022年，8月28日信息论与编码-线性分组码一般形式的G，得到的码字前k位的信息位也发生了变化，而一般来说，我们只是希望在信息位后加上冗余比特，所以，可以对生成矩阵通过行运算（以及列置换）作适当的变换，变成“系统形式”，即这样生成的（n，k）码是系统码。第十七页，共五十五页，2022年，8月28日信息论与编码-线性分组码与码空间C相对应，一定存在一个对偶空间H。对偶空间H的基底，是n维n重矢量空间的基底中，除去张成k维码字空间C的k个基底，而剩下的n-k个基底。因此，H空间和C空间一定正交。即生成矩阵的每一行，都是一个码字，所以有第十八页，共五十五页，2022年，8月28日信息论与编码-线性分组码因此H叫做码字空间C的校验矩阵，可以利用是否等于零矢量，来判断一个是不是码字。例题：对一个（7，4）码，其生成矩阵为第十九页，共五十五页，2022年，8月28日信息论与编码-线性分组码（1）对于信息组(1011)，对应码字是什么？（2）设计一个（7，4）分组编码器原理图。（3）若接收到一个7位码r=（1001101），判断它是否是码字。解：（1）由生成矩阵可知，得到的一定是系统码。由得第二十页，共五十五页，2022年，8月28日信息论与编码-线性分组码将信息位的值代入，得：，因此，编得的码字为。注意加法是模2加。（2）由编码后冗余位与信息位的关系，可得编码器的原理图如图所示：输入输出第二十一页，共五十五页，2022年，8月28日信息论与编码-线性分组码（3）要检验一个码序列R是否是码字，可以使用校验矩阵H，如果，则一定是码字，否则一定不是码字。因此，就产生三个方程，只有第一个为零，另两个不为零，所以R不是码字。系统码的前k位为信息位，后n-k位为校验位。第二十二页，共五十五页，2022年，8月28日信息论与编码-线性分组码校验矩阵H除了可以用来检验码字外，还与码的最小距离（也就和码的检错纠错能力）有关。因为其中，是H矩阵的列向量。第二十三页，共五十五页，2022年，8月28日信息论与编码-线性分组码因此，也就是说，n个矢量一定是线性相关的。如果分组码的最小距离为，则根据线性码的特点，码集里面一定有一个码字其重量最小为，即有个非零元素。将其代入校验矩阵的方程，左边就有个项，而右边为零。也就是说，个是线性相关的。而第二十四页，共五十五页，2022年，8月28日信息论与编码-线性分组码

个一定是线性无关的（反证法：如果个列矢量是线性相关的，则可以把其对应的系数当成码字，而该码字的重量为，这与码字的最小重量为相矛盾）。由于H是的矩阵，其秩最大为n-k，也就是说，最多有n-k个列矢量线性无关。所以第二十五页，共五十五页，2022年，8月28日信息论与编码-线性分组码在编码的时候，我们希望越大越好。二进制（n，k）线性码的最小码距的上界是n-k+1。称这样的码为极大最小距离码（MDC:MaximizedminimumDistanceCode）。第二十六页，共五十五页，2022年，8月28日信息论与编码-线性分组码本节讨论如何用伴随式译码伴随式设发送的码字为

通过有扰信道传输，信道产生的错误图样为收端译码器收到的n重矢量为第二十七页，共五十五页，2022年，8月28日信息论与编码-线性分组码R=C+E，译码器的任务就是要从收到的R中得出，或者由R中解出错误图样，从而得到，并使译码错误概率最小。对于二进制码字，模2减与模2加等同。对于[n，k]分组码C，满足，因此若E=0，则，若，并且仅与错误图样E有关，而与发送什么码字无关。第二十八页，共五十五页，2022年，8月28日信息论与编码-线性分组码令S称为接收矢量R的伴随式（校正子）。伴随式完全由E决定，它充分反映了信道的干扰情况。译码器的主要任务就是如何从S中得到最象E的错误图样，从而译出。S与E是否有一一对应的关系？如果一个[n，k]译码器要纠正t个错误，则要求对于错误个数的所有可能组合的错误图样，都应该有不同的伴随式与之对应。第二十九页，共五十五页，2022年，8月28日信息论与编码-线性分组码2.标准阵列由前面的讨论可知，[n，k]分组码的译码步骤可归结为以下三步：（1）由接收到的R，计算伴随式；（2）若S=0，则认为接收无误。若，则由

S找出错误图样；（3）由和R找出。这里最关键的是由S找出E，只要找出的E是正确的，译出的码也是正确的。第三十页，共五十五页，2022年，8月28日信息论与编码-线性分组码由S的定义式，，即共有n-k个方程，但有n个未知量，所以解不唯一。对于二进制，少一个方程导致两个解，少两个方程导致四个解，少k个方程导致有个解，也就是说，可以解出个不同的错误图样，从而对应了个码字（码字的全部可能）。根据最大似然译码规则，应该译成可能性最大的那个码字。第三十一页，共五十五页，2022年，8月28日信息论与编码-线性分组码对于二进制对称信道，若差错概率为p，则错一个比特的概率（）大于错两个比特的概率（），…。所以，应该译成所有个差错图样中重量最小的那一个。但如果每接收一个R就要解一次方程组，显然太麻烦了。可以预先把不同S下的方程组解出来，并得到最大概率的那个错误图样，和错误图样对应的R，存成一个表格，译码的时候，只要根据不同的R查表，就可以得到对应的最大可能的码字。第三十二页，共五十五页，2022年，8月28日信息论与编码-线性分组码下表就是一个这样的表，叫做标准阵列译码表。表中有列，每一列的头一个元素对应的是一个码字，所以共对应个不同的码字；每一列的列首元素下，是个禁用码字（即n维空间点中不是码字的那些点），代表该列首元素（码字）在不同差错图样下偏移后所对应的空间点，正好对应了个不同的伴随式。全部的元素个数是，正好是n维矢量空间中总的点数，也就是说，每一个空间点第三十三页，共五十五页，2022年，8月28日信息论与编码-线性分组码都有其所对应的码字，这样，在译码的时候，当接收到一个R后，只要在标准阵列表中找到该R的位置，这一列的列首元素就是它应该译成的码字。第三十四页，共五十五页，2022年，8月28日信息论与编码-线性分组码

标准阵列译码表第三十五页，共五十五页，2022年，8月28日信息论与编码-线性分组码表中第一行对应的是个码字，相当于差错为零；第二行到第n+1行分别对应n个差错为1的差错图样；…。每一行的行首元素叫做陪集首，是该行所对应的错误图样。但是，错误图样数有个，标准阵列译码表只有行，代表个伴随式和错误图样。那么，怎么从个错误图样中选择个，作为陪集首？第三十六页，共五十五页，2022年，8月28日信息论与编码-线性分组码原则当然是要使得译码的错误概率最小。前面已经说过，对BSC信道，当错误概率p<0.5时，产生一个错误的概率比产生两个错误的概率要大，产生两个错误的概率比产生3个错误的概率要大，…。总之，错误图样重量越小，产生的可能性就越大。因此，译码器必须首先保证能正确纠正这些出现可能性比较大的错误图样，这相当于构造标准阵列译码表时，要求按照错误图样重量从轻到重的顺序挑选为陪首集。第三十七页，共五十五页，2022年，8月28日信息论与编码-线性分组码例题：某（5，2）系统线性码的生成矩阵是设收到的码是R=(10101)，请先构造该码的标准阵列译码表，然后译出发码的估值C。第三十八页，共五十五页，2022年，8月28日H=[PT┆I3]==s1＝e1h11+e2h12+e3h13+e4h14+e5h15=e1+e2+e3

s2=e1h21+e2h22+e3h23+e4h24+e5h25=e1+e4s3=e1h31+e3h32+e3h33+e4h34+e5h35=e1+e2+e5解：对应（s1,s2,s3）=(111),e=(10000),(01010),(00111)和(11101)四种错误图样信息论与编码-线性分组码第三十九页，共五十五页，2022年，8月28日信息论与编码-线性分组码标准阵列译码表

n-k=3，，即标准阵列译码表共有8行，每行代表一种错误图样。按照错误图样重量从轻到重的顺序，无差错（错误图样重量为0）的有一种，重量为1的有种，重量为2的有种。我们挑选的陪首集是1种无错误（重量为0），5种有一个错误（重量为1）和重量为2的10种里面的2种。第四十页，共五十五页，2022年，8月28日信息论与编码-线性分组码码字共有种，将信息组的可能组合(00)、(01)、(10)、(11)代入生成矩阵，得到四个码字为：(00000)、(10111)、(01101)、(11010)。得到的标准阵列译码表如下图所示：第四十一页，共五十五页，2022年，8月28日信息论与编码-线性分组码标准阵列译码表S1=000E1=00000C2=10111C3=01101C4=11010S2=111E2=10000001111110101010S3=101E3=01000111110010110010S4=100E4=00100100110100111110S5=010E5=00010101010111111000S6=001E6=00001101100110011011S7=011E7=00011101000111011001S8=110E8=00110100010101111100第四十二页，共五十五页，2022年，8月28日信息论与编码-线性分组码当然，上述的标准阵列译码表不是唯一的，因为从10种重量为2的错误图样中选择两种，可以是任意选的。标准阵列译码表需要把个n重存储在译码器中。其复杂性随n的增大指数增长，当n比较大时很不实用。第四十三页，共五十五页，2022年，8月28日信息论与编码-线性分组码可以把标准阵列译码表进行简化，即只存储伴随式和错误图样的对应关系，译码时先计算得到伴随式，再查表得到错误图样，从而得到译码码字。这样码表可以简化，但译码时的计算量增加了。并且当n和k都比较大时，即使采用这种简化的码表，译码器的复杂性还是很高。因此在线性分组码理论中，如何简化译码器是最中心的研究课题之一。第四十四页，共五十五页，2022年，8月28日信息论与编码-线性分组码

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

第四十七页，共五十五页，2022年，8月28日信息论与编码-线性分组码因为有2k个可能发送的码字，也就有2k个不相重叠的半径为t的球。包含在2k个球中的码字总数不会超过2n个可能的接收码字。于是一个纠t差错的码必然满足不等式

2k•≤2n即2n-k≥第四十八页，共五十五页，2022年，8月28日信息论与编码-线性分组码如果等号成立，表示所有的收码都落在2k个球内，而球外没有一个码，这就是完备码。完备码具有下述特性：围绕个码字、汉明距离为t=└（dmin-1）/2┘的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码离发码的距离至多为t，这时所有的重量≤t的差错图案都能用最佳（最小距离）译码器得到纠正，而所有重量≥t+1的差错图案都不能纠正。第四十九页，共五