- 数据校验的基本原理
- <1> 数据校验的必要性
- <2> 校验的基本原理
- <3> 码距的概念
- <4> 码距与检错或纠错能力的关系
- <5> 选择码距要考虑的因素
- 奇偶校验
- CRC校验及其实现
- 海明校验
数据校验的基本原理
<1> 数据校验的必要性
- 受元器件的质量、电路故障或噪音干扰等因素的影响,数据在被处理、传输、存储的过程中可能出现错误
- 若能设计硬件层面的错误检测机制,可以减少基于软件检错的代价(系统观)
<2> 校验的基本原理
- 增加冗余码(校验位)
- 有效信息(k位) 校验信息(r位)
<3> 码距的概念
- 同一编码中,任意两个合法编码之间不同二进制位数的最小值
- 0011 与 0001 的码距为1,一位错误时无法识别
- 0000、0011、0101、0110、1001、1010、1100、1111等编码码距为2。 任何一位发生变化,如0000变成1000就从有效编码变成了无效编码,容易检测到这种错误
- 校验码中增加冗余项的目的就是为了增大码距
<4> 码距与检错或纠错能力的关系
- 码距
- 码距
- 码距e+t+1 : 可纠正t个错误,同时检测e个错误(e
<5> 选择码距要考虑的因素
- 码距越大,抗干扰能力越强,纠错能力越强,数据冗余越大,编码效率低,编码电路也相对负复杂
- 选择码距必须考虑信息发生差错的概率和系统能容许的最小差错率
奇偶校验
- 增加冗余码(检验位)
- 有效信息(k位) 校验信息(r=1位)
- 编码
- 根据有效信息计算校验信息位,使校验码(数据+1位校验信息)中1的个数满足奇/偶检验的要求
- 0001 -> 00011 (偶校验) P1 = D1D2D3D4D5D6D…Dn
- 0001 -> 00010 (奇校验) P2 =
- 特点
- 编码与检错简单
- 编码效率高
- 不能检测偶数位错误,无错结论不可靠,是一种错误检测码
- 不能定位错误,因此不具备纠错能力
- 奇偶校验的码距
- 码距为 2
- 改进的奇/偶校验
- 双向奇偶校验
- 可纠正1位错误
- 可检测出某行/列上的奇数位
- 可检测出一部分偶数位错误
- 不能检测出错码分布在矩形4个顶点上的错误
- 方块校验
- 垂直水平校验
- 奇/偶校验应用
- 应用场景
- 内存条
- 工程上的应用
- 路由器配置
- 一般在同步传输中常用奇校验
- 异步传输中常采用偶校验
CRC校验及其实现
- 原理
-
增加冗余码
有效信息(k位)检验信息(r位)
N = k + r <= 2r- 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 ≤ 2r-1 确定校验位r的位数
如对4位信息 1100 进行CRC编码,根据 4+r ≤ 2r-1
得 rmin= 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)编码不同数位出错对应的余数
- 一位出错情况下余数的循环特性
- 利用出错情况下余数的循环特性就行纠错
- 若余数不为0,一边对余数补0继续做模2除,同时让被检测的校验码循环左移,当余数为101时,出错位也移到A1位置。通过异运算纠正后继续循环左移和执行余数模2除法,直到修改后的出错位回原位。不需对每一位提供纠正电路
- 当位数增多时,循环码校验能有效地降低硬件代价,这是它得以广泛应用的主要原因
- CRC的应用
- 关于CRC的国际标准(部分)
海明校验
- 原理
-
增加冗余码
有效信息(k位)检验信息(r位)
N = k + r <= 2r - 1
- 设k+r位海明码从左到右依次为第1,2,3,……, k+r位,r位校验位记为Pi(i=1,2,…,r),分别位于k+r位海明编码的第2i-1 (i=1,2,…,r)位上,其余位依次放置被校验的数据位
- (7,4)海明校验码中校验位和被校验信息位的排列如下
-
海明码位号 Hj1 2 3 4 5 6 7 8 9 10 11
P和b的分布 P1P2b1P3b2b3b4P4b5b6b7
- Hj 位的数据被编号小于j的若干个海明位号之和等于j的校验位所校验 ,如:
设被传送的信息b1b2b3b5b5b6b7 = 1 0 1 1 0 0 0,采用偶校验
则
- 特点
- 指错字G4G3G2G1= 0000 不一定无错(利用偶校验的特点去判断)
- 一位错与两位错不能由指错字区别
-
海明校验的完善
G2G1= 0 0 0 0, 表明无错!
- 特点
- 指错字G4G3G2G1= 0000 不一定无错(利用偶校验的特点去判断)
- 一位错与两位错不能由指错字区别
- 海明校验的完善
- 在海明校验的基础上增加一位奇偶校验位