BCH编译码C实现：GF(2^m)运算与BM/Chien译码-平芜编程栈

简介：面向通信、存储与数据传输方向的学习者，这份BCH编译码C语言实现代码包聚焦有限域纠错编码的落地练习，适合已具备C语言基础、希望理解BCH码从理论到程序实现的中级读者。压缩包共1个文件，为单个C源文件，包体约5KB，代码围绕GF(2^n)上的多项式表示与模2运算展开，涵盖生成多项式构造、信息位编码、校验位生成以及BM迭代解码中的错误定位与校正思路。已有1426人学习，说明其在纠错编码入门与课程实验场景中具有一定参考价值。读者可借助这份紧凑实现梳理BCH码的核心概念，包括码字、最小距离、有限域加法乘法、多项式除法与硬判决解码流程，并据此开展无错、单错和多错用例的测试与调试，逐步理解算法模块划分和位操作优化方向，为数字通信系统中的纠错编码实践打下基础。

1. 从一次丢帧恢复说起：BCH 编译码 C 实现到底能拿来做什么

一个模拟采集链路的联调现场，回传帧里偶尔有 1 到 2 个 bit 翻转，重传能扛一阵，但缓存区里的历史数据没法重来。这时候 BCH 编译码 C 实现的价值就出来了：它不靠重传，而是在码字层面把有限个随机错误直接纠回来。你在搜 bch c语言，大概率也不是想抄一段公式，而是想要一套能塞进固件、能按码长和纠错能力调整、编译完就能跑的编解码代码。这套实现面向二进制 BCH 码，核心是 GF(2^m) 运算、生成多项式除法编码、伴随式加 Berlekamp-Massey 加 Chien 搜索译码。适合做存储校验、短帧通信、MCU 侧轻量纠错的底层开发者；如果你只想调库，不一定需要自己拆它。

2. 工程骨架与技术选型：GF(2^m)、生成多项式和 C 模块怎么落地

这套 BCH C 实现我一般会按三层拆：有限域运算层、BCH 编解码层、应用/测试层。技术选型不复杂，C99 加 Makefile，不依赖第三方库，目的就是能直接交叉编译到资源不宽裕的目标板上。有限域用查表法，码字先用“一位一字节”的数组存，调试时能直接看到第几个 bit 出错，量产前再压成字节流。这样做牺牲一点内存，换来的是编码和译码链路可观测，出了问题不至于变成黑匣子。

2.1 目录与模块边界：从位域到码字的职责划分

常见做法是把有限域和 BCH 码本身分开，不把gf_mul塞进bch_decode里。目录大概长这样：

路径	职责
`include/gf.h`	有限域上下文、乘法、除法、幂运算声明
`include/bch.h`	码字参数、编码接口、译码接口、错误码
`src/gf.c`	GF(2^m) 查表初始化和基础运算
`src/bch.c`	生成多项式接入、系统编码、伴随式、BM、Chien 搜索
`src/main.c`	最小调用示例，方便先跑通
`tests/test_bch.c`	单错、双错、超限错回归
`Makefile`	编译和清理

核心结构体不要塞太多业务字段，码长、信息位长度、纠错能力、本原多项式、生成多项式表、alpha 幂表就够了。下面这种定义比较常见：

