数据校验码

刺骨的言语ヽ痛彻心扉 2024-03-26 22:03 28阅读 0赞

**目录**

一、奇偶校验码

1、奇偶校验概念

2、简单奇偶校验

3、交叉奇偶校验

二、汉明校验码

三、循环冗余校验码

1、循环冗余校验码的编码方式

2、循环冗余校验码的检验与纠错

3、生成多项式的选择

--------------------

在数据存取和传输的过程中可能会发生错误，产生错的元原因可能有很多种：

*  设备临界工作状态
 *  外界高频干扰
 *  收发设备中的间接性故障
 *  电路的偶然瞬变现象
 *  ……

为了减少和避免错误，需要**提高硬件本身的可靠性**外，还需要**在数据编码上找出路**

**数据校验码**是指那些能够发现错误或者能够自动纠正错误的数据编码，又称为“检错纠错编码”

任何一种编码都有许多码字构成，任意两个码字之间最少变化的二进制位数称为数据校验码的**码距。**

具有检、纠错能力的数据校验码的实现原理是：在编码中，除去合法的码字外，再加进一些分非法的码字，当某个合法码字出现错误时就变成了非法码字。码距越大，检错、纠错的能力就越强，而且检错能力总大于纠错能力。

## 一、奇偶校验码 ##

### 1、奇偶校验概念 ###

奇偶校验是一种最简单的数据校验码，它的**码距等于2**，可以检查出**一位**错误（或奇数位错误），**但是不能确定出错的位置，也不能检查出偶数位错误。**

事实上，一位出现错的概率比多为出现错的概率要高得多，所以虽然奇偶校验的检错能力差，但是还是一种比较广泛的校验方式，常用于存储器读写检查、ASCII码字符传输过程中的检查

![17a9a38029ce4ada8d371391de06201e.png][]

奇偶校验的实现方法是：由若干有效信息（如一个字节），再加上一个二进制位（校验位）组成的校验码。校验位的取值（0或1）将使整个校验码中的1的个数位奇数或偶数，所以有两种可供选择的校验规律：

*  奇校验——整个校验码（有效信息位和校验位）中1的个数位奇数
 *  偶校验——整个校验码中1的个数位偶数个

### 2、简单奇偶校验 ###

简单奇偶校验仅实现**横向**的奇偶校验，下面给出几个字节奇偶校验后的结果

<table style="width:500px;">  奇偶检验实例  
 <tbody> 
  <tr> 
   <td style="text-align:center;"><strong>有效信息（8位）</strong></td> 
   <td style="text-align:center;"><strong>奇校验码（9位）</strong></td> 
   <td style="text-align:center;"><strong>偶校验码（9位）</strong></td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">0000 0000</td> 
   <td style="text-align:center;">1 0000 0000</td> 
   <td style="text-align:center;">0000 0000</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">0101 0100</td> 
   <td style="text-align:center;">0 0101 0100</td> 
   <td style="text-align:center;">1 0101 0100</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">0111 1111</td> 
   <td style="text-align:center;">0 0111 1111</td> 
   <td style="text-align:center;">1 0111 1111</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">1111 1111</td> 
   <td style="text-align:center;">1 1111 1111</td> 
   <td style="text-align:center;">0 1111 1111</td> 
  </tr> 
 </tbody> 
</table>

在上表所示的奇校验码或偶校验码中，**最高位为检验位**，其余八位为信息位。在实际应用中多采用奇校验，因为奇校验中不存在全0代码，在某些场合下更容易辨别

奇偶校验编码和校验是由专门的电路实现的，常见的有并行奇偶电路，这是由若干个异或门组成的塔形结构，同时给出了“偶形成”、“奇形成”、“偶校验出错”、“奇校验出错 ”等信号。

![2fbaffa241ce4e96990791442eeadbf4.jpeg][]

下面以奇校验为例说明对储存信息进行奇校验的全过程：

（1）校验位形成

当第一个字节的代码D7~D0写入储存时，就同时将他们送往奇偶校验逻辑电路，该电路产生机形成信号就是校验位，它将与8位代码一起作为奇校验码写入主存。

若D7~D0中有偶数个1，则“奇形成”=1；若有奇数个1，则“奇形成”=0

（2）校验检测

读出时，将读出的9位代码（8位信息位和1位校验位）同时送入奇偶校验电路检测，若读出代码无错，则“奇偶校验出错”=0；若读出代码中的一位上出现错误，则“奇偶校验出错”=1，从而指示这9位代码中一定有某一位出现了错误，但具体的错误位置是不能确定的。

