北京理工大学信息论第九章2.ppt

* * 定理9.4.4： (n,k) 循环码的生成多项式 g(x) 是 (xn+1)的因式，即 xn+1=h(x)?g(x)。 [证明]： 由于 xk g(x) 是 n 次多项式，可表示为 xk g(x)=1?(xn+1)+ g(k)(x) (9.4.1) 式中 g(k)(x) 是码多项式 g(x) 乘以 xk 除以 (xn+1) 的余式。 根据循环码的移位关系，它是 g(x) 循环移位 k 次所得到的码多项式，因而 g(k)(x) 是 g(x) 的倍式。 设 g(k)(x)=m(x)g(x) 代入式(9.4.1)得 (xn+1)=[xk+m(x)]g(x) 上式表明： g(x) 是 (xn+1) 的因式。 第九章作业 9.1, 9.3（1）（3）（4） * * * * * * * * * 第六章 信道编码 * 线性码的纠错及伴随式 ① 用校验矩阵编码，也用校验矩阵译码：接收到一个接收字 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 伴随式 * 接收字 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)得到 * ④ 总结 伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定； 伴随式是错误的判别式： 若S=0，则判为没有出错，接收字是一个码字； 若S≠0，则判为有错。 不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是H 阵中与错误码元对应列之和。 * ⑤ 举例： (7,3)码接收矢量 R 的伴随式计算 设发送码矢C=1010011，接收码字R＝1010011，R与C相同。 * 若接收字中有一位错误 * 当码元错误多于1个时 * ⑥ 伴随式计算电路 伴随式的计算可用电路来实现。 以(7,3)码为例：设接收字为R=(R6R5R4R3R2R1R0)，伴随式为 根据上式可画出伴随式计算电路，如图所示。 * 根据上式可画出伴随式计算电路，如图所示。 * 9.3.3 汉明码 常见的线形分组码有重复码，汉明 码，里德-穆勒码，戈雷码 （1）汉明码的构造和译码 汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。 * 汉明码的结构参数： 纠一个错误的线性码，其最小距离 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) * 例 一个二元（7，4）Hamming码的校验矩阵为 等价的编码方程为 * 生成矩阵为 * 因为信息元k=4,所以不同码字有M=16 汉明（7，4）码 0000000 0100101 1000011 1100110 0001111 0101010 1001100 1101001 0010110 0110011 1010101 1110000 0011001 0111100 1011010 1111111 * * 9.4.1 循环码的多项式描述 9.4.2 循环码的生成多项式 9.4 循环码 * * (1) 循环码的特点 循环码是线性分组码的一个重要子类； 由于循环码具有优良的代数结构，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法； 循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。 9.4.