typedef struct { int m; // GF(2^m) 的阶，常见 8 表示 255 长码 int n; // 码字 bit 数，完整码通常 n = 2^m - 1 int k; // 信息位 bit 数 int t; // 可纠随机错误 bit 数 int parity; // n - k，校验位长度 unsigned short order; // 2^m - 1 unsigned short prim_poly; // 本原多项式，必须和 g 表同源 unsigned char *g; // 生成多项式系数，长度 parity + 1 unsigned char *alpha_pow; // alpha^i，i 到 2t gf_ctx gf; // 有限域查表上下文 } bch_codec_t;

n和k是 bit 数，不是字节数；g的长度必须是n - k + 1，而且g[0] = 1，代表生成多项式的最高次项。alpha_pow[i]存的是 α^i，译码时计算伴随式直接取，不再每次现算。把prim_poly留在结构体里不是为了好看，而是为了在初始化和自检时确认生成多项式表和有限域表是同一套参数生成的。血泪经验是：这两者一旦不同源，编码可能看起来正常，译码伴随式却怎么都对不上。

2.2 有限域运算的 C 实现：查表还是现算

GF(2^m) 的加法和减法都是异或，真正影响性能的是乘法和求逆。BCH 译码里 BM 迭代和 Chien 搜索会频繁调用乘法，我一般直接用指数表和对数表。初始化时把 α^0 到 α^(order-1) 铺进exp，同时记录log，后面乘法就是查表加取模。

#include <string.h> #include "gf.h" int gf_init(gf_ctx *gf, int m, unsigned short prim_poly) { if (m <= 0 || m > 8) return -1; // 示例按 8 位以内实现，m 更大要换宽类型 memset(gf, 0, sizeof(*gf)); gf->m = m; gf->order = (1u << m) - 1; gf->prim_poly = prim_poly; unsigned short x = 1; for (int i = 0; i < gf->order; i++) { gf->exp[i] = (unsigned char)x; gf->log[x] = (unsigned char)i; x <<= 1; if (x & (1u << m)) { x ^= prim_poly; // 本原多项式必须包含 x^m 项 } } gf->exp[gf->order] = gf->exp[0]; // 方便部分运算不取模 return (gf->exp[gf->order] == 1) ? 0 : -2; } unsigned char gf_mul(const gf_ctx *gf, unsigned char a, unsigned char b) { if (a == 0 || b == 0) return 0; int idx = (int)gf->log[a] + (int)gf->log[b]; if (idx >= gf->order) idx -= gf->order; return gf->exp[idx]; } unsigned char gf_div(const gf_ctx *gf, unsigned char a, unsigned char b) { if (b == 0) return 0; // 调用方应先判 b 非零 if (a == 0) return 0; int idx = (int)gf->log[a] - (int)gf->log[b]; if (idx < 0) idx += gf->order; return gf->exp[idx]; }

prim_poly必须是本原多项式，m = 8时常见的是 0x11D 这一类，具体用哪个要和生成多项式表一起定。代码里exp至少开到order + 1，log开到 256；如果以后把m提到 9 或 10，unsigned char就不够了，要换成unsigned short，别只改宏不改类型。初始化末尾用exp[order] == 1做一次闭合校验，能提前发现本原多项式写错。常见误用是“编码和译码各写一套 GF 初始化”，参数稍微不一致就会变成玄学问题。

2.3 构建与跑通最小示例：Makefile 和测试入口

这套代码没有第三方依赖，构建入口越简单越好。一个够用的 Makefile 如下：

CC ?= cc CFLAGS ?= -std=c99 -O2 -Wall -Wextra -Iinclude SRC = src/gf.c src/bch.c src/main.c OBJ = $(SRC:.c=.o) bch_demo: $(OBJ) $(CC) $(CFLAGS) -o $@ $^ clean: rm -f $(OBJ) bch_demo

-Iinclude保证头文件路径一致，-Wall -Wextra不要省，位宽和符号问题在 BCH 实现里很常见。编译命令就是make，跑./bch_demo。最小入口不要一上来接业务帧，先构造信息位、编码、注入两个错误、译码，看纠正位数是否符合预期：

#include <stdio.h> #include <string.h> #include "bch.h" extern const unsigned char bch_g_255_239[]; // 由脚本按同一本原多项式生成 int main(void) { bch_codec_t codec; unsigned char msg[255] = {0}; unsigned char code[255], rx[255]; // m=8, n=255, k=239, t=2，g 表长度应为 17 if (bch_init(&codec, 8, 255, 239, 2, 0x11D, bch_g_255_239) != 0) { return 1; } for (int i = 0; i < codec.k; i++) { msg[i] = (unsigned char)((i * 7 + 1) & 1); } bch_encode(&codec, msg, code); memcpy(rx, code, sizeof(rx)); rx[10] ^= 1; // 模拟第 10 个 bit 翻转 rx[201] ^= 1; // 模拟第 201 个 bit 翻转 bch_decode_report rep; int st = bch_decode(&codec, rx, &rep); if (st == BCH_OK) { printf("corrected=%d\n", rep.corrected); } else { printf("decode failed: %d\n", st); } return 0; }

bch_init的参数依次是阶数、码长、信息位长度、纠错能力、本原多项式和生成多项式系数数组。bch_decode不要只返回 0/1，最好带一个报告结构，至少告诉调用方纠正了几位、失败原因是什么。这个最小示例跑通之后，再把它接到真实帧格式上；如果直接拿业务数据调试，位序、填充位、帧头都会混在一起，排查成本会翻倍。

3. 编码链路拆解：从信息位到系统码码字的每一步

编码部分的核心是系统码：前k位原样放信息位，后n-k位放校验位。数学上就是把信息多项式左移n-k位，再对生成多项式g(x)做除法，余数取反后放到校验位。C 实现里不需要真的做多项式抽象，用一个长度为n的work数组做长除法就够了。码长在 255 这个量级时，O(k * parity)完全能接受，代码也比移位寄存器版本好核对。

3.1 生成多项式与系统编码：多项式除法写成代码

生成多项式一般由脚本离线算好，按g[0]为最高次项、g[parity]为常数项存成二进制系数表。编码时把信息位放到work[0..k-1]，后面补parity个 0，然后从最高位开始消：

int bch_encode(const bch_codec_t *c, const unsigned char *msg_bits, unsigned char *code_bits) { int parity = c->n - c->k; unsigned char work[BCH_MAX_N]; memset(work, 0, (size_t)c->n); memcpy(work, msg_bits, (size_t)c->k); // 信息位在高次，低位先补 0 for (int i = 0; i < c->k; i++) { if (work[i] == 0) continue; for (int j = 0; j <= parity; j++) { work[i + j] ^= c->g[j]; // g[0] 必须为 1，才能消掉当前最高位 } } memcpy(code_bits, msg_bits, (size_t)c->k); memcpy(code_bits + c->k, work + c->k, (size_t)parity); return 0; }

work[i]是当前最高次项系数，g[j]是生成多项式系数，异或就是 GF(2) 上的减法。内层循环从j=0开始，因为g[0]=1，执行完work[i]一定变 0。循环只跑到i < k，后面的校验位不再消。最终work[k..n-1]就是余数，直接拼到信息位后面。参数上要注意code_bits至少n字节，msg_bits至少k字节；如果g表长度不是parity+1，这里会越界或者余数错位，所以初始化阶段就要校验g_len。

3.2 位打包与码字布局：字节序、位序和填充位

调试阶段一位一字节最直观，但传输和存储要压成字节流。打包函数必须固定一种位序，我一般约定code_bits[0]是x^(n-1)的系数，打包时按 MSB-first 写：

void pack_msb_first(const unsigned char *bits, int n, unsigned char *bytes) { int nbytes = (n + 7) / 8; memset(bytes, 0, (size_t)nbytes); for (int i = 0; i < n; i++) { if (bits[i]) { bytes[i >> 3] |= (unsigned char)(0x80 >> (i & 7)); } } } void unpack_msb_first(const unsigned char *bytes, int n, unsigned char *bits) { for (int i = 0; i < n; i++) { bits[i] = (unsigned char)((bytes[i >> 3] >> (7 - (i & 7))) & 1); } }

i >> 3定位字节，i & 7定位字节内偏移，0x80 >>表示高位先出。如果外部帧按 LSB-first 发，就统一改成1 << (i & 7)，编码、译码、测试三处一起改，不要只改打包函数。码字布局可以用一张表固定下来：

字段	长度	说明
信息位	`k`bit	原始数据，系统码中位置不变
校验位	`n-k`bit	生成多项式除法余数
完整码字	`n`bit	高位在前，`code_bits[0]`对应`x^(n-1)`
字节流	`(n+7)/8`字节	最后一个字节可能有填充位，不要当数据

缩短码场景要特别注意：如果完整码是 255 长，业务帧只有 200 位，常见做法是在信息位前面补零到完整码长再编码，译码后把补零段裁掉。补零位置不同，伴随式位置映射也不同，不能一边补在前面、一边按后面裁。

3.3 编码自检：用已知码字和恒等式验证

编码写完先别急着上译码，先验证码字对生成多项式取模为 0，也就是所有伴随式都为 0。这个检查函数和译码里的伴随式计算可以复用：

int bch_check_codeword(const bch_codec_t *c, const unsigned char *code) { for (int i = 1; i <= 2 * c->t; i++) { unsigned char s = 0; unsigned char a = c->alpha_pow[i]; for (int j = 0; j < c->n; j++) { s = gf_mul(&c->gf, s, a) ^ code[j]; // Horner，从最高次到常数项 } if (s != 0) return -i; // 第 i 个伴随式非零 } return 0; }

alpha_pow[i]是 α^i，s初值为 0，每读一位乘一次 α^i 再异或当前位，等价于把码字多项式在 α^i 处求值。返回负数表示第几个伴随式失败，排查时比只返回 0/1 有用。编码后先跑全零码字，再跑单 bit 信息位，再跑随机信息位；全零码字必须全零，单 bit 信息位的编码结果应该和g表有明确的对应关系。这个自检能提前抓出生成多项式表与本原多项式不匹配的问题，省得后面在 BM 里绕圈。

4. 译码核心：伴随式计算、BM 迭代与 Chien 搜索

译码链路比编码长，但责任很清晰：伴随式把接收码字映射到 GF(2^m)，BM 迭代求错误定位多项式，Chien 搜索找错误位置，翻转后重算伴随式验证。二进制 BCH 的错误值恒为 1，所以不需要 Forney 公式求错误幅值；如果拿这套代码去改非二进制 BCH，才要补错误值计算。译码函数一定要有失败出口，不能“找到几个根就当成功”。

4.1 伴随式：把接收码字映射到 GF(2^m)

接收码字rx进来后，先算S_i = r(α^i)，i 从 1 到 2t。数组下标从 0 开始存，S[0]对应S_1，BM 里按这个约定走：

void bch_syndromes(const bch_codec_t *c, const unsigned char *rx, unsigned char *S) { for (int i = 1; i <= 2 * c->t; i++) { unsigned char v = 0; unsigned char a = c->alpha_pow[i]; for (int j = 0; j < c->n; j++) { v = gf_mul(&c->gf, v, a) ^ rx[j]; } S[i - 1] = v; } }

c->alpha_pow要在初始化时算到2t，每个元素是 α^i。Horner 的顺序必须和码字布局一致：rx[0]是最高次项，所以从 0 读到n-1。如果伴随式全零，说明当前码字没有检测到错误，直接返回，不用进 BM。常见误用是只算t个伴随式，BM 需要连续2t个才能确定最多t个错误的位置。

4.2 Berlekamp-Massey：错误定位多项式的迭代更新

BM 的输入是2t个伴随式，输出错误定位多项式lambda，形式是1 + λ1 x + ... + λL x^L。下面这版是标准迭代写法，B保存上一次冲突前的多项式，b保存上一次偏差，m是位移：

int bm_solve(const bch_codec_t *c, const unsigned char *S, unsigned char *lambda, int *L_out) { int t = c->t; unsigned char B[BCH_MAX_T + 1] = {0}; unsigned char T[BCH_MAX_T + 1]; memset(lambda, 0, (size_t)(t + 1)); lambda[0] = 1; B[0] = 1; int L = 0, m = 1; unsigned char b = 1; for (int n = 0; n < 2 * t; n++) { unsigned char d = S[n]; for (int i = 1; i <= L; i++) { d ^= gf_mul(&c->gf, lambda[i], S[n - i]); } if (d == 0) { m++; continue; } memcpy(T, lambda, (size_t)(t + 1)); unsigned char coef = gf_div(&c->gf, d, b); for (int i = 0; i + m <= t; i++) { lambda[i + m] ^= gf_mul(&c->gf, coef, B[i]); } if (2 * L <= n) { L = n + 1 - L; memcpy(B, T, (size_t)(t + 1)); b = d; m = 1; } else { m++; } } *L_out = L; return (L <= t) ? 0 : -1; }

d是当前偏差，coef是本次修正系数，2*L <= n决定是否更新B和L。lambda至少t+1个元素，B和T也要同样大小。返回L > t时说明错误数超过纠错能力，不要继续 Chien 搜索硬纠。二进制 BCH 的错误值是 1，这里不需要算幅值；如果错误定位多项式次数和 Chien 找到的根数不一致，按失败处理。

4.3 Chien 搜索与纠错回写：定位后别忘了翻转

Chien 搜索枚举每个码字位置，代入Λ(α^{-e})，等于 0 就认为该位置出错。e是该位置对应的 x 幂次，数组位置pos和e的关系是e = n - 1 - pos：

int bch_chien_find(const bch_codec_t *c, const unsigned char *lambda, int L, unsigned char *err_pos) { int cnt = 0; for (int pos = 0; pos < c->n; pos++) { int e = c->n - 1 - pos; int idx = (c->order - (e % c->order)) % c->order; unsigned char xinv = c->gf.exp[idx]; // α^(-e) unsigned char v = 0, xp = 1; for (int i = 0; i <= L; i++) { v ^= gf_mul(&c->gf, lambda[i], xp); xp = gf_mul(&c->gf, xp, xinv); } if (v == 0) { err_pos[cnt++] = (unsigned char)pos; } } return cnt; }

找到位置后直接rx[pos] ^= 1，因为二进制错误值就是 1。翻转后不要马上返回成功，重算一遍伴随式：

for (int i = 0; i < cnt; i++) { rx[err_pos[i]] ^= 1; } unsigned char S2[BCH_MAX_T * 2]; bch_syndromes(c, rx, S2); for (int i = 0; i < 2 * c->t; i++) { if (S2[i] != 0) return BCH_ERR_VERIFY; }

cnt应该等于 BM 输出的L，不等就说明定位多项式有伪根或者位置映射错了。重算伴随式是最后一道防线，尤其在存储场景里，误纠比不纠更危险。

4.4 译码失败判定：不可纠错误别硬纠

译码主函数把上面几步串起来，返回状态要细分：

typedef enum { BCH_OK = 0, BCH_ERR_UNCORRECTABLE = -1, BCH_ERR_BAD_LOCATOR = -2, BCH_ERR_VERIFY = -3 } bch_status; int bch_decode(const bch_codec_t *c, unsigned char *rx, bch_decode_report *rep) { unsigned char S[BCH_MAX_T * 2]; bch_syndromes(c, rx, S); int nonzero = 0; for (int i = 0; i < 2 * c->t; i++) { if (S[i]) { nonzero = 1; break; } } if (!nonzero) { rep->corrected = 0; return BCH_OK; } unsigned char lambda[BCH_MAX_T + 1]; int L = 0; if (bm_solve(c, S, lambda, &L) != 0 || L > c->t) { return BCH_ERR_UNCORRECTABLE; } unsigned char err_pos[BCH_MAX_T]; int cnt = bch_chien_find(c, lambda, L, err_pos); if (cnt != L) return BCH_ERR_BAD_LOCATOR; for (int i = 0; i < cnt; i++) rx[err_pos[i]] ^= 1; unsigned char S2[BCH_MAX_T * 2]; bch_syndromes(c, rx, S2); for (int i = 0; i < 2 * c->t; i++) { if (S2[i]) return BCH_ERR_VERIFY; } rep->corrected = L; return BCH_OK; }

伴随式全零直接返回无错；BM 失败或L > t返回不可纠；Chien 根数不等于L返回定位失败；重算伴随式非零返回验证失败。调用方根据这些状态决定丢弃、重传还是记日志。rep里还可以加原始伴随式、失败位置等字段，调试时比单看返回值有用。

5. 避坑与排查：BCH C 实现里最容易翻车的五处

BCH 实现最难受的地方不是公式长，而是每一步都“看起来对”，但最后纠错结果不对。下面五处是我在调试和移植时反复遇到的，按“现象、原因、解决”拆开写，方便对着日志逐项排查。

5.1 位序反了：编码能过、译码全错

现象是编码后的码字用自检函数能过，但接到实际帧上译码全错，或者单 bit 错误位置偏移了 8 位。原因通常是多项式最高次约定和字节打包位序不一致：code_bits[0]被当成x^(n-1)，打包时却按 LSB-first 写到字节最低位，解包时又按 MSB-first 读回来。解决方法是把位序约定写进接口注释，编码、打包、解包、译码四处统一；测试里专门加一组“第 0 位出错、第 7 位出错、第 8 位出错”的用例，看错误位置是否精确回写。不要靠肉眼比对字节流，位序问题在 255 长码里很容易被当成算法错误。