Data Check Code

校验码是指能够发现或能够自动纠正错误的数据编码,也称为检错纠错编码

Posted by Dusign on 2019-09-10
Words 1k and Reading Time 3 Minutes
Viewed Times

校验码的原理是通过增加一些冗余码,来检验或纠错编码。通常编码都由许多码字构成,任意两个合法码字之间最少变化的二进制位数,称为数据校验码的码距。对于码距不小于$2$的数据校验码,开始具有检错的能力。码距越大,检错、纠错能力就越强,而且检错能力总是大于或等于纠错能力。下面介绍几种常用的校验码。

奇偶校验码

奇偶校验码比较简单,原理是在原编码上加一个校验位,它的码距等于2,可以检测出一位错误(或奇数位错误),但是不能确定错误位置,也不能检测出偶数位错误,增加的冗余位称为奇偶校验位。数据构成如下

odd-even

校验位的取值($0$ 或 $1$)将使整个校验码中 “$1$” 的个数为奇数或偶数,所以有两种可供选择的校验规律。

  • 奇校验码:整个校验码中 “$1$” 的个数为奇数
  • 偶校验码:整个校验码中 “$1$” 的个数为偶数

海明校验码

海明校验码是广泛采用的一种有效的校验码,它实际上是一种多重奇偶校验码。原理是在有效信息位中加入几个校验位形成海明码,并把海明码的每一个二进制位分配到几个奇偶校验组中,当某一位出错后,就会引起有关的几个校验位的值发生变化,这不但可以发现错位,还能指出错位的位置,位自动纠错提供了依据。

依据纠错理论得: $L-1 =D+C$     其中   $D≥C$

即编码最小码距 $L$ 越大,则其检测错误的位数 $D$ 越大,纠正错误的位数 $C$ 也越大,且纠错能力恒小于或等于检错能力。海明码就是根据这一理论提出的具有纠错能力的一种编码。

海明码计算步骤如下:

  • $n+k≤2^k-1$ , 若要检测 $2$ 位错,则需要 $k+1$ 位
  • 校验位 $Pi$ 在海明位号 $2^{i-1}$ 位上
  • 被校验数据位的海明位号等于检验该数据位的各校验位海明位号之和
  • 校验位 $Pi$ 取值为第 $i$ 组所有位求异或
  • 由校验位和参与形成校验位的各信息位进行奇偶校验检查(异或),若为 $0$ 则无错,否则为错误位号

CRC

循环冗余校验码即 CRC 码是在 $K$ 位信息码后再拼接 $R$ 位校验码,整个编码长度为 $N$ 位,因此,这种编码又称 $(N,K)$ 码。

CRC 码基于线性编码理论,在发送端将要传送的 $K$ 位二进制信息码左移 $R$ 位,将它与生成多项式 $G(x)$ 做模$2$除法,生成一个 $R$ 位校验码,并附在信息码后,构成一个新的二进制码(CRC码),共 $K+R$ 位。在接收端,则利用生成多项式对接收到的编码做模$2$除法,以检测和确定出错的位置,如无错则整除,其中生成多项式是接收端和发送端的一个约定。

任意一个二进制数码都可以用一个系数仅为 “$0$” 或 “$1$” 的多项式与其对应。生成多项式 $G(x)$ 的最高幂次为 $R$,转换成对应的二进制数有 $R+1$ 位。

CRC编码和检测过程如下:
数据 M 为 $k$ 位,需要添加 $n$ 位冗余位,共发送 $k+n$ 位,除数 P 为 $n+1$ 位

  • 在 M 后面添加 $n$ 位 $0$,变为 $k+n$ 位
  • M 变为 $k+n$ 位后与 $n+1$ 位的 P 做模$2$除法,得出商 Q ,余数 R ($n$位)
  • 则 R 为冗余位,也称帧检验序列 FCS
  • 接收端用接收数据模$2$除 P,若余数 R 为 $0$,则无差错,否则接收数据第 $R$ 位出错

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

...

00:00
00:00