简介：面向通信与存储系统开发者及纠错编码学习者，BCH编译码C语言实现源码包聚焦伽罗华域GF(2^n)下的编解码算法，提供完整工程与可运行示例，帮助读者理解生成多项式选取、模2除法、伴随式计算和错误定位等关键步骤。压缩包共81个文件，体积约4.7MB，核心内容为encode.h、decode.h头文件与main.cpp源程序，可直接阅读或编译运行；其余多为Visual Studio编译中间文件，如tlog日志、pdb调试符号、manifest清单及exe可执行文件，便于核对编译流程与排错。已有744人学习下载。通过研读代码，可掌握用位运算实现多项式乘除、用二维数组完成矩阵运算的技巧，并结合示例程序验证汉明距离与纠错能力，理解算法从数学理论到C语言工程化的完整转化过程，为在真实通信或存储系统中应用BCH码提供扎实参考，尤其适合需要快速上手纠错码实现的工程人员。

1. BCH编译码：一份能直接拿来用的C语言纠错编码工程

做存储或者通信的开发者，大概率都有过这种经历：从NAND Flash里读回一页数据，发现有几个bit莫名翻转了，查了半天发现是硬件噪声，得自己在软件里兜底。这时候BCH编译码就是最常用的后悔药之一——它的纠错能力比奇偶校验强得多，又能通过参数调节纠错位数，是NAND Flash主控、Ethernet、卫星通信里最常见的FEC方案之一。

这套BCH编译码的C语言实现，就是专门干这个用的。它不依赖任何第三方库，纯标准C写的，核心是一个完整的BCH编码器和译码器：编码端把信息位算成系统码，译码端能自动检测错误位置并修正，支持任意可配置的BCH参数（码长、信息位长、纠错能力t）。换句话说，你拿到一份数据，往里加冗余，传输出错后能自己找出来改回来。新手可以直接当黑盒用，熟手可以拿它当模板改造成自己的FEC模块。

2. 整体设计：先理解BCH的数学结构，再谈代码

2.1 目录结构与文件分工

工程文件不算多，但每个文件的职责很清晰。拿到源码包解压后，典型的文件划分是这样：

src/ bch.h // 对外API、参数宏定义 bch.c // 编码、译码主流程 gf.c // GF(2^m)有限域运算，查表实现 bm.c // Berlekamp-Massey迭代求错误位置多项式 chien.c // Chien搜索，找错误位置 test_main.c // 自测入口，随机出错后验证纠错

bch.h是门面，所有外部调用只需要看懂这个头文件就够。gf.c负责有限域上的加减乘除——这不是普通的整数运算，而是GF(2^m)上的多项式运算。bm.c和chien.c是译码的核心，也是整个BCH里最难啃的两块，后面会逐段展开。

设计上最让我认可的一点是：编码和译码完全分离，中间只通过有限域运算接口交互。这意味着你想把GF运算换成硬件加速指令，或者把BM算法换成Euclidean算法，只需要替换对应模块，其他部分不用动。

2.2 有限域GF(2^m)：整个BCH的地基

BCH码的所有运算都在GF(2^m)上进行。m的取值决定了码长上限：码长n最大为2^m - 1。比如m=4时，码长最多15；m=8时，码长最多255；m=13时，码长最多8191。实际使用中，NAND Flash场景常用m=13，码长取8191或者截短到4096、2048等。

GF(2^m)中，元素之间做加法就是按位异或，乘法要模一个本原多项式。这里有个新手容易绕晕的点：乘法不是普通的整数乘法，而是多项式乘完后对本原多项式取余。举个m=4的例子，本原多项式取0x13（即x^4+x+1），那么α^4 = α+1，所有元素都能表示成α的幂次和多项式系数的形式。

// gf.c 里建立指数-多项式映射表的典型实现 #define GF_M 4 #define GF_POLY 0x13 // 本原多项式 x^4+x+1 uint16_t gf_exp[1 << GF_M]; // 指数 -> 多项式值 uint16_t gf_log[1 << GF_M]; // 多项式值 -> 指数 void gf_init(void) { uint16_t x = 1; for (int i = 0; i < (1 << GF_M) - 1; i++) { gf_exp[i] = x; gf_log[x] = i; x <<= 1; if (x & (1 << GF_M)) x ^= GF_POLY; // 达到最高位后模掉本原多项式 } // 补最后一项，令 exp[2^m - 1] = exp[0] = 1 gf_exp[1 << GF_M - 1] = gf_exp[0]; }

