前言

在很多以太网、SATA 或其他高速接口项目中，我们经常会接触到 CRC（循环冗余校验）。通常，工程师会通过网站或软件工具生成一整套带异或操作的组合逻辑来实现 CRC 算法，而不去深入理解其原理——只知道可以这样用。事实上，在大多数情况下，确实不需要了解 CRC 的具体实现方法，这种黑盒化的使用方式在低频窄位宽场景下确实可行。

但是，当你的系统时钟非常高，例如 800MHz、1GHz，或数据位宽很大如 256bit、512bit时，工具生成的完整组合逻辑往往会因为时序问题而无法跑通。这时，就需要对 CRC 进行拆分设计，以优化时序和逻辑面积。如果不了解 CRC 的本质和计算方法，就很难进行这样的优化设计。

因此，理解 CRC 的原理和硬件实现方式非常必要。本文将分为两章，系统介绍 CRC 的发展历程与硬件高效实现方法。在本篇，我们将讲解：

• • 为什么CRC 选择除法来计算；
• • CRC 在数学上的核心思想；
• • CRC 多项式的表示方法及为什么选择特定的固定多项式；
• • 一种简单的硬件实现算法示例。

掌握这些内容之后，下一步将介绍如何实现高效的硬件 CRC 算法。

导读

CRC前传:错误检测

• • 错误检测的目的
• • 加法错误检测的缺陷
• • 除法错误检测的优势

CRC初识:CRC的关键元素

• • CRC 算法里的“多项式”是怎么回事？
• • CRC 算术的基本规则
• • CRC 计算的完整步骤
• • 如何选择CRC多项式（poly）

CRC硬件算法初探:简单CRC算法

CRC前传:错误检测

错误检测的目的

错误检测的目的，就是让接收方能判断一条在“嘈杂”（可能引入错误）的信道里传输过来的消息有没有被破坏。

做法是这样的：
发送方会根据消息本身计算出一个特定的值（叫做校验和，checksum），然后把它加到消息后面一起发出去。
接收方收到消息后，用同样的计算方法，再算一遍校验和，然后和消息中附带的校验和对比一下。

• • 一样 → 说明很可能没出错。
• • 不一样 → 说明传输过程中有数据被改了。

举个简单例子：
假设我们的校验和算法很粗暴，就是“把消息里的所有字节加起来，再对 256 取余”。
比如：

原始消息：  6  23  4  
加上校验和：6  23  4  33   （33 = (6+23+4) mod 256）  
传输后收到：6  27  4  33   （中间的 23 被传成了 27）  

接收方重新计算：

6 + 27 + 4 = 37

跟附带的校验和 33 不一样 → 发现出错！

当然，如果校验和本身在传输中被改了，就有可能把正常的消息误判成错误的，这种情况叫安全型错误（宁可多报错，不漏报）。

更糟的是，还有一种情况：数据和校验和都被改了，但恰好改得一致，这样接收方就完全察觉不到了。这叫危险型错误，而且是完全无法彻底避免的。我们只能通过增加校验和的信息量（比如从 1 字节扩展到 2 字节）来尽量降低这种风险。

除了简单的加和，还有更复杂的错误检测方法，比如对消息做复杂变换，加入更多冗余信息。
但本文只讨论 CRC（循环冗余校验）这种方法，它属于不改动原始数据，只在末尾追加一个校验和的算法，格式大概是：

<原始数据> <校验和>

加法错误检测的缺陷

在前面那个例子里，我们用“把所有字节加起来再对 256 取余”的方法检测消息是否被破坏。
比如：

原始消息：        6  23  4  
加上校验和：      6  23  4  33   （33 = (6+23+4) mod 256）  
传输后收到：      6  27  4  33  

这种方法能检测出错误没错，但它太简单了，所以也有缺陷。
如果数据在传输中被随机改动，有 1/256 的概率 恰好不会被发现。比如：

原始消息：        6  23  4  
加上校验和：      6  23  4  33  
传输后收到：      8  20  5  33  

虽然消息明显变了，但因为 (8+20+5) mod 256 仍然是 33，所以校验和对不上。

