数据校检

数据校验的基本原理

<1> 数据校验的必要性

• 受元器件的质量、电路故障或噪音干扰等因素的影响，数据在被处理、传输、存储的过程中可能出现错误
• 若能设计硬件层面的错误检测机制，可以减少基于软件检错的代价（系统观）

<2> 校验的基本原理

• 增加冗余码（校验位） - 有效信息(k位) 校验信息(r位)

<3> 码距的概念

• 同一编码中，任意两个合法编码之间不同二进制位数的最小值
• 0011 与 0001 的码距为1，一位错误时无法识别
• 0000、0011、0101、0110、1001、1010、1100、1111等编码码距为2。 任何一位发生变化，如0000变成1000就从有效编码变成了无效编码，容易检测到这种错误
• 校验码中增加冗余项的目的就是为了增大码距

<4> 码距与检错或纠错能力的关系

• 码距 $\geq$ e+1 : 可检测e个错误
• 码距 $\geq$ 2t+1 : 可纠正t个错误
• 码距 $\geq$ e+t+1 : 可纠正t个错误，同时检测e个错误(e $\geq$ t)

<5> 选择码距要考虑的因素

• 码距越大，抗干扰能力越强，纠错能力越强，数据冗余越大，编码效率低，编码电路也相对负复杂
• 选择码距必须考虑信息发生差错的概率和系统能容许的最小差错率

奇偶校验

• 增加冗余码（检验位） - 有效信息(k位) 校验信息(r=1位)
• 编码 - 根据有效信息计算校验信息位，使校验码（数据+1位校验信息）中1的个数满足奇/偶检验的要求 - 0001 -> 00011 (偶校验) P1 = D₁$\bigoplus$D₂$\bigoplus$D₃$\bigoplus$D₄$\bigoplus$D₅$\bigoplus$D₆$\bigoplus$D_...$\bigoplus$D_n - 0001 -> 00010 (奇校验) P2 = $\overline{P1}$
• 特点 - 编码与检错简单 - 编码效率高 - 不能检测偶数位错误，无错结论不可靠，是一种错误检测码 - 不能定位错误，因此不具备纠错能力
• 奇偶校验的码距 - 码距为 2
• 改进的奇/偶校验 - 双向奇偶校验 - 可纠正1位错误
  
  - 可检测出某行/列上的奇数位
  
  - 可检测出一部分偶数位错误
  
  - 不能检测出错码分布在矩形4个顶点上的错误
  
  - 方块校验 - 垂直水平校验
• 奇/偶校验应用 - 应用场景 - 内存条 - 工程上的应用 - 路由器配置 - 一般在同步传输中常用奇校验 - 异步传输中常采用偶校验

CRC校验及其实现

• 原理 - 增加冗余码 有效信息（k位）检验信息（r位） N = k + r <= 2^r - 1 - 生成多项式G(x) 收发双方约定的一个(r + 1)位二进制数，发送方利用G(X)对信息多项式做模2除运算,生成校验码。接收方利用G(X)对收到的编码多项式做模2除运算检测差错及错误定位 - G(x)应满足的条件 - 最高位和最低位必须为1 - 当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0 - 不同位发生错误时，模2除运算后余数不同 - 对不为0余数继续进行模2除运算应使余数循环
• 常见生成多项式G(x)

• 模2除运算 - 模2运算规则 - 加/减运算（异或运算，加不进位，减不借位） - 0±0＝0，0±1＝1，1±0＝1，1±1＝0 - 模2除法 - 按模2减，求部分余数，不借位 - 上商原则 - 部分余数首位为1时，商为1，减除数 - 部分余数首位为0时，商为0，减0 - 当部分余数的位数小于除数的位数时，该余数即为最后余数

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxYzZjOTMxZjI5YmVkNWFhNWZmMDE1ODQyNjIzMTYuanBn?x-oss-process=image/format,png)

• CRC编码方法 - 根据待校验信息的长度k，按照 k+r ≤ 2^r－1 确定校验位r的位数 如对4位信息 1100 进行CRC编码，根据 4+r ≤ 2^r－1 得 r_min = 3 - 根据r 和生成多项式的选择原则，选择位数为 r +1 的生成多项式G(X)= 1011 - 进行下列变化 有效信息（k位） 检验信息（r位） 1100 000 即：将待校验的二进制信息Q(X)逻辑左移 r 位,得到Q(X)’ - 对Q(X)’按模2运算法则除G(x)，求CRC编码中的r位校验信息

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxZGUzZjNhNWI1ZmE5NDY3NTNkMDE1ODQyNjMzMTEuanBn?x-oss-process=image/format,png)

