本文是对RFC1071标准的翻译，同时根据标准，用C语言实现了协议内容。
原文翻译
https://dl.acm.org/doi/pdf/10.17487/RFC1071
摘要
该标准总结了高效计算网际校验和的技术和算法。它不是一个标准，而是一组有用的实现技术。该标准的分发没有限制。
1. 介绍
该标准讨论了高效计算网际校验和的方法，这种校验和被用于标准的互联网协议，如 IP、UDP 和 TCP。
高效的校验和实现对良好的性能至关重要。随着实现技术的不断进步，协议处理的其他部分已得到优化，而校验和的计算往往成为 TCP 性能的瓶颈。例如，处理 TCP 数据字节时，每微秒的节省可能会在总体计算中带来显著的 CPU 时间节省。
总体来说，网际校验和算法非常简单：
(1) 相邻的8位(1字节)将被配对，形成16位数据，接着对这些16位数据求反码(1’s complement)。
(2) 为了生成校验和，首先清空校验和字段本身，然后计算涉及的16位数据的反码和，最后将计算得到的字段放入校验和字段中。
(3) 为了检查校验和，计算同一组的16位数据的反码和，包括校验和字段。如果结果是全1位（在反码中即表示-0），则校验通过。
假设需要计算的校验和是针对以下字节序列：
A, B, C, D, …, Y, Z。使用[a, b]表示16位整数a*256 + b，其中a和b是字节。那么这些字节的16位1的补码和可以表示为以下两种形式之一：
其中，+表示1的补码加法。这两种情况分别对应字节数为偶数和奇数的情况。
在二进制补码机器上，1的补码和必须通过“进位回绕”（end-around carry）来计算，也就是说，任何从最重要位（最高位）溢出的部分，都需要加到最低位。具体的例子将在后面给出。
第2节讨论了这个校验和的特性，这些特性可以用于加速其计算。第3节包含了一些最重要的实现技术的数字示例。最后，第4节展示了适用于各种常见CPU类型的特定算法示例。我们感谢Van Jacobson和Charley Kline对这一部分算法的贡献。
网际校验和的特性最初由Bill Plummer在《IEN-45: 校验和功能设计》中讨论。由于《IEN-45》未被广泛传播，我们将其作为附录扩展包含在本RFC中。
2. 计算校验和
这个简单的校验和具有许多出色的数学特性，能够加速其计算，接下来我们将讨论这些特性。
(A) 交换律与结合律
只要遵循字节的奇偶分配规则，求和的顺序可以任意改变，且可以随意将其拆分成若干组。例如，和式 [1] 可以拆分为：
这样，和式仍然保持不变。这意味着，我们可以灵活地调整字节的求和顺序，拆分成多个部分来加速计算。
(B) 字节顺序独立性
16位整数的和可以不依赖于字节顺序来计算。因此，如果我们计算交换字节顺序的和：
其结果与 [1] 相同，唯一的区别是字节的顺序被交换了！为什么是这样呢？因为无论如何交换字节，进位的过程是一样的：从第15位到第0位，以及从第7位到第8位。换句话说，一致地交换字节只是将和式中的位旋转，而不会影响它们的内部顺序。
因此，无论底层硬件的字节顺序（”大端”或”小端”）如何，求和的方式完全一样。例如，假设我们在一个”小端”机器上计算，数据按网络字节顺序（”大端”）存储。读取每个16位字时，字节会交换，结果是和式 [4]；但是，将结果存回内存时，和式的字节顺序会重新交换回网络字节顺序。
字节交换也可以显式地用于处理边界对齐问题。例如，[3] 中的第二组可以不考虑字节的奇偶顺序，直接按以下方式计算：
1 | [K,L] + ... + [Z,0] |
如果在将这个和式加到第一组之前对它进行字节交换，就可以避免字节的对齐问题。具体的例子将在下面给出。
(C) 并行求和
在那些字长是16位倍数的机器上，可以开发出更高效的实现。由于加法满足结合律，我们不必按照消息中整数出现的顺序进行求和。相反，我们可以通过利用更大的字长并行地进行求和。
为了并行计算校验和，只需使用机器的原生字长进行1的补码加法。例如，在32位机器上，我们可以一次加4个字节：[A,B,C,D] + ...。当和式计算完成后，我们可以通过将长和式的16位段相加，将其“折叠”回16位。每次16位加法可能会产生新的进位，这些进位需要被加上。
此外，字节顺序依然不重要；我们可以用以下不同的方式对32位字进行求和：
然后，根据需要对最终的16位和式进行字节交换。任何能够收集字节进行求和的排列方式都是允许的。请参阅下面的示例。允许任何排列，将所有偶数数据字节收集到一个总和字节中，将奇数数据字节收集到另一个总和字节中。还有进一步的编码技术可用于加速校验和计算。
3.进一步优化校验和计算
在校验和的计算过程中，还可以通过一些进一步的编码技术来加速计算过程。
(1) 延迟进位（Deferred Carries）
根据不同机器的架构，延迟处理进位直到主要求和循环结束可能会更加高效。
一种方法是将16位字求和并存储在一个32位累加器中，这样溢出就会积累到高16位。此方法通常避免了需要进位感知指令，但它需要进行比直接加32位段更多的加法。是否采用这种方法取决于硬件架构的具体细节，因为有些情况下加32位段可能会更快。
(2) 展开循环（Unwinding Loops）
为了减少循环的开销，通常可以将内层求和循环展开，在一次循环遍历中复制一系列加法指令。这种技术通常会带来显著的性能提升，尽管它可能会使程序的逻辑变得更加复杂。
(3) 与数据复制结合（Combine with Data Copying）
像校验和计算一样，从一个内存位置复制数据到另一个位置也涉及逐字节的开销。在两者的情况下，瓶颈基本上是内存总线，即数据提取的速度。在一些机器上（特别是相对较慢和简单的微型计算机），通过将内存到内存的复制与校验和计算结合，可以显著减少开销，避免多次访问内存。例如，数据只需访问一次，就能同时进行复制和校验和计算。
(4) 增量更新（Incremental Update）
最后，在某些情况下，当更新头部字段时，可以避免重新计算整个校验和。最著名的例子是网关更改IP头中的TTL字段，但也有其他类似的情况（例如，当更新源路由时）。在这些情况下，可以通过增量更新校验和，而无需重新扫描整个消息或数据报。
为了更新校验和，只需将已更改的16位整数的差值加上。为什么这种方法有效呢？因为每个16位整数都有加法逆元，并且加法是结合律的。由此可得，给定原始值m、新值m’和旧校验和C，新的校验和C’可以通过以下公式计算：
这种方法避免了重新计算整个校验和的过程，只需要处理那些已经改变的字段，从而提高了效率。
4. 数值计算示例
以下是如何在一个采用补码表示的计算机上显式地计算1的补码校验和的示例。
示例展示了以字节、16位字（常规和交换顺序）、以及32位字（3种顺序）逐步计算的结果。所有的数值均以十六进制表示。
字节逐步计算、正常顺序和交换顺序
| 步骤 | 字节逐步计算 | 正常顺序 (“Normal Order”) | 交换顺序 (“Swapped Order”) |
|---|---|---|---|
| 字节 0/1 | 00 01 | 0001 | 0100 |
| 字节 2/3 | f2 03 | f203 | 03f2 |
| 字节 4/5 | f4 f5 | f4f5 | f5f4 |
| 字节 6/7 | f6 f7 | f6f7 | f7f6 |
| 初次求和 (Sum1) | 2dc 1f0 | 2ddf0 | 1f2dc |
| 进位值 (Carrys) | 1 2 | 2 | 1 |
| 第二次求和 (Sum2) | dd f2 | ddf2 | f2dd |
| 最终交换 | dd f2 | ddf2 | ddf2 |
32位字逐步计算（3种不同的顺序）
| 步骤 | 正常顺序 (Normal Order) | 交换顺序1 (Swapped Order 1) | 交换顺序2 (Swapped Order 2) |
|---|---|---|---|
| 字节 0/1/2/3 | 0001f203 | 010003f2 | 03f20100 |
| 字节 4/5/6/7 | f4f5f6f7 | f5f4f7f6 | f7f6f5f4 |
| 初次求和 (Sum1) | 0f4f7e8fa | 0f6f4fbe8 | 0fbe8f6f4 |
| 进位值 (Carrys) | 0 | 0 | 0 |
| 高半部分 (Top half) | f4f7 | f6f4 | fbe8 |
| 低半部分 (Bottom half) | e8fa | fbe8 | f6f4 |
| 第二次求和 (Sum2) | 1ddf1 | 1f2dc | 1f2dc |
| 进位值 (Carrys) | 1 | 1 | 1 |
| 第三次求和 (Sum3) | ddf2 | f2dd | f2dd |
| 最终交换 | ddf2 | ddf2 | ddf2 |
分组计算示例
以下是将数据分为两组的情况，其中第二组从奇数边界开始：
| 步骤 | 字节逐步计算 | 正常顺序 |
|---|---|---|
| 字节 0/1 | 00 01 | 0001 |
| 字节 2/(填充为0) | f2 (00) | f200 |
| 第一次求和 (Sum1) | f2 01 | f201 |
| 字节 4/5 | 03 f4 | 03f4 |
| 字节 6/7 | f5 f6 | f5f6 |
| 字节 8/(填充为0) | f7 (00) | f700 |
| 第二次求和 (Sum2) | —- | 1f0ea |
| 第二次求和 (Sum2) | —- | f0ea |
| 进位值 (Carry) | —- | 1 |
| 第三次求和 (Sum3) | —- | f0eb |
| 第一次求和 (Sum1) | —- | f201 |
| 第三次求和字节交换 | —- | ebf0 |
| 最后求和 (Sum4) | —- | 1ddf1 |
| 最后求和 (Sum4) | —- | ddf1 |
| 进位值 (Carry) | —- | 1 |
| 最终校验和 (Sum5) | —- | ddf2 |
通过这些数值示例，可以清楚地看到校验和计算在不同分组和顺序上的一致性。尽管计算路径和顺序不同，最终结果都归一为校验和 ddf2，验证了算法的正确性和可移植性。
4. 实现示例
在本节中，我们展示了在各种CPU上被证明高效的互联网校验和实现算法示例。每个示例均仅展示算法核心部分，不包含环境代码（如子程序链接）或特殊情况代码。
4.1 使用 “C” 实现的互联网校验和算法
以下的 C 代码实现展示了一种算法，其内循环在 32 位累加器中每次累加 16 位数据：
1 | unsigned short checksum(void *addr, int count) { |
翻译及解释
- 初始化累加器： 使用
long类型（32 位）的sum变量作为累加器，用于存储累加的 16 位数据和可能的溢出。 - 主循环：
- 每次从地址
addr中读取一个 16 位数据（两个字节），并累加到sum。 - 地址指针
addr每次移动两个字节。 - 同时，剩余字节数
count减少 2。
- 每次从地址
- 处理剩余字节：
- 如果字节数是奇数，会剩余一个字节未处理。
- 使用类型转换为
unsigned char，读取并累加到sum。
- 折叠进位：
- 当
sum超过 16 位时，将高 16 位与低 16 位相加。 - 重复此过程直到没有进位。
- 当
- 取反操作：
- 最终对累加结果取反（按位取反），生成最终的校验和。
示例说明
这个算法适用于在 2’s 补码表示法的机器上实现 1’s 补码的加法运算，简洁而高效，同时考虑了数据对齐和进位的处理。
4.2 Motorola 68020
以下算法用汇编语言为 Motorola 68020 芯片实现。该算法每次对 32 位数据进行累加，并将循环展开成 16 次重复。为了清晰起见，我们省略了当长度不是 4 的倍数时处理最后一个字的逻辑。结果存储在寄存器 d0 中。
在 20MHz 时钟频率下，这段代码对随机数据的处理速度测得为 134 微秒/千字节。该算法由 Van Jacobson 开发。
1 | movl d1,d2 | 将计数值复制到寄存器 d2 |
翻译及解释
- 初始化阶段：
movl d1,d2：将计数值复制到寄存器d2。lsrl #6,d1：计算主循环的次数（每次循环处理 64 字节）。andl #0x3c,d2：获取不足一个块（64 字节）的数据部分。negl d2：求补，用于偏移计算。andb #0xf,cc：清除 X 标志位，确保后续加法的正确性。
- 主循环：
- 每次循环从内存中读取两个 32 位字，并将它们逐一累加到寄存器
d0中。 - 使用
addxl指令执行加法，同时处理进位。
- 每次循环从内存中读取两个 32 位字，并将它们逐一累加到寄存器
- 循环收尾：
- 使用
dbra指令递减计数器d1，判断是否继续循环。
- 使用
- 折叠进位：
movl d0,d1：将累加结果复制到d1。swap d1：交换d1的高 16 位和低 16 位，方便高低位累加。addxw d1,d0：将d1的高低位累加到d0中，同时处理进位。- 使用
jcc指令判断是否需要进一步修正。
- 结果修正：
- 如果有未处理的进位，用
addw #1,d0修正。 - 使用
andl #0xffff,d0确保结果为 16 位校验和。
- 如果有未处理的进位，用
性能特点
- 循环展开：通过每次处理 32 位数据和展开循环减少指令次数，从而提高效率。
- 进位优化：利用 Motorola 68020 的硬件特性，通过
addxl和addxw指令高效处理扩展进位。 - 汇编优化：算法充分利用寄存器和指令特性，最小化内存访问次数。
该实现在性能和硬件利用率上做出了良好权衡，适用于高效计算大数据块的校验和。
4.3 Cray
以下是为 Cray CPU 编写的汇编语言示例，由 Charley Kline 提供。该算法将校验和计算实现为向量操作，每次处理最多 512 字节，基本的求和单位为 32 位。为了简洁，示例省略了关于短块的许多细节。
注册 A1 存储待计算校验和的 512 字节内存块的地址。首先，将数据的两个副本加载到两个向量寄存器中。一个寄存器将数据右移 32 位，另一个寄存器与 32 位掩码进行向量按位与操作。然后，将这两个向量加在一起。由于所有这些操作是链式执行的，因此每个时钟周期就能得到一个结果。接着，通过一个循环将结果向量中的每个元素加到一个标量寄存器中。最后，进行环绕进位（end-around carry）并将结果折叠为 16 位。
1 | EBM |
翻译及解释
- 初始化阶段：
- A0 和 A1：
A1存储内存块地址，A0用来复制这个地址。 - VL 64：指定使用完整的 64 元素向量。
- S1 <32：从右侧 32 位形成掩码，存入
S1寄存器。 - A2 32：指定处理的数据单位为 32 位。
- V1：加载内存块的数据到向量寄存器
V1。 - V2 和 V3：通过向量按位与和右移操作，将数据分为两部分，并存入
V2和V3。 - V1 + V2：将这两部分相加，结果存入
V1。
- A0 和 A1：
- 计算过程：
- S1 初始化为零。
- S4 <16：从右侧形成 16 位掩码，用于后续的处理。
- A4 16：准备 16 位校验和的折叠操作。
- 折叠过程：
- 通过
CK$LOOP循环，每次将向量寄存器中的值加到标量寄存器S1中。 - 每次迭代更新
A2，并将累加结果加到S1。 - 最终通过环绕进位和移位操作，将结果折叠为 16 位。
- 通过
- 结果取反：
- 最后一步对计算结果
S1进行按位取反，得到最终的校验和。
- 最后一步对计算结果
性能特点
- 向量化操作：该算法利用 Cray 的向量处理能力，每次处理多个数据元素，大大提高了计算效率。
- 流水线操作：通过链式操作，每个时钟周期就能完成一次计算。
- 高效的折叠操作：通过有效的循环和移位操作，确保校验和的计算可以高效完成。
- 环绕进位：采用环绕进位方法确保结果的正确性，符合 16 位校验和要求。
这种实现方式非常适合于 Cray 这样的向量处理器，能够充分发挥硬件特性，进行大数据块的高效处理。
4.4 IBM 370
以下是为 IBM 370 CPU 编写的汇编语言示例。该算法每次处理 4 字节数据。为了简洁起见，示例省略了在数据长度不是 4 的倍数时如何添加最后一个完整字（fullword）的逻辑，以及在必要时如何反转字节。计算结果存储在寄存器 RCARRY 中。
该算法在 IBM 3090 CPU 上的性能为每千字节 27 微秒，处理全 1 位数据时。如果处理时确保数据对齐，时间可以减少到每千字节 24.3 微秒（这需要在开始和结束时处理特定的情况，并且在需要时进行字节交换以补偿从奇数字节开始的情况）。
说明：
- 寄存器
RADDR和RCOUNT分别包含待计算校验和的数据块的地址和长度。 (RCARRY, RSUM)必须是偶数/奇数寄存器对。(RCOUNT, RMOD)必须是偶数/奇数寄存器对。
1 | CHECKSUM SR RSUM,RSUM ; 清空工作寄存器 RSUM |
翻译及解释
- 初始化阶段：
SR RSUM,RSUM和SR RCARRY,RCARRY：将寄存器RSUM和RCARRY清零。LA RONE,1：将常数 1 加载到寄存器RONE，用于后续的加法和循环。SRDA RCOUNT,6：将数据块长度RCOUNT除以 64，结果存储在RCOUNT中。AR RCOUNT,RONE：将RCOUNT加 1，表示循环次数为RCOUNT + 1。S RADDR,=F(64)：将RADDR偏移 64 字节，为进入循环做准备。SRL RMOD,1：将RMOD除以 4，并乘以 2，得到半字索引，用于后续操作。
- 内循环：
AL RSUM,0(,RADDR)：从内存中读取 4 字节数据并加到RSUM中。BC 12,*+6：检查是否有进位，如果没有进位则跳过。AR RCARRY,RONE：如果有进位，则将进位加到RCARRY中。- 重复这两个步骤，处理接下来的 4 字节数据，直到处理完所有数据。
- 地址更新与循环控制：
A RADDR,=F'64'：更新地址指针RADDR，指向下一个 64 字节的块。BCT RCOUNT,LOOP：如果RCOUNT不为 0，则跳回循环，继续处理数据块。
- 折叠与进位处理：
- 将
RSUM和RCARRY相加，并检查是否有进位。如果有进位，则进行环绕进位操作。 SRDL RCARRY,16：将 32 位的RCARRY和RSUM折叠成 16 位。- 最后，进行 1 的补码操作，得到校验和的最终结果。
- 将
性能说明
- 时间：该算法在 IBM 3090 CPU 上测得的性能是每千字节 27 微秒。如果通过确保数据对齐，时间可以减少到 24.3 微秒，这要求在开始和结束时处理特殊情况，如字节交换（特别是当数据块的起始位置是奇数字节时）。
- 数据对齐：通过保证数据在字边界对齐，可以显著提高性能。
这种实现充分利用了 IBM 370 的处理能力，特别是在处理大块数据时，通过高效的内存访问和环绕进位操作确保了校验和计算的正确性和效率。
1. 引言
校验和（Checksum）是数据包中用来检测在传输过程中可能发生的错误的一种机制。对于如 TCP 等互联网协议 [1,9]，这尤其重要，因为数据包可能需要经过无线网络，如分组无线网络 [2] 和大西洋卫星网络 [3]，这些网络中数据包容易受到损坏。对于某些互联网协议（例如实时语音传输协议），系统可以容忍一定程度的传输错误，且可能通过前向纠错技术或者甚至完全不使用校验和来提高效率。但本文关注的是像 TCP 这样的协议，在这些协议中，可靠的数据传输是通过重传机制来实现的。
即便一个接收到的消息在校验和上看似正确，消息内部依然可能包含未被检测到的错误。这种错误发生的概率被限定为 2−C2^{-C}，其中 CC 是校验和的比特数。错误可能由硬件或软件故障、以及传输错误引起。硬件故障通常会以某些已知的方式表现出来，因此在设计校验和函数时，考虑这些常见的硬件故障类型是非常重要的。理想情况下，任何类型的常见硬件故障都不应该被漏检。
当前校验和函数能有效地检测到的一个故障示例是，当网络接口（或 I/O 总线、内存通道等）出现比特错误时，校验和将始终显示错误。然而，假设网络接口的一个控制信号失效，导致接口将零代替真实数据存储，这种“全零”消息可能会看起来具有有效的校验和。在 ARPANET 接口的“这是你的比特”线路 [4] 上的噪声也可能被漏检，因为额外输入的比特可能导致校验和与数据一样发生位移（即：扰动）。
尽管偶尔会有包含未检测错误的消息被传递到协议的更高层，但这些消息在更高层的协议中通常无法被理解。在 TCP 的情况下，大部分此类消息会被忽略，但有些消息可能会导致连接中断。损坏的数据可能会在 TCP 之上的协议层面被视为问题，而这些协议本身可能也有自己的校验和机制。
本文是设计新校验和函数的第一步，旨在改进 TCP 及其他互联网协议的校验和。我们识别了当前校验和函数的一些有用特性，并希望在任何新函数中尽可能保留这些特性。文章中还探讨了几种可行的校验和方案，其中只有“乘积码”（product code）方案看起来简单到足以进行考虑。
2. 当前的 TCP 校验和函数
当前的校验和函数主要面向16位机器，如PDP-11，但也可以轻松地在其他机器（例如PDP-10）上计算。数据包被视为一串16位字节，校验和函数是这些字节的“反码求和”（加法并进行环绕进位）。最终存储在 TCP 头部校验和字段中的值是该求和的反码。发送方在计算校验和之前，会将数据包的校验和字段置为零。如果接收方计算出的校验和为零，则认为数据包有效。这是因为校验和字段中的“负数”会正好抵消数据包其余部分的贡献。
忽略实际评估给定数据包校验和函数的复杂性，以上描述的校验和使用方法非常简单，但它假设了校验和操作符的一些特性（即反码加法，“+”）：
- (P1) 加法是交换的。因此，16位字节“加”在一起的顺序不重要。
- (P2) 加法有至少一个恒等元（当前函数有两个：+0 和 -0）。这使得发送方可以在计算校验和值之前，将数据包的校验和字段置为零。
- (P3) 加法有逆元。因此，接收方可以计算校验和并期望得到零。
- (P4) 加法是结合的，允许校验和字段位于数据包的任何位置，并且可以顺序扫描16位字节。
从数学角度看，二进制运算符“+”在16位数字集上具有以上特性，形成了一个阿贝尔群 [5]。当然，存在许多阿贝尔群，但并非所有的阿贝尔群都适合用作校验和操作符。（例如，PDP-11指令集中另一个满足这些特性的运算符是异或（XOR），但由于其他原因，XOR并不适用。）
尽管不够精确，但任何未来的校验和方案都必须保留以下性质：
- (P5) 加法应在各种机器上快速计算，并且对存储的需求应当有限。
当前的校验和函数在这方面做得很好。例如，在PDP-11上，内循环如下：
1 | LOOP: ADD (R1)+,R0 ; 将下一个16位字节加到R0 |
（每处理一个16位字节需要4个内存周期）
在PDP-10上，利用P1到P4的特性进一步优化，每次循环处理两个16位字节：
1 | LOOP: ILDB THIS,PTR ; 获取两个16位字节 |
（每处理一个16位字节需要3.1个内存周期）
上面循环中的“额外”指令用于将二进制补码加法转换为反码加法，通过使进位环绕。使用反码加法比使用二进制补码加法更好，因为它对所有比特位置的错误都同样敏感。如果使用二进制补码加法，则可能会在最重要的比特位置丢失（或获得）偶数个1，而不会影响校验和的值。正是这个特性使得某种加法比简单的异或更合适，而后者允许任何比特通道中偶数个比特丢失（或获得）。PDP-10上使用的RIM10B纸带格式 [10] 采用了二进制补码加法，因为加载程序的空间非常有限。
当前校验和方案的另一个特性是：
- (P6) 将校验和添加到数据包中不会改变信息字节。Peterson [6] 将此称为“系统化”编码。
这个特性允许中间计算机（如网关机器）在不解码数据包的情况下处理数据包中的字段（例如互联网目标地址）。错误检测的循环冗余校验（CRC）则不是系统化的。然而，大多数CRC的应用侧重于错误检测而非纠错，因此可以直接发送未修改的消息，只需在数据包末尾附加CRC校验码。ARPANET IMP和远程主机接口 [4] 使用的24位CRC，以及ANSI标准用于800和6250位每英寸磁带的CRC [11]，都采用这种模式。
需要注意的是，较高层协议的操作通常不会（按设计）受到网关可能对无效数据包所做的任何处理的影响。网关可以验证传入数据包的校验和，但通常如果校验和是协议特定的特性，网关并不知道如何进行验证。
当前校验和方案的最后一个特性，其实是P1和P4的结果：
- (P7) 校验和可以被增量修改。
这个特性使得中间网关可以在数据包中添加信息（例如时间戳），并“添加”适当的修改到数据包的校验和字段中。需要注意的是，校验和依然是端到端的，因为它并没有被完全重新计算。
3. 产品码（Product Codes）
某些“产品码”在校验和（checksum）处理中可能非常有用。以下是产品码在TCP协议中的简要描述。有关更一般的讨论，可以参考Avizienis [7]及其他一些较新的文献。
产品码的基本概念是，发送的消息（数据包）是通过转换原始源消息并添加一些“检查”位来形成的。接收方通过读取这些位并应用一个（可能不同的）转换，可以重构原始消息并判断其在传输过程中是否被损坏。
产品码的工作原理：
1 | Mo Ms Mr |
使用产品码时，发送的消息 Ms 是通过将原始消息 Mo 与某个已知常数 K 相乘得到的。即： Ms=K×MoMs = K \times Mo 接收方解码时，将接收到的消息 Ms 除以 K，如果消息没有损坏，商 Mr 就会等于 Mo，余数为零。
问题和注意事项：
选择合适的检查因子
K： 选择K时，必须确保它与用于表示消息的基数互质。例如，对于二进制消息，如果K被错误地选择为8，那么Ms看起来和Mo一模一样，只是附加了三个零。接收方只能通过检测到的错误位置来判断消息是否出现问题。对于TCP协议，基数
R选择为 2162^{16}： 每个16位字节（PDP-11上的一个字）被视为一个大数字的数字位，整个消息就被当做这个大数字来处理。因此，消息Mo可以表示为：Mo=∑i=0NBi×(Ri)Mo = \sum_{i=0}^{N} B_i \times (R^i)
其中 BiB_i 是第
i个字节。将Mo与K相乘得到Ms，如果数据包出现了单个字节的损坏，接收到的Ms'就会变成：Ms′=Ms+C×(Rj)Ms’ = Ms + C \times (R^j)
对接收到的消息
Ms'进行K除法时，会得到一个非零余数，表示消息Ms'被破坏。选择一个合适的
K： 为了检测到所有位突发错误，选择的K需要是 216−12^{16} - 1，这样所有小于等于15位的错误都会被检测出来。
实现：
乘法与除法的计算： 乘法和除法通常是比较复杂的运算，尤其是在存储和运算能力有限的小型机器上。然而，在这里的特定情况下，由于
K选择为 216−12^{16} - 1，可以通过简单的数字和运算快速检查校验和。例子： 在十进制中，基数为10时，选择
Q=6，则：6=0×9+6=6mod 96 = 0 \times 9 + 6 = 6 \mod 9
60=6×9+6=6mod 960 = 6 \times 9 + 6 = 6 \mod 9
600=66×9+6=6mod 9600 = 66 \times 9 + 6 = 6 \mod 9
同理，对于基数 R=216R = 2^{16}，校验和的计算也可以通过对各个字节求和来实现。
编码过程： 发送方需要将多精度的消息
Mo乘以 216−12^{16} - 1。这可以通过将Mo右移一个字长的位数然后减去Mo来实现。由于需要跨越字节的进位，因此采用的是补码运算。在PDP-11上的伪代码可能如下：
1
2
3
4
5LOOP: MOV -2(R2), R0 ; 取 (2^16) * Mo 的下一个字节
SBC R0 ; 处理上一个减法的进位
SUB (R2)+, R0 ; 减去 Mo 的下一个字节
MOV R0, (R3)+ ; 存储到 Ms
SOB R1, LOOP ; 遍历整个消息接收方解码： 在接收方，解码过程是通过观察每个
Ms中的字来推算原始消息Mo。由于在每个字中都包含了相邻两个字的差异，且低位字包含的是负的低位字，因此接收方可以逐步重建出原始消息。
额外的优化：
- 防止全零消息： 当一个消息完全是零时，除以
K会得到零，导致其看起来像是一个有效的消息。为此，可以引入一个常量C，例如C=1，以保证即使消息全为零也能正确处理。 - 性能评估： 相比当前的TCP校验和算法，产品码算法的计算时间大约是当前算法的两倍（即
P5被满足）。尽管如此，由于它具有较高的错误检测能力，仍然是一个可行的选择。 - 网关兼容性： 产品码校验和虽然不是系统化的（即不是每次都能得到有效的校验和），但它仍然能够快速验证消息的完整性，特别是当互联网目的地址位于数据包的低位部分时，网关可以在不解码整个消息的情况下进行校验。
总结来说，产品码校验和提供了一个强大的错误检测机制，能够通过简单的数字操作检测到消息中的错误，并且在TCP协议中能够快速实现。
4. 更复杂的编码（More Complicated Codes）
错误检测和纠正编码理论有着丰富的研究，Peterson [6] 是一个很好的参考。大多数“CRC”（循环冗余校验）方案是通过使用带反馈网络的移位寄存器来实现的，这个反馈网络由异或门（exclusive-ORs）构成。如果用程序来模拟这种逻辑电路，它的速度会太慢，无法满足实际需求，除非发现某些编程技巧。
一种被提出的技巧是由Kirstein [8] 提出的。基本上，当前移位寄存器状态的几位（四位或八位）与输入流（来自Mo的消息）中的位结合，结果用作查找表的索引，查找表给出新的移位寄存器状态，以及如果编码不是系统化的，输出流（Ms）中的位。对一个使用四位字节的特别“优良”CRC函数进行的试验编码显示，这种技巧使得编码速度大约是当前校验和函数的四倍。这在PDP-10和PDP-11机器上都是如此。
对于上述所列的期望特性，CRC方案仅满足以下两个特性：
- P3（它具有反向运算）。
- P6（它是系统化的）。
校验和字段在数据包中的位置非常关键，并且CRC不能被增量修改。
虽然编码理论的主要部分是针对二进制码的，但如果字母表包含 q 个符号，其中 q 是质数的幂，那么大部分理论同样适用。例如，选择 q = 2^{16}，就可以使得很多编码理论适用于按字处理。
5. 外部处理（Outboard Processing）
当像计算复杂的校验和这样的函数需要大量处理时，一种解决方案是将处理任务交给外部处理器。这样，“编码消息”和“解码消息”就成为了单一指令，能够避免占用主机处理器的资源。数字设备公司（DEC）生产的VAX/780计算机配备了专门的硬件来生成和检查CRC [13]。然而，一般来说，这种方案并不是一个很好的解决方法，因为每种不同的主机都需要为其构建一个专门的处理器，来处理TCP消息。
可以设想，某些大型主机的网关功能完全可以由一个“互联网前端机器”来完成。该机器将负责转发从网络接收的分组，或者从连接的主机的互联网协议模块接收的数据包，并将这些数据包重组为互联网段，传递给主机。该机器的另一项功能是检查校验和，以确保传递给主机的段在离开前端时已经是有效的。由于计算机周期被认为是廉价且可用的，这种方法是合理的。
问题与挑战：
将校验和验证工作放在前端进行，会破坏校验和的端到端特性。如果要实现这个功能，必须构建一个额外的协议来覆盖主机与前端机器之间的链接。具体做法是，前端机器在验证完从网络接收的数据包后，会将该数据包传递给主机，并告诉主机：“这是一个来自互联网的段，编号为 #123”。主机会保存这个段，并将其副本返回给前端机器，告诉前端：“这是你给我的 #123。它没问题吗？”然后，前端机器会与第一次传送的内容进行逐字对比，并告诉主机：“这是 #123 再次给你”，或者“你确实已经正确接收了 #123，放行它交给相应的模块进行处理。”
跨越主机与前端链接的消息头通常会使用一个较强的校验和，以确保其中的功能和消息参考编号等信息是可靠的。这些头部通常非常短，可能只有16位，因此校验和可以做得非常强大。消息的主体部分则通常不进行校验。
优势与问题：
这种方案减轻了主机的计算负担，因为验证消息的唯一要求是将它返回给前端机器。在PDP-10的例子中，这仅需每16位字节的互联网消息0.5个内存周期，并且仅需几个处理器周期来设置所需的传输操作。
然而，这种方法的一个问题是，它破坏了TCP校验和的端到端特性，而这正是该校验和最强大的特性之一。
6. 结论（Conclusions）
校验和函数是有序的，最简单的排序方式如下：
- 没有校验和：这种方法不提供任何错误检测或纠正。
- 发送一个常数：接收方检查这个常数，但这种方法非常弱。
- 数据的异或（XOR）：将数据进行异或运算并发送。XOR运算所需的计算时间最少，但它并不是一个好的校验和。
- 数据的二进制反码和：这种方法比异或稍微好一些，且计算时间不超过其他方法。
- 一的补码和：TCP协议当前使用的就是这种方法。它在计算上稍微更昂贵一些，但提供了更好的错误检测能力。
- 乘积编码（Product Code）：乘积编码与一的补码和密切相关，使用时需要更多的计算时间，提供了一定的抗硬件故障的能力，但它也有一些不太理想的特性。
- 真正的CRC多项式编码：这种方法仅用于检测，程序实现起来非常昂贵。
- 完整的CRC错误检测和纠正方案：这是一种最全面的错误检测与纠正方案。
对于TCP和互联网应用来说，乘积编码方案是可行的。它的主要问题在于，消息必须至少部分解码，以便通过中间网关进行转发。若不选择乘积编码作为改进的校验和方案，也可以对现有方案做一些轻微的修改。例如，“加法与旋转”（add and rotate）函数，曾由麻省理工学院人工智能实验室的PDP-6/10小组在纸带处理中使用，可能会有用，前提是能够证明它比现有方案更好，并且能够在多种机器上高效计算。