校验与纠错 :奇偶校验、汉明码、CRC

以前经常担心计算机里面存储的数据万一哪一位数据出错,就会导致很大后果的事情。其实这种事情完全不必担心,因为计算机的存储器在设计的时候就考虑到了防止出错以及纠错的情况。根据应用场景不同,校验的方案有很多,本文介绍经典的校验码校验。

奇偶校验

奇偶校验的原理是在原信息的基础上加一位校验位,使原信息的1的个数为奇数(或偶数)。

如果有一位出错,那么接受到的信息1的个数就不是奇数(或偶数),从而判断传输出错。

汗明码

汉明码的原理是将数据分成k个小组,然后对每个小组分别做偶校验。不仅可以判断数据是否出错,还可以得出出错的位置以便纠错。

这种小组的划分有如下特点:

  1. 每个小组 g_i 有一位且仅有一位为它所独占,这一位是其他小组所没有的,即 g_i 小组独占第 2^{i-1} 位。
  2. 每两个小组 g_i g_j 共同占有一位是其他小组没有的,即每两小组 g_i g_j 共同占有第 2^{i-1}+2^{j-1} 位。
  3. 每3个小组 g_i,g_j g_k 共同占有第 2^{i-1}+2^{j-1}+2^{k-1} 位,是其他小组所没有的。
  4. 以此类推...

例如,欲传递信息为 {b}_{4} {b}_{3} {b}_{2}{b}_{1}(n=4) ,配置成汉明码需增添3个检测位,将数据分成3组,且它们位置的安排如下:

\begin{array}{c|ccccccc} \text { 二进制序号 } & \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} & \mathbf{6} & \mathbf{7} \\ \hline \text { 名称 } & \mathbf{C}_{\mathbf{1}} & \mathbf{C}_{\mathbf{2}} & \mathbf{b}_{\mathbf{4}} & \mathbf{C}_{\mathbf{4}} & \mathbf{b}_{\mathbf{3}} & \mathbf{b}_{\mathbf{2}} & \mathbf{b}_{\mathbf{1}} \end{array}

C_1 对小组 1,3,5,7 做偶校验。
C_2 对小组 2,3,6,7 做偶校验。
C_4 对小组 4,5,6,7 做偶校验。

\begin{array}{l} C_{1}=b_{4} \oplus b_{3} \oplus b_{1}=0 \oplus 1 \oplus 1=0 \\ C_{2}=b_{4} \oplus b_{2} \oplus b_{1}=0 \oplus 0 \oplus 1=1 \\ C_{4}=b_{3} \oplus b_{2} \oplus b_{1}=1 \oplus 0 \oplus 1=0 \end{array}

故0101的汉明码应为 \mathrm{C}_{1} \mathrm{C}_{2} \mathrm{b}_{4} \mathrm{C}_{4} \mathrm{b}_{3} \mathrm{b}_{2} \mathrm{b}_{1} ,即0100101.

若第1位出错,则 C_1 出错。
若第2位出错,则 C_2 出错。
若第3位出错,则 C_1,C_2 出错。
若第4位出错,则 C_4 出错。
若第5位出错,则 C_1,C_4 出错。
若第6位出错,则 C_2,C_4 出错。
若第7位出错,则 C_1,C_2,C_4 出错。

由上面的规律可得出公式

2^{k} \geqslant n+k+1

CRC 循环冗余校验

CRC校验中有两个关键点:

  1. 预先确定一个n位二进制数(可按国际标准选择)。
  2. 原始帧左移k位,与上面选定的数进行“模2除法”运算,得到k位余数即为校验码。将校验码拼接到原始帧后面作为发送帧。(其中k=n-1,余数的位数比除数的位数少1)

因为发送帧后面附加了余数,做了“去余”处理,所以发送帧能够被这个数整除,如果不能整除则说明传输出错,不同的出错位其余数也不同。

【说明1】“模2除法”与“算术除法”类似,但它既不向上位借位,也不比较除数和被除数的相同位数值的大小,只要以相同位数进行相除即可。模2加法运算为:1+1=0,0+1=1,0+0=0,无进位,也无借位;模2减法运算为:1-1=0,0-1=1,1-0=1,0-0=0,也无进位,无借位。相当于二进制中的逻辑异或运算。也就是比较后,两者对应位相同则结果为“0”,不同则结果为“1”。如100101除以1110,结果得到商为11,余数为1。

image

【说明2】二进制信息码可以由多项式表示,例如 D_{n-1} D_{n-2} \cdots D_{2} D_{1} D_{0} ,可用多项式 M(x) 表示:

M(x)=D_{n-1} x^{n-1}+D_{n-2} x^{n-2}+\cdots+D_{1} x^{1}+D_{0} x^{0}

下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式(也就是除数)为 G(X) = X^4 + X^3 + 1 ,要求出二进制序列10110011的CRC校验码。下面是具体的计算过程:

(1)首先把生成多项式转换成二进制数,由 G(X) = X^4 + X^3 + 1 可得到它的二进制比特串为11001。

(2)因为生成多项式的位数为5,根据前面的介绍,得知CRC校验码的位数为4(校验码的位数比生成多项式的位数少1)。因为原数据帧10110011,在它后面再加4个0,得到101100110000,然后把这个数以“模2除法”方式除以生成多项式,得到的余数(即CRC码)为0100,如图所示。注意参考前面介绍的“模2除法”运算法则。

image

(3)把上步计算得到的CRC校验0100替换原始帧101100110000后面的四个“0”,得到新帧101100110100。再把这个新帧发送到接收端。

(4)当以上新帧到达接收端后,接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除,验证余数是否为0,如果为0,则证明该帧数据在传输过程中没有出现差错,否则出现了差错。

posted @ 2020-08-08 16:04:04
评论加载中...

发表评论

😃😄😁😆😅🤣😂🙂😉😊🥰😍😘😜🤪😝🤑🤔🤨😏😒🙄😮‍💨🤮😵‍💫🥳😎😳🥺😭😡(这里的表情可以复制)