这段代码做的事情是：从α^0=1开始，每次左移一位模拟乘以α，一旦溢出到第m位就异或本原多项式把它拉回来。最终得到的gf_exp表把每个指数对应的多项式值都存好了，gf_log表则是反查。后面的乘法、除法全部查表解决，速度远快于实时计算。

参数说明：GF_M决定有限域大小，GF_POLY是那个本原多项式，两者必须配套。用错本原多项式，整张表全错，后面所有结果都是错的。我一般建议在gf_init()里对gf_exp[2^m - 1]做一次断言检查，不等于1说明本原多项式选错了，尽早暴露问题。

2.3 BCH码参数三元组：(n, k, t) 到底怎么选

BCH码常用(n, k, t)三个参数描述：n是码字总长（信息位+校验位），k是信息位长度，t是纠错能力（最多能纠几个bit错误）。三个参数的关系是：n - k = 校验位长度，校验位越多，t越大，编码效率就越低。

举个例子，BCH(15, 7, 3)表示总长15bit，其中7bit是数据，8bit是校验，最多纠3个错误。这个参数有实际意义：m=4的有限域，码长上限正好15，t=3时校验位需要m×t=12bit，但这里只用了8bit，实际上是一个缩短码。物理存储中，校验位长度并不是严格等于m×t的整数倍，因为生成多项式的次数可能低于m×t。

代码里的参数配置在bch.h中，常见的写法是这样：

// bch.h 中 BCH 参数宏 #define BCH_M 13 // 有限域 GF(2^13) #define BCH_N 8191 // 码长 #define BCH_T 4 // 纠错能力：最多纠 4 位错误 #define BCH_K (BCH_N - BCH_M * BCH_T) // 信息位 = 8119

BCH_K的计算公式是n - m×t，这是一个近似式，实际设计中生成多项式的次数可能小于m×t，需要根据最小多项式做精确计算。工程上先按这个公式估算，再用生成多项式的实际次数校准。选参数时注意：n不能超过2^m - 1，否则有限域里根本没有那么多元素，查表直接越界。

3. 编码流程：生成多项式与系统码构造

3.1 生成多项式是怎么算出来的

BCH编码的核心是生成多项式g(x)。它是一个在GF(2^m)上有t个连续根的二进制多项式，理论来源于最小多项式。工程实现上不要求你重新推导，直接用现成的生成多项式表即可。比如BCH(15, 7, 3)的g(x) = x^8 + x^7 + x^6 + x^4 + 1，十六进制表示是0xD1。

实现时这步通常做成一个独立函数，输入t和m，输出g(x)的系数数组。计算过程是：找出α^1到α^(2t)这些元素各自的最小多项式，再求它们的LCM（最小公倍式）。完整实现比较长，这里给一个简化思路：

// 计算单个元素的最小多项式（示意版） // 返回多项式的系数数组 poly[]，poly[i] 表示 x^i 的系数 void minimal_poly(uint16_t elem, int gf_m, uint8_t *poly, int *deg) { uint16_t cur = elem; uint8_t seen[1 << gf_m] = {0}; int coef[64] = {0}; // 先构造共轭根集合 // 共轭根：elem, elem^2, elem^4, ... 直到重复 int idx = 0; while (!seen[cur]) { seen[cur] = 1; cur = gf_mul(cur, cur); // 平方 idx++; } // 用这些根连乘构造多项式，共轭个数就是多项式次数 // 具体连乘展开略，实现时用多项式乘法逐项累加 }

这段代码展示了最小多项式计算的核心逻辑：利用共轭根在GF(2^m)上闭合的性质，找到元素的所有共轭对，把它们连乘展开就得到最小多项式。elem是α的某个幂次，gf_mul是有限域乘法，cur每次平方得到下一个共轭根。