为了加强校验，我们可以把寄存器从 8 位扩展到 16 位（也就是对 65536 取余），这样理论上出错没被发现的概率能从 1/256 降到 1/65536。

听起来不错，但这里有个坑：
如果公式太简单（像这种单纯的加法），每个输入字节只会影响寄存器的一小部分位，不管寄存器多宽，还是可能漏检。
比如上面的例子，即使校验寄存器有一兆字节宽，错误也能逃过去。

解决这个问题的方法就是：
换一个更复杂的公式，让每一个输入字节都有可能影响寄存器的任何一位。

所以，一个强的校验和算法至少需要满足两个条件：

1. 1. 宽度 (WIDTH) ：寄存器要够宽，降低理论上的漏检概率。比如 32 位宽 → 漏检概率 1/2³²。
2. 2. 混乱度 (CHAOS) ：公式要够“乱”，让每个输入字节都有机会改动寄存器的任意一位。

顺便一提，“checksum”这个词原来是指简单的加法校验，但现在已经被扩展到更复杂的算法，比如 CRC（循环冗余校验）。CRC 在第二个条件上做得很好，而且可以灵活配置宽度。

除法错误检测的优势

在寻找比“加法”更复杂的校验方式时，我们可能会想到各种奇葩的办法：

• • 用圆周率 (π) 的数字做查表；
• • 把每个新字节和寄存器里所有字节混合做哈希；
• • 甚至用电话簿，把新字节和寄存器内容组合成一个索引，查到的新电话号码就是新的寄存器值。

想法可以天马行空，但其实没必要搞这么夸张。只要从加法往下一个算术步骤——除法，就够了。

加法做校验太弱，而除法在某些条件下就能做出很强的校验算法，尤其是当除数的位宽接近校验和寄存器位宽时。

CRC（循环冗余校验）的核心思想就是：

1. 1. 把整个消息看作一个超大的二进制数；
2. 2. 用一个固定的二进制数（多项式）去除它；
3. 3. 把余数作为校验和。

接收方收到数据后，再用同样的除数除一遍，看余数是不是和附带的校验和一致，如果一致，就说明数据大概率没出错。

举个小例子：
假设消息是两个字节 (6, 23)，用十六进制就是 0x0617，二进制写出来是 0000 0110 0001 0111。
我们用一个 4 位（1 字节宽）校验寄存器，除数是二进制的 1001（十进制 9）。
做二进制长除法，最后的余数是 0010（十进制 2）。

          ...0000010101101 = 00AD =  173 = QUOTIENT
         ____-___-___-___-
9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDEND
DIVISOR   0000.,,....,.,,,
          ----.,,....,.,,,
           0000,,....,.,,,
           0000,,....,.,,,
           ----,,....,.,,,
            0001,....,.,,,
            0000,....,.,,,
            ----,....,.,,,
             0011....,.,,,
             0000....,.,,,
             ----....,.,,,
              0110...,.,,,
              0000...,.,,,
              ----...,.,,,
               1100..,.,,,
               1001..,.,,,
               ====..,.,,,
                0110.,.,,,
                0000.,.,,,
                ----.,.,,,
                 1100,.,,,
                 1001,.,,,
                 ====,.,,,
                  0111.,,,
                  0000.,,,
                  ----.,,,
                   1110,,,
                   1001,,,
                   ====,,,
                    1011,,
                    1001,,
                    ====,,
                     0101,
                     0000,
                     ----
                      1011
                      1001
                      ====
                      0010 = 02 = 2 = REMAINDER

这时候，发送方发出去的内容是：

0x0617（原消息） + 0x2（校验和）

接收方收到后再做一遍 0x0617 ÷ 9，如果余数还是 2，就认为传输没出错。

为什么除法比加法好？

• • 在加法里，每个输入字节对寄存器的影响很局限；
• • 在除法里，每一位数据都会让余数在计算过程中被“搅动”，而且随着数据变长，余数会快速发生巨大变化；
• • 这种“混乱度”让漏检错误的概率大大降低。

CRC初识:CRC的关键元素

CRC 算法里的“多项式”是怎么回事？

在上一节里我们把 CRC 除法当作普通二进制除法（无进位 XOR），
但在很多书里，你会听到说：

“CRC 算法使用某个多项式”
“CRC 运算是多项式算术”

