当前位置：首页 > news >正文

【软件考试】错误校验码-奇偶校验码,CRC,海明码...

news 2025/6/29 8:11:04

文章目录

- 什么是错误校验码？
- - 常见的错误检测方法包括：
- 奇偶校验码
- - 奇校验（Odd Parity）：
  - 偶校验（Even Parity）：
  - 实现步骤：
  - 优点：
  - 缺点：
- CRC冗余码
- - CRC的基本原理
  - CRC的特点
  - CRC码的计算步骤
  - CRC校验
  - 应用示例
- 海明码
- - 海明码的工作原理
  - 海明码的例子

什么是错误校验码？

错误检测方法是用来识别数据在传输、存储或处理过程中是否发生错误的一种机制。这些方法通过在数据中添加冗余信息来实现，使得接收方能够检测到数据是否被篡改或损坏。

常见的错误检测方法包括：

奇偶校验（Parity Check）
- 奇校验：确保数据位中1的个数为奇数。
- 偶校验：确保数据位中1的个数为偶数。
- 计算公式：无固定公式，通常是简单的计数。
校验和（Checksum）
- 计算公式：将数据分成多个小块，对每块进行求和，最后将这些和相加或进行特定的位运算，得到一个校验值。
- 例子：对数据0xA8, 0x50进行校验和计算，累加得到0xF8，取反得到校验和0x07。接收方接收到数据后，对数据和校验和进行累加，如果结果为0，则数据无误。
循环冗余校验（Cyclic Redundancy Check, CRC）
- 计算公式：使用除法和余数的原理来检测数据在传输或存储过程中是否发生了变化。
- 例子：生成多项式G(X)=X^4+X^3+1，二进制序列10110011后面再加4个0，得到101100110000。通过模2除法（异或操作）计算得到CRC校验码101100110100。
海明码（Hamming Code）
- 计算公式：通过增加冗余校验位，使得任何单比特错误导致的不同码字之间的汉明距离至少为3。
- 例子：对数据位1011进行海明码编码，确定需要3个校验位。将校验位放在2的幂次位置，数据位放在其他位置，计算得到海明码0110011。
数字签名
- 计算公式：涉及密钥生成、签名生成和验证三个算法，通常基于哈希函数和非对称加密。
- 例子：使用RSA算法，私钥签名，公钥验证。具体实现涉及复杂的数学运算，通常由库函数提供支持。
序列化/反序列化
- 计算公式：无固定公式，通常涉及将对象状态转换为可存储或传输的格式。
- 例子：在Java中，实现Serializable接口的类可以通过对象流进行序列化和反序列化。这通常用于网络传输或持久化存储。
校验矩阵
- 计算公式：通过特定的矩阵运算来检测错误。
- 例子：使用生成矩阵和校验矩阵，可以通过初等行变换来快速给出另一个矩阵。
LRC校验（纵向冗余校验）
- 计算公式：对需要校验的数据两两组成一个16进制的数值求和，将求和结果与256求模，用256减去所得模值得到校验结果。
- 例子：16进制数据01 A0 7C FF 02求和为21E，取模1E，计算得到校验结果E2。

这些方法可以单独使用，也可以组合使用，以提供不同级别的错误检测能力。选择哪种方法取决于具体的应用需求、数据传输的环境以及对错误检测和纠正的要求。

奇偶校验码

奇偶校验码是一种简单的错误检测技术，用于检测数据传输或存储过程中的单比特错误。它通过在数据中添加一个额外的位（校验位）来实现，这个校验位使得数据位中1的总数为奇数（奇校验）或偶数（偶校验）。

奇校验（Odd Parity）：

目的：确保数据位（包括校验位）中1的总数为奇数。
计算方法：首先计算数据中1的个数，然后根据这个数量是奇数还是偶数，添加一个1或0作为校验位，使得1的总数为奇数。
例子：假设数据位为1011（4位数据），其中有3个1（奇数个）。为了保持奇数个1，校验位应为0，所以奇校验码为01011。

偶校验（Even Parity）：

目的：确保数据位（包括校验位）中1的总数为偶数。
计算方法：首先计算数据中1的个数，然后根据这个数量是奇数还是偶数，添加一个1或0作为校验位，使得1的总数为偶数。
例子：假设数据位为1011（4位数据），其中有3个1（奇数个）。为了使1的总数为偶数，校验位应为1，所以偶校验码为11011。

实现步骤：

确定校验类型：决定使用奇校验还是偶校验。
计算数据位中1的个数：对原始数据的每一位进行计数，记录1的个数。
添加校验位：
- 对于奇校验，如果1的个数是奇数，则校验位为0；如果是偶数，则校验位为1。
- 对于偶校验，如果1的个数是奇数，则校验位为1；如果是偶数，则校验位为0。
传输或存储：将包含校验位的数据进行传输或存储。
校验：在接收方，对接收的数据（包括校验位）进行同样的计数和校验，如果不符合奇偶性，则认为数据有误。