实际使用中，我不会让代码每次都算生成多项式——那是开发调试阶段的做法。工程上把生成多项式做成静态常量表，编译期就确定，运行时零开销。BCH(15,7,3)用0xD1，BCH(511, 493, 2)等常用参数都有现成查表，网上也能找到生成多项式手册。

3.2 系统码编码：信息位左移后求余

BCH编码最常用的形式是系统码：码字前面k位就是原始信息，后面n-k位是校验位。编码过程分三步：信息多项式m(x)左移n-k位（腾出校验位位置），然后除以g(x)取余数，余数就是校验多项式。

// 系统码编码核心函数 // msg: 输入信息位数组，每个元素1bit // code: 输出码字数组 void bch_encode(const uint8_t *msg, uint8_t *code, int n, int k, const uint8_t *g, int g_deg) { // 第一步：把信息位放到码字高 k 位 for (int i = 0; i < k; i++) code[i] = msg[i]; // 第二步：计算 x^(n-k) * m(x) 对 g(x) 的余数 // 用长除法，逐位处理，类似 CRC 但用的是生成多项式 uint8_t rem[BCH_MAX_DEG] = {0}; for (int i = 0; i < k; i++) { uint8_t feedback = msg[i] ^ rem[g_deg - 1]; // 左移一位 for (int j = g_deg - 1; j > 0; j--) rem[j] = rem[j - 1]; rem[0] = 0; if (feedback) { for (int j = 0; j < g_deg; j++) rem[j] ^= g[j]; } } // 第三步：余数放到码字低 n-k 位 for (int i = 0; i < g_deg; i++) code[k + i] = rem[i]; }

逻辑说明：这个实现实际上是一个线性反馈移位寄存器（LFSR）的软件模拟。feedback是当前信息位与寄存器最高位的异或结果，决定这一轮要不要把g(x)异或进去。整个循环跑完k轮，寄存器里的值就是余数，也就是校验位。

参数说明：g_deg是生成多项式的次数，等于校验位长度；g数组是生成多项式系数，g[j]对应x^j的系数。这段代码的时间复杂度是O(k×g_deg)，对短码完全够用，长码建议改成按字节处理的查表版本，速度能提升好几倍。

3.3 编码的自测手段

编码写完之后怎么确认没写错？最简单的办法就是验证一个特性：任意信息位编码得到的码字，代回编码过程再做一次，余数必须全零。这是BCH码的数学性质——码字都是g(x)的倍式。我习惯在test_main.c里把这个断言写上，每次改动后跑一遍，能挡住大量低级错误。

// 编码自测：码字必须能被 g(x) 整除 int check_codeword(const uint8_t *code, int n, const uint8_t *g, int g_deg) { uint8_t rem[BCH_MAX_DEG] = {0}; for (int i = 0; i < n; i++) { uint8_t feedback = code[i] ^ rem[g_deg - 1]; for (int j = g_deg - 1; j > 0; j--) rem[j] = rem[j - 1]; rem[0] = 0; if (feedback) { for (int j = 0; j < g_deg; j++) rem[j] ^= g[j]; } } for (int i = 0; i < g_deg; i++) if (rem[i]) return 0; return 1; }

这一段的思路跟编码完全对称，只是不再输入信息位，而是直接对整个码字做除法。如果余数不为零，说明编码过程有bug，或者生成多项式g和码长n不匹配。这个函数在设计测试用例、做随机数据回归时非常重要，我每次改完GF运算都要先跑一遍它。

4. 译码链路：从伴随式到错误定位的完整闭环

4.1 伴随式计算：错误检测的第一步

译码的第一步是接收码字r(x)，计算它在2t个根上的值，得到伴随式集合S_1, S_2, ..., S_2t。如果所有伴随式全为零，说明没有错误（或错误模式恰好不可检测）；否则说明有错误，需要进一步处理。

