企业官网建设流程全解析

简介：面向通信、存储与数据传输领域的学习者，这套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[]。有了这两张表，域乘法就退化成「查两次对数、做一次加法、再查一次指数」，加法直接异或，除法把指数相减。表很小，m=8 也才 512 字节，放 MCU 的 RAM 里毫无压力。

代价是必须先选定一个本原多项式。它是 GF(2) 上次数为 m 的不可约多项式，作用是定义 α^m 如何约简回低次。m=4 取 x^4+x+1，完整位表示 0x13；m=5 取 x^5+x^2+1，即 0x25；m=6 取 x^6+x+1，0x43；m=7 取 x^7+x^3+1，0x89。这几个是工程上用滥了的取值，对应的表在多数教材附录里都能查到，自检很方便。

/* 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 项，例如 m=4 传 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 就得同步改本原多项式，两者必须配套，比如 m=4 配 0x13 才自洽，配 0x19（对应 x^4+x^3+1）虽然也是不可约的，但不一定能生成满周期的循环群，表会提前出现重复值。BCH_N固定为(1<<BCH_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决定了要并入多少个共轭类，t=2 时并入 m₁ 和 m₃，g 的次数为 8；t=3 时并入 m₁、m₃、m₅，次数为 15−5=10 往上。跑完之后必须断言deg_g == BCH_N - BCH_K，这个等式不成立说明 t 和 k 没配好，或者共轭标记的循环写错了。

第二个要注意的是build_minpoly里那层 do-while。当 e 与 BCH_N 不互素时，共轭类会更短。比如 n=15、e=5，共轭类是 {5,10}，只有 2 个元素，最后乘出来的最小多项式次数是 2 而不是 4，完全正常。循环条件写成cur != e而不是固定跑 m 次，就是为了兼容这种情况。

拿 m=4、t=2、本原多项式 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 再反推得到。很多人在这里翻车：先拍脑袋定 k=16，再去找能纠 2 位的 m，结果发现凑不上。下面这张表给的是常用配置，nk是校验位数，务必和deg_g对得上。

表里有个隐含约束：nk ≤ m·t 是 BCH 界，实际值通常贴着上界，偶尔小于。选型时的顺序我一般是反着走的——先看帧长和能容忍的冗余，定 n 和 k 的比值，再算 n−k，然后用这张表去查 m 和 t。如果 n−k 落在两档中间，宁可往上取一档 t，也别自己造一个不满足界的组合，那个生成多项式根本不存在。

提示：n=31 以上时，gf_exp的索引上界会到 2N−2=124，uint8_t存得下，但如果你打算扩到 m=9 以上，记得把表元素类型换成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]=1，g[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_NK+1，最后一位是常数项，如果生成多项式算出来次数不对，这里会读到未初始化内存，输出看着像随机数。

有个小优化很多人会漏：内层循环其实不用每次都跑满 nk+1，因为work[i]被清零之后，后面再扫到同一下标不会重复触发。如果改成从i+BCH_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[j+1]的下标偏移是因为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 轮，每轮用当前 σ 预测下一个伴随式，预测值和实际值之差记作 d，d 非零就修正 σ 并调整一个叫 L 的计数器。

/* 返回错误个数估计值 L，sigma[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 href="https://download.csdn.net/download/jxw735/4560873" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>