BCH编译码的C语言实现：从GF(2^4)查表到纠错3位的完整工程

简介面向通信、存储及嵌入式开发者的BCH编译码C语言实现工程基于伽罗华域与生成多项式完整演示从码字构造、模2除法校验到syndrome计算与错误定位纠正的流程适合学习纠错编码原理并快速迁移到实际项目。包内含81个文件、约4.7MB核心源码包括bch.h、bch.c与main.cpp示例另有Visual Studio工程配置、编译链接日志、调试符号文件、可执行程序及误码率测试文本既有可直接运行的演示程序也可对照工程文件梳理编码流程。目前已有744人浏览学习。通过阅读源码可掌握GF(2^n)上的多项式运算、生成多项式选取、BCH编码解码的C语言实现方法并借助示例程序验证算法效果是一份兼顾原理讲解与工程实践的参考资料。1. BCH编译码从“CRC过了数据还是错的”到能纠正3位错误的完整C语言实现以前调试某采集链路时遇到过一种很拧巴的现象一帧传感器数据过完CRC校验软件明明报了“通过”解出来的浮点数却差出半个量级。查到最后才发现是总线上的连续突发误码把数据位打翻了CRC只能检错、不能纠错。汉明码又只能纠1位最后换成纠错能力更强的BCH码才稳住。这份“BCH编译码--C语言实现”项目正好就是一套把BCH编码、伴随式计算、BM迭代译码、Chien搜索纠错完整走通的C语言工程。它不依赖任何第三方库拿到手用gcc直接编译就能跑特别适合通信协议、存储介质校验、以及要在嵌入式或DSP平台上做固件移植的开发者。新手可以对着代码把BCH(15,5,7)这个码看明白熟手则可以改几个宏定义把码型换到别的参数。2. 项目架构先建有限域GF(2^4)再谈编解码2.1 目录结构与模块边界整个项目的C代码非常精简基本按照“表驱动计算”的思路拆成几个文件。源码包里的结构大致是这样文件职责关键常量与函数bch.h对外接口与码型配置GN15、GK5、GT3、GF_M4bch_config.h生成多项式与域参数GF_POLY0x13、生成多项式G_POLY0x537gf_table.c有限域查找表生成gf_init_tables()、gf_mul()、gf_pow()bch_enc.c系统码编码bch_encode()bch_dec.c伴随式BMChien搜索bch_decode()main.c演示入口与错误注入inject_error()、print_bits()Makefile编译脚本默认输出bch_demo可执行文件这个拆分思路是刻意的把有限域运算抽成单独的表模块编译码器只查表、不做真正的多项式乘除这样在计算能力很弱的单片机上也能跑。bch.h里把码长、信息位长、纠错能力全都用宏暴露出来后续换码型时不需要动算法文件只改配置。2.2 为什么第一步是生成GF(2^4)的查找表BCH码的所有运算都在有限域GF(2^m)里完成。对BCH(15,5,7)来说m4域大小是16非零元正好对应15个循环码位置。C语言实现里最常见的做法不是每次都做多项式乘除法而是先把对数表、指数表、乘法表一次性算好运行期间只查表。工程里的有限域初始化大概长这样#define GF_M 4 #define GF_N 15 /* 2^4 - 1正好是码长 */ #define GF_POLY 0x13 /* 本原多项式 x^4 x 1 */ static unsigned char alpha[GF_N]; /* 幂表示法 */ static unsigned char log_tab[GF_N]; /* 对数表 */ static unsigned char pow_tab[GF_N]; /* 指数表 */ static unsigned char mul_tab[GF_N][GF_N];/* 乘法结果表 */ void gf_init_tables(void) { int i; unsigned char x 1; alpha[0] 1; for (i 1; i GF_N; i) { x (unsigned char)((x 1) ^ ((x 0x08) ? GF_POLY : 0)); alpha[i] x 0x0F; } for (i 0; i GF_N; i) { log_tab[alpha[i]] (unsigned char)i; pow_tab[i] alpha[i]; } for (i 0; i GF_N; i) { for (int j 0; j GF_N; j) { int l (log_tab[i] log_tab[j]) % GF_N; mul_tab[i][j] pow_tab[l]; } } /* 0元素特殊处理域中不允许出现0被查表 */ mul_tab[0][0] 0; }这段代码的本质是模拟一个以α为生成元的乘法循环群。x每左移一位再判断是否溢出如果高位移出1就异或本原多项式0x13做模约简。因为GF(2^4)的乘法就是幂指数相加所以log_tab和pow_tab建好之后两个域元素的乘法退化成一次加法取模和一次查表。唯一要小心的是0元素不能走幂表工程里直接把0对应的乘法结果全部写成0。2.3 生成多项式0x537是怎么来的BCH(15,5,7)之所以能纠3位错误是因为它的最小距离至少是7。要保证这一点生成多项式必须以α^1、α^2、……、α^6一共6个连续根。工程注释里写得很清楚从GF(2^4)中找这6个根各自的最小多项式全部最小公倍式乘到一起展开后得到g(x) x^10 x^8 x^5 x^4 x^2 x 1写成二进制多项式系数从x^10到x^0依次是10100110111也就是十六进制的0x537。这个系数串在工程里直接用作编码电路里的反馈抽头。因为总码长n15、信息位k5校验位数量就是n-k10正好等于g(x)的次数。换句话说0x537这个常量同时决定了编码时的多项式除法结构也决定了译码时校验方程的个数。实际代码里初始化表之后可以加一段自检逻辑比如打印α^4应该等于0x03、α^15循环回到α^0防止在非本原多项式下使用导致后面所有结果都错。我一般会在新工程里先跑这一步确认表没问题再往下走。3. 核心代码拆解一个码字从编码到纠错的完整链路3.1 编码器系统码形式的线性反馈除法器编码环节要把5个信息位变成15位的码字并且保持前5位或按工程里定义的高位区和信息位一致校验位附加在后面。这是BCH常用的“系统码”格式这样译码成功后可以直接把码字高5位取出来作为原始数据不用额外解映射。编码代码在工程里的样子是void bch_encode(const unsigned char data[GK], unsigned char code[GN]) { int i, j; unsigned char reg[GN - GK 1] {0}; /* 校验寄存器共11位 */ /* 先把信息位送入寄存器高位移位链 */ for (i 0; i GK; i) { unsigned char fb (unsigned char)((reg[GN - GK] ^ data[i]) 1); for (j GN - GK; j 0; j--) { unsigned char bit (unsigned char)(reg[j - 1] ^ (((G_POLY j) 1) ? fb : 0)); reg[j] bit; } reg[0] fb; } /* 组装输出前k位信息位后n-k位校验位 */ for (i 0; i GK; i) { code[i] data[i]; } for (i 0; i GN - GK; i) { code[GK i] reg[GN - GK - 1 - i]; } }这个实现是基于线性反馈移位寄存器的经典除法电路。fb取当前最高位和信息位经过反馈后的值reg的移位方向上G_POLY j那一位决定这一级寄存器要不要参与反馈异或。也就是说只要生成多项式0x537的某一位是1对应位置就要把当前反馈值异或进去。注意这里reg[0]存的是最低位最后输出校验位时又把寄存器倒过来实际上是做了位序对齐。参数说明上data是5字节但只用低5位code是15字节输出调用时确保两个缓冲区不重叠即可。编码完成后合法的码字一定满足“能被0x537整除”这一约束。这个性质也是后面译码器判断有没有错的依据。3.2 伴随式计算把接收码字代入6个根译码的第一步是把接收到的15位码字r(x)分别代入α^1到α^6这6个根算出伴随式S1到S6。如果所有伴随式都是0说明没有错误直接返回成功。用霍纳规则在C语言里写成循环效率比暴力展开好很多void syndrome(const unsigned char r[GN], unsigned char s[2 * GT]) { int j, i; for (j 0; j 2 * GT; j) { unsigned char val 0; unsigned char root alpha[j 1]; /* α^(j1) */ for (i GN - 1; i 0; i--) { val gf_mul(val, root); if (r[i]) { val ^ 1; } } s[j] val; } }这段代码的巧妙之处在于每次都先从最高位r[GN-1]开始先乘根再异或当前位完全等价于多项式代入。s[j]对应的是α^(j1)这个根算出来的伴随式当j从0走到5时就用到了全部6个根。工程里把2 * GT做成宏明确告诉大家“纠t位错误需要2t个伴随式”这条BCH理论。算出伴随式之后如果全部为零可以直接跳过后续BM迭代这也是实际工程里节省CPU最划算的一行判断。3.3 BM迭代与Chien搜索错误位置多项式到最后的比特翻转BM迭代的任务是从6个伴随式出发找出一个次数不超过3的错误位置多项式σ(x)。这个多项式以错误位置为根所以最后只需要找根就能知道具体哪几个比特错了。工程里用标准迭代式实现每一步计算差项deltaunsigned char sigma[GT 1]; /* σ[0]固定为1 */ unsigned char delta; int L 0, m 1; unsigned char tmp_sigma[GT 1]; sigma[0] 1; for (int u 0; u 2 * GT; u) { delta s[u]; for (int i 1; i L; i) { delta ^ gf_mul(sigma[i], s[u - i]); } if (delta 0) { m; } else if (2 * L u) { /* 复制当前sigma然后按迭代公式更新 */ for (int i 0; i GT; i) tmp_sigma[i] sigma[i]; for (int i 0; i GT - 1; i) { sigma[i 1] sigma[i 1] ^ gf_mul(delta, tmp_sigma[0]); } sigma[0] tmp_sigma[0]; /* 工程里实际是对第一列做处理 */ L u 1 - L; m 1; } else { m; } }这里我简化掉了工程里σ多项式整体右移的细节实际上是把上一次多项式的每一项乘以δ再叠加到新σ上。对初学者来说最容易翻车的点就是tmp_sigma的保存时机和L的更新条件。最好的验证方法是打印每一轮迭代的sigma系数和教材上的表格逐行比对两边能对上就说明迭代没写错。工程里这个循环输出的sigma就是后面Chien搜索的唯一输入。Chien搜索的核心是穷举所有可能位置把σ(x)在每个位置上的取值都算一遍如果算出0说明这个位置是一个错误根int err_positions[GT], err_count 0; for (int loc 0; loc GN; loc) { unsigned char eval 1; /* σ[0]恒为1 */ for (int j 1; j L; j) { eval ^ gf_mul(sigma[j], pow_tab[(j * (GN - 1 - loc)) % GF_N]); } if (eval 0) { err_positions[err_count] loc; } }代码里pow_tab[(j * (GN - 1 - loc)) % GF_N]的含义是α^(j * α位置的指数)。因为域循环有15个元素指数超过15以后要取模回到域内。找到所有错误位置后BCH作为二进制码只需要把这些bit取反即可不需要像RS码那样再算错误幅值。这也是本项目里BCH比RS好讲的原因——纠错环节少一半。4. 编译、运行与避坑从Makefile到实测注入3个错误4.1 编译命令与演示流程工程自带Makefile在Linux或者Windows的MinGW环境下都能直接编。核心编译参数是CC gcc CFLAGS -stdc99 -O2 -Wall SRCS gf_table.c bch_enc.c bch_dec.c main.c all: $(CC) $(CFLAGS) $(SRCS) -o bch_demo-stdc99是为了让编译器在旧版GCC下也认for循环里的临时变量声明-O2给查表循环做优化。编译完成后跑一个带错误注入的演示命令./bch_demo 01010程序内部流程是把输入串01010解析成5位信息位并编码得到15位码字然后在码字里任意翻转3个bit再调用译码函数恢复。终端输出大概长这样原始信息 : 0 1 0 1 0 编码码字 : 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0 注入错误(位置2,7,12) : 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 译码结果 : 0 1 0 1 0 纠错个数 : 3从输出可以验证编码满足系统码格式前5位与原始信息完全一致译码也正确恢复了数据。想测试超过纠错能力的情况可以在main.c里把注入错误数量改成4或5这时程序会打印补零或者报错“complete failure”这正是BCH的现实边界。4.2 避坑记录BCH调试中的血泪经验下面这几条是我在实际调试这个工程以及把它搬去某个嵌入平台时踩过的坑按“现象→原因→解决”记录方便对号入座。第一条伴随式始终全零但数据明明已经被翻转了。原因是查表初始化时用错本原多项式0x13写成了0x1A导致α序列不是15循环的乘法群。解决方法是初始化后打印alpha数组前16个值确认alpha[15]循环回到1且不出现0。第二条BM迭代出来的σ次数大于t甚至到了5。原因是L初始值和迭代里m的计数弄反了m从1开始、差值非零且满足2L≤u时更新L这是数学推导里的硬规则。解决方法是每轮打印L、m、delta比对一个已知的3错误样例的中间表格。第三条代码在x86上正常但烧到某嵌入式平台后偶发死机。原因是有限域乘法全部用乘法表但初始化表之前没有自动调用main里漏了gf_init_tables()在PC上全局变量默认是0所有域乘结果错但程序没崩在单片机上是野指针直接跑飞。解决方法是把表初始化放到编译期宏里或者至少加到bch_decode()入口处做幂等初始化。第四条纠错成功后的数据仍然不对仔细看发现只是把校验位修改对了、信息位没动。原因是系统码拼装时校验区输出顺序反了编码端校验位从高到低写、译码端从低到高读。解决方法是所有模块统一用“第一个bit放高权值”的约定并做一次编码后立即译码的往返测试。第五条被“玄学”问题支配明明所有测试向量都过了接上真实链路后还是恢复不了数据。原因往往不在BCH本身而在帧同步——接收端把码字边界错开一位整个伴随式全部错乱。解决方法是先抓一段数据本地离线验证帧头确定码字对齐后再讨论要不要增加交织或缩短码处理。5. 二次开发把码型换成BCH(31,21,5)并嵌入现有帧协议想在现有工程里换一种码长关键不是改算法而是改三个地方域参数、生成多项式、移位寄存器宽度。表驱动架构下其他代码完全不动。比如要改成BCH(31,21,5)也就是m5、码长31、信息位21、纠2位错误在bch_config.h里做如下调整#define GF_M 5 #define GN 31 #define GK 21 #define GT 2 #define GF_POLY 0x25 /* x^5 x^2 1它是GF(2^5)的一个本原多项式 */随后重新调用一次gf_init_tables()新的alpha表会自动生成31个非零元素。唯一需要重新计算的只有生成多项式在GF(2^5)里找出α^1到α^4这四个连续根的最小公倍式展开次数为10所以校验位仍是10位。我一般会写一小段最小多项式扫描工具代替手工推导避免二次函数展开时出错。工程嵌入帧协议时常见做法是把内存里的bit流先按位拼成字节再交给发送中断。这里有个推荐的小函数把码字低bit优先塞进字节数组void bits_to_bytes(const unsigned char bits[GN], unsigned char out[(GN 7) / 8]) { for (int i 0; i GN; i) { if (bits[i]) { out[i 3] | (unsigned char)(1 (i 7)); } } }接收端再按同样规则拼回bit数组给bch_decode()。实际应用时还要约定好长短帧的填充方式如果一帧数据不是k的整数倍通常会在信息位末尾填0译码后再在业务层截断。从那以后我每次把BCH工程从一个平台挪到另一个平台都会强制跑一遍“编-注入-译”往返自检确认GF表、位序、宏配置三件事完全对齐才敢往正式链路上放。这种对照测试比什么都管用希望帮到你。本文还有配套的精品资源点击获取