信息论与编码循环码

1、信息论与编码循环码1第1页，共35页，2022年，5月20日，1点14分，星期一线性分组码的一般原理线性分组码的构造H矩阵（监督阵）H AT = 0T 或A HT = 0监督阵2第2页，共35页，2022年，5月20日，1点14分，星期一H矩阵的性质： H的行数就是监督关系式的数目，等于监督位个数r。 典型监督阵可分解为P Ir形式，P为r k阶矩阵，Ir 为r r阶单位方阵。 由代数理论可知，H矩阵的各行应该是线性无关的 3第3页，共35页，2022年，5月20日，1点14分，星期一生成阵如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵。系统码4第

2、4页，共35页，2022年，5月20日，1点14分，星期一G矩阵的性质： G矩阵的各行是线性无关的。 G的各行本身就是一个码组。 如果已有k个线性无关的码组，则可以用其作 为生成矩阵G。5第5页，共35页，2022年，5月20日，1点14分，星期一错误图样 B A = E错误图样接收码发送码6第6页，共35页，2022年，5月20日，1点14分，星期一2. 监督矩阵H和生成矩阵G（1） 监督矩阵第7页，共35页，2022年，5月20日，1点14分，星期一我们把H称为监督矩阵，或称一致校验矩阵，一旦H给定，信息位和监督位之间的关系也就确定了。H为 rn阶矩阵，H矩阵每行之间是彼此线性无关的。H矩

3、阵可分成两部分，其中P为rk阶矩阵，Ir为rr阶单位阵。能写成H=PIr形式的矩阵称为典型监督矩阵。第8页，共35页，2022年，5月20日，1点14分，星期一（2） 生成矩阵第9页，共35页，2022年，5月20日，1点14分，星期一称为生成矩阵，由G和信息组就可以产生全部码字。G为kn阶矩阵，各行也是线性无关的。生成矩阵也可以分为两部分：其中Q为kr阶矩阵，Ik为k阶单位阵，可以写成式（8-12）形式的G矩阵，称为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。第10页，共35页，2022年，5月20日，1点14分，星期一（3） 监督矩阵H和生成矩阵G之间的关系由上可知，

4、监督矩阵H和生成矩阵G之间有一一对应的关系。由于G的每一行都为码字，因此它必然满足式HAT=0T即HGT=0T第11页，共35页，2022年，5月20日，1点14分，星期一3. 线性分组码的译码伴随式（校正子）S若某一码字为许用码组，则它必然满足式。利用这一关系，在接收端将收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件，则认为接收正确；反之，则认为传输过程中发生了错误，进而设法确定错误的数目和位置。第12页，共35页，2022年，5月20日，1点14分，星期一例：设分组码(n, k)中k = 4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r = 3，则n =

5、 k + r = 7。S1 S2 S3错码位置S1 S2 S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码错码位置与校正子关系监督关系式13第13页，共35页，2022年，5月20日，1点14分，星期一令S=BHT，称为伴随式或校正子。S=BHT=（A+E）HT=EHT由此可见，伴随式S与错误图样E之间有确定的线性变换关系，与发送码组A无关。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。第14页，共35页，2022年，5月20日，1点14分，星期一从以上分析可以得出线性分组码译码的基本步骤： 计算接收码组B的伴随式S

6、； 根据S找出错误图样E，判定误码位置； 根据E纠正错误，得到正确的码组A=E+B。第15页，共35页，2022年，5月20日，1点14分，星期一错误图样和伴随式定义：发送码字c = (c1, c2, , cn)经过有扰信道得到接收向量v = (v1, v2, , vn)，则称e = (e1, e2, , en)为错误图样，其中ei = vi ci。定义：设码C的校验矩阵为H，接收向量v的伴随式为s = v HT。16第16页，共35页，2022年，5月20日，1点14分，星期一译码步骤1）由接收向量v计算伴随式s；2）由伴随式s求得错误图样e；3）c = v e。17第17页，共35页，20

7、22年，5月20日，1点14分，星期一循环码18第18页，共35页，2022年，5月20日，1点14分，星期一 循环码的概念： 循环性是指任一码组字循环一位后仍然是该编码中的一个码字。 例：一种(7, 3)循环码的全部码字如下 表中第2码字向右移一位即得到第5码字；第5码字向右移一位即得到第7码字。 码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001019第19页，共35页，2022年，5月20日，1点14分，星期一一般情况