// 计算伴随式 // r: 接收码字数组, n: 码长, m: 有限域位数 void compute_syndromes(const uint8_t *r, int n, int m, uint16_t * syndromes) { uint16_t alpha = 2; // α = 多项式 x，即 GF 中的 2 for (int s = 1; s <= 2 * BCH_T; s++) { uint16_t acc = 0; uint16_t xi = 1; // 把 r(x) 带入求值 for (int i = 0; i < n; i++) { if (r[i]) acc ^= xi; // GF(2^m) 上的加法 = 异或 xi = gf_mul(xi, alpha); // xi = α^i } syndromes[s - 1] = acc; alpha = gf_mul(alpha, alpha); // 下一个根 α^s } }

逻辑说明：这里对每个根α^s计算r(α^s)，本质是霍纳法的简化形式。xi从α^0=1开始，每次乘上当前根，相当于在计算α^(s·i)。当接收码字中第i个比特为1时，把它累加到结果里。GF(2^m)上加法就是异或，所以acc ^= xi没有进位问题。

参数说明：alpha初始值为2，这是因为在GF(2^m)的二进制多项式表示中，x对应的数值恰好是2。循环内的alpha = gf_mul(alpha, alpha)让根依次变为α^1, α^2, ..., α^(2t)。注意伴随式输出顺序：syndromes[0]对应S_1= r(α)，syndromes[1]对应S_2= r(α^2)，依次类推。

4.2 Berlekamp-Massey算法：求解错误位置多项式

伴随式算出来后，接下来要求错误位置多项式σ(x)。BM算法是迭代式解法，每一次迭代利用当前的伴随式值修正σ(x)，核心思想是让σ(x)的系数和伴随式满足一组递推关系。实现紧凑但有点玄学，我第一次看的时候也绕了很久，后来才明白本质上是在线性反馈移位寄存器里找最短连接多项式。

// BM 算法求错误位置多项式 sigma(x) // s: 伴随式数组, t: 纠错能力, sigma: 输出多项式系数 void berlekamp_massey(const uint16_t *s, int t, uint16_t *sigma) { uint16_t C[64] = {0}; // 当前多项式 uint16_t B[64] = {0}; // 上一次修正用多项式 uint16_t T[64] = {0}; C[0] = 1; B[0] = 1; int L = 0; // 当前多项式的次数 int m = 1; // B(x) 的移位量 uint16_t b = 1; // 上一次的差值，初始化为1 for (int n = 0; n < 2 * t; n++) { // 计算差值 d = S_n + sum(C_i * S_{n-i}) uint16_t d = s[n]; for (int i = 1; i <= L; i++) d ^= gf_mul(C[i], s[n - i]); if (d == 0) { m++; } else if (2 * L <= n) { // 需要更新 L，保存旧 C 到 B for (int i = 0; i < 64; i++) T[i] = C[i]; // C(x) = C(x) - d * b^{-1} * x^m * B(x) uint16_t coef = gf_div(d, b); for (int i = 0; i < 64 - m; i++) C[i + m] ^= gf_mul(coef, B[i]); L = n + 1 - L; for (int i = 0; i < 64; i++) B[i] = T[i]; b = d; m = 1; } else { // C(x) = C(x) - d * b^{-1} * x^m * B(x)，L 不变 uint16_t coef = gf_div(d, b); for (int i = 0; i < 64 - m; i++) C[i + m] ^= gf_mul(coef, B[i]); m++; } } // 拷贝结果 for (int i = 0; i <= L; i++) sigma[i] = C[i]; }

逻辑说明：变量L表示当前已知最短LFSR的长度，b是上一次修正时的差值，m是迭代间隔。每次迭代计算一个差值d，如果为零，说明当前多项式对这一步也成立，只需要把m加1；如果不为零且2L <= n，说明多项式次数不够，必须更新L并且把旧多项式存到B里；如果d不为零但2L > n，只在当前C上修正而不动L。

参数说明：所有数组下标从0开始，sigma[i]对应x^i的系数。GF运算全部走gf_mul和gf_div查表接口。代码里数组大小设为64，对应t最大32的场景，如果t更大需要调大数组。

BM算法跑出来的σ(x)如果次数超过t，说明错误数量超过纠错能力，这时可以直接报错“不可纠”，不要继续往下算，否则Chien搜索会输出无意义的结果。工程代码里一定要在BM返回后检查L <= t，不满足就提前退出。

