计算机网络(7) 错误检测
一.校验和
使用补码计算校验和是一种常见的错误检测方法，应用于网络协议如IP和TCP。补码是二进制数的一种表示方法，可以有效地处理符号位和进位。下面是如何利用补码计算校验和的详细步骤和算数例子。
### 计算步骤
1. **将数据分块**：将数据分成16位（2字节）一块。
2. **求和**：将所有16位块的值求和，如果求和结果超过16位，则将高位的进位加回到结果中。
3. **取反**：将最终的和取反，得到校验和。
### 算数例子
假设我们有一个简单的数据序列，用于计算IP或TCP校验和。这里以16进制表示的数据序列为例：
```
4500 003C 1C46 4000 4006 B1E6 C0A8 0001 C0A8 00C7
```
#### 第一步：分块
将数据分成16位（2字节）一块：
```
4500
003C
1C46
4000
4006
B1E6
C0A8
0001
C0A8
00C7
```
#### 第二步：求和
将每个16位块转换为十进制并求和，注意每一步保持结果在16位以内（即如果有进位，则将进位加回到和中）：
```
4500 -> 0x4500 = 17664
003C -> 0x003C = 60
1C46 -> 0x1C46 = 7238
4000 -> 0x4000 = 16384
4006 -> 0x4006 = 16390
B1E6 -> 0xB1E6 = 45542
C0A8 -> 0xC0A8 = 49320
0001 -> 0x0001 = 1
C0A8 -> 0xC0A8 = 49320
00C7 -> 0x00C7 = 199
```
将这些值相加：
```
17664 + 60 + 7238 + 16384 + 16390 + 45542 + 49320 + 1 + 49320 + 199 = 201118
```
由于这个和超过16位，我们需要将进位加回：
```
201118 = 0x313AE （以16进制表示）
将0x313AE分解为16位和进位部分：
0x313AE = 0x13AE + 0x30000 = 5038 + 3 = 5041 (0x13AE + 3 = 0x13B1)
```
所以最终的和为：
```
5041 = 0x13B1
```
#### 第三步：取反
将最终的和取反，得到校验和：
```
0x13B1 -> 取反 -> 0xEC4E
```
所以，校验和为：
```
0xEC4E
```
### 代码示例
下面是上述计算过程的Python实现：
```python
def calculate_checksum(data):
checksum = 0
# 将数据分块，每块16位（2字节）
for i in range(0, len(data), 2):
word = (data[i] << 8) + (data[i + 1] if (i + 1) < len(data) else 0)
checksum += word
# 如果有进位，则加回到结果中
if checksum > 0xFFFF:
checksum = (checksum & 0xFFFF) + 1
# 取反
checksum = ~checksum & 0xFFFF
return checksum
# 示例数据，以字节数组形式表示
data = [
0x45, 0x00, 0x00, 0x3C, 0x1C, 0x46, 0x40, 0x00,
0x40, 0x06, 0xB1, 0xE6, 0xC0, 0xA8, 0x00, 0x01,
0xC0, 0xA8, 0x00, 0xC7
]
# 计算校验和
checksum = calculate_checksum(data)
print("校验和: 0x{:04X}".format(checksum))
```
### 解释
1. **分块**：将数据分成16位一块。
2. **求和**：将所有块的值相加，如果超过16位，将进位部分加回到和中。
3. **取反**：将最终的和取反，得到校验和。
通过这个例子，我们可以清楚地看到如何利用补码计算校验和，这种方法在网络协议中广泛应用，确保数据传输的完整性和正确性。
解释
- 分块：将数据分成16位一块。
- 求和：将所有块的值相加，如果超过16位，将进位部分加回到和中。
- 取反：将最终的和取反，得到校验和。
通过这个例子，我们可以清楚地看到如何利用补码计算校验和，这种方法在网络协议中广泛应用，确保数据传输的完整性和正确性。
校验和的工作原理
校验和的目的是检测数据传输中的错误。当发送方发送数据时，它计算数据的校验和，并将这个校验和附加到数据包中。接收方在接收到数据包后，会重新计算数据的校验和，并将这个校验和与接收到的校验和进行比较。如果两个校验和相同，说明数据在传输过程中没有错误；如果不同，则表示数据在传输过程中发生了错误。
取反的作用
取反的目的是使得校验和的计算能够检测到尽可能多的错误类型。具体原因如下：
-
生成全零结果：取反后，当接收方计算校验和时，将所有数据块、校验和以及取反结果相加，如果数据传输没有错误，总和应该为全1（即0xFFFF）。这个全1结果取反后应该是全0（即0x0000）。如果数据在传输过程中发生了变化，总和将不会是全1，取反后也不会是全0，从而可以检测到错误。
-
错误检测的增强：通过取反，可以确保即使某些位翻转（例如1变成0或0变成1），校验和也能更有效地检测到这些错误。取反增加了检测到单个位错误和多位错误的可能性，从而增强了校验和的错误检测能力。
二.CRC校验（循环冗余码）