- 用得到的余数替换Q(X)’的最后r位即可得到对应的CRC编码
1100 010

• CRC的检错与纠错 - 接收方利用G(X)对收到的编码多项式做模2除运算

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxMTdjOTc3ODRmYTNiOWI3M2UwMDE1ODQyNjM0NTIuanBn?x-oss-process=image/format,png)

余数为0说明传输没有错误

- 接收方利用G(X)对收到的**有错**编码多项式做模2除运算

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxMTMwMmQ1YzZkMzQyN2JiMTc1MDE1ODQyNjM1NzIuanBn?x-oss-process=image/format,png)

余数不为0说明传输有错

- （7,4）编码不同数位出错对应的余数

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxNjUzZTM1MzY2MGIzZmY0MDk2MDE1ODQyNjM3OTYuanBn?x-oss-process=image/format,png)

- 一位出错情况下余数的循环特性

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxNTg0ZjE1Yjk3MmViMmU4ZjUyMDE1ODQyNjM5MTEuanBn?x-oss-process=image/format,png)

- 利用出错情况下余数的循环特性就行纠错

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxMDk2MjVmZGQxMGU4MGM0OTk2MDE1ODQyNjQwMDguanBn?x-oss-process=image/format,png)

	- 若余数不为0，一边对余数补0继续做模2除，同时让被检测的校验码循环左移，当余数为101时，出错位也移到A1位置。通过异运算纠正后继续循环左移和执行余数模2除法，直到修改后的出错位回原位。不需对每一位提供纠正电路
	- 当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因

• CRC的应用 - 关于CRC的国际标准（部分）

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxZWMzN2IyNzMwMWUwODU2NTI1MDE1ODQyNjQzNTkuanBn?x-oss-process=image/format,png)

海明校验

• 原理 - 增加冗余码 有效信息（k位）检验信息（r位） N = k + r <= 2^r - 1 - 设k+r位海明码从左到右依次为第1，2，3，…...， k+r位，r位校验位记为P_i（i=1，2，…，r)，分别位于k+r位海明编码的第2^i-1 （i=1，2，…，r)位上，其余位依次放置被校验的数据位 - (7，4)海明校验码中校验位和被校验信息位的排列如下 - 海明码位号 H_j      1 2 3 4 5 6 7 8 9 10 11 P和b的分布          P₁ P₂ b₁ P₃ b₂ b₃ b₄ P₄ b₅ b₆ b₇

- H<sub>j</sub> 位的**数据**被编号小于j的若干个海明位号之和等于j的**校验位**所校验 ,如:

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxMWJlMjNmNDRjNjUzMjZkN2YwMDE1ODQyNjUyNjUuanBn?x-oss-process=image/format,png)

设被传送的信息b<sub>1</sub>b<sub>2</sub>b<sub>3</sub>b<sub>5</sub>b<sub>5</sub>b<sub>6</sub>b<sub>7</sub>  = 1 0 1 1 0 0 0，采用偶校验

则

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxOWQ0YTZmZjkxYmY4ZWExYjBiMDE1ODQyNjU0ODguanBn?x-oss-process=image/format,png)

得到的海明编码为H = 0 1 1 0 0 1 1 0 0 0 0

![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ncmFwaC5iYWlkdS5jb20vcmVzb3VyY2UvMTIxOTQ0Yzk3ZDlkNTExZTFmNGExMDE1ODQyNjk1MTguanBn?x-oss-process=image/format,png)

G<sub>4</sub>G<sub>3</sub>G<sub>2</sub>G<sub>1</sub>= 0 0 0 0， 表明无错！

• 特点 - 指错字G₄G₃G₂G₁= 0000 不一定无错（利用偶校验的特点去判断） - 一位错与两位错不能由指错字区别
• 海明校验的完善 </sub>G₂G₁= 0 0 0 0， 表明无错！
• 特点 - 指错字G₄G₃G₂G₁= 0000 不一定无错（利用偶校验的特点去判断） - 一位错与两位错不能由指错字区别
• 海明校验的完善 - 在海明校验的基础上增加一位奇偶校验位