4.3 Chien搜索与错误值修正

σ(x)求出来后，需要找到它的根。Chien搜索的思路很直接：把α的每个幂次代进σ(x)逐个验证，σ(α^i) = 0说明α^(-i)是错误位置。但逐项计算多项式的开销不小，Chien搜索的巧妙之处是用迭代累加代替重新求值。

// Chien 搜索：找出错误位置 // sigma: BM 求出的错误位置多项式, L: sigma 次数 // n: 码长, err_loc[]: 输出错误位置下标数组 int chien_search(const uint16_t *sigma, int L, int n, int *err_loc) { int err_count = 0; // 预计算 sigma 各项系数乘上 α^j 的初始值 uint16_t s_coef[64]; for (int j = 1; j <= L; j++) s_coef[j] = sigma[j]; for (int i = n - 1; i >= 0; i--) { uint16_t sum = sigma[0]; // σ0 恒为 1 for (int j = 1; j <= L; j++) { sum ^= s_coef[j]; // 累加 s_coef[j] = gf_mul(s_coef[j], gf_exp[j]); } if (sum == 0) { // σ(α^{-i}) = 0，说明位置 i 有错 err_loc[err_count++] = i; } } return err_count; }

逻辑说明：s_coef[j]初始为σ_j·α^j，每次迭代后都再乘上α^j，这样第i轮算出来的实际上是σ_j·α^(j·i)的累加和，正好等于σ(α^i)。整个过程不需要重新算多项式，每轮只用L次乘法和异或，效率很高。

参数说明：循环从n-1递减到0，是因为我们的码字下标从0开始，对应α^n的幂次位。err_loc输出的是码字中的bit位置，译码时把这些位置翻转就能完成纠错。这个函数返回的错误个数必须与BM算出的L一致，如果不一致，说明要么Chien搜索有bug，要么错误模式不可纠。

错误修正本身很简单：for (int i = 0; i < err_count; i++) code[err_loc[i]] ^= 1;即可。到这里，一个完整的BCH译码闭环就结束了：伴随式 → BM → Chien → 翻转bit。

5. 避坑指南：跑通BCH编译码最常见的5个坑

5.1 生成多项式算错，导致译码结果全乱

现象：编码自测时码字能被g(x)整除，但译码后纠错结果完全不正确，甚至无错时也会报错。

原因：生成多项式g(x)必须是α^1到α^(2t)这些根的最小多项式LCM，少一个根或者多一个根都会破坏BCH码的结构。最常见的错是直接从CRC表里拿了个多项式来用，CRC的多项式跟BCH不是一回事。

解决：确认生成多项式的根集合是否正确。我的做法是写一个校验函数：把g(x)的根代进去逐一验证，所有2t个根都必须让g(x)为零。

5.2 GF表初始化顺序出错

现象：gf_exp表最后一项gf_exp[2^m - 1]不是1，或者gf_log表中某些项是默认值0。

原因：gf_init()里的循环只跑了(1 << GF_M) - 1次，漏掉了最后一项。GF(2^m)中0和1以外的元素个数是2^m - 1，但指数范围是0到2^m - 2共2^m - 1个值，最后必须手动补上gf_exp[2^m - 1] = gf_exp[0]。

解决：初始化后立刻断言检查。血的教训：有一次我忘了补最后一项，前255个元素都正常，第256个查表结果全错，定位这个问题花了整整一下午。

5.3 码长n超过2^m - 1

现象：编译能过，运行开始正常，数据量一大就出现莫名其妙的越界崩溃。

原因：BCH码要求n ≤ 2^m - 1。比如m=8，码长最多255，你却配了n=512，GF运算查表时直接越界访问。

解决：代码里必须加编译期断言或运行时检查。#if BCH_N > ((1 << BCH_M) - 1) #error "invalid BCH_N" #endif一行编译期检查就能挡掉大部分翻车现场。

5.4 伴随式的索引和α指数错位

现象：t=4的码，前几个错误能纠，错误一多就纠不动或误纠。

原因：伴随式S_i要求的是r(α^i)，i从1到2t。有些人从i=0开始算，或者只算了t个伴随式，信息不足导致BM算法求不出正确多项式。

