数据校验的基本原理

<1> 数据校验的必要性

• 受元器件的质量、电路故障或噪音干扰等因素的影响，数据在被处理、传输、存储的过程中可能出现错误

• 若能设计硬件层面的错误检测机制，可以减少基于软件检错的代价（系统观）

<2> 校验的基本原理

• 增加冗余码（校验位）

• 有效信息(k 位) 校验信息(r 位)

<3> 码距的概念

• 同一编码中，任意两个合法编码之间不同二进制位数的最小值

• 0011 与 0001 的码距为 1，一位错误时无法识别

• 0000、0011、0101、0110、1001、1010、1100、1111 等编码码距为 2。 任何一位发生变化，如 0000 变成 1000 就从有效编码变成了无效编码，容易检测到这种错误

• 校验码中增加冗余项的目的就是为了增大码距

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

• 码距 $\ge$ e+1 : 可检测 e 个错误

• 码距 $\ge$ 2t+1 : 可纠正 t 个错误

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

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

• 码距越大，抗干扰能力越强，纠错能力越强，数据冗余越大，编码效率低，编码电路也相对负复杂

• 选择码距必须考虑信息发生差错的概率和系统能容许的最小差错率

奇偶校验

• 增加冗余码（检验位）

• 有效信息(k 位) 校验信息(r=1 位)

• 编码

• 根据有效信息计算校验信息位，使校验码（数据+1 位校验信息）中 1 的个数满足奇/偶检验的要求

• 0001 -> 00011 (偶校验) P1 = D₁$⨁$D₂$⨁$D₃$⨁$D₄$⨁$D₅$⨁$D₆$⨁$D_...$⨁$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

• 当部分余数的位数小于除数的位数时，该余数即为最后余数

• 
  
  

• 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 位校验信息

• 
  
  

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

• CRC 的检错与纠错

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

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

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

• 
  余数不为 0 说明传输有错

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

• 
  
  

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

• 
  
  

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

• 
  
  

• CRC 的应用

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

• 
  
  

海明校验

• 原理

• 增加冗余码有效信息（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 11P 和 b 的分布          P₁ P₂ b₁ P₃ b₂ b₃ b₄ P₄ b₅ b₆ b₇

• H_j 位的数据被编号小于 j 的若干个海明位号之和等于 j 的校验位所校验 ,如:

• 
  
  

• 设被传送的信息 b₁b₂b₃b₅b₅b₆b₇ = 1 0 1 1 0 0 0，采用偶校验则

• 
  
  

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

• 
  
  

• G₄G₃G₂G₁= 0 0 0 0， 表明无错！

• 特点

• 指错字 G₄G₃G₂G₁= 0000 不一定无错（利用偶校验的特点去判断）

• 一位错与两位错不能由指错字区别

• 海明校验的完善</sub>G₂G₁= 0 0 0 0， 表明无错！

• 特点

• 指错字 G₄G₃G₂G₁= 0000 不一定无错（利用偶校验的特点去判断）

• 一位错与两位错不能由指错字区别

• 海明校验的完善

• 在海明校验的基础上增加一位奇偶校验位