计算机网络中的CRC

什么是洪泛法？

在计算机网络中，CRC 被称为循环冗余校验。它用于识别数据传输或存储中的错误。它是一种错误检测码，广泛应用于网络通信和数据存储。

CRC 可以准确地检测出常见的错误类型，例如单比特错误和一些突发错误。循环冗余校验是网络协议（如以太网）中广泛使用的方法，有助于我们在数据传输过程中保持数据的完整性。如果发现错误，接收方可以要求重新传输数据，以确保数据是否正确接收。

尽管 CRC 是一种相对简单有效的错误校验技术，但它只能识别错误。更复杂的纠错方法，如前向纠错（FEC），用于错误纠正。

它是如何工作的？

在计算机网络中，循环冗余校验（CRC）首先生成一个短二进制序列，称为 CRC 码。它是通过对正在传输的数据执行数学运算生成的。让我们详细了解一下它的工作原理。

• 数据分割：在 CRC 中，使用一系列比特来表示传输的数据。因此，使用特定的多项式作为除数，以便我们可以创建 CRC 码。用于创建 CRC 码的多项式码称为生成多项式。
• 附加零：数据最后附加一串零，通常等于生成多项式的位数减一。生成的 CRC 码将放在这些零之间。
• CRC 计算：发送方使用生成多项式作为除数，对扩展数据执行二进制除法运算。二进制 XOR（异或）运算用于执行此除法运算。
• CRC 码生成：CRC 码是使用除法运算的余数创建的。然后将原始数据附加到此 CRC 码。
• 传输：整个消息，包括 CRC 码和原始数据，被发送到网络。
• 接收方计算：接收方也在接收端执行相同的 CRC 计算。它使用相同的生成多项式对接收到的数据进行除法，并考虑 CRC 码。
• 错误检测：如果接收方生成的 CRC 码与数据一起收到的 CRC 码匹配，则数据传输中很可能没有错误。如果计算出的 CRC 码与接收到的 CRC 码不匹配，则会发生传输错误。
• 对错误的响应：如果发现错误，接收方可能会要求重新传输数据，以确保正确接收。

生成多项式的数学特性对于 CRC 的效率至关重要。它经过精心选择，以增加检测错误的可能性，尤其是可能在数据传输过程中发生的常见错误。

总之，CRC 通过数学算法从数据创建校验和（CRC 码）。此校验和与数据一起发送，并在接收方进行重新计算以查找错误。如果计算出的校验和与收到的校验和一致，则认为数据无误；否则，则会发现错误。

为什么我们在计算机网络中使用 CRC？

计算机网络和数据存储系统出于几个重要原因使用循环冗余校验（CRC）。

1. 错误检测

CRC 主要用于数据传输和存储过程中的错误检测。通过这种方式，可以快速有效地识别常见的错误类型，例如单比特错误或突发错误，这些错误可能由于数据传输过程中的电噪声、信号干扰或其他因素而发生。

2. 数据完整性

在网络和数据存储应用中，确保数据完整性至关重要。通过使用 CRC，数据接收者可以确认他们接收到的数据与发送的数据相同。如果发现错误，他们可以要求重新传输或采取其他适当的措施来确保数据准确性。

3. 效率

CRC 计算效率高，可以相对快速地完成，因此适合以太网等高速数据传输系统中的实时错误检测。其有效性确保了较短的数据处理时间。

4. 开销低

与其他错误检测技术（如添加冗余数据位（奇偶校验位））相比，CRC 码相对较短。这意味着 CRC 在提供强大的错误检测功能的同时，几乎不会增加传输数据的开销。

5. 广泛采用

以太网、Wi-Fi、蓝牙以及许多其他网络协议和数据存储系统都使用 CRC。它们的广泛使用确保了各种系统和设备的兼容性和互操作性。

6. 简单性

CRC 的实现相对简单，并且用于 CRC 计算的硬件或软件组件易于获取。其在许多系统中的普及和简单的应用可归因于这种简单性。

7. 通用性