解决：循环从1开始，alpha初始为2且每轮平方。算完后打印伴随式检查：如果S_1到S_2t和手算的一致，再往下走。

5.5 误码数超过t时的“假纠错”

现象：故意加t+1个错误，程序没有报错，输出了一个看似合理但依然错误的结果。

原因：BM算法被迫解一个超过纠错能力的问题，求出的σ(x)次数可能超过t，此时Chien搜索得到的位置是数学上有解但实际不可靠的。代码没有做次数检查。

解决：BM算法结束后检查σ的次数，超过t直接返回“不可纠”；Chien搜索找到的错误个数与σ次数不一致时也返回失败。宁可让上层拿到失败标记，也不能返回错误数据。这个习惯在存储场景尤其重要——静默数据损坏比直接报错可怕得多。

6. 二次开发：把固定参数编译码改造成通用BCH引擎

6.1 参数宏化，动态适配不同码长

工程上做FEC模块，很少只用一套固定参数。比如NAND Flash不同页面大小，可能需要BCH(8191, 8151, 4)和BCH(2047, 2015, 4)两套配置。粗暴做法是复制两份代码，但维护成本高。

更好的思路是把参数做成运行时配置：

typedef struct { int m; // GF 位数 int n; // 码长 int k; // 信息位 int t; // 纠错能力 uint16_t gf_poly; // 本原多项式 const uint8_t *g_poly; // 生成多项式 int g_deg; // 生成多项式次数 } bch_config_t; int bch_init(bch_config_t *cfg); void bch_encode(const bch_config_t *cfg, const uint8_t *msg, uint8_t *code); int bch_decode(const bch_config_t *cfg, const uint8_t *in, uint8_t *out);

改造时要重点解决两个问题：一是GF表要根据cfg->m动态重建，而不是编译期写死；二是生成多项式表要为每套参数准备一份，或者干脆在bch_init()里调用最小多项式LCM函数现算。第一种省空间但慢，第二种灵活但需要你的最小多项式实现是完整的——不能像我上面给的示意版那样只算共轭根不展开系数。

我一般会把代码拆成两个层次：底层GF运算和BM、Chien逻辑做成完全参数无关的纯函数，所有值都从bch_config_t里取；上层针对常用参数做宏封装，比如BCH_8191_4_ENC。这样既保证了灵活性，常用路径又能走编译期优化。

6.2 性能优化：从bit级到表驱动

纯C的逐bit软实现，在长码、大吞吐场景下性能不够。三个最有效的优化方向：

第一，GF乘法查表改成预计算的乘法表。gf_mul(a, b)拆成查gf_log和gf_exp两次索引，本质是3次数组访问，足够快。但如果乘法出现在循环内层（比如Chien搜索每轮L次乘法），可以用二维表把常用值的乘法结果缓存下来。

第二，编码过程从bit级LFSR改成byte级查表。CRC领域成熟的按字节查表法可以直接迁移到BCH编码上，每处理8个bit只查一次表，速度提升大约8倍。

第三，Chien搜索并行化。每个错误位置的验证互不依赖，这个特性天然适合SIMD或硬件流水。软件实现中，可以把一轮循环展开为同时检查多个σ系数。

优化前务必先测profile，确认热点到底在编码还是译码。遇到过不止一次，有人优化了半天Chien搜索，最后发现瓶颈在GF初始化上。

6.3 改造后的验证方法

改完参数引擎，不能只测一套参数就收工。我的固定动作是写一个随机错误注入器：随机生成信息位 → 编码 → 随机翻转t个以内的bit → 译码 → 断言输出和原始信息一致。这个循环至少要跑几万组数据，覆盖不同错误位置分布。

两个容易漏掉的边界测试：一是错误数恰好等于t时的极限验证，二是错误数等于t+1时必须返回失败标记。前者验证纠错能力上限，后者验证失败处理路径。从此以后我每次动编码译码的核心代码，都强制走一遍这套回归脚本加上GF表完整性检查再合入，血泪经验总结出来的流程，希望帮到你。

本文还有配套的精品资源，点击获取