简介这是BCH(192,116,21)差错控制编码的C实现面向通信与存储领域需要处理随机错误的开发者和学习信道编码的学生提供了一套可阅读、可扩展的编解码参考。BCH码的参数为n192、k116、t21即码字长度192位其中116位为有效信息可纠正21位随机错误编码过程在GF(2^7)伽罗华域上利用生成多项式计算校验位解码则通过伴随式定位错误并完成修正。资源包为rar压缩格式大小仅4KB包含2个C源文件分别实现编码与解码功能结构清晰、易于对照学习。目前已有290人学习下载适合快速入门。代码完整实现了从信息位到最终码字的编码过程以及通过伴随式计算进行错误定位与修正的解码逻辑可纠正21位以内的随机错误可作为信道编码课程设计、通信系统仿真或BCH算法研究的实用参考便于结合教材验证编解码细节。1. 项目背景为什么需要192位BCH编解码做存储控制器或者嵌入式通信开发的同行对BCH这个名字应该都不陌生。NAND Flash的原始误码率随着制程缩进和写擦次数的增加越来越高控制器必须在前端加上纠错引擎BCH码因为纠错能力强、硬件实现简单成了最常被选中的方案之一。这个项目里说的192BCH指的是码字总长度为192 bit的BCH码。这种参数在不少存储和通信场景里很常见——数据按小扇区组织、延迟要求高的时候码长过长会引入额外的编码延迟码长太短又会浪费校验位。192这个数字可以配出多种纠错能力的组合比如BCH(192, 176, 2)是2比特纠错、16位校验BCH(192, 168, 3)是3比特纠错、24位校验具体选哪个看芯片给出的ECC规格。注意192小于GF(2^8)能支持的最大码长255所以它本质上是一个缩短BCH码实现时需要在标准BCH的基础上做缩短处理这一点后面细说。我这边遇到的项目需求是在纯C环境下实现一套可嵌入的BCH编解码模块不依赖第三方库能够对192 bit的数据块完成编码、计算伴随式、定位和纠正错误位。做这个模块的初衷是给一个NAND模拟器做端到端的误码注入测试所以性能要求不能太离谱至少要能跑出有统计意义的数据。如果是刚接触纠错码的同学看完这篇也可以独立把代码写出来因为我拆解得比较细每一步都能对上号。2. 理论部分必须打通的两个基础有限域和生成多项式2.1 GF(2^8)上的乘法为什么不能直接做BCH码的一切运算都在有限域上完成。码长是192 bit所以我们需要一个能覆盖192个位置元素的有限域。取m8时GF(2^8)包含256个元素非零元素的数量是255刚好大于192所以GF(2^8)够用这也是最常见的选择。GF(2^8)里的加法就是异或这个没有疑问。难点在乘法两个域元素相乘结果不能直接当整数乘必须在一个本原多项式下做模约减。可以这样理解域里的每个元素本质上是一个次数小于8的多项式乘法是普通多项式乘法乘完以后如果次数超过7就要用本原多项式去除取余数。本原多项式通常取0x11D也就是x^8 x^4 x^3 x^2 1它保证了域里非零元素能形成完整的循环群。工程实现上逐位循环相乘虽然能跑但效率太低每乘一个元素都要做8次移位和条件异或在编码循环里会被反复调用累计开销很可观。我用的是经典查表方案初始化阶段生成两张表指数表exp和对数表log乘法就变成查表和一次加法。贴一下表生成的代码#include cstdint #include cstring // 生成 GF(2^8) 的指数表和对数表本原多项式 0x11D // exp 表长度 510避免乘法时对 255 取模的多余指令 void gf8_init_tables(uint8_t exp[510], uint8_t log[256]) { uint8_t x 1; for (int i 0; i 255; i) { exp[i] x; log[x] (uint8_t)i; x 1; if (x 0x100) { x ^ 0x1D; // 最高位溢出时模去 0x11D 的低 8 位 } } // 扩展表为两倍长度乘法的指数和直接作为下标 for (int i 255; i 510; i) { exp[i] exp[i - 255]; } } // 查表法乘法a、b 均非 0 inline uint8_t gf8_mul(uint8_t a, uint8_t b, const uint8_t *log, const uint8_t *exp) { if (a 0 || b 0) { return 0; } return exp[log[a] log[b]]; }2.2 生成多项式到底怎么来BCH码的生成多项式g(x)的根是连续2t个本原元的幂次即α^1, α^2, ..., α^{2t}。因为二进制BCH的特殊性成对出现的共轭根会共享同一个最小多项式所以实际算g(x)时不需要把2t个最小多项式都乘一遍只需要取奇数幂次对应的最小多项式求它们的最小公倍式即可。还是用BCH(192, 176, 2)举例。t2所以需要考虑的根是α^1和α^3。先分别求出这两个根的最小多项式m1(x)和m3(x)它们的次数都是8在GF(2^8)下然后做多项式LCM得到16次的生成多项式。校验位的数量就等于g(x)的次数这里就是16位。求最小多项式对很多人来说是第一道坎。最简单的实现是暴力验证从1次多项式开始往上测试找到不可约多项式的候选再把α^i代进去看结果是否为0。更高效的做法是分析分圆陪集比如α^1的共轭类有α^1、α^2、α^4、α^8、α^16、α^32、α^64、α^128这8个元素共享同一个最小多项式m1(x)的系数就是这些根的初等对称多项式。实际编码时生成多项式可以直接预先算好写成常量数组没必要在运行时重新推导这样既降低了启动开销也让代码更清晰。我建议把这一步做成独立的Python脚本离线算好把系数数组直接粘到C代码里。2.3 缩短码的编码实现要点标准BCH码的码长是2^m - 1也就是255。我们的目标码长是192比255短所以需要把标准码缩短具体做法是假设码字的前63位都是信息0编码时跳过这些位只对后面的192位做处理。因为前导零在系统码编码中不会影响校验位的计算所以缩短之后校验逻辑不变但生成多项式的次数也没有变化。在实际编码实现中缩短码带来的直接好处是省掉了前63个0比特的移位处理坏处是位序和字节对齐会更绕一些。192 bit天然是24字节刚好对齐这是个很舒服的尺寸。我的做法是把数据按64位一组组织信息位从MSB开始取编码时按位遍历。#include cstdint #include vector // 192 bit 对应的 64 位组数是 3 组 constexpr int kCodewordBits 192; constexpr int kInfoBits 176; constexpr int kParityBits 16; constexpr uint16_t kGenPoly 0x537; // 以 BCH(192,176,2) 为例实际按你的多项式来 // 编码输入 176 bit 信息输出 192 bit 码字信息位 16 bit 校验位 // 位序约定每组 uint64 先处理高位 bit63依次向低位 void bch192_encode(const uint64_t info[3], const uint8_t *log, const uint8_t *exp, uint64_t codeword[4]) { uint32_t reg 0; const int parity_width 16; // 需要遍历的信息比特数 for (int i 0; i kInfoBits; i) { int byte_idx i / 64; int bit_idx 63 - (i % 64); int info_bit (info[byte_idx] bit_idx) 1; int fb (reg (parity_width - 1)) 1; reg ((reg 1) 0xFFFF); if (fb ^ info_bit) { reg ^ kGenPoly; } } // 组装码字前 3 组是原信息最后一组高 16 位放校验位 memcpy(codeword, info, 3 * sizeof(uint64_t)); codeword[3] ((uint64_t)reg (64 - kParityBits)); }这里最容易出错的两个点我提前说一下。第一反馈位fb不光要和生成多项式异或还要和当前输入比特做异或这是系统码编码的反馈路径要求漏掉就会得到完全错误的校验值。第二生成多项式kGenPoly必须是左对齐表示也就是它的最高1在bit15的位置这样每次移位后异或才能对齐到正确的位置上。3. 解码全流程伴随式、BM算法和Chien搜索3.1 伴随式计算解码的第一公里拿到一个接收向量r(x)之后解码的第一步是计算伴随式。伴随式的定义是r(α^i)i从1到2t。如果接收向量没有错误所有这些值都应该是0只要有任何一个伴随式非零就说明接收向量里有错误。伴随式的计算可以用霍纳法则迭代也可以用查表法。这里有个细节初学者容易忽视码字多项式的系数顺序要和编码时的位序保持一致否则算出来的伴随式看着是错的其实是顺序反了。以BCH(192, 176, 2)为例2t4我们需要计算S1到S4一共4个伴随式每个都是GF(2^8)里的一个元素。// 计算 2t 个伴随式r 是 192 bit 接收向量共 3 组 校验组共 4 组 uint64 void bch192_syndrome(const uint64_t r[4], const uint8_t *log, const uint8_t *exp, uint8_t synd[4]) { // GF(2^8) 本原元 alpha 2二进制表示 00000010 const int t 2; int parity_width 16; for (int s 1; s 2 * t; s) { uint8_t alpha_power 1; // 用于计算 alpha^s 的迭代乘方 // 先计算 alpha^s for (int p 0; p s; p) { alpha_power gf8_mul(alpha_power, 2, log, exp); } // 霍纳法求 r(alpha^s) uint8_t acc 0; // 从最高位 bit191 开始向低位迭代 for (int i 0; i kCodewordBits; i) { int byte_idx i / 64; int bit_idx 63 - (i % 64); int bit (r[byte_idx] bit_idx) 1; acc gf8_mul(acc, alpha_power, log, exp); if (bit) { acc ^ 1; } } synd[s - 1] acc; } }伴随式计算的复杂度是O(n·t)n是码长192t是纠错能力。对2比特纠错来说一次伴随式计算大概要迭代4×192768次域乘法和加法在PC上微秒级别就能跑完。这里用霍纳法每次迭代做一次域乘效率不是最高的但胜在逻辑清楚不容易写错。等项目跑通性能有瓶颈了再考虑用矩阵预计算或者比特跳跳查表的优化。3.2 Berlekamp-Massey算法从伴随式到错误位置多项式伴随式算完接下来的任务是找到错误位置多项式Λ(x)。这个多项式的次数就等于错误个数e它的根的倒数对应着错误所在的位置。Berlekamp-Massey算法BM算法是标准解法它本质上是用一个线性反馈移位寄存器去拟合给定的2t个伴随式序列最小化移位寄存器的长度得到的寄存器特征多项式就是错误位置多项式。BM算法让我来说透。初始状态Λ(x)1辅助多项式B(x)1度数记录器L0迭代变量k从1到2t。每次迭代算一个差量delta如果delta非零就更新Λ(x)和B(x)否则只做移位。别看算法只有十几行但很多写得不对的版本都死在何时更新L这个分支条件上。正确逻辑是当delta非零并且2L ≤ k-1时才更新L为k-L否则L不变。这个条件如果写错短周期错误图案下算法会发散。// Berlekamp-Massey 求解错误位置多项式synd[4] 是伴随式 void bch192_bm(const uint8_t synd[4], const uint8_t *log, const uint8_t *exp, uint8_t lambda[3]) { int t 2; int n 2 * t; // 4 uint8_t C[3] {1, 0, 0}; // 当前估计的 Λ(x) uint8_t B[3] {1, 0, 0}; // 辅助多项式 int L 0; int m 1; uint8_t b 1; for (int k 0; k n; k) { // k 0..3对应 σ_{k1} // 计算差量 d synd[k] Σ C[i] * synd[k-i] uint8_t d synd[k]; for (int i 1; i L; i) { d ^ gf8_mul(C[i], synd[k - i], log, exp); } if (d 0) { m; } else { // T(x) C(x) d * b^{-1} * x^m * B(x) uint8_t coef gf8_mul(d, gf8_inv(b, log, exp), log, exp); uint8_t T[3] {C[0], C[1], C[2]}; for (int j 0; j m 2; j) { T[j m] ^ gf8_mul(coef, B[j], log, exp); } if (2 * L k) { L k 1 - L; for (int j 0; j 3; j) { B[j] C[j]; } b d; m 1; } else { m; } for (int j 0; j 3; j) { C[j] T[j]; } } } lambda[0] C[0]; lambda[1] C[1]; lambda[2] C[2]; }代码里用到了GF(2^8)的求逆这个也是查表实现的在循环群里任意非零元素a的逆是a^(254)用对数表就是exp[(255 - log[a]) % 255]。当然更高效的做法是预置好逆元表256个byte而已。3.3 Chien搜索把错误位置从多项式里挖出来错误位置多项式Λ(x)求出之后理论上它的根的倒数就是错误位置。把这个根逐个试出来就是Chien搜索做的事。它利用的是GF(2^8)循环群的性质对每个位置i计算α^(-i)代入Λ(x)如果结果等于0说明第i位有错误。由于GF(2^8)的元素总共有255个非零值而我们只关心192个码位所以Chien搜索的复杂度是O(n × deg(Λ))。实现时可以把Λ(x)按次数分解每次迭代都只做低次项的累加避免对整个多项式反复求值。以下是逐位置检测的直观版本// Chien 搜索把错误位置记录到 err_pos 数组返回错误个数 int bch192_chien(const uint8_t lambda[3], const uint8_t *log, const uint8_t *exp, int err_pos[4]) { int cnt 0; // 位置 i 从 0 到 191对应的根试算是 alpha^{192 - i - 1} 的倒数 // 简化处理对每个位置计算 lambda(alpha^{-pos}) for (int pos 0; pos kCodewordBits; pos) { // 位置 pos 对应的域元素 x alpha^{-pos} int exp_idx (255 - pos) % 255; uint8_t x exp[exp_idx]; uint8_t x2 gf8_mul(x, x, log, exp); // lambda(x) lambda0 lambda1*x lambda2*x^2 uint8_t val lambda[0]; val ^ gf8_mul(lambda[1], x, log, exp); val ^ gf8_mul(lambda[2], x2, log, exp); if (val 0) { err_pos[cnt] pos; if (cnt 4) { return -1; // 超出纠错能力直接放弃 } } } return cnt; }注意一个顺序问题码字第0位对应的是码字多项式里的哪一个幂次这个全看你编码时的位序约定。如果编码时第0位是最低位那Chien搜索里的位置对应关系也要保持一致。我在写代码时统一约定第0位是码字第0比特也就是最先进入信道的那一位后续调试时只需要按照同一个约定来定位错误位即可。4. 完整解码流程与C工程整合4.1 解码主流程从伴随式到纠错一气呵成把各个模块串起来之后完整解码函数长这样// 完整解码入口输入接收向量 r输出纠错后的码字 decoded // 返回值纠错成功返回 0出现纠不动的错误返回 -1 int bch192_decode(const uint64_t r[4], const uint8_t *log, const uint8_t *exp, uint64_t decoded[4]) { uint8_t synd[4]; bch192_syndrome(r, log, exp, synd); bool all_zero true; for (int i 0; i 4; i) { if (synd[i] ! 0) { all_zero false; break; } } if (all_zero) { // 无错误直接拷贝 memcpy(decoded, r, 4 * sizeof(uint64_t)); return 0; } uint8_t lambda[3]; bch192_bm(synd, log, exp, lambda); int err_pos[4] {0}; int err_cnt bch192_chien(lambda, log, exp, err_pos); if (err_cnt 0 || err_cnt 2) { // 错误数量超出纠错能力或算法失效 return -1; } // 纠错 memcpy(decoded, r, 4 * sizeof(uint64_t)); for (int i 0; i err_cnt; i) { int pos err_pos[i]; if (pos 0 pos kCodewordBits) { decoded[pos / 64] ^ (1ULL (63 - (pos % 64))); } } return 0; }这个流程的顺序性很强伴随式全零说明没错误直接返回这一步能省掉绝大部分无错情况下的解码延迟。BM算法解不出合法多项式或者Chien搜索找到的错误数量超出纠错能力都要返回解码失败让上层协议来决定是重读还是重传。在工程整合阶段我给每个模块写了一个简单的单元测试函数构造一个已知码字翻转随机位置的特定位然后跑解码对比纠错后的码字和原始码字是否一致。这个测试我建议你也写一个而且是边写边测不要等所有模块都写完再联调不然出错之后定位问题的范围太大了。4.2 内存布局与位序约定BCH解码这种位级操作最难受的就是位序约定一旦约定错了全套逻辑都是反着的但伴随式又不会报错只会在某些特定错误图案下翻车排查起来非常隐蔽。我在这个项目里的约定如下供你参考192 bit码字按bit0到bit191的顺序编址bit0先进入编码器。uint64数组中bit0位于data[0]的最高位即第63位。校验位位于第3组的最高16位即data[3]的bit48到bit63。Chien搜索返回的位置也是bit0到bit191的索引纠正时直接按这个索引翻转。按这个约定整个编码和解码链路的逻辑是对齐的。我一开始没有特别在意这个约定导致编码器输出的码字在译码器里总是解出错误位置后来把所有模块的输入输出从位0到bit191打印出来比对才意识到是位序反了。这类问题靠肉眼调试很难发现最好的办法是对比法先用一个小矩阵比如16 bit码字手算一遍编码结果然后用代码跑一遍逐位对比。4.3 代码组织的模块划分工程上我习惯把BCH模块拆成三个文件gf8.h / gf8.cpp有限域表生成、乘法、求逆、打印等基础操作bch192.h / bch192.cpp编码、伴随式、BM算法、Chien搜索、解码主流程test_bch192.cpp测试用例包含编码纠错验证、遍历小规模错误图案的穷举测试这样的划分方便以后扩展到其他码长。比如要支持BCH(192, 160, 4)只需要修改kParityBits和生成多项式相关常量再调整BM算法的数组长度其他逻辑基本可以复用。在main函数里我加了一段穷举测试逻辑遍历所有1比特错误和2比特错误组合对每个组合都做一次编解码。192 bit里选2个位置的组合数是18336种加上192个单比特错误总共一万八千多次编解码在debug模式下也只要几秒跑完就能对模块正确性有很高的信心。这个测试强烈建议保留后续改代码的时候它就是你最后的防线。5. 常见问题与排查技巧实录5.1 坑一生成多项式的对齐方式第一次跑通编码的时候我发现输出的校验位和手算结果全对不上排查了半天发现是生成多项式没有左对齐。标准教材里生成多项式通常写成x^16 x^15 ... 的低位形式比如0x8533之类的样子但LFSR编码实现里寄存器左移反馈路径需要的是左对齐表示——也就是生成多项式的最高位在最高bit位上。解决办法有两个要么把生成多项式的二进制表示按左对齐提前处理要么在编码循环里把反馈路径反着接。前一种更直观我推荐用前一种。5.2 坑二GF(2^8)乘法里0的处理这个问题特别隐蔽。用查表法做乘法时如果某个操作数是0log表中根本没有对应项直接查表会索引到垃圾值。我一开始也严格按教材写乘法函数只处理了非零情况后来某一类错误图案下伴随式结果偏掉了。正确的写法就是第2节代码里的那个分支操作数为0时直接返回0。在硬件实现里这个分支可以合并到布尔逻辑里但在软件里一定要显式判断尤其是伴随式计算中接收比特为0时需要跳过异或操作如果这时仍然调用域乘就要确保乘法函数能正确处理0。5.3 坑三BM算法的L更新条件有了正确的算法流程之后BM算法看似不可能写错但2L ≤ k这个条件用的是当前迭代的k不是循环变量加1之后的值不少代码在这个细节上翻车。更难受的是这个错误不会立刻暴露因为很多错误图案下计算过程碰巧能解出正确结果只有当遇到特定组合的错误位置时才会解出错误的多项式然后Chien搜不到错误位置或者搜出超过t个位置。如果你发现解码在个别错误图案下失败而其他图案全部正常优先检查BM算法里的L更新条件。5.4 坑四校验位的bit位偏移192 bit码字用4个uint64存储时校验位在第4组的bit48到bit63而不是bit0到bit15。我因为图省事把校验位放在了最低16位结果编码和解码虽然各自内部是一致的但和外部系统对接时怎么都对不上对方认为校验位在码字末尾而我放在了码字中间。这个点位序约定一定要在头文件注释里写清楚不然同事接手之后大概率会踩同一个坑。5.5 性能实测与一点优化思路在普通x86 CPU上不开任何编译器优化时一次192比特解码大约在数十微秒级开-O2之后能降到几微秒。如果未来需要更高的吞吐可以考虑这几条优化路径一是把GF(2^8)查表乘法进一步展开成常数表索引比如预先算出每一个α^s的乘法表二是伴随式计算改成按字节并行处理利用SIMD指令把多个位置的求值同时算出来三是对BM算法做并行化因为它的迭代步之间有依赖但每次迭代内部的域乘和异或可以做指令级并行。我实测下来对于2比特纠错这种低阶场景瓶颈其实不在BM算法而在伴随式计算里大量的查表和异或操作。把GF(2^8)乘法表做成展开形式也就是预计算256个元素分别乘以256个值的完整乘法矩阵每次乘法变成一次内存读取虽然占64KB内存但带来的性能提升非常明显。当然在嵌入式MCU上内存紧张这种方法就得掂量一下用原来的256字节对数表就够了。6. 结语这套代码还能怎么扩展做完192 bit的版本后如果你手头的项目需要支持更长的码长或者更强的纠错能力扩展路径其实很清晰。核心的GF(2^8)表生成、BM算法和Chien搜索逻辑都不用动需要改的就是生成多项式的选择、校验位长度相关的常量、以及存储码字的uint64数组个数。如果换成GF(2^16)的码元比如做码长超过4095的BCH码那么域表会变成65536项乘法表变成128MB级别查表方案就得换掉了一般是直接用对数表加一次加法再加一次查表内存占用是可控的。这种场景通常出现在高速通信和固态硬盘主控的LDPC配合方案之前的老一代ECC设计里。我个人在实际调试中的体会是BCH编解码实现难度不在算法本身而在位序和约定。无论是编码、伴随式、BM还是Chien搜索只要按照同一个故事线把位序理清楚每一步的代码都不难写。建议你拿到这套代码后先跑一遍我提到的单比特和双比特穷举测试再做自己的业务集成这样心里会很有底气。如果后面遇到某些随机图案解不出来优先怀疑位序约定再看生成多项式对齐这两个问题解决了解码链路基本就稳了。本文还有配套的精品资源点击获取