通过选择各种生成多项式，CRC 可以适应各种应用和错误检测需求。

8. 实时检测

由于 CRC 校验是实时进行的，因此一旦接收到数据就可以识别错误。对于网络协议来说，快速响应任何错误并确保数据完整性，即时反馈至关重要。

总之，CRC 错误检测方法在计算机网络和数据存储中很受欢迎且有效，因为它在简单性、速度和错误检测效率之间取得了平衡，有助于确保传输或存储数据的完整性和可靠性。

示例

让我们举一个 CRC 在计算机网络中使用的例子

假设一根网线连接了两台计算机，计算机 A（发送方）和计算机 B（接收方），计算机 A 希望将一条消息发送给计算机 B。

数据准备（计算机 A，发送方）

• 假设计算机 A 要发送的消息以单词“HELLO”开头。
• 消息的二进制表示如下：“01001000 01000101 01001100 01001100 01001111”（每八位一组对应一个 ASCII 字符）。

CRC 计算（计算机 A，发送方）

• 为了进行错误检查，计算机 A 在消息中添加了一个 CRC 码。
• 它选择了一个特定的 CRC 多项式，例如 CRC-32，作为除数。
• 计算机 A 使用 CRC 多项式作为除数，对扩展数据（消息 + CRC）执行二进制除法运算。
• CRC 码由该除法的余数创建。

CRC 数据（发送方：计算机 A）

• CRC 码已附加到原始“HELLO”消息中。假设计算出的 CRC 码是“1101”。
• 现在需要发送的信息是“01001000 01000101 01001100 01001100 01001111 1101”。

传输（计算机 A 是发送方，计算机 B 是接收方）

• 通过网络，计算机 A 将数据（包括消息和 CRC 码）传输给计算机 B。

接收方计算（接收方 - 计算机 B）

• 计算机 B 接收到数据，并将消息与 CRC 码分开。
• 它还使用相同的 CRC 多项式（之前与计算机 A 约定）将接收到的消息除以二来计算 CRC 码。

接收方错误检测（计算机 B）

• 如果计算机 B 生成的 CRC 码与从计算机 A 收到的 CRC 码匹配，则消息很可能没有错误。
• 如果计算出的 CRC 码与接收到的 CRC 码不匹配，则会发生传输错误，消息被视为已损坏。

错误响应（接收方 - 计算机 B）

如果发现错误（CRC 码不匹配），计算机 B 可以要求计算机 A 重新发送消息，以确保收到正确的数据。

CRC 的局限性

尽管 CRC 是一种在计算机网络和数据存储系统中流行且成功的错误检测方法，但它确实存在一些限制。

• 无法修复错误：CRC 只能检测错误，不能修复错误。如果发现错误，典型的 CRC 过程将要求重新发送数据以纠正错误。其他错误校验技术可以纠正错误，例如 Reed-Solomon 码。
• 有限的错误检测：尽管 CRC 能够有效地检测多种类型的错误，但它可能会遗漏一些错误，特别是当这些错误遵循与 CRC 多项式特征一致的某些模式时。CRC 可能无法识别一些复杂的错误模式。
• 固定长度 CRC：所选的生成多项式将决定 CRC 码的长度。这意味着为了确保对不同应用或数据大小的充分错误检测，您可能需要使用不同的生成多项式。选择错误的生成多项式可能会导致较弱的错误检测能力。
• 碰撞的可能性：有时，两个不同的数据集会生成相同的 CRC 码。这被称为碰撞。好的生成多项式的特性使得这种情况极不可能发生，但理论上是可能的。
• 突发错误倾向：尽管 CRC 可以检测到一些突发错误（连续比特出错），但其检测长突发错误的成功率取决于所使用的多项式。
• 实现复杂性：尽管 CRC 的基本思想相当简单，但在硬件或软件中有效实现可能很困难，尤其是在高速数据传输系统中。这种复杂性可能会减慢系统速度。
• 依赖于生成多项式：选择合适的生成多项式对 CRC 提供的错误检测精度有显著影响。好的多项式选择可以带来更多的错误检测。