1. 模2运算的编码本质什么时候你会真的需要它做通信、写底层驱动、做存储校验、甚至玩点嵌入式开发的朋友模2运算这四个字一定不陌生。它还有一个更常见的名字——二进制多项式运算。我第一次接触模2运算是当年调一个CRC16校验模块对着数据手册怎么都算不对后来才意识到问题出在我用普通十进制除法的思路去理解模2除法从一开始就错了。模2运算不是普通四则运算的“二进制版本”它是有限域GF(2)上的运算。这里的“2”指的是模数整个运算体系只有0和1两个元素。它最核心、最反直觉的一条规则是加法等价于减法也就是按位异或XOR。所有进位和借位全部被丢掉1101-10。如果你以前没接触过有限域会觉得这简直是在胡闹但硬件中最省门的加法器、最常用的校验算法、最经典的纠错编码全建立在这套看似荒唐的规则之上。这篇文章想做的事是把模2加法、模2减法、模2乘法、模2除法这四种运算彻底讲透。我会从数学定义、手算过程、多项式视角、工程应用四个维度拆开把每一步为什么这么算说清楚顺便附上一些我踩过的坑。适合刚接触CRC、LFSR、汉明码的学生也适合需要亲手实现算法但总被资料绕晕的工程师。2. 模2加法与模2减法为什么它们在二进制世界里是同一件事2.1 按位异或的三种理解方式模2加法用符号⊕表示规则极其简单0⊕000⊕111⊕011⊕10。你把这组规则展开成真值表会发现它和逻辑门电路里的异或门XOR gate完全一致。所以很多场合下模2加法直接就叫“按位异或”。第一种理解方式是把它当“二进制无进位加法”。普通加法里1110会产生进位模2加法里这个进位被直接扔进垃圾桶只剩下最低位的0。这正是数字电路中半加器输出端“和位”的算法两个一位二进制数相加不计算进位输出结果就是异或。第二种理解方式是把它当“奇偶统计器”。把两个比特相加结果是1就说明这一位上有奇数个1结果是0说明偶数个1。这个性质是后面汉明码、奇偶校验的基础你不用记住复杂公式只记住“异或就是在数1的个数是奇数还是偶数”就够了。第三种理解方式则是多项式系数相加mod 2。把二进制串a3a2a1a0写成多项式a3x³a2x²a1xa0模2加法就是两个多项式对应项系数相加再模2。例如1011⊕01101101用多项式写就是(x³x1)⊕(x²x)x³x²1。这种视角的价值在于它能解释模2运算和普通多项式除法之间的关联是后面理解CRC的一把钥匙。2.2 模2减法瞧它和加法长得一模一样模2减法规则0-001-011-100-11。你仔细看一下除了符号不同结果和加法真值表完全一样差异只在“按位来看时加法和减法都等价于异或”。因为GF(2)中-1等于1因为110移项可得-11所以减法和加法是同一种运算。这个“减法等于加法”的性质在实际工程中带来的直接收益是设计校验电路时接收端不需要区分“加法校验”还是“减法校验”统统用一个异或门阵列搞定。我第一次算CRC时看着手册里发送端“用0补位然后模2除”和接收端“直接对接收到的码字做模2除”的两种描述绕了很久才明白其实接收端做模2除法时每一步的中间减法全部可以换成加法结果不变。有人会问那模2减法有什么独立存在的必要其实它更多的是数学形式上的需要。在推导汉明码校验矩阵、描述线性分组码时我们经常写“校验方程”用加号还是减号表达都不影响计算结果但习惯上人们会按代数风格写成减法形式。你只要记住“模2减法就是异或”所有相关计算立刻变得简单。2.3 实际手算注意事项位数对齐与符号手算多位数模2加/减时最大的坑就是进位和借位直觉。普通十进制加法看到11会下意识进位模2运算必须忍住每列独立异或。举个具体例子1101⊕10110110计算过程是第3位1⊕10第2位1⊕01第1位0⊕11第0位1⊕10。任何一位上出现“两个1”结果直接归零别往前一位送东西。省略前导0的规则也要注意。很多人算完高位为零后直接去掉这在数学上没错但做校验时数位长度的约定很讲究被除数的位长决定除法结果的位长。我建议手算时先把高位0补齐再操作避免漏位。3. 模2乘法不产生进位的多项式相乘到底在算什么3.1 手算竖式的变种模2乘法规则可以归结为两句话中间结果按位乘就是逻辑与部分积累加时用异或而非普通加法。以101×011为例1 0 1 × 0 1 1 ---------- 1 0 1 1 0 1 0 0 0 ---------- 1 1 1 1 (模2加法合并)普通乘法里第二行要左移一位第三行左移两位最后把所有行加起来。模2乘法里左移策略完全一样区别只在最后合并时用异或第一行101、第二行1010、第三行0000三者异或得到1111。这里有个看起来诡异的结果11×11101对应十进制3×39你们自己感受下这已经不是十进制乘法能解释的范畴它本质是多项式相乘。多项式解释最优雅101代表x²1011代表x1相乘得到x³x²x1对应二进制1111。你能看到多项式乘法里的系数合并用了模2加法这就是“无进位乘法”的由来。3.2 模2乘法的用途BCH码、加密与通信干扰设计模2乘法看起来“算不准”却在代数和工程上撑起了不少重要算法BCH码和Reed-Solomon码这类纠错码的编码过程需要对信息多项式乘一个生成多项式这个乘法就是模2更一般地说GF(2^m)上的乘法。LFSR的跳跃计算当线性反馈移位寄存器需要一次性跳过多拍、生成某个位置的序列时本质上是把状态寄存器视为多项式做模2乘。经典加密中的混淆扩散很多轻量级密码算法比如AES内部的某些操作底层的有限域乘法扩展自模2乘法的思想只是它把每个字节当作GF(2^8)元素规则更复杂。初学者最大的误区是试图把模2乘法的结果和十进制乘法对应起来。它俩没任何数值上的等价关系模2乘法关心的是“多项式相乘后的系数分布”不是“数值相乘的积”。理解到这一层你再去看BCH码的编码公式会顺畅很多。3.3 一个容易忽视的细节乘法结果的最高位普通乘法里n位乘m位结果最多nm位模2乘法同样如此但当你把乘法用在编码算法里时通常会对结果做一个截断。比如某些生成多项式设计里乘完后会“丢弃最高项”只保留低n位这实际上是模一个特定多项式的操作已经进阶到“模2多项式乘法取余数”的范畴。我提醒你很多资料里写“乘”其实是“乘后取模”不仔细看上下文会拿错中间数据。这种“乘法 取模”的组合和普通算术里的同余运算非常像。你可以把它理解为先做一个无进位多项式乘法然后除以一个固定的生成多项式只留下余数。若没理解这层后面看NTT数论变换或者CRC计算都会犯迷糊。4. 模2除法CRC校验码的计算基石4.1 长除法的每一步为什么是“异或”模2除法更像普通长除法但规则变成了“被除数当前位对齐除数用异或代替减法”。核心步骤如下在信息位后面补r个0r是除数的位数减1对于CRC这个除数叫生成多项式。从被除数最高位开始找到第一个为1的位与除数最高位对齐。对这一段做模2减法等价于异或。把结果写下来继续下一步。举个例子被除数110101除数10114位r3求余数。1 0 1 1 (商其实我们不关心) ---------- 1011 ) 1 1 0 1 0 1 1 0 1 1 --------- 1 1 0 0 1 0 1 1 --------- 1 1 1 1 1 0 1 1 --------- 1 0 0 0 1 0 1 1 --------- 1 1 - 余数但这里有个严重的问题上面的写法容易让人误以为和普通除法一样用“试商法”实际模2除法里商的每一位由当前被除数最高位直接决定当前最高位是1商位就为1是0商位就为0这时直接把除数左移成对应长度的0等同于跳过。所以实现时通常用移位寄存器逐位处理而不是像上面这样写完整的长除法。4.2 模2除法手算的完整CRC例子假设要发送的信息为1011生成多项式为10011对应x⁴x1则补4个0后得到10110000。除的过程第一步10110的前四位1011 vs 10011异或得到00101剩余位0。第二步有效位从00101开始最高位为0则跳过直到遇到1相当于对应的商位为0继续下拉。继续处理直到被除数全部消耗最后的余数就是CRC校验值。我算出来余数为1001。那么发送的码字就是1011 1001信息位余数。接收端把整个10111001除以同一个生成多项式如果余数为0说明没有检测到错误余数非0则说明数据被篡改或发生传输错误。这一步是所有CRC校验算法的基础逻辑。4.3 余数的位数陷阱不是所有余数都叫CRC初学最常见的错误之一是补0个数没弄清楚。生成多项式r位时补0的个数是r-1不是r。以生成多项式10011为例它是5位所以补4个0。很多手册直接说“生成多项式为0x13多项式最高次为4因此r4”这里的r是指多项式的次数而不是二进制位长度。如果你按最高位补齐就会多补1位导致整个校验码完全错误。另外余数是r-1位还是r位当被除数补了r-1个0后最终余数最多是r-1位。以上面的例子生成多项式5位余数最多4位正好可以和信息位拼接成“信息位4位校验位”的完整码字。这个“发送码字长度 原信息长度 生成多项式次数”的关系是整个CRC编码里最重要的一条准则。5. 从手算到程序实现模2运算的代码思路与查表优化5.1 基本位运算实现不要以为必须写一个复杂的多项式计算库模2运算用C语言位运算十几行就搞定了。模2乘法uint32_t gf2_mul(uint32_t a, uint32_t b) { uint32_t result 0; while (b) { if (b 1) result ^ a; // 异或累加 a 1; // 左移一位 b 1; } return result; }这段代码模拟了手算竖式b的最低位决定要不要把当前a累加到结果a每次左移相当于竖式里的“部分积左移一位”。模2除法取余uint32_t gf2_mod(uint32_t dividend, uint32_t divisor) { int shift 0; uint32_t tmp divisor; while (tmp dividend) { tmp 1; shift; } for (; shift 0; shift--) { if (dividend (1u (shift __builtin_clz(divisor) ... ))) dividend ^ (tmp shift) ??? } }这段看得头大没关系因为工程上根本没人每次手写逐位异或。标准做法是表驱动预先把被除数的一个字节8位和生成多项式组合算好256种余数存成表然后每个字节查表处理。这就是CRC查表法的核心思路。我实测下来同样是在STM32上算CRC32逐位法要几毫秒查表法只需几十微秒差距非常大。5.2 两种常见实现风格的对比实现方式核心思想优点缺点逐位算法模拟长除法每次处理1比特代码简单适合教学和验证慢数据量大时消耗CPU查表法预计算256个表项每次处理1字节快适合嵌入式实时场景需要额外RAM存表需注意反射/非反射问题不夸张地说我见过至少三个工程师被CRC的反射reflected和非反射模式坑过。同一份查表代码参数里多了一个“输入是否反射”的开关结果就完全不同。这些参数本质上不影响模2运算的数学定义但影响你按什么顺序把字节喂进除法器。新手手算的时候可以忽略一旦上代码调通信协议就得仔细核对规范里的CRC参数模型。5.3 从手算到程序的验证技巧我每次写完CRC或LFSR相关代码不会直接上板测。我的习惯是先找一份已知正确结果的测试向量比如IEEE 802.3 CRC32的标准测试输入123456789结果是0xCBF43926。用脚本或计算器手算一遍小数据比如前面提到的信息位1011、生成多项式10011验证输出1001。再把代码里所有中间状态打印出来和手算步骤逐位比对。这一步虽然费时间但能快速定位实现里“左移方向”“初始值”“异或顺序”的问题。别问我怎么知道的当年调CRC16时整整卡了一个礼拜最后发现只是初始寄存器应该填0xFFFF而不是0x0000。6. 那些藏在模2运算背后的知名应用LFSR、汉明码与生成多项式6.1 LFSR一条异或链就能生成伪随机序列线性反馈移位寄存器LFSR看起来是数字电路核心其实就是一个反复做模2除法的机器把寄存器的某些位抽出来做反馈本质上是构造一个多项式除法器。你选定一个本原多项式作为反馈系数寄存器每移位一次等效于状态多项式乘以x后对生成多项式取模。这样生成的0/1序列具有伪随机性被广泛用在扩频通信、测试码生成、白噪声模拟中。LFSR和CRC有极强的亲缘关系很多CRC硬件模块内部就是一个LFSR。换句话说CRC编码器就是一个时序化的模2除法电路。理解了这个共通性从软件CRC到FPGA实现的调试思路就能互相借鉴。6.2 汉明码用一组异或方程定位哪一位错了汉明码是历史上第一个实用的纠错码它用一组校验位对信息位进行监督。校验位的计算就是模2加法——即便这种计算方式被包装成“校验方程”本质仍然是数一数该组数据里有奇数个还是偶数个1。举个例子经典的(7,4)汉明码4位信息d1~d43位校验p1~p3。校验位计算公式为p1 d1 ⊕ d2 ⊕ d4p2 d1 ⊕ d3 ⊕ d4p3 d2 ⊕ d3 ⊕ d4接收端收到7位后重新计算三组校验方程根据哪几组校验失败就能定位出是第几位出了差错。这套定位逻辑本质上是在解一组GF(2)上的线性方程矩阵形式就是校验矩阵H。如果你熟悉模2乘法还能看到汉明码的码字生成其实也是一个生成矩阵G作用在信息向量上的过程也就是模2矩阵乘法。6.3 生成多项式的选择好的多项式决定了算法好不好用整个模2除法在CRC中最关键的变量就是生成多项式本身。为什么有的多项式被广泛采用比如CRC-16/IBM的0x8005、CRC-32/IEEE的0x04C11DB7因为它们经过了大量数学分析和工程验证错误检测能力、碰撞概率、最大可检测突发错误长度都做得比较好。现场调试时很多人遇到“CRC偶发校验不过”第一反应是代码有bug其实问题经常出在生成多项式不匹配对端设备用的多项式和你用的不一样或者初始值/结果异或值不同。这些参数在模2运算里不显眼但在具体协议里是必须严格对齐的元数据。我的建议是工程开头就把“多项式、初值、输入反射、输出反射、结果异或值”这五项统统写进设计文档别让后人拿代码猜来猜去。7. 进阶思考有限域GF(2)与GF(2^m)的关系以及更广的模2应用7.1 把模2运算扩展成字节级运算你可能已经发现上面所有的模2运算都是针对单个bit的。但工程中的RS码、AES算法经常提到的却是“字节在GF(2^8)上的运算”。它和本文的模2运算什么关系我先说结论GF(2^8)里的每个元素本身就是一个8比特二进制数可以看作一个多项式元素之间的加法就是逐比特异或就是本文的模2加法但乘法不再是单纯的模2多项式乘法而是“模2多项式乘法再模一个8次不可约多项式”。换句话说GF(2^8)乘法是广义的模2运算——加法和减法仍然是异或乘法多了一个“取余不可约多项式”的环节。这就是为什么你会看到AES加密里字节相乘的结果十六进制下看起来“不按常理出牌”。7.2 经典算法中的模2思想奇偶校验码最简单的错误检测发送前算所有数据位异或结果接收端再算一遍。如果你能接受“异或就是模2和”的观念会发现奇偶校验本质上就是在GF(2)上求和。线性反馈移位寄存器LFSR前面说过状态转移本质上是有限域上的乘法。无线通信中的加扰/解扰很多标准里的扰码器就是LFSR原因之一是模2运算在硅片上实现极便宜。ZUC、SNOW这类序列密码其线性部分大多建立在GF(2)或GF(2^32)上用的还是模2加法和GF上的乘法。看多了你会发现模2运算是一座很基础的桥梁。从简单的校验位到复杂的密码算法最底层无非“异或、移位、取模”这三个动作在组装。理解了它再去学那些看似高深的东西会有一种“原来还是老朋友”的爽快感。7.3 我自己对学习顺序的建议如果你现在刚入门我的建议是先别急着背公式。第一步把本文的手算例子自己各算一遍感受“无进位加法”和“异或减法”。第二步用C语言写一个最朴素的逐位CRC函数不查表、不优化纯粹模拟长除法。第三步找一个标准协议比如Modbus CRC16参数用咱们前面提的测试向量验证代码。第四步再回头学LFSR和汉明码你会发现它们的数学骨架你已经全部打好了。这个顺序是我自己走了弯路后总结出来的。当初我直接从查表法抄代码结果遇到反射参数、初始值这类问题就完全懵了因为我不懂底层原理。后来静下心从手算和逐位模拟开始再回头看查表法所有参数的意义一目了然。技术这行越是基础的东西越值得砸时间。模2运算就是这样一个“基础但不简单”的存在。希望这篇长文能帮你们绕开那些我曾经踩过的坑需要讨论细节的朋友评论区见。