那是因为在数学上，我们把二进制数看作一个多项式的系数序列（通俗讲就是把二进制数变成多项式的形式） 。

1. 把二进制数变成多项式

例：
普通数 23（十进制）= 17（十六进制）= 10111（二进制）
如果把每一位二进制数当作一个多项式的系数（0 或 1），就得到：

1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0

简写为：

x^4 + x^2 + x^1 + x^0

这样，消息和除数都能表示成多项式。

2. 多项式乘法（正常规则）

如果我们想计算 1101 × 1011，对应多项式是：

(x^3 + x^2 + 1) × (x^3 + x^1 + 1)

按普通多项式乘法展开：

= (x^6 + x^4 + x^3)
+ (x^5 + x^3 + x^2)
+ (x^3 + x^1 + 1)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + 1

在普通算术里，我们知道 x=2，可以把 3*x^3 进位成：

x^7 + x^3 + x^2 + x^1 + 1

3. CRC 用的多项式算术：模 2 & 无进位

CRC 不这样做。
CRC 的多项式运算是在模 2 下进行的：

• • 系数只能是 0 或 1
• • 系数相加按 mod 2 运算（相当于 XOR）
• • 不存在进位

于是：

x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + 1

中，3*x^3 按模 2 变成：

1*x^3   （因为 3 mod 2 = 1）

最后结果：

x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1

4. 结论

• • 多项式 mod 2 算术 ↔ 二进制无进位算术
• • 加法、减法都是 XOR
• • 系数之间没有“进位”关系，每一项的计算独立
• • 用多项式只是数学上方便推导 CRC 的方式，但在实际实现时，直接用无进位二进制运算（XOR）就够了

CRC 算术的基本规则（无进位运算）

抛开多项式选择，我们现在关注 CRC 计算的核心算术特点：
所有运算都是二进制的，并且没有进位。
虽然很多人叫它“多项式算术”，但这里我们直接称它 CRC 算术。

1. 加法和减法

CRC 加法与普通二进制加法的唯一区别：不进位。
这意味着每一位的结果只取决于这一位对应的两个输入位，不影响其他位。

例如：

 10011011
+11001010
---------
 01010001

位运算规则：

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0   (无进位)

减法在 CRC 算术里和加法完全一样：

 10011011
-11001010
---------
 01010001

位运算规则：

0 - 0 = 0
0 - 1 = 1   (借位不需要，因为是 XOR)
1 - 0 = 1
1 - 1 = 0

所以：

CRC 的加法、减法、本质上就是 XOR（异或）
XOR 也是它自己的逆运算（做一次 XOR 再 XOR 同样的数，就回到原值，A XOR B = C，C XOR B = A）。

2. CRC 算术里的大小关系失效

在普通二进制里，1010（10）显然比 10（2）大。
但在 CRC 算术中，这种“大小”比较没意义。

例：

1010 = 1010 + 0011
1010 = 1010 - 0011

也就是说，同一个数可以通过加或减同样的值变成另一个数，因此无法定义严格的大小顺序。

3. 乘法

CRC 乘法就是按位移后的加法（XOR）求和：

例：

        1101
      x 1011
        ----
        1101
       1101.
      0000..
     1101...
     -------
     1111111  Note: The sum uses CRC addition
     -------

4. 除法

CRC 除法类似长除法，但判断“能除”是用最高位 1 的位置来比较的：

• • 如果被除数的最高位 1 在同一位置或更高，就能除。

例：

            1100001010
       _______________
10011 ) 11010110110000
        10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder

最终余数：

1110

5. 倍数与可整除的含义

在 CRC 算术中：

• • A 是 B 的倍数 → 可以从 0 开始，通过 XOR 加上若干个 B 的不同位移(位移相当于乘以2的幂)，得到 A。

例：

A = 0111010110
B = 11
A = B*2 + B*(2^4) + B*(2^5) + 2*(2^7)

                  0111010110
                = .......11.
                + ....11....
                + ...11.....
                  .11.......

如果 A = 0111010111，就不可能用 B 的若干位移 XOR 出来，所以不可整除。

6. CRC算术核心思想

