做通信协议和底层软件这行几乎天天要和模2运算打交道。奇偶校验、CRC校验、LFSR伪随机序列、汉明码纠错这些看似各不相同的技术剥开外壳后核心全是模2加法、模2减法、模2乘法、模2除法这一套四则运算。很多人一开始觉得简单不就是异或吗可真到自己手算CRC、设计校验矩阵时才发现模2除法里的门道比想象中多得多什么时候算够除、余数保留几位、为什么减法等于加法每一个细节都可能让结果完全对不上。这篇文章我从原理讲到实操把这套运算一次讲透。无论你是做嵌入式、写网络协议栈、搞数据校验还是刚开始啃编码理论只要愿意跟着手算几道题基本就能把模2运算的底子打牢。放心数学门槛不高会用二进制、会看真值表就足够。1. 模2运算到底是什么一个XOR撑起的算术体系1.1 从一次车载总线错误说起先讲个我早年的经历。有次调试一块采集板I2C总线上偶尔会读出错误数据排查到最后怀疑是校验和不对。当时同事用C写了一个校验函数思路是逐个字节异或求和这思路本身没错但他把最后一步写成“如果计算结果为负数就加256取正”。问题来了异或的结果根本没有正负概念这步操作纯属画蛇添足反而把一个正常的校验和给改错了。后来把这个多余操作删掉系统立刻稳定。这件事给我的触动很大。模2运算是整个数据校验体系的底子但很多人的理解停留在“异或就是按位不一样”这种表面层次一旦涉及加减乘除、涉及多项式、涉及余数位宽就特别容易出问题。所以这篇文章不急着讲CRC-32怎么查表而是先把模2加法、减法、乘法、除法这四则运算本身彻底讲明白。只有把这四则运算吃透后面那些看起来高大上的应用在你眼里都只是换了个马甲的异或操作。1.2 数学定义与GF(2)域只有0和1的世界模2运算的正式说法是在二元域GF(2)上做算术。所谓GF(2)就是只包含0和1两个元素的有限域所有运算结果都对2取模。这个“对2取模”是什么意思呢就是普通计算结果除以2只保留余数。比如1122除以2余0所以模2结果是0再比如0-1-1-1除以2余1所以模2结果是1。你可以把GF(2)想象成一个只有两个状态的世界0和1。在这个世界里任何超过1的数都会被折叠回0和1。现实中最形象的类比是电灯开关一个开关按一下是开再按一下又关了按两次等于没按。如果把“按”看成加1那就成了110这正是模2加法的直觉。为什么这个领域如此重要因为数字系统里所有数据归根到底都是0和1只要涉及“判断两段数据是否一致”“从一段数据中提取校验信息”就绕不开GF(2)上的运算。奇偶校验是一个字节内所有位做模2加法CRC校验是一整段数据和一个生成多项式做模2除法纠错码是把码字看成GF(2)上的向量做线性变换。可以说模2运算就是数字世界的基本语法之一。四种运算的总体关系我整理成一张表可以先当目录看运算规则本质典型应用模2加法110等价异或奇偶校验、XOR校验和模2减法与模2加法完全相同模2除法的中间步骤模2乘法移位相加部分积用异或合并多项式乘法、BCH码相关运算模2除法长除但减法全是异或CRC循环冗余校验2. 模2加法与模2减法为什么它们其实是同一件事2.1 规则、真值表与电路里的异或门模2加法的规则一共四条背下来只需要十秒输入A输入B模2和000011101110这其实就是硬件里的异或门XOR。教科书给它的定义是“两个输入不相同时输出1”但用模2的眼光看它就是一个无进位加法器11本该等于10但我们把进位丢掉只留最低位0。这个视角非常重要因为当你把位扩展到字节、把字节扩展到整段数据时按位异或就是在做一串彼此独立、互不进位的模2加法。模2减法也简单规则同样四条0-001-011-100-11。看到规律了吗这和加法真值表一模一样。也就是说在GF(2)里减法和加法是同一个运算。用数学语言说GF(2)中每个元素都满足a-a一个数和自己的相反数相加等于0而它的相反数就是它自己。这一点在普通十进制里完全无法想象但在0和1的二值世界里就是事实1加1等于0同时1减1也等于0。2.2 减法等于加法的等价关系到底意味着什么普通人第一次看到0-11往往会愣一下0比1小怎么能减出1来我们换个角度解释。普通算术里0-1-1。可-1在模2意义下和1属于同一个等价类因为-1除以2的余数是11除以2的余数也是1。所以0-11成立而且01也等于1。这就是模2减法和模2加法等价的原因。这个等价关系看似不起眼却是所有模2运算能统一的基础。模2乘法的部分积相加、模2除法的每一步“减法”实际执行的都是异或。很多人初学CRC时盯着“除法”两个字理所当然地用普通减法去算结果每一步都在借位算出来的余数永远不对。问题的根源就在这里模2除法里的减法其实一直是加法异或。吃透这一点还有个好处你在设计校验算法时不需要专门写一个“模2减法”函数一切都复用异或运算。硬件上更简单一个XOR门既做加法又做减法逻辑资源几乎可以不计。这也是为什么奇偶校验、CRC这类算法能在极其廉价的MCU上跑得飞快。2.3 实操用XOR计算一组数据的校验值工程上最常见的模2加法应用是XOR校验和。假设你要发送4个字节0xA5、0x3C、0x5A、0x0F校验字节取它们的按位异或。我一步步算给你看。先把0xA5和0x3C展开成二进制10100101 ^ 00111100 10011001也就是0x99。再拿0x99和0x5A继续异或10011001 ^ 01011010 11000011也就是0xC3。最后拿0xC3和0x0F异或11000011 ^ 00001111 11001100也就是0xCC。这个0xCC就是校验字节。接收方把数据字节连同校验字节一起异或如果结果是0就说明这些字节的奇偶关系没问题。你可以试着算一遍0xA5 ^ 0x3C ^ 0x5A ^ 0x0F ^ 0xCC确实等于0。这个方案虽然不能定位错误也扛不住偶数个比特同时出错的情况但计算成本极低在很多低速总线、存储校验场景里依然是首选。3. 模2乘法没有进位的二进制乘法3.1 运算规则与手算示例模2乘法在初看时和普通二进制乘法很像仍然是乘数每一位去乘被乘数得到若干部分积再把部分积加起来。唯一区别是所有部分积相加时用异或而不是普通加法也就是每一列上如果1的个数是偶数该位结果就是0奇数就是1。因为在相加过程中不存在进位所以部分积彼此独立这是模2乘法的核心。我拿一个具体例子说明计算1011 × 11011 0 1 1 × 1 1 0 1 ------------- 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1四个部分积分别是1011乘数最低位为1、0000乘数第二位为0、1011乘数第三位为1、1011乘数最高位为1依次左移0、1、2、3位。接下来逐列做异或相加第0列只有1个1结果1。第1列第0个部分积是1第1个部分积是0结果1。第2列第0个部分积是0第2个部分积是1结果1。第3列三个1相遇奇数个结果1。第4列两个1偶数个结果0。第5列一个1结果1。第6列一个1结果1。最终结果是1111111。这里必须强调一个常见误区1011和1101在普通十进制乘法里是11×13143换算成二进制是10001111这和我们模2乘法的结果1111111完全不同。因为模2乘法丢掉了一切进位所以它不能套用“先算十进制再转二进制”的思路。3.2 多项式乘法视角为什么结果不是11×13如果你看过编码理论的教材一定会遇到“码多项式”这个概念。模2乘法的本质就是把二进制数看成GF(2)上的多项式然后做标准多项式乘法只是系数相加遵循模2加法。比如1011对应多项式x^3x11101对应x^3x^21两者相乘(x^3x1)(x^3x^21) x^6x^5x^3x^4x^3xx^3x^21这里有个值得注意的细节x^3项一共出现了三次。按照模2加法奇数个1保留所以x^3项的系数是1。合并同类项之后得到x^6x^5x^4x^3x^2x1系数从高到低排列就是1111111和手算结果一致。这个多项式视角最大的优势是让你能够用代数的方法理解后面的一切模2除法本质上就是多项式长除法CRC的本质就是多项式求余。在学习BCH码、里德-所罗门码这些更高级的编码技术时这个视角几乎是必需品。4. 模2除法唯一不能一眼看穿的运算4.1 运算规则与“够除”的判断标准模2除法是四个运算里最容易翻车的一个。它的外形跟普通二进制长除法很像从被除数高位开始逐段取位和除数做运算得到商和余数。但和普通长除法相比有两个关键区别。第一每一步的“减法”全部用模2减法也就是按位异或所以不会出现借位现象。第二“够除”的判断不看数值大小只看当前参与运算窗口的最高位。如果当前窗口最高位是1就说明够除商位写1然后把除数和窗口做异或如果最高位是0就说明不够除商位写0直接把窗口往右滑动一位。为什么能只看最高位因为在GF(2)的多项式除法里判断一个多项式能否被另一个多项式整除只取决于次数关系而最高位是1就代表当前窗口次数不低于除数次数。这个规则和普通十进制长除的“够不够减”有本质区别。普通除法里窗口1001和除数1001比大小可能刚好够减但在模2除法里只要最高位是1哪怕窗口值看起来比除数小也要商1并做异或异或结果可能是0也可能是其他值。4.2 完整手算示例10111 ÷ 101我拿一个具体例子逐步演示。被除数10111除数101。第一步从被除数最高位开始取三位除数位数作为窗口101。窗口最高位是1够除商位写1。然后做异或101 ^ 101 000把结果000作为新窗口从被除数剩余部分拉入下一位1窗口变为001。第二步窗口001最高位是0不够除商位写0。继续拉入下一位1窗口变为011。第三步窗口011最高位是0不够除商位写0。此时被除数所有位用完除法结束。商的二进制是100也就是多项式里的x^2。余数取最后一次窗口的后两位因为除数是三位余数位数约定不超过两位011取后两位就是11。当前窗口最高位商位操作说明操作后窗口10111101 ^ 101 000拉入下一位100100100不异或直接拉入下一位101101100无剩余数据位停止011最终结果商100余数11。验算一下10111对应多项式x^4x^2x1除数101对应x^21。x^4除以x^2得x^2乘积为x^4x^2两者异或后剩x1也就是11。完全正确。这个例子里窗口变化比较快核心就是记住每次拉入新位后重新看最高位最高位为1就异或为0就只移位。实际工程里做CRC时这个操作可以用一个移位寄存器加异或门自动完成但理解手算过程能帮你搞清楚寄存器里每一步到底在干什么。4.3 余数位数约定CRC里最容易踩的坑余数到底保留几位这是整个模2除法里约定最重要、也最容易被忽视的地方。在标准CRC计算中除数生成多项式通常写成r1位余数固定为r位。比如生成多项式是1011这是4位r3余数就必须写成3位生成多项式是1101也是4位r3余数也是3位。我们刚才算出来的余数是11如果按r3的约定就要写成011。很多人在这一步掉坑明明余数算对了拼装发送帧时却没有把余数补足到r位结果接收端怎么验都验不对。类似的错误还有除法中间过程里擅自丢弃前导0导致窗口错位。我建议初学者一开始就按“除数是n位余数固定为n-1位”的约定来练习每一步都保持窗口位数一致等熟练之后再跳步。5. 模2运算的应用从奇偶校验到汉明码5.1 成本几乎为零的奇偶校验模2加法最直接的应用是奇偶校验位。发送数据前统计数据中1的个数如果采用偶校验就在校验位填上能让总1个数为偶数的值。这本质上就是把数据所有位做一遍模2加法再把和放到末尾。接收端对所有位再做一次模2加法如果结果不是0说明传输过程中出现了奇数个比特错误。奇偶校验能检测出所有奇数位错误但检测不了偶数位错误。比如数据1010两个1偶校验位为0如果传输中变成1100仍然两个1校验通过但数据确实错了。这是这种方案的天花板。不过它的优势也很突出一个异或门就能实现成本几乎为零时延也极小。所以在很多对可靠性要求不极端、但对成本和时延敏感的场合比如UART串口通信奇偶校验至今仍是标配。5.2 CRC循环冗余校验模2除法的经典舞台CRC可能是大多数人接触模2运算的真正原因。它的核心思想不复杂发送端把数据看作一个多项式M(x)为了让接收端能够检测错误发送端额外附加一个余数FCS这个余数是M(x)乘上x^r之后除以生成多项式G(x)得到的。接收端把整个帧数据加余数除以同一个G(x)如果余数是0就认为传输没有出错。这里有个重要前提为什么发送端要把M(x)先乘上x^r因为这样才能腾出r个空位让余数拼接到数据后面之后整体能被G(x)整除。这一步如果漏掉整个CRC校验的整除性质就不成立。我用一个完整小例子说明。假设数据M101101生成多项式G1101r3。第一步M乘以x^3也就是把数据左移三位补零得到101101000。第二步对101101000做模2除法除数是1101。按长除流程逐步算窗口是4位拉入的数据依次是0、1、0、0、0。序号当前窗口最高位商位操作说明操作后窗口11011111011 ^ 1101 0110拉入0110021100111100 ^ 1101 0001拉入100113001100不异或拉入001104011000不异或拉入0110051100111100 ^ 1101 0001拉入000106001000无剩余数据位停止-最后窗口是0010按r3取后三位余数R010。所以发送帧是101101 010也就是101101010。接收端用1101去除101101010余数为0校验通过。这个例子虽然小但完整展示了“左移补零、模2除法、附加余数、整除验错”的全流程。真实工程里CRC-16、CRC-32等标准还会在基本流程之外加很多环节比如初值寄存器、输出前异或、数据反射等等。这些都不是模2运算本身的改动而是为了让检测效果更稳定、兼容性更好。理解基本流程后那些标准参数读起来就像一张配置表不再是玄学。5.3 LFSR一个反馈异或生成伪随机序列线性反馈移位寄存器LFSR是另一个经典应用。它的核心结构是一个移位寄存器某些位抽头出来做模2加法再反馈回到寄存器输入端。如果抽头位置对应一个本原多项式那么只要初始状态不是全0输出序列就会以2^n-1为周期循环形成伪随机序列。以生成多项式x^3x1为例对应3级LFSR反馈抽头在第0位和第1位规则是新输入 当前第0位 ^ 当前第1位。寄存器状态依次为001、100、110、111、011、101、010然后回到001。这个序列里所有非零状态都出现了一次周期正好是2^3-17这就是最长线性移位寄存器序列也叫m序列。这类序列在通信里非常常用可以用作PN码做扩频、跳频图案也可以做伪随机数发生器。它的好处是硬件极简几个D触发器和异或门就能跑出看起来毫无规律、实际完全可复现的序列。很多加密、加扰场景的基础逻辑都靠它。5.4 Hamming码校验位背后的异或方程汉明码Hamming Code是纠错码里最基础的一种它的核心也是模2加法。拿Hamming(7,4)来说4个数据位D1到D43个校验位P1到P3校验位由下面的异或方程确定P1 D1 ^ D2 ^ D4P2 D1 ^ D3 ^ D4P3 D2 ^ D3 ^ D4比如数据1011代入计算P11^0^10P21^1^11P30^1^10校验位就是010。接收端根据同样的方程重新计算校验位并与收到的校验位比较得到三位校正子。如果校正子全0说明没有错误否则校正子的二进制值直接指明出错位置。这里的底层逻辑仍然是模2加法校验位就是一组特定数据位的模2和校正子就是接收数据重新计算后与原始校验位的模2差。没有异或整个纠错体系都无从谈起。6. 编程实现与避坑指南6.1 用Python写一个通用的模2除法函数理解了手算过程用程序实现就非常直接。这里我写一个最简单的逐位异或版本目的是展示原理不追求性能def mod2_div(data_bits, gen_bits): # data_bits和gen_bits都是0/1列表gen_bits最高位必须为1 data list(data_bits) n len(gen_bits) for i in range(len(data) - n 1): if data[i] 1: # 当前窗口最高位为1够除做异或 for j in range(n): data[i j] ^ gen_bits[j] # 余数是最后n-1位 return data[-(n - 1):] # 验证M101101, G1101, r3 m_bits [1, 0, 1, 1, 0, 1] g_bits [1, 1, 0, 1] # M 3 padded m_bits [0] * (len(g_bits) - 1) remainder mod2_div(padded, g_bits) print(remainder) # 输出 [0, 1, 0]这个函数的关键在于循环里只看data[i]是否为1这正好对应手算时“看窗口最高位”的规则。每次异或就相当于从高位消去一项循环结束后后面n-1位就是余数。实际工程中CRC算法为了提高速度会做成查表法一次处理4位或8位但底层逻辑和这个逐位版本完全一致。查表不过是把移位异或的中间结果提前算好缓存起来。6.2 初学模2运算最常犯的五个错误我见过不少工程师在不熟悉模2运算时踩同样的坑整理成一张表对照检查很方便。错误做法直接后果正确做法模2除法里用普通减法出现借位余数完全错误减法全部替换为按位异或用数值大小判断是否够除窗口数值小于除数但最高位为1时漏算只看窗口最高位是否为1余数不补前导0拼帧后校验位位数不够接收端验错按r位固定补齐如余数11写成011把模2乘法当普通整数乘法进位污染结果与多项式乘积不符部分积相加用异或丢掉进位做CRC时忽略初值、终值异或、反射等约定发送端和接收端计算结果不一致先统一标准参数再动手写代码第三条尤其隐蔽。很多人手算余数得到11觉得直接放到帧尾就行却没意识到接收端把“11”当作三位余数“011”来解析结果怎么都对不上。这个坑我当年也踩过后来养成习惯算完CRC先检查余数长度是不是正好等于生成多项式位数减1。6.3 几个实战技巧与心算经验最后分享几个实操中沉淀下来的技巧。第一少量位的模2运算完全可以靠多项式展开来算不容易出错。把位串换成x的多项式合并同类项时数一下系数的个数奇数个就保留偶数个就消掉。这个方法在验证手算结果时特别好用。第二算CRC时心里记一个固定模板先左移r位补零再做除法取余数。整个过程就是一个“M左移r位后再除以G”的公式。我习惯把发送帧写成(M r) | R其中R就是余数这样在任何场合都不容易忘记拼接规则。第三程序验证手算结果是最快的。上面那段Python代码只有十来行随手定义一个列表就能验算。我平时做协议设计时会先手算一组小样本再用程序验一遍两边对上才放心。第四如果做的是标准CRC比如CRC-16/CCITT、CRC-32建议直接把标准参数多项式、初值、输入反射、输出异或、结果异或当成配置项。真正要理解的是模2除法本身标准参数的差异只是对输入数据做的预处理和后处理不影响核心思想。做校验和编码这些年我的体会是模2运算就像一把螺丝刀看着简单用对了地方才有价值。真正常用的核心操作其实只有一个异或但要把它和多项式、寄存器状态机串成一个整体去理解才能在CRC、BCH、LFSR这些场景里不吃亏。如果你刚开始接触我的建议是先别急着背CRC查表程序找个下午拿纸笔把101101除以1101这样的题多算几遍把所有约定都理清楚上了工程之后会省很多心。