线性分组码实验报告.doc

线性分组码 一、原理： 监督矩阵： 线性分组码中许用码组为个。定义线性分组码的加法为模二加法，乘法为二进制乘法。即、、、；、、、。且码组与码组的运算在各个相应比特位上符合上述二进制加法运算规则。 线性分组码具有如下性质的性质： 封闭性。任意两个码组的和还是许用的码组。 码的最小距离等于非零码的最小码重。 对于码组长度为、信息码元为位、监督码元为位的分组码，常记作码，如果满足，则有可能构造出纠正一位或一位以上错误的线性码。 下面我们通过（7，4）分组码的例子来说明如何具体构造这种线性码。设分组码中，，为能纠正一位误码，要求。取，则。该例子中，信息组为,码字为。用，，的值与错码位置的对应关系可以规定为如表1所列。 由表中规定可知，当已知信息组时，按以下规则得到三个校验元，即： （式.1） 表1 错码位置示意表。 错码位置 错码位置 001 101 010 110 100 111 011 000 无错 在发送端编码时，信息位，，和的值决定于输入信号，因此它们是随机的。监督位，和应根据信息位的取值按监督关系来确定，即监督位应使上三式中，和的值为零（表示编成的码组中应无错码）。由上式经移项运算，解出监督位： （式.2） 给出信息位后，可直接按上式算出监督位，其结果见表2。 接收端收到每个码组后先按式(.1)计算出，和，再按表1判断错码情况。 表2 （7，4）线性分组码（海明码） 信息组 码组 信息组 码组 0000 0000000 1000 1000111 0001 0001011 1001 1001100 0010 0010101 1010 1010010 0011 0011110 1011 1011001 0100 0100110 1100 1100001 0101 0101101 1101 1101110 0110 0110011 1110 1110100 0111 0111000 1111 1111111 给出（7,4）线性分组码有即16个许用码字或合法码字，另有个禁用码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。 按上述方法构造的码称为海明码。表2所列的(7,4)海明码的最小码距，因此，这种码能纠正一个错码或检测两个错码。海明码的编码效率等于 （式.3） 当n很大时，则编码效率接近1。可见，海明码是一种高效码。 现在再来讨论线性分组码的一般原理。上面已经提到，线性码是指信息位和监督位满足一组线性方程的码，式(.1)就是这样一组线性方程的例子。现在将它改写成： （式.4） 式（.4）可以表示成如下矩阵形式： （模2） （式.5） 上式还可以简记为： 或 （式.6） 其中 右上标“T”表示将矩阵转置。 将称为监督矩阵，编码时只要监督矩阵给定，编码时监督位和信息位的关系就完全确定。由式（.4）、式（.5）都可看出，的行数就是监督关系式的数目，它等于监督位的数目。的每行中的“1”的位置表示相应码元之间存在的监督关系。式（.5）中的矩阵可以分为两部分： （式.7） 式中，为阶矩阵，为阶单位方阵，将具有形式的矩阵称为典型监督矩阵。 由代数理论可知，矩阵的各行应该是线性无关的，否则将得不到个线性无关的监督关系式，从而也得不到个独立的监督位。若一行矩阵能写成典型的矩阵形式，则其各行一定是线性无关的。因为容易验证的各行是线性无关的，故也是线性无关的。生成矩阵类似于式（.4）改变成式（.5）中矩阵形式那样，式（.5）也可以改写成： （式.8） 或者 （式.9） 式中，为一个阶矩阵，即它为的转置，即 （式.10） 式（.9）表明，信息位给定后，用信息位的行距乘矩阵就产生出监督位。 将的左边加上一阶单位方阵就构成一矩阵，即 （式.11） 称为生成矩阵，因为由它可以产生整个码组，即有 （式.12） 或者 （式.13） 因此，如果找到了码的生成矩阵，则编码的方法就完全确定。具有形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组中，信息位不变，监督位附加于其后，这种码称为系统码。 与矩阵相似，也要求矩阵的各行是线性无关的。因为由式（.13）可以看出，任一码组都是的各行的线性组合。共有行，若它们线性无关，则可组合出种不同的码组，它恰是有为信息位的全部码组；若的各行有线性相关的，则不可能由生成种不同码组了。实际上，的各行本身就是一个码组。因此，如果已有个线性无关的码组，则可以用其作为生成矩阵，并由它生成其余的码组。 码的距离 两个码字之间，对应位取之不同的个数，称为汉明距离，用表示。一个码的最小距离定义为，两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字