优点：

实现简单，计算成本低。
可以检测出数据中的单比特错误。

缺点：

只能检测出奇数个错误，对于偶数个错误（如同时翻转两位）无法检测。
不能定位错误的具体位置。
不能纠正错误。

奇偶校验是一种基本的错误检测方法，通常用于检测单个位错误，但在错误纠正和更复杂的错误检测场景中，可能需要更高级的编码技术，如CRC或海明码。

CRC冗余码

循环冗余校验（Cyclic Redundancy Check，CRC）是一种常用的错误检测技术，广泛应用于各种数据通信和存储系统中。CRC通过将数据视为一个多项式，并使用一个预定的生成多项式进行除法运算，得到的余数作为校验码附加到数据后面。以下是CRC冗余码的详细说明：

CRC的基本原理

数据表示为多项式：将数据序列表示为一个多项 $\ M(x)$ ，其中最高次幂不超过 $x^{n-1}$ 。
生成多项式：选择一个生成多项式 $\ G(x)$ ，它是一个$\k+1$位的二进制数，最高次幂为 $x^k$ 。
乘以 $x^k$ ：将 $\ M(x)$ 乘以 $x^k$ ，然后除以 $\ G(x)$ ，得到的余数就是校验位。
模2运算：在除法过程中，使用模2运算，即按位异或操作，不产生借位。
$\text{Received Data} \mod G(x) = 0$

CRC的特点

可以检测出所有奇数位错误；
可以检测出所有双比特错误；
可以检测出所有小于或等于校验位长度的突发错误。

CRC码的计算步骤

确定生成多项式：根据应用选择一个合适的生成多项式 $\ G(x)$ 。
数据附加零位：在原始数据后面附加 $\ k$ 个零位，其中 $\ k$ 是生成多项式的次数。
进行模二除法：使用模2除法将附加了零位的数据多项式除以生成多项式，得到的余数即为CRC校验码。
附加校验码：将计算得到的校验码附加到原始数据后面，形成最终的传输数据。

CRC校验

在接收端，使用相同的生成多项式对接收的数据（包括CRC校验码）进行模二除法运算。如果余数为零，则数据被认为是正确的；如果余数非零，则表明数据在传输过程中发生了错误。

应用示例

假设要传输的数据为101011，生成多项式为G(x) = x^4 + x + 1（二进制表示为10011）。

附加零位：在数据后附加4个零位，得到1010110000。
模二除法：使用模2除法（异或操作）计算得到余数，即CRC校验码。
附加校验码：将校验码附加到原始数据后面，得到最终的传输数据。

通过这种方式，CRC提供了一种有效的错误检测机制，确保数据的完整性和准确性。在实际应用中，CRC的选择和实现可能会根据具体的通信协议和需求有所不同。

海明码

海明码（Hamming Code）是一种用于错误检测和纠正的编码技术，由理查德·海明（Richard Hamming）在1950年提出。它通过在数据中添加冗余位（parity bits），使得在传输过程中出现的错误可以被检测和纠正。海明码的一个关键特点是能够检测和纠正单个位错误，并且能够检测多个位错误。

海明码的工作原理

确定校验位数：根据数据位数和校验位数的关系，确定所需的校验位数。公式为 $\ 2^r - 1 \geq m + r$ ，其中 (m) 是数据位数， $\ r$ 是校验位数。这个公式确保了校验位足够覆盖整个需要校验的码组。
确定校验位的位置：校验位放置在2的幂次方位置上，即第1位、第2位、第4位、第8位等。数据位填充在其他位置。
计算校验位：每个校验位负责一组特定的数据位。例如，第一个校验位负责所有二进制表示中第1位为1的数据位，第二个校验位负责所有二进制表示中第2位为1的数据位，以此类推。校验位的值通过奇偶校验来确定，确保相关位的总和为偶数（偶校验）。
生成编码：将计算得到的校验位填入相应位置，生成编码后的海明码。
错误检测和纠正：在接收端，通过重新计算校验位并比较，可以检测到错误。如果检测到错误，可以通过校验位的位置确定错误位，并进行纠正。

海明码的例子

假设我们需要传输4位二进制数据 1011，请使用海明码对其进行编码。

确定校验位的数量：根据公式 $\ 2^r - 1 \geq m + r$ ，当 $\ m=4$ 时，最小的 $\ r$ 为3，因此需要3个校验位。
确定校验位的位置：校验位放置在第1位、第2位、第4位，数据位填充在其他位置。
计算校验位的值：
- p₁（位置1）负责检测位置1、3、5、7，计算得到 $\ p₁ = 0$ 。
- p₂（位置2）负责检测位置2、3、6、7，计算得到 $\ p₂ = 1$ 。
- p₃（位置4）负责检测位置4、5、6、7，计算得到 $\ p₃ = 0$ 。
生成编码后的海明码：将计算得到的校验位填入相应位置，得到的海明码为 0110011。