不断把某个固定模式（poly）在不同位置 XOR 进数据里（通俗的讲 （信息+CRC校验） 是可以被poly整除的，不能整除CRC校验就错了）
这样既能构造倍数，也能做除法检测。

CRC 计算的完整步骤

1. 选择一个多项式（poly）

• • 这是 CRC 算法的“除数”
• • 叫它 生成多项式（generator polynomial）
• • 宽度 W = 最高位 1 的位置（从 0 开始数）
• • 例子：

Poly = 10011   → W = 4

2. 准备消息

原始消息：

1101011011

在末尾追加 W 个 0， 附加W个0后，信息相当于被左移W位（即乘以 2^W），为后续的模2除法（CRC计算）预留空间。这样可以在信息位后腾出位置，容纳最终的CRC校验码：

1101011011 0000

3. 在 CRC 算术（无进位 XOR）下做二进制长除法

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

4. 得到 CRC 校验码

Remainder = 1110

这就是 CRC 校验值（checksum）。

5. 发送数据

将原消息和 CRC 码拼接后发送：

1101011011 1110

6. 接收端校验方式

接收端有两种常见做法：

方法 A

1. 1. 拆分出消息部分和 CRC 部分
2. 2. 对消息（加 W 个 0）重新做 CRC 运算
3. 3. 对比计算结果和接收到的 CRC 是否相等

方法 B

1. 1. 对“消息+CRC”整体做一次 CRC 运算
2. 2. 如果结果是 0，则校验通过

如何选择CRC多项式（poly）

选择 CRC 的多项式（poly）其实是一门“玄学”，细节可以参考 Tanenbaum 的书（p.130–132），那里讲得很清楚。
我这里只是想劝你——千万别自己随便拍脑袋造一个 poly，不然你会踩坑。如果你不关心为什么某个 poly 更好，只想直接搞个靠谱又快的实现，那就直接用附录A列出的“算术上可靠”的标准 poly，别自己发明。

1. CRC 校验的数学背景

先记住一点：发送出去的消息 T（消息T尾部带了CRC校验） 一定是 poly 的倍数。
原因是：

1. 1. 发送前我们会在消息末尾加 W 位的余数（W 是 poly 的位宽），这个余数是用 poly 除扩展后的消息算出来的；
2. 2. 在 CRC 中，加法和减法是一样的（都是 XOR），所以把余数加回去会让整个值变成 poly 的整数倍。

如果传输过程中消息被破坏，接收方收到的其实是：

T + E

其中 E 是“错误向量”（+ 代表 XOR）。
接收方用 poly G 去除：

(T + E) mod G = E mod G

因为 T mod G = 0，剩下的就全看 E 能不能被 G 整除。
如果 E 是 G 的倍数，那么错误检测不出来，所以选 poly 的目标就是：找一个 G，让它的倍数尽量不像传输线路里常见的噪声模式。

2. 常见的错误类型和 poly 选择原则

单比特错误（Single-Bit Error）

错误形态：

E = 1000...0000

解决方法：选一个 G，至少有两个 1 位。这样它的倍数不可能是只有一个 1 的数，所以单比特错误一定能检出。

双比特错误（Two-Bit Error）

错误形态：

E = 100...000100...000

解决方法：选一个 G，它的倍数不包含以下模式：

11, 101, 1001, 10001, 100001, ...

有些 G 满足这个条件，比如 (15,14,1) 这个多项式就不会整除长度小于 1...1（32767 个 0）的模式。

奇数个比特错误（Odd Number of Bit Errors）

如果想让所有“1 的个数是奇数”的错误都能被发现，可以选一个 1 的个数是偶数 的 G。
原因：

• • CRC 乘法就是不断 XOR 某个固定值到寄存器的不同偏移；
• • XOR 就是“翻转位”；
• • 如果一个值里 1 的个数是偶数，每次翻转偶数个位，1 的奇偶性不会变。
  所以用偶数个 1 的 poly，可以确保奇数个比特错误全被发现。
  Tanenbaum 还指出，更严格的条件是：G 要是 11 的倍数。

突发错误（Burst Error）

错误形态：

E = 000...000 111...111 000...000

即中间连续一段是 1，其它全是 0。
解决方法：