8、 若(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可以表示为 20第20页，共35页，2022年，5月20日，1点14分，星期一循环码的运算 整数的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1 + 1 = 2 0 (模2)，1 + 2 = 3 1 (模2)， 2 3

9、= 6 0 (模2) 等等。 一般说来，若一个整数m可以表示为式中，Q为整数，则在模n运算下，有m p (模n) 所以，在模n运算下，一个整数m等于它被n除得的余数。21第21页，共35页，2022年，5月20日，1点14分，星期一码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则在按模N(x)运算下，有这时，码多项式系数仍按模2运算。 例1：x3被(x3 + 1)除，得到余项1，即 例2：因为xx3 + 1 x4 +x2 + 1x4 + x x2 +x +1 在模2运算中加法和减法一样。22第22页，共35页，2022

10、年，5月20日，1点14分，星期一循环码的数学表示法 在循环码中，设T(x)是一个长度为n的码字，若则T (x)也是该编码中的一个码字。 证 设一循环码为 则有 上式中的T (x) 正是码组T (x)向左循环移位 i 次的结果。例： 一循环码为1100101，即 若给定 i = 3，则有 上式对应的码组为0101110，它正是T(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn + 1)运算的一个余式。 23第23页，共35页，2022年，5月20日，1点14分，星期一循环码的生成 如果有了生成矩阵G，就可以由k个信息位得出整个码字A：例: (7,4)码式中，生成矩阵G的每一行都

11、是一个码组。因此，若能找到 k 个已知的码字，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。在循环码中，一个(n, k)码有2k个不同的码字。若用g(x)表示其中前(k-1)位皆为“0”的码字，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。24第24页，共35页，2022年，5月20日，1点14分，星期一在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(

12、x)必须是一个常数项不为“0”的(n - k)次多项式，而且这个g(x)还是这种(n, k)码中次数为(n k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的。我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n, k)循环码就被确定了。25第25页，共35页，2022年，5月20日，1点14分，星期一因此，循环码的生成矩阵G可以写成例：上表中的编码为(7, 3)循环码，n = 7, k = 3, n k = 4，其中唯一的一

13、个(n k) = 4次码多项式，且前(k-1)=2位皆为“0”的码字是第二码字0010111，与它对应的码多项式，即生成多项式，为g(x) = x4 + x2 + x + 1。 码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001026第26页，共35页，2022年，5月20日，1点14分，星期一g(x) = x4 + x2 + x + 1 即 “1 0 1 1 1”将此g(x)代入上矩阵，得到 或上式不符合G = IkQ形式

14、，所以它不是标准生成矩阵。但它经过线性变换后，不难化成标准阵。此循环码的码字多项式表示式T(x)： 上式表明，所有码字多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。 27第27页，共35页，2022年，5月20日，1点14分，星期一寻求码生成多项式 因为任意一个循环码T(x)都是g(x)的倍式，故它可以写成T(x) = h(x)g(x)而生成多项式g(x)本身也是一个码组，即有 T (x) = g(x)由于码字T (x)是一个(n k)次多项式，故xk T (x)是一个n次多项式。由可知，xk T (x)在模(xn + 1)运算下也是一个码

15、组，所以有上式左端分子和分母都是n次多项式，故相除的商式Q(x) = 1。因此，上式可以写成28第28页，共35页，2022年，5月20日，1点14分，星期一将 T(x) = h(x)g(x) 和 T (x) = g(x) 代入化简后，得到上式表明，生成多项式g(x)应该是(xn + 1)的一个因子。例：(x7 + 1)可以分解为为了求出(7, 3)循环码的生成多项式 g(x)，需要从上式中找到一个(n k) = 4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。 选用的生成多项式不同，产生出的循环码码字也不同。 29第29页，共35页，2022年，5月20日，1点14分，星期一循

16、环码的编码方法用xn-k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它写成多项式为m(x) = x2 + x。当n k = 7 3 =4时，xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示码组1100000。用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即有例：若选定g(x) = x4 + x2 + x + 1，则有 上式是用码多项式表示的运算。它和下式等效：编出的码字T(x)为：T(x) = xn-k m(x) +r(x)在上例中，T(x) = 1100000 + 101 = 1100101 30第30页，共35

17、页，2022年，5月20日，1点14分，星期一 循环码的解码方法在检错时：当接收码字没有错码时，接收码组R(x)必定能被g(x)整除，即下式中余项r(x)应为零；否则，有误码。当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出了。 在纠错时：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。31第31页，共35页，2022年，5月20日，1点14分，星期一2. 监督多项式和监督矩阵为了便于对循环码编译码，通常还定义监督多项式，令其中g（x）是常数项为1的r次多项式，是生成多项式；h（x）是常数项为1的k次多项式，称为监督多项式。同理，它的监督矩阵H第32页，共35页，2022年，5月20日，1点14分，星期一第33页，共35页，2022年，5月20日，1点14分，星期一根据上述原理，循环码编码步骤可归纳如下。 用xr乘m（x）。这一运算实际上是把信