简介面向通信、存储与数据传输领域的学习者这套BCH编译码C语言实现给出了一份聚焦纠错编码落地的参考代码适合具备C语言基础、希望理解有限域运算与线性分组码实现细节的开发者。压缩包仅含1个c源文件整体约5KB代码集中覆盖BCH编码与解码主流程便于按模块研读伽罗华域加法乘法、生成多项式构造、信息位与校验位组合、伴随式计算以及BM迭代译码等要点。已有1426人学习下载在课程设计、算法复现和工程入门中具备一定参考意义。读者可据此梳理从信息位到码字的构造路径理解错误定位与错误值求解的基本框架并在此基础上补充无错、单错、多错等测试用例调试边界条件尝试用位操作优化有限域运算从而形成可运行、可扩展的编译码实验版本。1. BCH 码在 C 里落地九成实现死在有限域建表这一步搜bch c语言的人目标通常很具体手上没有现成的纠错编码库又要在固件里塞一段能纠 1~3 位随机错的代码。BCH 码正好踩在这个位置上——码长 2^m−1纠错能力 t 可配生成多项式有闭式推导译码只用到有限域运算加一个 Berlekamp-Massey 迭代。但我翻过不少「能编译、跑起来全错」的版本问题几乎都不在 BM 算法本身而在最开始那一步GF(2^m) 的指数表和对数表建错了或者建对了但位序约定和译码端对不上。后面所有伴随式、错误位置、翻转操作全部跟着错而且错得很隐蔽测试用例稍微短一点根本看不出来。这一篇按可复现的顺序拆一遍有限域表怎么建、生成多项式怎么自动算、编码器两种写法怎么选、译码三段式怎么串、以及最容易翻车的几个点在哪。2. 有限域与生成多项式先把表算对再谈算法2.1 GF(2^m) 的指数表、对数表和本原多项式BCH 码的运算是定义在 GF(2^m) 上的。这个域有 2^m 个元素去掉零元后剩下的 2^m−1 个元素构成一个循环群生成元记作 α。所谓「建表」就是把每个元素 α^i 的 m 位二进制值存进gf_exp[i]把反查关系存进gf_log[]。有了这两张表域乘法就退化成「查两次对数、做一次加法、再查一次指数」加法直接异或除法把指数相减。表很小m8 也才 512 字节放 MCU 的 RAM 里毫无压力。代价是必须先选定一个本原多项式。它是 GF(2) 上次数为 m 的不可约多项式作用是定义 α^m 如何约简回低次。m4 取 x^4x1完整位表示 0x13m5 取 x^5x^21即 0x25m6 取 x^6x10x43m7 取 x^7x^310x89。这几个是工程上用滥了的取值对应的表在多数教材附录里都能查到自检很方便。/* bch_gf.c —— GF(2^m) 指数/对数表参数由 bch_cfg.h 给出 */ #include stdint.h #include string.h #include bch_cfg.h uint8_t gf_exp[2 * BCH_N]; /* 故意建两倍长乘法里省一次取模 */ uint8_t gf_log[BCH_N 1]; /* prim_poly 传完整位表示含 x^m 项例如 m4 传 0x13 */ void gf_init(uint16_t prim_poly) { int x 1; memset(gf_exp, 0, sizeof(gf_exp)); memset(gf_log, 0, sizeof(gf_log)); for (int i 0; i BCH_N; i) { gf_exp[i] (uint8_t)x; gf_log[x] (uint8_t)i; /* 本原元保证 1..2^m-1 每个值恰好出现一次 */ x 1; if (x (1 BCH_M)) x ^ prim_poly; /* 最高位溢出时按本原多项式约简 */ } /* 把前半段复制到后半段gf_exp 的索引就能直接到 2N-2 */ for (int i BCH_N; i 2 * BCH_N; i) gf_exp[i] gf_exp[i - BCH_N]; gf_log[0] 0; /* 形式上的占位调用方必须先判零 */ } /* 域乘a 或 b 为 0 直接返回 0绝不能拿去查 log 表 */ static inline uint8_t gf_mul(uint8_t a, uint8_t b) { if (a 0 || b 0) return 0; return gf_exp[gf_log[a] gf_log[b]]; } /* 域除除数为 0 属于编码错误这里不做运行期判断 */ static inline uint8_t gf_div(uint8_t a, uint8_t b) { if (a 0) return 0; return gf_exp[gf_log[a] BCH_N - gf_log[b]]; }这段代码有三个参数要盯住。BCH_M决定表长和元素位宽改 m 就得同步改本原多项式两者必须配套比如 m4 配 0x13 才自洽配 0x19对应 x^4x^31虽然也是不可约的但不一定能生成满周期的循环群表会提前出现重复值。BCH_N固定为(1BCH_M)-1写死是为了让编译器把% BCH_N优化成位运算。prim_poly必须含 x^m 项如果只传低 m 位约简那一步会少清最高位x 会一路涨到溢出。判断建表成功的标准很简单跑完之后gf_exp[0]到gf_exp[BCH_N-1]必须两两不同且都不为 0。常见做法是加一段只在调试版本编译的断言循环把 1..BCH_N-1 每个值在gf_log里回查一遍发现重复立刻停。我吃过一次亏某次把 prim_poly 写成低 4 位表只建到第 5 个元素就开始重复编码器输出看着挺正常译码端伴随式永远是零查了整整一个下午。注意gf_log[0]在数学上没有定义。把 gf_mul 写成内联函数并显式判零比事后补 if 靠谱得多编译器通常也不会为这个分支付出代价。2.2 用共轭根系自动推导生成多项式 g(x)生成多项式是整个编译码器的心脏。它的定义是 g(x) LCM(m₁(x), m₃(x), …, m_{2t−1}(x))其中 m_i(x) 是 α^i 在 GF(2) 上的最小多项式。注意下标只取奇数原因是二进制 BCH 码里 α^{2i} 的最小多项式和 α^i 完全一样——共轭关系是 α^i、α^{2i}、α^{4i}…指数翻倍在同一个共轭类里打转所以偶数下标全部被奇数下标覆盖重复乘进去只会把 g(x) 的次数抬高码率白白损失。最小多项式怎么算把 α^i 的整个共轭类找出来然后连乘 (x − α^j)。共轭类的大小一定整除 m乘出来的系数会全部落回 {0,1}这也是一个很好的中间校验点如果最后系数里出现了非 0 非 1 的值说明共轭类没算完整。/* 计算 alpha^e 的最小多项式系数按升幂写入 coef[0..deg]返回次数 */ static int build_minpoly(int e, uint8_t *coef) { uint8_t tmp[BCH_M 1]; int deg 0; int cur e; coef[0] 1; /* p(x) 1 */ do { for (int i 0; i deg 1; i) tmp[i] 0; /* p(x) * (x alpha^cur)特征 2 下加减等价 */ for (int i 0; i deg; i) { tmp[i 1] ^ coef[i]; /* x 项 */ tmp[i] ^ gf_mul(coef[i], gf_exp[cur]); /* 常数项 */ } deg; for (int i 0; i deg; i) coef[i] tmp[i]; cur (cur * 2) % BCH_N; /* 共轭指数翻倍 */ } while (cur ! e); /* 回到起点说明共轭类闭包完成 */ return deg; } /* 生成 g(x)按降幂写入 g[0..BCH_NK]g[0] 恒为 1 */ void build_generator(uint8_t *g) { uint8_t mp[BCH_M 1], mpd[BCH_M 1], tmp[64]; uint8_t used[BCH_N] {0}; int deg_g 0; g[0] 1; for (int i 1; i 2 * BCH_T; i 2) { if (used[i]) continue; /* 该共轭类已并入 g */ for (int j i; !used[j]; j (j * 2) % BCH_N) used[j] 1; int d build_minpoly(i, mp); for (int a 0; a d; a) mpd[a] mp[d - a]; /* 翻成降幂 */ for (int a 0; a deg_g d; a) tmp[a] 0; for (int a 0; a deg_g; a) for (int b 0; b d; b) tmp[a b] ^ (uint8_t)(g[a] mpd[b]); /* 系数已退化为 0/1用与代替域乘 */ deg_g d; for (int a 0; a deg_g; a) g[a] tmp[a]; } }两个参数说明。BCH_T是纠错位数代码里i 2*BCH_T决定了要并入多少个共轭类t2 时并入 m₁ 和 m₃g 的次数为 8t3 时并入 m₁、m₃、m₅次数为 15−510 往上。跑完之后必须断言deg_g BCH_N - BCH_K这个等式不成立说明 t 和 k 没配好或者共轭标记的循环写错了。第二个要注意的是build_minpoly里那层 do-while。当 e 与 BCH_N 不互素时共轭类会更短。比如 n15、e5共轭类是 {5,10}只有 2 个元素最后乘出来的最小多项式次数是 2 而不是 4完全正常。循环条件写成cur ! e而不是固定跑 m 次就是为了兼容这种情况。拿 m4、t2、本原多项式 0x13 跑一遍g 的降幂系数应当是 1,1,1,0,1,0,0,0,1打包成 9 位就是 0x1D1也就是 x⁸x⁷x⁶x⁴1。这是 BCH(15,7,2) 里流传最广的一组值如果算出来不是它先回去查本原多项式别急着往下写译码器。2.3 参数表n、k、t 互相咬合的地方BCH 码的 n 由 m 唯一确定但 k 不是——t 定下来之后g(x) 的次数 n−k 是算出来的k 再反推得到。很多人在这里翻车先拍脑袋定 k16再去找能纠 2 位的 m结果发现凑不上。下面这张表给的是常用配置nk是校验位数务必和deg_g对得上。mntnkk本原多项式说明41514110x13汉明码特例只纠 1 位4152870x13经典短码自检最方便531210210x25通信里常见开销约 32%531315160x25k 是 2 的幂做块处理顺手663212510x43码率约 0.81663318450x43码率约 0.71NAND 场景常用71273211060x89长码表查询开销开始明显表里有个隐含约束nk ≤ m·t 是 BCH 界实际值通常贴着上界偶尔小于。选型时的顺序我一般是反着走的——先看帧长和能容忍的冗余定 n 和 k 的比值再算 n−k然后用这张表去查 m 和 t。如果 n−k 落在两档中间宁可往上取一档 t也别自己造一个不满足界的组合那个生成多项式根本不存在。提示n31 以上时gf_exp的索引上界会到 2N−2124uint8_t存得下但如果你打算扩到 m9 以上记得把表元素类型换成uint16_t。3. 编码器系统码长除法与移位寄存器的取舍3.1 系统码结构位序约定必须一次定死编码侧产出的码字分两段前 k 位原样搬信息位后 nk 位是校验位。数学上写成 c(x) x^nk·m(x) r(x)r(x) 是 x^nk·m(x) 除以 g(x) 的余式次数严格小于 nk。系统码的好处是信息位不用译码就能直接读这对逐层处理的数据块特别友好也是绝大多数实现选它的原因。真正容易出事的是位序。我统一约定cw[0]是 x^{n−1} 的系数cw[n−1]是 x⁰ 的系数发送时从cw[0]开始。这条约定必须贯穿编码、信道模拟、译码、错误位置换算四个环节任何一处反了整套逻辑立刻失效。血泪经验是先写一个bch_dump()把码字按 x 的幂次打印出来对着手算结果核一遍再往下写别的。为什么这件事这么要紧因为伴随式计算里 r(α^j) Σ r_i·α^{j(n−1−i)}指数里的 (n−1−i) 就是位序的体现。如果编码端把cw[0]当成 x⁰ 用译码端却按 x^{n−1} 算两个多项式根本不是同一个东西伴随式必然全错而且错得毫无规律看起来就像算法本身有 bug。另一个坑是「信息位在高位」这个说法本身有歧义。有的资料指的是发送时先进去的那一位有的指的是多项式的最高次。写代码时不要用这种描述直接写cw[0]对应 x^{n−1}落到注释里比什么解释都清楚。3.2 一次长除法把余式算干净最直白的实现是多项式长除法。把信息位摆到work[0..k−1]work[k..n−1]先清零然后从高次往低次扫每逢当前位为 1 就把 g(x) 对齐异或过去。循环结束时work[k..n−1]恰好就是余式。/* g 为降幂系数g[0]1g[BCH_NK] 为常数项 */ void bch_encode(const uint8_t *msg, uint8_t *cw) { uint8_t work[BCH_N] {0}; for (int i 0; i BCH_K; i) work[i] (uint8_t)(msg[i] 1); /* 信息位占据高次端 */ for (int i 0; i BCH_K; i) { if (!work[i]) continue; /* 当前位为 0跳过一整轮异或 */ for (int j 0; j BCH_NK; j) work[i j] ^ (uint8_t)(g[j] 1); } for (int i 0; i BCH_K; i) cw[i] work[i]; /* 信息位原样保留 */ for (int i 0; i BCH_NK; i) cw[BCH_K i] work[BCH_K i]; /* 余式 */ }这段的复杂度是 O(k·nk)BCH(15,7,2) 只要 56 次异或BCH(63,45,3) 也才 810 次在 100 MHz 的 MCU 上一帧不到 10 微秒。所以除非帧率特别高长除法版本完全够用可读性也最好。参数上只有两个地方能动BCH_K和BCH_NK两者之和必须严格等于BCH_N配置头文件里用编译期断言卡死。g[]数组长度是BCH_NK1最后一位是常数项如果生成多项式算出来次数不对这里会读到未初始化内存输出看着像随机数。有个小优化很多人会漏内层循环其实不用每次都跑满 nk1因为work[i]被清零之后后面再扫到同一下标不会重复触发。如果改成从iBCH_NK往回扫的写法可以把异或次数压到一半但代码会难读不少我一般不在第一版里做。3.3 移位寄存器版本与吞吐长除法版本的问题是每次都要访问整个work数组cache 不友好。工程上更常见的是 LFSR 形式只维护 nk 个比特的余式寄存器信息位一位一位喂进去反馈位决定这一轮要不要异或 g 的低 nk 位。/* sr[0] 对应 x^(nk-1)sr[nk-1] 对应 x^0 */ void bch_encode_lfsr(const uint8_t *msg, uint8_t *cw) { uint8_t sr[BCH_NK] {0}; for (int i 0; i BCH_K; i) { uint8_t fb (uint8_t)((msg[i] ^ sr[0]) 1); /* 反馈位 */ /* 左移一级反馈为 1 时异或 g 的对应系数 */ for (int j 0; j BCH_NK - 1; j) sr[j] (uint8_t)((sr[j 1] ^ (g[j 1] (uint8_t)(0 - fb))) 1); sr[BCH_NK - 1] (uint8_t)(g[BCH_NK] (uint8_t)(0 - fb)); } for (int i 0; i BCH_K; i) cw[i] (uint8_t)(msg[i] 1); for (int i 0; i BCH_NK; i) cw[BCH_K i] sr[i]; }(uint8_t)(0 - fb)这个写法是把 0/1 的反馈位展开成全 1 或全 0 的掩码避免分支编译器会把它编译成一条取反加一。g[j1]的下标偏移是因为g[0]对应 x^nk已经隐含在反馈路径里了不需要再异或。两种实现的结果必须逐位相同这是我在合并代码前的固定动作随机生成 1000 组 k 位信息两套编码器各跑一遍memcmp比对。只要有一次不一致说明其中一套的位序或者 g 的下标写反了这种问题靠肉眼看代码基本看不出来。LFSR 版本真正的价值不在速度而在资源。nk 个比特的寄存器加一个临时变量RAM 占用是个位数字节而长除法版本要开一个 n 字节的work数组。如果目标平台是那种 RAM 只有 2 KB 的小芯片这个差别是决定性的。4. 译码器伴随式、BM 迭代、Chien 搜索三段式4.1 伴随式计算与二进制 BCH 的共轭简化译码第一步是判断「有没有错」。把收到的 n 位码字多项式 r(x) 代进 α^1 到 α^{2t} 这 2t 个点结果全零就认为没错注意是「认为」后面会讲为什么。这 2t 个值就是伴随式 S_j。/* S[1..2t]S[0] 留空不用 */ void bch_syndrome(const uint8_t *r, uint8_t *S) { for (int j 1; j 2 * BCH_T; j) { uint8_t s 0; uint8_t aj gf_exp[j]; /* alpha^j */ for (int i 0; i BCH_N; i) s (uint8_t)(gf_mul(s, aj) ^ (r[i] 1)); /* Horner 求值 */ S[j] s; } }这里用 Horner 而不是逐项累加是因为逐项写法要算j*(n-1-i) % n那个取模在 MCU 上很贵而且指数容易写错。Horner 把 n 次求值变成 n 次乘加gf_mul内部是两次查表加一次加法整体非常轻。参数上有一点容易被忽略S_j 的个数是 2t但二进制 BCH 有个性质 S_{2j} S_j²也就是说偶数下标的伴随式完全由奇数下标决定。所以真正有用的只有 t 个值另外 t 个可以只用来做一致性校验。我在实现里两个都算多花的代价很小但能白捡一层自检——如果 S_2 不等于 S_1 的平方说明 GF 表或者位序有问题直接报错比带病往下跑强。常见误用是把 α 的幂次起点写成 0 而不是 1。S_0 r(α^0) r(1)也就是所有位的异或这个值对纠错没有贡献还会让 BM 的迭代次数错位。生成多项式的根是从 α^1 开始的伴随式必须对齐。4.2 Berlekamp-Massey 迭代求错误位置多项式拿到 2t 个伴随式之后目标是找一个次数不超过 t 的多项式 σ(x)使得它和伴随式满足牛顿恒等式。BM 算法就是干这个的迭代 2t 轮每轮用当前 σ 预测下一个伴随式预测值和实际值之差记作 dd 非零就修正 σ 并调整一个叫 L 的计数器。/* 返回错误个数估计值 Lsigma[0..L] 为降幂系数sigma[0]1 */ int bch_bm(const uint8_t *S, uint8_t *sigma) { uint8_t C[BCH_T 1] {0}, B[BCH_T 1] {0}, T[BCH_T p a hrefhttps://download.csdn.net/download/jxw735/4560873 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p