信息论与编码-循环码11.27.ppt

线性分组码 1. 线性分组码的定义和特点 线性分组码，是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码，即在（n，k）分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的纠错码，应用很广。 线性分组码的一般原理 线性分组码的构造 H矩阵（监督阵） H矩阵的性质： ? H的行数就是监督关系式的数目，等于监督位个数r。 ? 典型监督阵可分解为[P Ir]形式，P为r ? k阶矩阵，Ir 为r ? r阶单位方阵。 ?由代数理论可知，H矩阵的各行应该是线性无关的 G矩阵的性质： ? G矩阵的各行是线性无关的。 ? G的各行本身就是一个码组。 ?如果已有k个线性无关的码组，则可以用其作 为生成矩阵G。 错误图样 2. 监督矩阵H和生成矩阵G （1） 监督矩阵 我们把H称为监督矩阵，或称一致校验矩阵，一旦H给定，信息位和监督位之间的关系也就确定了。H为 r×n阶矩阵，H矩阵每行之间是彼此线性无关的。H矩阵可分成两部分，其中P为r×k阶矩阵，Ir为r×r阶单位阵。能写成H=［PIr］形式的矩阵称为典型监督矩阵。 （2） 生成矩阵 称为生成矩阵，由G和信息组就可以产生全部码字。G为k×n阶矩阵，各行也是线性无关的。生成矩阵也可以分为两部分：其中Q为k×r阶矩阵，Ik为k阶单位阵，可以写成式（8-12）形式的G矩阵，称为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。 （3） 监督矩阵H和生成矩阵G之间的关系 由上可知，监督矩阵H和生成矩阵G之间有一一对应的关系。由于G的每一行都为码字，因此它必然满足式 HAT=0T 即 HGT=0T 3. 线性分组码的译码——伴随式（校正子）S 若某一码字为许用码组，则它必然满足式。利用这一关系，在接收端将收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件，则认为接收正确；反之，则认为传输过程中发生了错误，进而设法确定错误的数目和位置。 例：设分组码(n, k)中k = 4，为了纠正1位错码，由上式可知，要求监督位数 r ? 3。若取 r = 3，则n = k + r = 7。 令S=BHT，称为伴随式或校正子。 S=BHT=（A+E）HT=EHT 由此可见，伴随式S与错误图样E之间有确定的线性变换关系，与发送码组A无关。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。 从以上分析可以得出线性分组码译码的基本步骤： ① 计算接收码组B的伴随式S； ② 根据S找出错误图样E，判定误码位置； ③ 根据E纠正错误，得到正确的码组A=E+B。 错误图样和伴随式 定义：发送码字c = (c1, c2, …, cn)经过有扰信道得到接收向量v = (v1, v2, …, vn)，则称e = (e1, e2, …, en)为错误图样，其中 ei = vi – ci。 定义：设码C的校验矩阵为H，接收向量v的伴随式为s = v HT。 译码步骤 1）由接收向量v计算伴随式s； 2）由伴随式s求得错误图样e； 3）c = v – e。 循环码 循环码的概念： 循环性是指任一码组字循环一位后仍然是该编码中的一个码字。 例：一种(7, 3)循环码的全部码字如下 表中第2码字向右移一位即得到第5码字；第5码字向右移一位即得到第7码字。 一般情况 若(an-1 an-2 …a0)是循环码的一个码字，则循环移位后的码字： (an-2 an-3 … a0 an-1) (an-3 an-4 … an-1 an-2) … … (a0 an-1 …a2 a1) 仍然是该编码中的码字。 多项式表示法 一个长度为n的码字(an-1 an-2 …a0)可以表示成 上式中x 的值没有任何意义，仅用它的幂代表码元的位置。 例：码字1 1 0 0 1 0 1可以表示为 循环码的运算 整数的按模运算 在整数运算中，有模n运算。例如，在模2运算中，有 1 + 1 = 2 ? 0 (模2)， 1 + 2 = 3 ? 1 (模2)， 2 ? 3 = 6 ? 0 (模2) 等等。 一般说来，若一个整数m可以表示为 式中，Q为整数，则在模n运算下，有 m ? p (模n) 所以，在模n运算下，一个整数m等于它被n除得的余数。 码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和