CN-差错编码

[[CN-NotesView]]

差错检测：差错编码

差错编码基本原理：

$D \to DR$ 其中R为差错检测和纠正bit（冗余bit）

如果是没有出错的就直接还原就好

但是即便判断出当前的R一致，也不能保证一定可靠

差错编码的检错能力

差错编码可以分为检错码和纠错码

对于检错码，如果编码集的汉明距离$d_s = r+1$ 那么差错编码可以检测r位的差错。

例如，编码集{0000,0101,1010,1111}的汉明距离$d_s$=2，可以100%检测1比特差错

对于纠错码，如果编码集的汉明距离$d_s$=2r+1，则该差错编码可以纠正r位的差错

例如，编码集{000000,010101,101010,111111} 的汉明距离$d_s$=3可以纠正1比特差错，如100010纠正为101010。

奇偶校验码

1bit校验位：

• 检测奇数位差错

编码的效率很高

二维奇偶校验

检测奇数位的差错：部分偶数位的差错

纠正同一行/列的奇数位错误

Internet校验和

发送端:

将数据（校验内容）划分为16位的二进制整数序列

求和

校验和

放入分组

接收端：

和发送端相同的算法进行计算

计算得到checksum

循环冗余校验码

检错能力更强大的校验编码

将数据bit，D，视为一个二进制数

选择一个r+1位的比特模式（生成bit模式）

目标：选择r位的CRCbit，R，满足

• <D,R> 刚好可以被G整除

• 接收端检错：利用G除<D,R>,余式全为0，无错；否则，有错！

• 可以检测所有突发长度小于r+1位差错

广泛应用于实际网络(以太网，802.11 WIFI，ATM)

期望：

$D \cdot 2^r \ XOR = \ nG$

相当于如果利用G去去除$D \cdot 2^r$，则余式即为R：