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

信息论与编码-线性分组码 上次课小结： 信道编码定理： 差错控制的途径 增加码长、增加带宽、提高信噪比、噪声均 化 码距与检错纠错的关系 信息论与编码-线性分组码 最优译码与最大似然译码 最优译码： 最大似然译码： 汉明距离、码字重量 信息论与编码-线性分组码 一、线性分组码的基本概念 分组码是建立在码的代数结构基础上的，所以 对分组码的讨论和分析需要一定的代数基 础。在这里我们不准备系统地学习代数知 识，只介绍一些相关的内容。 信息论与编码-线性分组码 域（Field）的概念 域是定义了两种代数运算的系统。 所谓代数系统，是指满足一定规律或定律的系 统，系统中有一群元素构成的集合、定义 了一些运算等。 在域中定义的两种算术运算是： 信息论与编码-线性分组码 （i）加法： o集合F在加法运算下是封闭的，即如果 必有 。 o满足加法结合率，即 o集合中一定包含一个零元素，满足 o集合中每个元素都有其逆元素，元素a的逆记 为-a，有a+(-a)=a-a=0 信息论与编码-线性分组码 （ii）乘法： o集合F在乘法运算下是封闭的，即如果 ，则必有 o满足乘法结合率，即 o满足乘法交换率，即 o满足乘法分配率，即 o集合中一定有一个单位元I，对任何 有 o除零元素外，集合中每一个元素都有逆元素。 信息论与编码-线性分组码 当域由有限个元素组成时，叫做有限域，也称为伽 罗华（Galois Field）域，记为GF(q)，其中q是 域中元素的个数。 例如，集合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）为基底可以张成一个三维三重空间，取 其中的两个为基底可以构成一个二维三重空间 。 以互相正交的基底张成的两个空间也正交，并互 称为另一个空间的零空间。这两个空间对偶。 信息论与编码-线性分组码 线性分组码 一个n，k分组码，是把信息划成k个为一段（ 称为信息组），通过编码器变成长为n个码 元的一组，作为n，k分组码的一个码字。 则共可能有 个码字。 如果这些码字集合组成一个k维线性空间，则称它 是一个n，k线性分组码。 信息论与编码-线性分组码 对于线性分组码，如果 是码字，则 必定也是码字。其中 是码元 字符集里的任意两个元素。 因为一个定义了加法的域一定有零元素，如果取 ，则得到的码字一定是全零码。因此，线性分 组码一定包含全零码。 因此： 信息论与编码-线性分组码 也就是说： （i）两个码字之间的距离必定等于另一个码字的 重量，所以线性分组码的最小码距 等于码 集中非零码字的最小重量： （ii）研究两两码字之间的距离，可用码字与全零 码的距离，或各码字自身的重量来代替。 信息论与编码-线性分组码 对于n，k二进制分组码，共有 个码字，可以 看成是n维n重空间S的一个子空间。这个子空 间是由k个基底张成的，记作码空间C，它是一 个k维n重空间。n维n重空间的另外n-k个基底则 张成一个n-k维的子空间，称为校验空间H。分 组编码器的工作，就是要把k维k重的信息组空 间的 个矢量一一对应到k维n重码空间C。因 此，编码算法就要研究两个问题： （i）如何确定码空间C，和（ii）如何映射。 信息论与编码-线性分组码 二、生成矩阵和校验矩阵 n，k分组码的编码问题就是要在n维线性空间中 ，找出满足一定要求的由 个矢量组成的k维n 重线性子空间，或者说，要由k个信息码元得到n -k个冗余码元。 设 是一组k个信息组，可以写成矢量形 式 。编码器输出的是k维n重 码空间C的一个矢量，记为 。因此有 信息论与编码-线性分组码 对二进制分组码来说， 。上式也可以写成 矩阵形式： 其中， 均为一个含有n个元素的行向 量。所以有 信息论与编码-线性分组码 G是一个k行n列的矩阵，给定任何k码元的信息比 特，都可以由G利用公式 求出对应的 码字，因此，G被称为码的生成矩阵。 可以看出，任何码子都是G的行矢量的线性组合 ，即 从矢量空间的角度来说，G的k个行矢量相当于k 维n重码字矢量空间的一组基底，该空间的任 何矢量（码字）都可以由这组基底的线性组合 得到。并且这组基底本身也是一组码字。 信息论与编码-线性分组码 一般形式的G，得到的码字前k位的信息位也发生 了变化，而一般来说，我们只是希望在信息位 后加上冗余比特，所以，可以对生成矩阵通过 行运算（以及列置换）作适当的变换，变成“系 统形式”，即 这样生成的（n，k）码是系统码。 信息论与编码-线性分组码 与码空间C相对应，一定存在一个对偶空间H。对 偶空间H的基底，是n维n重矢量空间的基底中， 除去张成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）由生成矩阵可知，得到的一定是系统码 。由 得 信息论与编码-线性分组码 将信息位的值代入，得： ，因 此，编得的码字为 。注意加法是 模2加。 （2）由编码后冗余位与信息位的关系，可得编码 器的原理图如图所示： 输入 输出 信息论与编码-线性分组码 （3）要检验一个码序列R是否是码字，可以使用 校验矩阵H，如果 ，则一定是码字，否 则一定不是码字。 因此， 就产生三个方程，只有第一个为零， 另两个不为零，所以R不是码字。 系统码的前k位为信息位，后n-k位为校验位。 信息论与编码-线性分组码 校验矩阵H除了可以用来检验码字外，还与码的最 小距离（也就和码的检错纠错能力）有关。 因为 其中， 是H矩阵的列向量。 信息论与编码-线性分组码 因此， 也就是说，n个矢量 一定是线性相关的。 如果分组码的最小距离为 ，则根据线性码的 特点，码集里面一定有一个码字其重量最小为 ，即有 个非零元素。将其代入校验 矩阵的方程，左边就有 个 项，而右边为 零。也就是说， 个 是线性相关的。 而 信息论与编码-线性分组码 个 一定是线性无关的（反证法：如 果 个 列矢量是线性相关的，则可以 把其对应的系数当成码字，而该码字的重量为 ，这与码字的最小重量为 相矛盾）。 由于H是 的矩阵，其秩最大为n-k，也就是 说，最多有n-k个列矢量线性无关。所以 信息论与编码-线性分组码 在编码的时候，我们希望 越大越好。 二进制（n，k）线性码的最小码距的上界是n-k+1。 称这样的码为极大最小距离码（MDC:Maximized minimum Distance Code）。 信息论与编码-线性分组码 本节讨论如何用伴随式译码 伴随式 设发送的码字为 通过有扰信道传输，信道产生的错误图样为 收端译码器收到的n重矢量为 信息论与编码-线性分组码 R=C+E，译码 器的任务就是要从收到的R中得 出 ，或者由R中解出错误图样 ，从而得到 ，并使译码错误 概率最小。对于二进制码字 ，模2减与模2加等同。 对于n，k分组码 C，满足 ，因此 若E=0，则 ，若 ， 并且仅与错误图样 E有关，而与发送什么码 字无关。 信息论与编码-线性分组码 令 S称为接收矢量R的伴随式（校正子）。伴随式 完全由E决定，它充分反映了信道的干扰情 况。译码器的主要任务就是如何从S中得到 最象E的错误图样 ，从而译出 。 S与E是否有一一对应的关系？ 如果一个n，k译码器要纠正t个错误，则要求 对于错误个数 的所有可能组合的错误图 样，都应该有不同的伴随式与之对应。 信息论与编码-线性分组码 2. 标准阵列 由前面的讨论可知，n，k分组码的译码步骤可 归结为以下三步： （1）由接收到的R，计算伴随式 ； （2）若S=0，则认为接收无误。若 ，则由 S找出错误图样 ； （3）由 和R找出 。 这里最关键的是由S找出E，只要找出的E是正确的 ，译出的码也是正确的。 信息论与编码-线性分组码 由S的定义式， ，即 共有n-k个方程，但有n个未知量，所以解不唯一。对 于二进制，少一个方程导致两个解，少两个方程 导致四个解，少k个方程导致有 个解，也就是 说，可以解出 个不同的错误图样，从而对应 了 个码字（码字的全部可能）。根据最大似然 译码规则，应该译成可能性最大的那个码字。 信息论与编码-线性分组码 对于二进制对称信道，若差错概率为p，则错一个 比特的概率（ ）大于错两个比特的概 率（ ），。所以，应该译成所有 个差错图样中重量最小的那一个。 但如果每接收一个R就要解一次方程组，显然太麻 烦了。可以预先把不同S下的方程组解出来，并 得到最大概率的那个错误图样，和错误图样对 应的R，存成一个表格，译码的时候，只要根据 不同的R查表，就可以得到对应的最大可能的码 字。 信息论与编码-线性分组码 下表就是一个这样的表，叫做标准阵列译码表。 表中有 列，每一列的头一个元素对应的是一 个码字，所以共对应 个不同的码字；每一列 的列首元素下，是 个禁用码字（即n维空间 点中不是码字的那些点），代表该列首元素（ 码字）在不同差错图样下偏移后所对应的空间 点，正好对应了 个不同的伴随式。全部的 元素个数是 ，正好是n维矢量空 间中总的点数，也就是说，每一个空间点 信息论与编码-线性分组码 都有其所对应的码字，这样，在译码的时候， 当接收到一个R后，只要在标准阵列表中找 到该R的位置，这一列的列首元素就是它应 该译成的码字。 信息论与编码-线性分组码 标准阵列译码表 信息论与编码-线性分组码 表中第一行对应的是 个码字，相当于差错为 零；第二行到第n+1行分别对应n个差错为1 的差错图样；。每一行的行首元素叫做陪 集首，是该行所对应的错误图样。 但是，错误图样数有 个，标准阵列译码表只 有 行，代表 个伴随式和错误图样 。那么，怎么从 个错误图样中选择 个 ，作为陪集首？ 信息论与编码-线性分组码 原则当然是要使得译码的错误概率最小。前面已经 说过，对BSC信道，当错误概率p0.5时，产生 一个错误的概率比产生两个错误的概率要大，产 生两个错误的概率比产生3个错误的概率要大， 。总之，错误图样重量越小，产生的可能性就 越大。因此，译码器必须首先保证能正确纠正这 些出现可能性比较大的错误图样，这相当于构造 标准阵列译码表时，要求按照错误图样重量从轻 到重的顺序挑选为陪首集。 信息论与编码-线性分组码 例题：某（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)四种错误图样 信息论与编码-线性分组码 信息论与编码-线性分组码 标准阵列译码表 n-k=3， ，即标准阵列译码表共有8行 ，每行代表一种错误图样。 按照错误图样重量从轻到重的顺序，无差错（ 错误图样重量为0）的有一种，重量为1的有 种，重量为2的有 种。 我们挑选的陪首集是1种无错误（重量为0）， 5种有一个错误（重量为1）和重量为2的10 种里面的2种。 信息论与编码-线性分组码 码字共有 种，将信息组的可能组合 (00)、(01)、(10)、(11)代入生成矩阵，得到四 个码字为：(00000)、(10111)、(01101)、 (11010)。 得到的标准阵列译码表如下图所示： 信息论与编码-线性分组码 标准阵列译码表 S1=000 E1=00000C2=10111C3=01101C4=11010 S2=111 E2=10000 00111 11101 01010 S3=101 E3=01000 11111 00101 10010 S4=100 E4=00100 10011 01001 11110 S5=010 E5=00010 10101 01111 11000 S6=001 E6=00001 10110 01100 11011 S7=011 E7=00011 10100 01110 11001 S8=110 E8=00110 10001 01011 11100 信息论与编码-线性分组码 当然，上述的标准阵列译码表不是唯一的，因为从 10种重量为2的错误图样中选择两种，可以是任 意选的。 标准阵列译码表需要把 个n重存储在译码器中。 其复杂性随n的增大指数增长，当n比较大时很 不实用。 信息论与编码-线性分组码 可以把标准阵列译码表进行简化，即只存储伴 随式和错误图样的对应关系，译码时先计 算得到伴随式，再查表得到错误图样，从 而得到译码码字。这样码表可以简化，但 译码时的计算量增加了。并且当n和k都比 较大时，即使采用这种简化的码表，译码 器的复杂性还是很高。因此在线性分组码 理论中，如何简化译码器是最中心的研究 课题之一。 信息论与编码-线性分组码 完备码 对于纠错能力为t的（n，k）分组码，重量 小于等于t的错误图样共有 因此，要想纠正t个错误，必须有 信息论与编码-线性分组码 如果伴随式的数目刚好等于重量小于等于t的错 误图样的数目，即 则称这样的（n，k）分组码为完备码。 这样每一个错误图样，都有一个不同的伴随式与 之对应，每一个伴随式都对应一个不同的错 误图样。 信息论与编码-线性分组码 o从多维矢量空间的角度来看完备码 o假定我们围绕每一个码字ci放置一个半径为 t的球，每个球内包含了与该码字汉明距离 小于、等于t的所有收码R的集合，这样在 半径为t(dmin-1)/2的球内的收码数是 。 信息论与编码-线性分组码 因为有2k个可能发送的码字，也就有2k个不相 重叠的半径为t的球。包含在2k个球中的码 字总数不会超过2n个可能的接收码字。于 是一个纠t差错的码必然满足不等式 2k 2n 即 2n-k 信息论与编码-线性分组码 如果等号成立，表示所有的收码都落在2k个球 内，而球外没有一个码，这就是完备码。 完备码具有下述特性：围绕个码字、汉明距离 为t=（dmin-1）/2的所有球都是不相交 的，每一个接收码字都落在这些球中之一 ，因此接收码离发码的距离至多为t，这时 所有的重量t的差错图案都能用最佳（最 小距离）译码器得到纠正，而所有重量 t+1的差错图案都不能纠正。 信息论与编码-线性分组码 o完备码并不多见，迄今发现的完备码有t=1 的汉明码，t=3的高莱码，以及长度n为奇 数、由两个码字组成、满足dmin=n的任何 二进制码，还有三进制t=3的（11，6）码 。 信息论与编码-线性分组码 汉明码是一类码的总称。汉明码的纠错能力 t=1。对于二进制汉明码，码长n和信息位k 满