### 3、交叉奇偶校验 ###

计算机在进行大量字节（数据块）传输时，不仅每一个字节有一个奇偶校验位，做横向校验，而且全部字节的同一位也设置一个就校验位，做纵向校验，这种横向纵向同时校验的方法称为**交叉校验。**

![14dec494a8464f588f5065c9572612c2.jpeg][]

交叉校验可以发现两位同时出错的情况，假设第2个字节A6、A4两位均出错，第2个字节的横向检验位无法检验出错，但是第A6、A4位所在列的纵向校验位会显示出错，这与前面的简单奇偶校验相比要保险多了。

## 二、汉明校验码 ##

汉明码（因为是英文翻译，故有时也称为海明码）是于1950年提出的，目前仍然广泛采用的一种有效的校验码，主存的EEC采用的就是与此类似的校验码。

汉明码实际上是一种多重奇偶校验，其实现原理是在有效信息位中加入几个校验位，形成汉明马使码距比较均匀地拉大，并把汉明码的每一个二进制位分配到几个奇偶校验组中，当一位出错后就会引起有关的几个校验位的值发生变化，这不**但可以发现错误，还能指出错误的位置**，为自动纠错提供了依据。

下面仅介绍能检验和自动矫正一位错并能发现两位错的汉明码的编码原理。此时校验位的位数K和信息位的位数N应该满足： ![2^\{K-1\}\\geq N+K+1][2_K-1_geq N_K_1]

按该不等式信息为N值和校验位K值的对应关系如下表

<table style="width:500px;">  信息位N值和检验位K值的对应关系  
 <tbody> 
  <tr> 
   <td style="text-align:center;"><strong>N值</strong></td> 
   <td style="text-align:center;"><strong>最小K值</strong></td> 
   <td style="text-align:center;"><strong>N值</strong></td> 
   <td style="text-align:center;"><strong>最小K值</strong></td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">1~3</td> 
   <td style="text-align:center;">4</td> 
   <td style="text-align:center;">26~56</td> 
   <td style="text-align:center;">7</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">4~10</td> 
   <td style="text-align:center;">5</td> 
   <td style="text-align:center;">57~119</td> 
   <td style="text-align:center;">8</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">11~25</td> 
   <td style="text-align:center;">6</td> 
   <td style="text-align:center;"></td> 
   <td style="text-align:center;"></td> 
  </tr> 
 </tbody> 
</table>

若汉明码的最高位号m，最低位号为1，即有![H\_\{m\}H\_\{m-1\}...H\_\{2\}H\_\{1\}][H_m_H_m-1_...H_2_H_1]，则此汉明码的编码规则通常为下:

（1)校验位和信息位之和为m，每个校验位![P\_\{i\}][P_i]在汉明码中被分到位号![2^\{i-1\}][2_i-1]的位置，上其余各位为信息位

（2）汉明码每一位![H\_\{i\}^\{\}][H_i]由多个校验位校验，其关系是被校验的每一位位号等于校验它的个校验位的位号之和，即汉明码的位号实质上是参与校验的各校验位权值之和，这样安排的目的是希望校验的结果能正确地反映出错的位号

（3）在增大码距时应使所有编码的码距尽量均匀的增大，以保证对所有代码的检测能力平衡的提高

**汉明码设计思路**：分组校验一>多个校验位一>校验位标注出错位置

![63854d6033934f229329ea00c3749e1f.jpeg][]

## 三、循环冗余校验码 ##

循环冗余校验码，是通过除法运算来建立有效信息位和校验位之间的约定关系的

假设带编码的有效信息以多项式![M(X)][M_X]表示，将它左移若干位后，用另一个约定的多项式![G(X)][G_X]去除产生的余数![R(X)][R_X]就是检验位。

有效信息和检验位像拼接就构成了CRC码

当整个CRC码被接收后，仍用约定的多项式![G(X)][G_X]去除，若余数为零表示该代码是正确的；若余数不为零，则表明某一位出错，再进一步由于数值确定出错的位置以便进行纠正。

### 1、循环冗余校验码的编码方式 ###

![3f1d33ee773349ffa378e6883ca29cfc.png][]

循环冗余校验码是由两个部分组成。左边位信息位，右边为校验位。

若信息位为N位，校验位为K位，则**该校验码称为（N+K，N）码**。

循环冗余校验码编码的规律如下：

