信息论第9章北理工

1线性码的纠错及伴随式①用校验矩阵编码，也用校验矩阵译码：接收到一个接收字R后，校验H

RT=0T是否成立：若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；H

RT的值是否为0是校验码字出错与否的依据。②伴随式/校验子：S=R

HT或ST=H

RT。③如何纠错？设发送码矢C=(Cn－1,Cn－2,…,C0)信道错误图样为E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n－1,n－2,…,0。9.3.2伴随式2接收字R为R=(Rn－1,Rn－2,…,R0)=C+E=(Cn－1+En－1,Cn－2+En－2,…,C0+E0)求接收字的伴随式（接收字用监督矩阵进行检验）

ST=H

RT=H

(C+E)T=H

CT+H

ET

(9.43)由于H

CT=0T，所以ST=H

ET设H=(h1,h2,…,hn)，其中hi表示H的列。代入式(9.43)得到3④总结伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；伴随式是错误的判别式：若S=0，则判为没有出错，接收字是一个码字；若S≠0，则判为有错。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是H阵中与错误码元对应列之和。4⑤举例：(7,3)码接收矢量R的伴随式计算设发送码矢C=1010011，接收码字R＝1010011，R与C相同。5若接收字中有一位错误6当码元错误多于1个时7⑥伴随式计算电路伴随式的计算可用电路来实现。以(7,3)码为例：设接收字为R=(R6R5R4R3R2R1R0)，伴随式为根据上式可画出伴随式计算电路，如图所示。8根据上式可画出伴随式计算电路，如图所示。99.3.3汉明码

常见的线形分组码有重复码，汉明码，里德-穆勒码，戈雷码（1）汉明码的构造和译码汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。10汉明码的结构参数：纠一个错误的线性码，其最小距离dmin=3；监督矩阵任意两列线性无关/H的任两列互不相同；没有全0的列。监督元个数n－k=r；H阵中每列有r个元素，至多可构成2r－1种互不相同的非0列。对于任意正整数r≥3，汉明码的结构参数为码长：n=2r－1信息位数：k=2r－r－1监督位数：r=n－k码的最小距离：dmin=3(t=1)11例一个二元（7，4）Hamming码的校验矩阵为

等价的编码方程为

12生成矩阵为

13因为信息元k=4,所以不同码字有M=16汉明（7，4）码00000000100101100001111001100001111010101010011001101001001011001100111010101111000000110010111100101101011111112024/6/23149.4.1循环码的多项式描述9.4.2循环码的生成多项式9.4循环码2024/6/2315(1)循环码的特点循环码是线性分组码的一个重要子类；由于循环码具有优良的代数结构，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。9.4.1循环码的多项式描述2024/6/2316(2)循环码的定义循环码：如果(n,k)线性分组码的任意码矢C=(Cn－1,Cn－2,…,C0)

的i次循环移位，所得矢量C(i)=(Cn－1－i,Cn－2－i,…,C0,Cn－1,…,Cn－i)

仍是一个码矢，则称此线性码为(n,k)循环码。2024/6/2317(3)循环码的多项式描述码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=Cn－1xn－1+Cn－2xn－2+…+C0)码多项式i次循环移位的表示方法记码多项式C(x)的一次左移循环为C(1)(x)

，i次左移循环为C(i)(x)2024/6/2318码多项式的模(xn+1)运算0和1两个元素模2运算下构成域。2024/6/2319码矢C循环i次所得码矢的码多项式

C(x)乘以x，再除以(xn+1)，得2024/6/2320上式表明：码矢循环一次的码多项式C(1)(x)是原码多项式C(x)乘以x除以(xn+1)的余式。写作因此，

C(x)的i次循环移位C(i)(x)是C(x)乘以xi除以(xn+1)的余式，即结论：循环码的码矢的i次循环移位等效于将码多项式乘xi后再模(xn+1)。2024/6/2321(4)举例：(7,3)循环码，可由任一个码矢，比如(0011101)经过循环移位，得到其它6个非0码矢；也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,…,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表9.4.1所示。2024/6/23222024/6/2323(1)循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在(n,k)循环码的2k个码字中，取前(k－1)位皆为0的码字g(x)（其次数r=n－k），再经(k－1)次循环移位，共得到k个码字：g(x),xg(x),…,xk－1g(x)

9.4.2循环码的生成多项式

这k个码字显然是相互独立的，可作为码生成矩阵的k行，于是得到循环码的生成矩阵G(x)2024/6/2324(2)循环码的生成多项式码的生成矩阵一旦确定，码就确定了；这就说明：(n,k)循环码可由它的一个(n－k)次码多项式g(x)来确定；所以说g(x)生成了(n,k)循环码，因此称g(x)为码的生成多项式。2024/6/2325(3)

生成多项式和码多项式的关系定理9.4.1：在(n,k)循环码中，生成多项式g(x)是惟一的(n－k)次码多项式，且次数是最低的。

[证明]：先证在(n,k)循环码系统中存在(n－k)次码多项式。因为在2k个信息组中，有一个信息组为，它的对应码多项式的次数为n－1－(k－1)=n－k(n－k)次码多项式是最低次码多项式。若g(x)不是最低次码多项式，那么设更低次的码多项式为g’(x)，其次数为(n－k－1)。g’(x)的前面k位为0，即k个信息位全为0，而监督位不为0，这对线性码来说是不可能的，因此g(x)是最低次的码多项式，即gn－k必为1。2024/6/2326g0=1，否则经(n－1)次左移循环后将得到低于(n－k)

次的码多项式。g(x)是惟一的(n－k)

次多项式。如果存在另一个(n－k)次码多项式，设为g’’(x)，根据线性码的封闭性，则g(x)+g’’(x)也必为一个码多项式。由于g(x)和g’’(x)的次数相同，它们的和式的(n－k)

次项系数为0，那么g(x)+g’’(x)是一个次数低于(n－k)

次的码多项式，前面已证明g(x)的次数是最低的，因此g’’(x)不能存在，所以g(x)是惟一的(n－k)

次码多项式。2024/6/2327定理9.4.2：在(n,k)循环码中，每个码多项式C(x)都是g(x)的倍式；而每个为g(x)倍式且次数小于或等于(n－1)的多项式，必是一个码多项式。

[证明]：设m=(mk－1,mk－2,…,m0)为任一信息组，G(x)为该(n,k)循环码的生成矩阵，则相应的码多项式为2024/6/2328上式表明：循环码的任一码多项式为g(x)的倍式。显然，凡是为

g(x)的倍式且次数小于或等于(n－1)的多项式，一定能分解成上式的形式，因而它就是信息多项式

m(x)=(mk－1xk－1+mk－21xk－2+…+m0)并由生成矩阵G(x)所生成的码多项式。定理9.4.3(定理9.4.2的逆定理)：在一个(n,k)线性码中，如果全部码多项式都是最低次的(n－k)次码多项式的倍式，则此线性码为一个(n,k)循环码。

注：一般说来，这种循环码仍具有把(n,k)线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进行循环移位，就未必能得到码的所有非0码矢了。所以称这种循环码为推广循环码。2024/6/2329码字循环关系图单纯循环码的码字循环图：(7,3)循环码2024/6/2330推广循环码的码字循环图：(6,3)循环码2024/6/2331定理9.4.4：(n,k)循环码的生成多项式g(x)是(xn+1)的因式，即xn+1=h(x)

g(x)。

[证明]：由于xkg(x)是n次多项式，可表示为xkg(x)=1

(xn+1)+g(k)(x)(9.4.1)

式中g(k)(x)是码多项式