计算机网络(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. **取反**：将最终的和取反，得到校验和。

通过这个例子，我们可以清楚地看到如何利用补码计算校验和，这种方法在网络协议中广泛应用，确保数据传输的完整性和正确性。

解释

1. 分块：将数据分成16位一块。
2. 求和：将所有块的值相加，如果超过16位，将进位部分加回到和中。
3. 取反：将最终的和取反，得到校验和。

通过这个例子，我们可以清楚地看到如何利用补码计算校验和，这种方法在网络协议中广泛应用，确保数据传输的完整性和正确性。

校验和的工作原理

校验和的目的是检测数据传输中的错误。当发送方发送数据时，它计算数据的校验和，并将这个校验和附加到数据包中。接收方在接收到数据包后，会重新计算数据的校验和，并将这个校验和与接收到的校验和进行比较。如果两个校验和相同，说明数据在传输过程中没有错误；如果不同，则表示数据在传输过程中发生了错误。

取反的作用

取反的目的是使得校验和的计算能够检测到尽可能多的错误类型。具体原因如下：

1. 生成全零结果：取反后，当接收方计算校验和时，将所有数据块、校验和以及取反结果相加，如果数据传输没有错误，总和应该为全1（即0xFFFF）。这个全1结果取反后应该是全0（即0x0000）。如果数据在传输过程中发生了变化，总和将不会是全1，取反后也不会是全0，从而可以检测到错误。

2. 错误检测的增强：通过取反，可以确保即使某些位翻转（例如1变成0或0变成1），校验和也能更有效地检测到这些错误。取反增加了检测到单个位错误和多位错误的可能性，从而增强了校验和的错误检测能力。

二.CRC校验（循环冗余码）