（1）把待编码的N位有效信息表示为多项式![M(X)][M_X]

（2）把![M(X)][M_X]向左移K位，得到![M(X)\*X^\{k\}][M_X_X_k]，这样就空出来K位，一边拼装K位余数（即校验位）

（3）选取一个K+1位的产生多项式![G(X)][G_X]，对![M(X)\*X^\{k\}][M_X_X_k]做模2除

![\\frac\{M(X)\*X^\{k\}\}\{G(X)\}=Q(X)+\\frac\{R(X)\}\{G(X)\}][frac_M_X_X_k_G_X_Q_X_frac_R_X_G_X]

（4）把左移K位以后的有效信息与余数![R(X)][R_X]做模2加减，拼接为CRC码，此时的CRC码共有N+K位。

![M(X)\*X^\{k\}+R(X)=Q(X)\*G(X)][M_X_X_k_R_X_Q_X_G_X]

![29787539f48743759ced867711b5b8c3.jpeg][]

### 2、循环冗余校验码的检验与纠错 ###

把接收到的CRC码用约定生成的多项式![G(X)][G_X]去除，如果正确，则余数为零；如果某一位出错，则余数不为零，不同的位数出错余数不同余数和除错位序号之间有唯一的对应关系![9d313bca2a194386a2f8e7345c10b3ac.jpeg][]

如果某一位出错则余数不为零，对此余数补零后，当做被除数再继续除下去，余数将按表的顺序循环。

例如第7位出错余数为001，把其后补零再除以第2次余数为010以后依次分别为100、011、110、111、101，然后又回到001，反复循环，这就是“循环码”的词的来源，根据循环码的特征一边对于树补零，继续做模2除法，同时让被检测到的检验码循环左移。当余数为101时，原来出错的位置已经移到了A1的位置，通过异或门将其法纠正，在下一次循环左移时又送回原来的位置，所以满一个循环就可以得到一个纠正的码字。

### 3、生成多项式的选择 ###

生成多项式被用来生成CRC码，并不是任意一个k+1位多项式都可以作为生成多项式用的，它应该满足以下条件：

*  任何一位发生错误都应使余数不为0
 *  不同位发生错误应当使余数不同
 *  对余数作模2除法应使余数循环

[17a9a38029ce4ada8d371391de06201e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/74071baa289a41e6b4991703308c038a.png
[2fbaffa241ce4e96990791442eeadbf4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/226e9289f0b844e29d9118e69d207fde.png
[14dec494a8464f588f5065c9572612c2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/375dfc5168744c83abd35f80daaa5d3b.png
[2_K-1_geq N_K_1]: https://latex.csdn.net/eq?2%5E%7BK-1%7D%5Cgeq%20N&plus;K&plus;1
[H_m_H_m-1_...H_2_H_1]: https://latex.csdn.net/eq?H_%7Bm%7DH_%7Bm-1%7D...H_%7B2%7DH_%7B1%7D
[P_i]: https://latex.csdn.net/eq?P_%7Bi%7D
[2_i-1]: https://latex.csdn.net/eq?2%5E%7Bi-1%7D
[H_i]: https://latex.csdn.net/eq?H_%7Bi%7D%5E%7B%7D
[63854d6033934f229329ea00c3749e1f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/04290ab716864697b1c170479012a391.png
[M_X]: https://latex.csdn.net/eq?M%28X%29
[G_X]: https://latex.csdn.net/eq?G%28X%29
[R_X]: https://latex.csdn.net/eq?R%28X%29
[3f1d33ee773349ffa378e6883ca29cfc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4781ddba51d244febf7d5f99b0b957a8.png
[M_X_X_k]: https://latex.csdn.net/eq?M%28X%29*X%5E%7Bk%7D
[frac_M_X_X_k_G_X_Q_X_frac_R_X_G_X]: https://latex.csdn.net/eq?%5Cfrac%7BM%28X%29*X%5E%7Bk%7D%7D%7BG%28X%29%7D%3DQ%28X%29&plus;%5Cfrac%7BR%28X%29%7D%7BG%28X%29%7D
[M_X_X_k_R_X_Q_X_G_X]: https://latex.csdn.net/eq?M%28X%29*X%5E%7Bk%7D&plus;R%28X%29%3DQ%28X%29*G%28X%29
[29787539f48743759ced867711b5b8c3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d42c4fb188054773b5b3ac3d36152738.png
[9d313bca2a194386a2f8e7345c10b3ac.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9b0fee4785e142d986395b74d1938315.png