简介：面向通信、存储与数据传输场景开发者的BCH（Bose-Chaudhuri-Hocquenghem）编译码C语言实现，适合需要掌握纠错编码原理并落地代码的电子、计算机专业学生及工程师。包内共1个C语言源文件，压缩后仅5KB，虽精简但完整覆盖从伽罗华域GF(2^n)运算、生成多项式构造，到编码、BM算法解码及错误定位修正的核心过程。已有1419人学习下载，是快速入门BCH码不可多得的紧凑示例。读者可借此厘清多项式表示与模2运算、校验位设置、软硬决策差异等关键概念，并能对照代码理解编译码流程，或直接移植到自己的通信链路、存储校验模块中。这份材料以极小体量呈现了从理论到工程实现的完整思路，注释清晰、模块化程度高，适合在理解后继续扩展为可复用的工具函数，或作为RS码等同类纠错码的学习起点，非常值得认真研读与二次开发。
1. BCH码是什么，为什么嵌入式开发绕不开它
我最早接触BCH码，是在做NAND Flash的驱动调试时。当时主控要校验读取的数据是否因为块老化出现跳变，硬件ECC只能纠正有限的几位，一旦坏块增多就频繁报错。后来换成软件BCH校验，纠正能力直接提升一个量级，那一刻我才真正意识到BCH在数据完整性场景里的分量。
BCH（Bose-Chaudhuri-Hocquenghem）码属于循环纠错码家族，是汉明码的推广。它的特点在于：可以人为指定纠错能力t，只要码长n和冗余位满足约束关系，就能纠正t位随机错误。和RS码不同，BCH码工作在二进制域GF(2)上，每个符号就是1个比特，实现起来天然适合C语言这种贴近硬件的语言。
BCH码的实际应用非常广：NAND Flash的ECC、二维码的纠错（QR码用的就是BCH变体）、卫星通信、DVB广播、固态硬盘主控，乃至一些传感器无线传输协议里都在用。很多芯片硬件里集成了BCH编解码引擎，但在没有硬件引擎或硬件引擎能力不够时，软件实现就是最后的防线。用C语言写一套BCH编解码器，既能在MCU上裸跑，也能在Linux用户态编译成工具用，是嵌入式开发者的实用技能。
适合阅读这篇文章的读者有两类：一类是刚接触差错控制编码、想在代码层面理解BCH原理的学生；另一类是实际工程中需要快速集成BCH纠错能力、但没有现成库可用的嵌入式工程师。我会从有限域运算开始，一步步把编解码的每一行C代码逻辑讲清楚，并附上实测踩坑记录。
2. 编码前的数学地基：有限域与生成多项式
2.1 从GF(2)到GF(2^m)的直觉理解
BCH所有运算都建立在二进制扩域GF(2^m)上。GF(2)就是普通的二进制加减法，只是把加法和减法都变成异或。GF(2^m)则可以理解为m位的二进制数集合，它们之间定义了一套封闭的加减乘除规则，这套规则对应着一个本原多项式。
我打个比方：GF(2^m)就像自定义的一套“另类整数系统”，里面的“整数”是m位二进制数，但乘法不是普通乘法，而是“先按多项式相乘，再对某个本原多项式取余”。这个本原多项式相当于模运算里的模数，它必须是不可约的，而且是本原的，才能让GF(2^m)里的非零元素形成循环群。
在C语言实现时，最常用的是查表法。m=8时，域大小是256，完全可以在内存里放两张表：log表和antilog表。log表记录每个非零元素是生成元的几次方，antilog表反之。有了这两张表，域内乘法就能变成查表加整数加法再查表，速度比逐位多项式乘快一个数量级。
2.2 生成多项式的计算方法
BCH码的生成多项式g(x)是最小多项式的LCM（最小公倍式）。对于纠正t位错误的BCH码，取本原元alpha的连续幂次alpha^1, alpha^2, ..., alpha^(2t)，它们的极小多项式之LCM就是g(x)。
以经典的BCH(15,7,5)码为例：码长n=15，信息位k=7，可纠t=2位错误。它的生成多项式是g(x)=x^8+x^7+x^6+x^4+1。这个多项式怎么来的？就是取alpha和alpha^3的极小多项式LCM得到的。C语言实现时可以把这个多项式直接硬编码成整数0b111010001 = 0x1D1，最高位对应x^8。
工程的细节在于，生成多项式的码长不是随便定的。n必须满足n=2^m-1或其因子。BCH(15,7,5)对应的m=4，本原多项式常用x^4+x+1。如果码长不够，可以缩短，比如NAND Flash常用的BCH(1024, 976)之类的变体，本质是把原码缩短，但纠错能力不变。
注意：不同资料里生成多项式的表示法可能不同，有的按二进制高位在前，有的按低位在前，转换到C语言位数组时一定要先统一方向，否则编出来的码字全错。
3. C语言编码实现：从原理到可直接抄的代码
3.1 编码的两种套路：除法余数法 vs 查表法
BCH编码本质是系统码：前k位是原始信息，后n-k位是校验位。校验位通过信息多项式m(x)乘以x^(n-k)再对生成多项式g(x)取模得到。也就是说，编码就是做一次多项式除法，余数就是校验位。
最直接的方式是线性反馈移位寄存器（LFSR）。用C语言实现LFSR时，不需要真的模拟硬件移位寄存器，只需要用一个长度等于校验位数目的数组，按位迭代即可。下面是一个BCH(15,7,5)的编码函数：
#include <stdio.h> #include <string.h> #define N 15 #define K 7 #define PARITY_LEN (N - K) // 8 // 生成多项式 g(x) = x^8 + x^7 + x^6 + x^4 + 1 // 二进制: 1 1101 0001，从 x^8 到 x^0 #define G_POLY 0x1D1 // data_in: 长度为K的比特数组（每元素0或1） // parity_out: 长度为PARITY_LEN的校验比特输出 void bch_encode(const unsigned char *data_in, unsigned char *parity_out) { unsigned char reg[PARITY_LEN] = {0}; int i, j; for (i = 0; i < K; i++) { unsigned char feedback = data_in[i] ^ reg[PARITY_LEN - 1]; // 移位 for (j = PARITY_LEN - 1; j > 0; j--) { reg[j] = reg[j - 1]; } reg[0] = 0; if (feedback) { // 与生成多项式异或（去掉最高位x^8，因为它由反馈决定） reg[0] ^= (G_POLY >> 0) & 1; reg[1] ^= (G_POLY >> 1) & 1; reg[2] ^= (G_POLY >> 2) & 1; reg[3] ^= (G_POLY >> 3) & 1; reg[4] ^= (G_POLY >> 4) & 1; reg[5] ^= (G_POLY >> 5) & 1; reg[6] ^= (G_POLY >> 6) & 1; reg[7] ^= (G_POLY >> 7) & 1; } } memcpy(parity_out, reg, PARITY_LEN); } int main() { unsigned char info[K] = {1, 0, 1, 0, 0, 1, 1}; // 随便给一组信息位 unsigned char parity[PARITY_LEN] = {0}; bch_encode(info, parity); printf("校验位: "); for (int i = 0; i < PARITY_LEN; i++) { printf("%d", parity[i]); } printf("\n"); return 0; }这段代码把生成多项式的每一位展开在循环里，虽然啰嗦但直观。实际项目里可以用一个掩码数组，或者用整数移位的方式一次性完成：
// 更紧凑的LFSR实现 void bch_encode_fast(const unsigned char *data_in, unsigned char *parity_out) { unsigned int reg = 0; for (int i = 0; i < K; i++) { unsigned char feedback = data_in[i] ^ ((reg >> (PARITY_LEN - 1)) & 1); reg = (reg << 1) & 0xFF; if (feedback) { reg ^= (G_POLY & 0xFF); // 只保留低8位 } } for (int i = 0; i < PARITY_LEN; i++) { parity_out[i] = (reg >> (PARITY_LEN - 1 - i)) & 1; } }紧凑版的技巧是：reg里只保存8位校验状态，最高位反馈是移位前reg的最高位，移位后取低8位参与异或。这种方式时间复杂度O(K)，每个比特只需若干次操作，在MCU上跑几十微秒就能完成一帧。
3.2 面向字节的编码加速
如果信息位是一整字节一进来的，逐比特处理就太慢了。成熟的实现会把每个字节输入产生的LFSR状态变化预先算成256项表，编码时每进来一个字节，查一次表、异或一次，完成8比特的运算。这就是字节级查表编码。
字节级查表本质上是对LFSR状态转移矩阵的预计算。每个可能的输入字节对应一个增量向量，和当前寄存器状态异或后得到新状态。以BCH(15,7,5)这种小码为例没必要，但当校验位达到14位甚至更多时，逐比特编码的耗时在高速数据传输中是不可接受的。
工程实现上，常见做法是把整个BCH码按码长n切分为字节对齐的结构，生成一张state_transition[256]表，每项是16位或32位的状态增量。然后编码主循环变成：
for (int i = 0; i < data_len; i++) { reg = (reg << 8) ^ table[(reg >> (PARITY_LEN - 8)) ^ data[i]]; }这种优化思路和CRC查表法完全一致。事实上BCH编码的LFSR结构和CRC就是同一种数学结构，只是生成多项式来源不同。
实操心得：如果你的BCH码校验位不是8的倍数，最高字节需要特殊处理，先补齐0再查表。这个细节我在做NAND Flash时漏掉过一次，结果连续几页数据都校验不过，排查了大半天。
4. 译码实现：三步走，从接收码字到纠错完成
4.1 译码算法脉络
BCH译码比编码复杂，但标准步骤很固定，分为三步：
- 计算伴随式（Syndrome）：把接收多项式r(x)代入alpha^(i)，得到2t个伴随值S_i。
- 求错误位置多项式σ(x)：通过Berlekamp-Massey算法或欧几里得算法，从伴随式求出σ(x)。
- 找错误位置并纠正：用Chien搜索逐位测试，找出σ(x)的根，根的倒数就是错误位置，然后翻转对应比特。
4.2 有限域上的伴随式计算
伴随式计算相当于对接收码字做2t次多项式求值。如果接收码字无错，所有伴随式都为零；有错时伴随式非零。在C语言里，借助log/antilog表，逐位累加：
#include <stdio.h> #define GF_SIZE 16 // m=4 // 本原多项式 x^4 + x + 1，生成元alpha=2 int alpha_pow[GF_SIZE * 2]; // 预计算的幂 int alpha_log[GF_SIZE + 1]; void gf_init() { int val = 1; for (int i = 0; i < GF_SIZE * 2; i++) { alpha_pow[i] = val; if (i < GF_SIZE) { alpha_log[val] = i; } val <<= 1; if (val & 0x10) { // 达到x^4项，约简 val ^= 0x13; // 0b10011 = x^4+x+1 } } } // syndrome[i] 对应 S_i = r(alpha^(i+1)) void compute_syndrome(const unsigned char *received, int len, int *syndrome, int t) { for (int i = 0; i < 2 * t; i++) { int exp = i + 1; // alpha的指数 int sum = 0; for (int j = 0; j < len; j++) { if (received[j]) { // 计算 alpha^((len-1-j)*exp) int e = ((len - 1 - j) * exp) % (GF_SIZE - 1); sum ^= alpha_pow[e]; } } syndrome[i] = sum; } }注意：GF(15)里alpha^(15)=1，所以指数需要模15。m=4时域大小是16，但非零元素只有15个周期。
4.3 Berlekamp-Massey算法求错误位置多项式
BM算法是译码的核心。它的思路是：用已知的伴随式序列去拟合一个最短的LFSR，这个LFSR的特征多项式就是错误位置多项式σ(x)。C语言实现BM算法有个常见陷阱：多项式系数的下标和数组顺序要统一。我通常把σ(x)数组定义为sigma[i]表示x^i的系数，其中sigma[0]恒等于1。
// 在GF(2^m)域上执行BM算法 // syndrome: 长度为2t // sigma: 输出sigma[0..t]，sigma[0]=1 void berlekamp_massey(int *syndrome, int t, int *sigma) { int C[2*t + 1] = {0}; int B[2*t + 1] = {0}; C[0] = 1; B[0] = 1; int L = 0, m = 1; int b = 1; for (int n = 0; n < 2 * t; n++) { // 计算差值 d = S_n + C1*S_{n-1} + ... + CL*S_{n-L} int d = syndrome[n]; for (int i = 1; i <= L; i++) { if (C[i] && (n - i) >= 0) { d ^= gf_mul(C[i], syndrome[n - i]); } } if (d == 0) { m++; } else { int *T = C; // 临时备份 int coef = gf_mul(d, gf_inv(b)); for (int i = 0; i < 2*t + 1 - m; i++) { if (B[i]) { C[i + m] ^= gf_mul(coef, B[i]); } } if (2 * L <= n) { // 更新B为旧C，重置m for (int i = 0; i < 2*t + 1; i++) { B[i] = T[i]; } L = n + 1 - L; b = d; m = 1; } else { m++; } } } for (int i = 0; i <= L; i++) { sigma[i] = C[i]; } }上面的gf_mul和gf_inv需要自己实现，用查表法就是查log表和antilog表。注意T = C并不是真正备份，上面伪代码只是示意，实际写C代码时要用临时数组拷贝，否则B指向的还是C的地址，更新C会污染B。这个坑我帮别人查过好多次。
4.4 Chien搜索：逐位找到出错位置
Chien搜索的原理是：如果alpha^(-i)是σ(x)的根，那么第i个位置出错。它能用迭代方式高效地检查每个位置。实现时维护一组“当前幂次”值，每移动一位就乘以alpha的幂：
// 返回错误位置数组，pos_count为错误个数 // sigma: 错误位置多项式系数，sigma[deg]为最高次系数 int chien_search(int *sigma, int deg, int *error_pos, int n, int *alpha_inv) { int count = 0; // 初始化values[i] = sigma[i] * alpha^(i*1) int values[deg + 1]; for (int i = 0; i <= deg; i++) { values[i] = sigma[i]; } for (int pos = 0; pos < n; pos++) { int sum = 0; for (int i = 0; i <= deg; i++) { sum ^= values[i]; } if (sum == 0) { error_pos[count++] = pos; // 该位置出错 } // 每个values[i]乘以alpha^i for (int i = 0; i <= deg; i++) { values[i] = gf_mul(values[i], alpha_pow[i]); } } return count; }这里要特别留意位置索引方向。如果接收码字第0位是最高位（通常通信约定），而数组索引0是数组第一个元素（通常是码字的最高位），需要统一。我在做二维码解析时吃过亏，打印出来错误位置后，发现纠错后数据依然不对，最后发现是Chien搜索的索引少加了一个偏移，导致从1计数还是从0计数差了一位。
4.5 完整译码流程示例
把以上模块串起来，一个可用的BCH(15,7,5)译码器如下：
int bch_decode(unsigned char *received, int len) { int syndrome[4]; // 2t=4 compute_syndrome(received, len, syndrome, 2); if (syndrome[0] == 0 && syndrome[1] == 0 && syndrome[2] == 0 && syndrome[3] == 0) { return 0; // 无错 } int sigma[3] = {0}; // t=2，最高次数为2 berlekamp_massey(syndrome, 2, sigma); int error_pos[2] = {0}; int count = chien_search(sigma, 2, error_pos, len); if (count > 2) { return -1; // 超过纠错能力 } for (int i = 0; i < count; i++) { received[error_pos[i]] ^= 1; // 翻转错误比特 } return count; }这段代码只适合m=4、t=2的特定场景。真正的通用实现要动态分配数组、根据m和n生成域表，但核心逻辑完全一致。
5. 工程化落地：内存、性能与错误处理
5.1 查表生成的时机与内存占用
BCH的参数一动，生成多项式和GF(2^m)表全都要重算。我的习惯是在初始化时一次性生成所有表，包括gf_log、gf_antilog、alpha_pow、alpha_inv，甚至编码用的字节查表。在资源紧张的MCU上，这些表可能是ROM还是RAM要仔细规划。
以m=13为例，域大小8192，log和antilog表各8192个元素，用uint16_t存储，大约32KB。多数MCU放得下，但你要直接定义一个uint16_t gf_antilog[8192]在栈上就完蛋了，栈直接爆掉。必须用static或const，放在全局区。
5.2 对多码长支持的封装设计
实际项目中码长往往不止一种。比如一个NAND驱动会同时支持512字节和2048字节的页大小，对应BCH码参数也不同。建议定义结构体：
typedef struct { int m; // 域参数 int n; // 码长 int k; // 信息位长度 int t; // 纠错能力 uint16_t *gf_log; uint16_t *gf_antilog; uint32_t gen_poly; // 生成多项式 } bch_control;所有编解码函数第一个参数传这个结构体，不同码长通过不同实例管理。这样既能避免全局变量污染，也方便支持多个通道同时编解码。
5.3 编译期与运行期的性能实测
我在STM32F407上实测过BCH(15,7,5)和BCH(255, 223, 4)的软件实现。小码单次编码不到1微秒，译码在无错时也就几微秒。但大码t=8的BCH(1023, 863)译码，无表优化时需要几毫秒，优化后大约几百微秒。对实时性要求高的场景，务必使用查表法和循环展开。
性能优化优先级建议：
- 有限域乘除必须查表，绝不能在循环里逐位乘。
- Chien搜索循环里，避免每次计算alpha幂次乘积，用增量乘法。
- 在可能的情况下，把2t个伴随式并行计算，减少循环次数。
- 用短整型而不是int存储域元素，减少内存带宽。
注意：有些编译器会为了优化把
for循环自动向量化，但BCH的异或操作很难向量化。可以用__attribute__((optimize("O3")))在函数级别强制优化，实测有效。
6. 常见问题与调试技巧实录
6.1 编码结果和硬件ECC对不上
这种情况十有八九是生成多项式字节序问题。硬件引擎手册里给的多项式可能写成x^8+x^7+x^6+x^4+1，但寄存器里是低位对齐还是高位对齐，必须看时序图。解决方法是先编码一个全零信息序列，得到校验位，再和硬件输出的已知校验位比对，立刻能判断出转换方向。
6.2 译码器纠错后比特反而变多
我遇到过很多次，尤其是从MATLAB移植到C时。MATLAB的索引从1开始，C的索引从0开始，Chien搜索得到的位置直接减1才是C语言数组下标。另外，MATLAB里的poly向量表示顺序和C数组相反，手工转换时低次项和高次项容易颠倒。
6.3 无错码字却伴随式非零
这通常意味着接收码字长度和生成多项式码长不匹配。比如你按BCH(15,7,5)编码，但接收端把数据当作16位数组处理，多读了一位或者少读了一位。在工程里，码字是按字节存储的，存在填充位混乱。建议在发送端和接收端都用同一套比特流转换函数，并打印前几个码字对照检查。
6.4 查表法在MCU上跑飞
查表法如果定义了大数组但没有声明为静态，极容易把栈踩爆。我经历过一次诡异现象：编码函数调用没问题，但译码函数一调用就进HardFault。最后查出来是gf_antilog表定义在函数内部，16KB局部数组把栈击穿。改成static后问题消失。
6.5 如何自测BCH代码是否正确
没有现成硬件时，我的自测方法是：随机生成一段信息，编码得到码字；随机翻转t位（或少于t位），译码后比对是否恢复；再翻转t+1位，确认译码器返回错误或拒绝纠正。写一个循环测试1000次，如果全通过，基本可以放心集成到项目里。
// 自测伪代码 for (int test = 0; test < 1000; test++) { random_info(bits, K); bch_encode(bits, parity); memcpy(codeword, bits, K); memcpy(codeword + K, parity, PARITY_LEN); int flipped = random() % t + 1; for (int i = 0; i < flipped; i++) { codeword[random() % N] ^= 1; } int ret = bch_decode(codeword, N); assert(ret == flipped); assert(memcmp(codeword, original_codeword, N) == 0); }这个自测能同时检验编码、伴随式、BM算法和Chien搜索是否正确。我在移植算法到新平台时，每次都先跑一遍这个测试，比单测好使。
7. 再分享一个实用技巧：如何把BCH代码复用为RS码
BCH和RS码的区别只在符号域：BCH每个符号1比特，GF(2)上运算；RS每个符号m比特，GF(2^m)上运算。如果你把BCH的每比特操作抽象成“符号操作”，那么GF(2)的符号就是1位，而RS的符号就是m位。实际上很多开源库会把两者写同一套框架，只改域表和符号宽度。
在C语言里，可以把gf_mul和gf_add封装成函数指针，当符号域是1比特时，gf_mul就是逻辑与，gf_add就是异或。这样做的好处是，以后如果要做RS码或者扩域BCH，不需要重写编解码主逻辑。
嵌入式项目里，我建议把BCH编解码做成一个独立模块，不依赖操作系统也不依赖具体驱动，输入输出都通过比特数组接口。调试时写一个命令行工具传入十六进制字符串，输出带校验位的码字，这样既方便验证，也方便和MATLAB/Octave模型对照。
从数学公式到可落地的C代码，BCH最大的门槛其实是域运算抽象。把GF(2^m)的乘法、幂运算想清楚，编码只是除法，译码只是解方程。希望这篇笔记能帮你少走一些弯路。
本文还有配套的精品资源，点击获取