• • 让 G 的最低位是 1，这样错误左边那段 0（LEFT 部分）就不会是 G 的因子；
• • 只要 G 的位宽比连续 1 的那段（RIGHT 部分）更大，这种错误就能被检测出来。
  Tanenbaum 说，如果突发错误的长度大于 W（poly 宽度），漏检概率是 (0.5)^W。

3. 一些常用的可靠多项式

• • 16 位
  • • (16,12,5,0) → X.25 标准
  • • (16,15,2,0) → 常见的 “CRC-16”
• • 32 位
  • • (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) → Ethernet 用的 CRC-32

‍

CRC硬件算法初探:简单CRC算法

让我们从最朴素的实现开始 ，这个版本可能很慢，但能清晰展现算法本质。理解这个基础后，我们会像搭积木一样，一步步添加优化技巧，最终打造出那个你在实际项目中常见的、高效的表驱动实现。

核心思路

• • 用一个 W 位的寄存器（W = 多项式最高位位置）
• • 依次把 消息的每一位（加上 W 个 0 的“尾巴”）送进寄存器
• • 每次移位后，如果左端（最高位）弹出的是 1，就执行一次 寄存器 XOR 多项式
• • 最后寄存器中的值就是 CRC 校验值

此方法看似稍显杂乱，但其本质是通过从消息中不断”减去”多项式的不同幂次（即移位操作），直至剩余仅余余数。若对此理解困难，可参考CRC计算的完整步骤中长除法的示例说明。

步骤流程

                  3   2   1   0   Bits
                +---+---+---+---+
       Pop! <-- |   |   |   |   | <----- Augmented message
                +---+---+---+---+

             1    1   0   1   1   = The Poly

假设：

• • W = 4
• • Poly = 11011（注意多项式是 W+1 位，但寄存器只有 W 位）
• • 寄存器初始全 0
• • 消息 = 1101（按位高到低依次送入）
• • 最后要加上 W 个 0（用于得到余数）

算法伪代码：

R = 0                      ; W 位寄存器初始化为 0
M = 消息 + W 个 0           ; 扩展消息

for bit in M:               ; 从最高位到最低位
    out = R[W-1]            ; 记录左边弹出的最高位
    R = (R << 1) | bit      ; 左移一位，把新位送到最低位
    if out == 1:            ; 如果弹出位是 1
        R = R XOR poly_low  ; 与多项式的低 W 位异或

注意：poly_low 是 去掉最高位的多项式位串，因为最高位对应的“除法对齐”已经由 out==1 触发了。说白了就是pop出来的1和poly最高位的1抵消掉了，所以不用关注最高位。

动作对照

可以把它想象成一个小机器：

1. 1. Shift：寄存器内容左移一位，右边塞入新数据位
2. 2. Check：如果左边溢出的是 1，就触发一次 XOR（“减去”多项式）
3. 3. 循环直到所有消息位都处理完
4. 4. 剩下的寄存器值就是 CRC

示例

以 Poly=11011，W=4 为例：

• • Poly 除最高位外的部分是 1011
• • 消息 = 1101（按位高到低依次送入）
• • 每当最高位溢出 1，就 R = R XOR 1011
• • 最后 R 的内容就是 CRC 值 1000

‍

‍

写在最后

通过上述内容，相信你已经对CRC校验的数学原理和基础实现有了系统性的理解。在后续章节中，我们将深入探讨面向高性能计算场景的CRC硬件优化架构，包括并行化处理等关键技术。

‍

往期回顾

每天学一点可综合SystemVerilog语法（合集）

其他技术专栏

‍

附录A

附录B

欢迎加入FPGA/IC专属AI知识库，在这里你可以查阅更多知识，无需下载App，微信小程序即可一键使用。

点击链接一键加入

附录C

欢迎加入FPGA与数字IC学习交流群!
在这里，你可以提出问题、分享你的学习心得，或是参与到有趣的讨论中。

链接：FPGA芯研社

附录D

#FPGA #数字IC #EDA #Verilog #CRC #循环冗余校验 #错误检测 #硬件实现 #多项式除法 #模2运算 #校验和 #数据完整性 #通信协议 #高速接口 #以太网 #SATA #并行计算 #时序优化