计算机网络中的汉明码
在计算机网络中，汉明码是指数据从发送方传输到接收方时可能出现的一组纠错码。汉明码通过查找错误发生时的状态来纠正错误。
冗余位
冗余位是额外的二进制位，它们被生成并添加到数据传输的信息承载位中，以确保在数据传输过程中不会丢失任何位。冗余位被放置在特定的计算位置以消除错误，两个冗余位之间的距离称为"汉明距离"。
纠错码 − 这是数据位和冗余位之间的关系，用于纠正单位错误。 A帧由M个数据位和R个冗余位组成，设该帧的总长度为N(N=M+R)。包含数据和校验位的 N 位单元通常称为 N 位码字。
以下公式用于计算冗余位数。
单位错误数 = M + R
无错误状态数 = 1
因此，代表所有状态 (M+R+1) 的冗余位数 (R) 必须满足 −
2𝑅 ≥ 𝑀 + 𝑅 + 1
其中 R = 冗余位，M = 数据位。
计算汉明码的步骤 −
汉明方法使用额外的奇偶校验位来识别单位错误。
- 步骤 1 − 首先以二进制形式写入从 1 开始的位位置(1、10、11、100 等)。
- 步骤 2 − 将所有 2 的幂的位位置标记为奇偶校验位(1、2、4、8、16、32、64 等)。
- 步骤 3 − 所有其他位位置用于要编码的数据(3、5、6、7、9、10 和 11 等)。
每个奇偶校验位都会计算代码字中某些位的奇偶校验。奇偶校验的位置决定了它交替检查和跳过的位序列。
- 位置 1 - 检查 1 位，然后跳过 1 位，检查 1 位，然后跳过 1 位，依此类推(例如 - 1、3、5、7、11 等)
- 位置 2 - 检查 2 位，然后跳过 2 位，检查 2 位，然后跳过 2 位(例如 - 2、3、6、7、10、11、14、15 等)
- 位置 4 - 检查 4 位，然后跳过 4 位，检查 4 位，然后跳过 4 位(例如 - 4、5、6、7、12、13、14、15 等)
- 位置 8 - 检查校验 8 位，然后跳过 8 位，校验 8 位，然后跳过 8 位(例如 - 8、9、10、11、12、13、14、15、24、25、26、27、28、29、30、31)。
注意 - 如果校验位置上 1 的总数为奇数，则将奇偶校验位设置为 1;如果校验位置上 1 的总数为偶数，则将奇偶校验位设置为 0。
示例 -
为数据字节 1001101 构造偶校验汉明码字。
1001101 的位数为 7。
r 的值计算如下:−
2𝑅 ≥ 𝑀 + 𝑅 + 1
⇒ 24 ≥ 7 + 4 + 1
因此，冗余位数 = 4
现在，我们来计算所需的奇偶校验位数。
我们取 𝑃 = 2， 那么 2𝑃 = 22 = 4 且 𝑛 + 𝑃 + 1 = 4 + 2 + 1 = 7
2 个奇偶校验位对于 4 位数据来说是不够的。
现在，我们取 𝑃 = 3，那么 2𝑃 = 23 = 8 且 𝑛 + 𝑃 + 1 = 4 + 3 + 1 = 8
因此，3 个奇偶校验位对于 4 位数据来说已经足够了。
码字中的总位数为 − 4 + 3 = 7
位置 1:检查位 1、3、5、7、9 和11.
? _1_0 0 1_1 0 1 0. 在位置 1 处为偶校验，因此将位置 1 设置为 0:0_1_0 0 1_1 0 1 0.
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
位置 2:检查位 2、3、6、7、10、11.
0 ? 1_0 0 1_1 0 1 0。位置 2 为奇校验，因此将位置 2 设置为 1:0 1 1_0 0 1_1 0 1 0
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
位置 4 检查位 4、5、6、7、12。
0 1 1 ? 0 0 1_1 0 1 0。位置 4 为奇校验，因此将位置 4 设置为 1:0 1 1 1 0 0 1_1 0 1 0
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
位置 8 检查位 8、9、10、11、12。
0 1 1 1 0 0 1 ? 1 0 1 0。由于位置 8 为偶校验，因此将位置 8 设置为 1:0 1 1 1 0 0 1 0 1 0 1 0
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
代码字 = 011100101010
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
