软考知识点3：校验码
## 考点 在软考中，关于校验码的考点通常涉及以下几个方面： - 校验码的概念：需要了解校验码的基本
渲染中...
## 考点
在软考中，关于校验码的考点通常涉及以下几个方面：
- 校验码的概念：需要了解校验码的基本概念，即用于验证数据传输或存储过程中数据的完整性和准确性的一种技术。
- 常见的校验码算法：要求了解和掌握一些常见的校验码算法比较：，- 如： **奇偶校验码、CRC（循环冗余校验码）、海明校验码等**。需要理解这些算法的原理和应用场景。
- 校验码的应用：需要了解校验码在实际应用中的使用情况，如在网络通信、存储介质中的数据校验、数据备份等方面的应用。
- 校验码的计算和验证：计算给定数据的校验码，或者验证给定数据的校验码是否正确。这涉及到对校验算法的理解和运用。
- 校验码的错误检测和纠正能力：评估不同校验码算法的错误检测和纠正能力，以及它们在不同情况下的适用性和局限性。
> 关注公众号“**月上老狗**”，发送“**软件设计师**”，获取历年软件设计师软考真题。
>
> 
<!-- more -->
## 码字、码距、校验码
当我们谈论通信和编码理论时，我们会涉及到以下几个重要概念：码字、码距和校验码。
### 码字（Codeword）：
- 概念： 码字是经过编码处理后的原始数据，它包含了用于错误检测或纠正的附加信息。
- 特点： 每个原始数据或信息都被映射到一个特定的码字上，以便在传输或存储过程中进行处理。
- 举例： 在奇偶校验码中，原始数据位"`1011`"经过奇偶校验编码后，可能会生成码字"`10111`"，其中最后一位是校验位。
### 码距（Hamming Distance）：
- 概念： 码距是两个码字之间不同位置的位的个数，用于衡量它们之间的差异程度。
- 特点： 码距越大，表示两个码字之间的相似性越低，也就意味着校验码具有更好的检测和纠错能力。
- 举例： 对于码字"`1011`"和"`1001`"，它们之间的码距为`1`，因为它们只在第二个位置上这一位数字不同。
### 校验码（Error Detection and Correction Code）：
- 概念： 校验码是一种用于验证数据传输或存储过程中数据的完整性和准确性的技术，通常由码字构成。
- 作用： 校验码通过对码字的检验来验证数据的完整性和准确性，从而检测和纠正传输或存储过程中的错误。
- 举例： 奇偶校验码、`CRC`（循环冗余校验码）和海明校验码是常见的校验码技术，它们通过不同的编码方式来实现错误检测和纠正。
### 关系
- 码字是校验码的基本组成部分，它是经过编码处理后的原始数据。
- 码距是两个码字之间的差异程度的度量，它用于衡量校验码的性能。
- 在设计校验码时，我们会尽量选择具有较大码距的码字，以提高校验码对错误的容忍性。
## 检验码算法
### 理论概念
校验码是一种用于验证数据传输或存储过程中数据的完整性和准确性的一种技术。它通常是一段额外的数据，附加在原始数据后面，用于检测数据在传输或存储过程中是否发生了错误或失真。校验码的计算基于原始数据的内容，通过对数据进行特定的计算或处理得到。在接收端，接收到的数据经过同样的计算或处理，然后与附加的校验码进行比较，从而确定数据是否在传输或存储过程中发生了错误。
校验码的作用包括但不限于以下几个方面：
- 错误检测：校验码能够帮助检测数据在传输或存储过程中是否发生了错误。通过比较接收到的数据和附加的校验码，可以发现数据中的单个位或多个位的错误。
- 错误纠正：一些校验码技术还具有纠正数据中错误的能力。除了能够检测错误之外，它们还能够通过附加的校验码对数据进行纠正，从而恢复原始的数据内容。
- 数据完整性验证：校验码还能够验证数据的完整性，即数据是否在传输或存储过程中被篡改或损坏。如果校验码验证失败，则表示数据可能已被篡改或损坏。
常见的校验码算法有：
- **奇偶校验码**：奇偶校验码是最简单的校验码算法之一，只需要在数据末尾添加一个额外的位来使得数据中的1的个数满足奇偶性要求。奇偶校验码只能检测单个位的错误，不能纠正错误。因此，它主要用于检测传输过程中的错误，而不是纠正错误。奇偶校验码的计算复杂度非常低，因为它只需要统计数据中`1`的个数，并进行一次简单的判断。
- **CRC循环冗余校验码**：`CRC`（循环冗余校验码）是一种强大的校验码算法，能够检测和纠正多位错误，具有较高的纠错能力。`CRC`广泛应用于数据通信和存储系统中，例如以太网、无线通信、磁盘存储等领域。`CRC`的计算复杂度相对较高，因为它需要进行多项式除法运算，特别是对于较长的数据块，计算量会更大。
- **海明校验码**：海明校验码具有较强的纠错能力，可以检测并纠正多个位的错误，具有一定的容错性。海明校验码的计算复杂度相对较高，因为它需要计算校验位的位置和值，特别是对于海明距离较大的海明码，计算量会更大。海明校验码通常用于对传输容易出错的数据进行纠错，如在数字通信、存储系统中的应用。
| | 校验码位数 | 校验码位置 | 检错 | 纠错 | 校验方式 |
| --------------- | ---------------------- | ---------------- | ------------ | -------- | ------------------------------------------------------------ |
| 奇偶校验 | 1 | 一般拼接在头部 | 可检奇数位错 | 不可纠错 | 奇校验:最终1的个数是奇数个;<br />偶校验:最终1的个数是偶数个; |
| CRC循环冗余校验 | 生成多项式最高次幂决定 | 拼接在信息位尾部 | 可检错 | 不可纠错 | 模二除法求余数，拼接作为校验位 |
| 海明校验 | $$2^r ≥ m+r+1$$ | 插入在信息位中间 | 可检错 | 可纠错 | 分组奇偶校验 |
### 奇偶校验码
- 概念： 奇偶校验码是一种简单的校验码，用于验证数据传输过程中的误码情况。它通过添加一个额外的位（通常是`1`个`bit`），使得数据的位数中具有奇数个`1`，或者偶数个`1`，从而实现简单的错误检测。
- 考点：
1. 奇偶校验码的计算方法：通常是在数据中添加一个附加位，使得整个数据中的1的个数是奇数或偶数，具体方法取决于所使用的奇偶校验规则。
2. 奇偶校验码的检验方法：在接收数据时，检查附加的奇偶校验位是否符合规则，从而确定数据是否在传输过程中发生了错误。
- 计算方法：统计数据中1的个数。
- 如果1的个数是奇数，则在数据末尾添加一个`0`，使得总的`1`的个数为偶数。
- 如果1的个数是偶数，则在数据末尾添加一个`1`，使得总的`1`的个数为奇数。
- 举例： 对于数据"`10110010`"，有`4个1`，所以我们需要在末尾添加一个`1`，最终数据变成"`101100101`"。
### CRC循环冗余校验码
- 概念： `CRC`是一种强大的校验码技术，广泛应用于数据通信和存储系统中。它通过对数据进行多项式运算，生成一个校验码，用于检测数据传输或存储过程中的错误。
- 考点：
1. `CRC`的生成方法：`CRC`通常使用多项式除法来生成校验码，计算过程中需要选择合适的生成多项式和初始值。
2. `CRC`的校验方法：在接收数据时，将接收到的数据和生成多项式进行同样的多项式除法运算，得到的余数用于验证数据的完整性。
- 计算方法：
- 选择一个生成多项式和初始值。
- 将数据位和一些附加的`0`（通常是生成多项式的位数减去`1个0`）连接起来，得到一个较长的二进制数。
- 对这个较长的二进制数进行多项式除法运算。
- 最终的余数就是CRC校验码。
- 举例： 对于数据"`11011011`"，我们选择生成多项式 $$x^3 + x^2 + 1$$，并且初始值为`0`。将数据与`3个0`连接起来得到"`11011011000`"，然后进行多项式除法运算，最终的余数就是CRC校验码。
### 海明校验码
校验位公式：$$2^r ≥ m+r+1$$，其中 `m` 代入信息位的个数，求得 `r` 的最小值，也就是校验位的最小值。
- 概念： 海明校验码是一种具有纠错功能的校验码技术，能够检测并纠正传输过程中的错误。它通过在数据中添加一定数量的校验位，使得接收端能够检测并纠正单位错误，提高数据传输的可靠性。
- 考点：
1. 海明校验码的生成方法：海明码通常采用海明距离的概念来设计校验位的位置，以实现最大的错误检测和纠正能力。
2. 海明校验码的校验方法：接收端使用相同的海明码规则来计算数据的校验位，并与接收到的校验位进行比较，以检测和纠正传输过程中的错误。
- 计算方法：
- 计算海明距离所需的校验位的数量。
- 确定校验位的位置。
- 根据数据位和校验位的位置关系计算校验位的值。
- 举例： 对于数据"`11011011`"，如果我们选择使用海明距离为`3`的海明码，那么我们需要添加3个校验位。然后，根据校验位的位置关系，计算校验位的值，使得数据和校验位之间的海明距离满足要求。
### 总结
- 奇偶校验码简单但纠错能力有限
- `CRC`具有较强的纠错能力但计算复杂度较高
- 海明校验码具有较强的纠错能力且能够纠正多个位的错误，但计算复杂度也较高。
选择适合的校验码算法取决于具体的应用需求和计算资源的限制。END
评论
登录后查看和发表评论
前往登录