多项式域编码(修改).ppt

* 2.6 系统循环码 系统循环码的生成矩阵 系统的一致校验矩阵是 例6： 以g(x)=(x3+x+1)为生成多项式生成一个(7,4)循环码，要求生成的循 环码是系统码。 解：由定义得对应给定g(x)的循环码的一般生成矩 阵为： * 对矩阵G的行进行运算，将第⑴、⑶、⑷行相加后作为第1行，第⑵、⑷行相加后作为第2行，得： 对应： 这样，就得到系统循环码的生成矩阵和一致校验矩阵。 2.6 系统循环码 在数据通信中，信息都是先划分成小块再组装成帧后(或叫分组、包等，仅名称不同而已)在线路上统计复用传送或存入共同物理介质的，帧尾一般都留有8、12、16或32位用作差错校验。如把一帧视为一个码字，则其校验位长度 不变而信息位 和码长 是可变的，其结构符合 缩短循环码的特点。只要以一个选定的 循环码为基础，改变 的值，就能得到任何信息长度的帧结构，而纠错能力保持不变。这种应用下的缩短循环码称为循环冗余校验码(Cyclic Redundancy Check，CRC)。 2.7 常用的循环码 2.7.1 循环冗余校验码 循环冗余校验码是系统的缩短循环码，码的结构如图所示。 图 循环冗余校验码(CRC)结构 图中，码字用码多项式 表示， 是 除以 后的余式， 为 次多项式，它们之间满足： 。虽然循环冗余校验码指的是整个码字 ，但人们习惯上仅把校验部分称为CRC码。 如果传输过程无差错，则接收码字 应等于发送码字 这时 能被 整除；如果不能被整除，则说明在传输过程中出现了误码。 2.7 常用的循环码 例7：某CRC的生成多项式为 。如果想发送一串信息“110001?”的前6位，并加上CRC校验，发送码字 应如何安排，接收码字 又如何校验？ 解：本题信息码字多项式 ， ，从生成多项式 的阶数得校验位数等于4，因此 。 将 除以 得余式 ： 于是，发送码字多项式 对应的发送码字为(1100011100)。 2.7 常用的循环码 在接收端，CRC校验实际上就是做除法运算：如果传输过程无差错，则 能被 整除，余式为“0”；如果余式不为“0”，则说明一定有差错。 例8 假设 ，即信息码字为(1011001)， ，求CRC校验码。由题得： 用 去除 ，有： 2.7 常用的循环码 经相除后得到的最后余数1010就是冗余校验码 。所以，发送码字(10110011010)。 需要注意的是，这里所涉及的运算与前面一样都是模2运算。 如果例子中的发送码字(10110011010)经传输后受噪声的干扰，在接收端变成为(10110011100)。求余式的除法如下： 2.7 常用的循环码 求得余式不为零，相当于在发送码字上加了差错图样“00000000110”。差错图样相应的多项式为 。有差错时，接收端收到的不再是 ，而是 + 。由于： 若 ，则这种差错就能检测出来，若 ，那么由于接收到的码字多项式仍然可被 整除，错误就检测不出来，也即发生了漏检。 理论上可以证明，循环冗余校验码的检错能力如下： ① 可检测出所有奇数个错； ② 可检测出所有单比特和双比特的错； 2.7 常用的循环码 ③ 可检测出所有小于、等于校验码长度 的突发错误； ④ 对于 位的突发性错误，查出概率为 ； ⑤ 对于多于 位的突发性错误，查出概率为