简介这是一份面向通信、存储及编码学习者的BCH纠错编码源码采用C#语言实现并针对m小于等于20的场景做了算法修正在短码字、低数据量与实时性要求较高的系统中表现稳定。压缩包仅含1个c文件体积约5KB结构精炼却覆盖了BCH编码解码的核心流程生成多项式构造、模2除法编码、Syndrome计算、错误定位多项式求解以及纠错校正。通过阅读和调试这份代码可以直观理解伽罗华域上的多项式运算以及Berlekamp-Massey算法在解码中的实际运用为后续移植到其他平台或集成进通信系统提供基础。目前已有202人学习下载适合对编码理论感兴趣、希望结合实例掌握BCH实现细节的IT从业者与相关专业学生。1. BCH码不是黑匣子C# 里做前向纠错绕不开这张有限域表做 C# 上位机的人大概率遇过这种场景下位机通过 RS485 或自定义以太网协议回传采集数据链路偶尔受干扰丢一两个字节。传统做法是 CRC 校验发现错了就请求重传可一旦走到无线、存储或者不能随意停下来的实时链路重传成本太高这时候就需要前向纠错。BCH 码是一类经典的循环纠错码BCH(15,7,5) 用 7 位数据附带 8 位校验位能纠正 2 位随机错误工程里常被拿来当独立纠错模块用。C# 里实现 BCH 并不难真正让新手卡住的是有限域查表、位序方向和缩短码这几个细节。这篇文章把从建域、编码、译码到验证的完整路径走一遍适合要在 .NET 项目里集成纠错能力的开发者也适合正在读别人 C/C 源码想移植到 C# 的人。2. 先建伽罗华域 GF(2^m)两张表和一个本原多项式决定 BCH 的全部行为2.1 为什么校正子计算必须发生在 GF(2^m) 而不是普通二进制BCH 码的本质是把码字看成多项式要求它在若干个特定的域元素上取值为零。这些“特定的域元素”不是普通整数而是伽罗华域 GF(2^m) 里的元素通常写成 α 的幂次。BCH(15,7,5) 对应 GF(2^4)域里有 16 个元素BCH(31,21,5) 对应 GF(2^5)域里有 32 个元素。接收端拿到一个码字 r(x)只要 r 里没有错误那么 r(α^1)0、r(α^3)0这是因为生成多项式 g(x) 以 α 和 α^3 为根。一旦传输中引入了错误 e(x)校正子 S1 r(α^1) 就等于 e(α^1)S3 r(α^3) 就等于 e(α^3)。错误图形只有两种常见形态错 1 位或者错 2 位。两种形态下 S1、S3 会呈现完全不同的代数关系译码器靠这两个值反推出错误位置。这就是 BCH 绕不开有限域的原因你需要在 GF(2^m) 里做乘法、除法和求逆而不是普通整数四则运算。GF(2^m) 里的加法是异或乘法是“指数相加后查表”一切运算都在 α 的幂次循环里进行。听上去很玄学但代码落地后你会发现核心不过是两张查表数组。2.2 C# 查表实现指数表、对数表与乘除法先给出一个最精简的 GF(2^4) 实现。本原多项式选用 x^4x1十六进制是 0x13。这个多项式决定了 α 的每一个幂次长什么样也决定了后面所有 BCH 参数。public class Gf16 { private readonly int[] exp new int[16]; private readonly int[] log new int[16]; public Gf16(int primitivePoly) { int x 1; for (int i 0; i 15; i) { exp[i] x; log[x] i; x 1; // 左移后如果第4位溢出就用本原多项式做约简 if ((x 0x10) ! 0) x ^ (primitivePoly 0x0F); } exp[15] 1; // α^15 1周期闭合 } public int Exp(int i) exp[i % 15]; public int Log(int x) log[x]; public int Mul(int a, int b) { if (a 0 || b 0) return 0; return exp[(log[a] log[b]) % 15]; } public int Div(int a, int b) { if (a 0) return 0; return Mul(a, exp[(15 - log[b]) % 15]); } public int Add(int a, int b) a ^ b; }循环里做的事情是计算 α^0 到 α^14 的每一个值。变量 x 从 1 开始每次左移一位相当于乘一次 α。左移后如果第 4 位二进制 10000置位说明乘出了域范围需要用本原多项式做模约简异或 0x13 的低 4 位 0x3。这样 exp[i] 存的就是 α^i 的二进制表示log[x] 存的是反查表。Mul 和 Div 是这套实现里最常用的两个函数。乘法走“对数相加再查指数表”除法走“乘以逆元”逆元通过 exp[(15 - log[b]) % 15] 得到。注意如果 b 是 0除法会踩到 log[0] 的坑调用方必须保证除数非零。在后面的 Peterson 译码里我会专门处理除零分支。2.3 常用 BCH 码参数BCH(15,7,5) 与 BCH(31,21,5) 对照网上能找到的 BCH C/C# 源代码里出现频率最高的两组参数是 BCH(15,7,5) 和 BCH(31,21,5)。前者的域是 GF(2^4)适合演示和短帧场景后者域是 GF(2^5)适合实际链路里 21 位一组的数据块。参数BCH(15,7,5)BCH(31,21,5)域GF(2^4)GF(2^5)码长 n1531数据位 k721校验位810纠错能力 t22本原多项式0x13x^4x10x25x^5x^21生成多项式 g(x)0x1D1x^8x^7x^6x^410x769x^10x^9x^8x^6x^5x^31有一件事必须提醒生成多项式跟本原多项式是绑定的。比如 BCH(15,7,5) 如果换一个本原多项式 0x19生成的 g(x) 就不是 0x1D1。从网上找 C# 实现时先检查这两个值是否配套不要只抄 g(x) 就去算校正子。后面避坑章还会展开这一点。3. BCH(15,7,5) 编码器用 C# 把 7 位数据变成 15 位可纠错码字3.1 系统码编码等于一次二进制多项式长除不需要有限域乘法不少初学者以为 BCH 编码也要在 GF(2^4) 里做乘法其实编码只在 GF(2) 上进行也就是普通二进制异或逻辑。原理是把 7 位数据左移 8 位腾出校验位空间然后除以生成多项式 g(x)余数就是校验位。最终码字 数据多项式左移 8 位 余数。为什么这样做能让码字成为 g(x) 的倍数因为码字多项式 C(x) x^8·D(x) R(x)而 D(x)·x^8 除以 g(x) 的余数正好是 R(x)所以 C(x) 整除 g(x)。这是循环码的通用构造方式BCH 是循环码的一个子类。此处不需要有限域表只需要一个 15 位整数的逐位异或除法。3.2 编码函数与生成多项式 0x1D1 的实际用法下面是完整的 C# 编码函数。输入是 0 到 127 的整数输出是 15 位码字用 int 存放。// 生成多项式 g(x) x^8 x^7 x^6 x^4 1 // 二进制 1_1101_0001十六进制 0x1D1 const int Gp157 0x1D1; static int EncodeBch157(int data) { int poly data 8; // 7 位数据左移 8 位变成 15 位被除数 for (int i 14; i 8; i--) { // 如果当前最高位是 1就异或生成多项式做长除 if ((poly (1 i)) ! 0) poly ^ Gp157 (i - 8); } // 循环结束后 poly 只剩 8 位这就是校验位 return (data 8) | poly; }编码过程就是逐位消去被除数的高位。从 bit14 往 bit8 扫逢 1 就异或生成多项式左移相应位数。循环结束后 poly 的低 8 位就是余数也就是校验位。生成多项式 0x1D1 一共 9 位最高位 x^8 在代码里不直接参与异或因为每一次异或都通过左移把最高位对齐到当前要消去的位上。实际串口传输时15 位码字没法按整字节发常见做法是发两个字节先发高 8 位再发低 7 位或者把校验位压缩成两个字节并预留 1 位给协议状态。工业场合用得更多的是 BCH(31,21,5)因为 21 位数据加 10 位校验组合成 31 位后可以放进 4 字节里对齐更方便。3.3 从 7 位推广到 21 位把编码函数写成通用版写死 BCH(15,7,5) 只能用于演示。实际项目里更常见的是把编码逻辑抽成通用函数用参数切换码型。我一般这样封装static int EncodeBch(int data, int dataBits, int genPoly, int parityBits) { int totalBits dataBits parityBits; int poly data parityBits; for (int i totalBits - 1; i parityBits; i--) { if ((poly (1 i)) ! 0) poly ^ genPoly (i - parityBits); } int parityMask (1 parityBits) - 1; return (data parityBits) | (poly parityMask); }调用方式BCH(15,7,5) 用EncodeBch(data, 7, 0x1D1, 8)BCH(31,21,5) 用EncodeBch(data, 21, 0x769, 10)。参数里 genPoly 的位数必须等于 parityBits 1因为生成多项式的最高次就是校验位长度。如果 genPoly 写错位数循环会直接越界或者异或出一堆垃圾。![注意] 编码器本身不查有限域表所以上面的通用函数在 BCH(15,7,5) 和 BCH(31,21,5) 之间切换时只要换参数即可。生成多项式的二进制位宽要严格核对0x1D1 是 9 位0x769 是 11 位。4. BCH 译码器三次校正子和一次 Chien 搜索纠正 2 位错4.1 校正子 S1、S3霍纳法在 C# 里的紧凑实现接收端拿到 15 位码字 rv 后先算两个校正子 S1 rv(α^1)S3 rv(α^3)。这里用霍纳法从最高位迭代到最低位每步做一次 GF 乘法和一次异或。GF(2^4) 里 α^1 的值是 2α^3 的值是 8这两个数来自前面建立的 exp 表。static (int S1, int S3) CalcSyndrome(int rv, Gf16 gf) { int s1 0, s3 0; for (int i 14; i 0; i--) { int bit (rv i) 1; // 提取第 i 位系数 s1 gf.Mul(s1, 2) ^ bit; // s s * α bit s3 gf.Mul(s3, 8) ^ bit; // s s * α^3 bit } return (s1, s3); }霍纳法的好处是不需要为每一项系数单独查表一次循环同时算出两个校正子。注意 rv 的 bit14 对应 x^14bit0 对应 x^0这个方向在后面的 Chien 搜索里也必须保持一致。如果接收端拼字节时高低位搞反校正子全对但错误位置会全部错位。计算出 S1 和 S3 后分三种情况。两者都是 0说明没错误。S1 非零、S3 等于 S1^3说明只有 1 位错误。S1 非零、S3 不等于 S1^3说明有 2 位错误。这套判断逻辑不需要 BM 算法t2 时用 Peterson 算法更直接。4.2 Peterson 算法解错误位置多项式t2 版t2 时错误位置多项式是 σ(x) 1 σ1·x σ2·x^2其中 σ1 S1σ2 (S3 S1^3) / S1。这个公式来自牛顿恒等式推导过程在多数教材里有代码里只需要记住两个结论单错时 σ2 0双错时 σ2 ≠ 0。除法必须在 GF(2^4) 里做就是前面 Gf16.Div 做的事。static int DecodeBch157(int rv, Gf16 gf) { (int s1, int s3) CalcSyndrome(rv, gf); if (s1 0 s3 0) return rv; // 没有错误 if (s1 0) return -1; // 无法纠正多错且 S1 恰好为 0 int sigma1 s1; int s1Cubed gf.Mul(gf.Mul(s1, s1), s1); int sigma2 gf.Div(gf.Add(s3, s1Cubed), s1); // sigma2 0 表示单错误错误位置直接查对数表 if (sigma2 0) { int pos gf.Log(s1); return rv ^ (1 pos); } // 双错误需要 Chien 搜索找两个位置 int errMask 0; for (int pos 0; pos 15; pos) { // 代入 x α^(-pos)判断 σ(x) 是否为 0 int rootInv gf.Exp((15 - (pos % 15)) % 15); int val 1 ^ gf.Mul(sigma1, rootInv) ^ gf.Mul(sigma2, gf.Mul(rootInv, rootInv)); if (val 0) errMask | (1 pos); } return rv ^ errMask; }这里有两个关键分支必须解释清楚。第一s1 0 但 s3 ! 0 的情况Peterson 公式除数为零不能硬算直接返回 -1 让上层走重传策略这比抛异常体面得多。第二单错误时 σ2 为 0错误位置就是 log 表反查 S1 得到的幂次这个位置是 x^pos 的系数位直接翻转即可。4.3 Chien 搜索与错误翻转最容易写反的一行Chien 搜索是逐位代入 σ(x) 求根的过程。工程实现里最容易写反的是“代入 x α^(-pos)”还是“代入 x α^pos”。我见过不少 C# 移植版在这个地方差一个正负号结果单比特测试能过双比特测试全挂。原因在于 σ(x) 的定义是 ∏(1 - X_l·x)根是 X_l^(-1)也就是 α^(-pos)。在 Gf16 里求 α 的负次幂用的是周期性质α^(-pos) α^(15-pos)。代码里gf.Exp((15 - (pos % 15)) % 15)就是为了处理 pos 等于 0 时的情况避免出现 Exp(15) 越界。错误掩码 errMask 直接和 rv 异或完成纠错。位序约定从第 2 章延续到这里bit14 是 x^14bit0 是 x^0。编码、校正子、Chien 搜索这三处位序必须统一任何一处反过来都会让纠错结果错到对面位置。这也是我建议在写完译码器后立刻做全搜索验证的原因后面专门有一章讲怎么验。5. BCH 避坑指南本原多项式、位序、缩短码三个高发区5.1 本原多项式从网上抄错校正子永远是 0现象从某份 C 源码把 GF(2^4) 的建表逻辑移植到 C#编码输出看着正常但接收端把收到的数据喂进译码器S1、S3 永远算出来是 0即使人为翻转两位也纠不回来。最后发现错误根本不在译码器而在建表阶段。原因BCH(15,7,5) 的域可以由不同的本原多项式生成比如 x^4x10x13和 x^4x^310x19。代码里建表用的本原多项式如果和生成多项式 g(x) 不配套整个 α 的幂次循环都是另一套校正子自然对不上。解决先检查建表循环里的 primitivePoly 是不是 0x13。再一个快速自检α^15 应该等于 1如果 exp[15] 不是 1说明建表约简逻辑有 bug。最后核对 g(x)0x13 对应的 BCH(15,7,5) 生成多项式是 0x1D1不是 0xD8。有些文档把最高位 x^8 省略写成 0xD8移植时要把最高位补回来。5.2 位序放反单比特测试第一个用例就翻车现象给译码器喂一个只在 bit0 翻转的码字纠错结果把 bit14 翻掉了。或者单错误能修双错误修完反而多一个错误。这类问题不是有限域算错而是整条链路的位序约定不一致。原因C 语言源码里常见的位序有两种。一种是把数组下标 0 当最高位另一种是把 bit0 当 x^0。C# 移植时如果只搬了除法逻辑没同步位序约定编码器和译码器就会各说各话。还有一种隐蔽情况从串口收到两字节后rv hi 8 | lo如果原 C 源码是lo 8 | hi同样会导致位置错乱。解决定死一个规则全项目统一。我推荐用“bit i 对应 x^i”也就是最低位是 x^0。编码器返回的 int 直接按这个规则构造校正子循环从 i14 往下扫Chien 搜索里 errMask 也按1 pos累加。写成代码后先跑一遍黄金用例翻转 bit0 能修 bit0翻转 bit2 能修 bit2再往下走。5.3 缩短码当完整码写码长超过周期 15现象项目里用 BCH(12,4) 缩短码也就是从 BCH(15,7,5) 里砍掉高 3 位固定为零的数据位。有人拿着完整 BCH(15,7,5) 的源码直接改参数把码长写成 12结果查表越界或者校正子计算读到不存在的位。原因缩短码不是一种新码它只是把完整 BCH 码的码字“前导零”去掉。BCH(12,4) 的数据位从 7 位减到 4 位校验位仍然 8 位所以码长 12。但域还是 GF(2^4)周期还是 15Chien 搜索仍然要按完整码长 15 做只不过有效数据位置从 bit14 变成了 bit11。把循环改成 12 位会让搜索漏掉后面的错误位置。解决缩短码的编码、校正子计算都按完整码的参数来只是在组帧时把高位的固定零位省略掉。比如编码时 data 只有 4 位仍然左移 8 位得到 12 位码字再送进原有的完整 BCH(15,7,5) 流程。Chien 搜索照常跑 15 个位置但只对低 12 位做翻转。网上很多二维码相关的 BCH(18,6) 就是缩短码直接套完整码源码必踩这个坑。5.4 参数里的“5”不是纠 5 位设计距离和实际纠错数的换算现象团队里新来的同事看到 BCH(15,7,5)以为这个码能纠 5 位错误于是测试时翻 5 位译码器输出了错误数据项目组开始质疑 BCH 算法的正确性。原因BCH 码三元组里的第三个数字是设计距离 d不是纠错位数 t。BCH(15,7,5) 的设计距离是 5错误位置多项式最多解 2 个根所以 t floor((d-1)/2) 2。能纠 5 位的 BCH 码设计距离至少要 11校验位会多得多。解决拿到任何一个 BCH 参数先算 t。这一步还能用来估校验位的合理性BCH(15,7,5) 有 8 位校验理论上最多区分 1 15 C(15,2) 121 种错误图形8 位校验有 256 个状态所以能塞下双错误校正。如果某个参数声称 t3 但校验位只有 8 位直接用码字数量上限一算就知道不可能。6. 给 BCH 代码做一次全搜索验证2 位错误穷举比随机测试有用6.1 单比特黄金用例与双比特穷举BCH(15,7,5) 一共只有 15 个单错误位置和 105 个双错误组合全量穷举只需要几毫秒比随机测一百万个样本更能说明问题。我的做法是先跑单比特用例再跑双比特穷举两个全过才敢把译码器接到协议栈里。int data 0x2D; int code EncodeBch157(data); int singleOk 0; for (int pos 0; pos 15; pos) { int rv code ^ (1 pos); if (DecodeBch157(rv, gf) code) singleOk; } Console.WriteLine($单比特纠正: {singleOk}/15); int doubleOk 0, total 0; for (int a 0; a 15; a) { for (int b a 1; b 15; b) { total; int rv code ^ (1 a) ^ (1 b); if (DecodeBch157(rv, gf) code) doubleOk; } } Console.WriteLine($双比特纠正: {doubleOk}/{total});如果单比特全过、双比特不全过问题几乎一定出在 Chien 搜索的代入方向或者 σ2 公式的符号上。如果单比特都不过优先检查建表打印 exp[15] 是否为 1打印 alpha 序列的前几项是否和手算一致。全搜索验证还有个额外好处它能帮你确认 Decode 函数的返回值语义。我习惯让译码失败返回 -1上层看到 -1 就当作“不可纠正错误”这种做法在真实项目里比抛异常更稳。6.2 超出纠错能力时的行为测试验证译码器不能只测“能修的”还要测“修不了的”。给码字随机翻转 3 位跑一千次确认函数不抛异常、不越界、不死循环。因为 BCH(15,7,5) 的校验位只有 8 位理论上限就是最多纠正 2 位3 位错误被收进校正子后可能被错判成其他位置的 2 位错误并修翻这是正常现象但代码必须明确返回一个失败标记或者修出错误结果由上层 CRC 兜底。我自己的习惯是在这套验证通过之前不把译码器接进 C# 上位机的主流程。有限域表和位序这两个坑单靠肉眼审查代码极难发现只有全搜索能逼出它们。跑完这套用例BCH 对你来说就不是黑匣子了而是协议栈里一个可预测、可测试的纠错零件。希望这篇笔记能帮你少走几步弯路顺利把纠错能力落到自己的工程里。本文还有配套的精品资源点击获取