简介为满足通信、存储方向学习者掌握Golay码纠错原理与C实现的需求这份压缩包提供了一套Visual Studio下的Golay码译码器完整工程内容涵盖工程配置、核心算法代码及可直接运行验证的可执行程序。包内共28个文件、2.23MB既有golay.h、StdAfx.h等4个头文件和golay.cpp、golayDlg.cpp等3个cpp源文件也包含obj/pdb/exe等编译生成文件和dsp/dsw等工程说明文件便于对照源码与运行结果进行调试学习。已有586人学习或下载尤其适合本科课程设计、毕业设计及自学纠错编码时作为参考工程。通过阅读这套实现可以完整走通23位信息位与11位校验位组成的34位码字译码流程理解前处理、奇偶校验、错误定位、错误校正和后处理各环节如何落地为具体函数与数据结构在此基础上还能结合理论进一步优化解码速度、增强错误检测能力或降低内存开销。1. Golay码译码C实现从伴随式计算到查表纠正的完整链路拿到 Golay 码译码的 C 实现时我最先找的是查表逻辑——不是因为它简单而是因为它把纠错码从“黑匣子”变成了数组查下标。Golay(23,12,7) 这套参数在卫星遥测、数据记录仪和窄带无线链路里很常见一个 23 位码字能纠正最多 3 位随机错误在信噪比不高的场景里相当于数据抢救。这份工程适合要快速集成纠错能力的嵌入式开发者也适合想从源码层面弄懂 BCH/Golay 译码原理的通信方向学生。整份实现不依赖第三方库任何一个带 C17 编译器的人都能直接跑起来。2. 工程结构与技术选型一台普通电脑就能跑的Golay译码器2.1 Golay(23,12,7) 的参数决定了代码怎么写Golay 码是 BCH 码家族里少有的完备码。码长 n23信息位 k12校验位 r11最小汉明距离 d7所以它能纠正 t floor((7-1)/2) 3 位错误。所谓完备是指所有可纠正错误图样从 0 到 3 位错误加起来正好等于 1 C(23,1) C(23,2) C(23,3) 2048而 2^11 也是 2048。这说明 11 位伴随式与“距离某个合法码字不超过 3 的错误图样”是一一对应的不需要做二次匹配。这个性质是后面查表译码可行的前提。这个参数对 C 实现有三个直接影响。第一伴随式可以用一个 uint16_t 保存查表索引最大 2047表长固定 2048。第二信息位只有 12 位和多数微控制器的字长不天然对齐代码里统一用 uint32_t 作为中间容器避免用 vector 这类位压缩容器给自己挖坑。第三因为码是非二进制的 BCH 子类生成多项式可以写成一个十六进制常量编码和译码共用同一个多项式除法省掉一整套矩阵运算代码。2.2 工程目录头文件、源码和构建脚本怎么分工整个项目没有引入一个开源依赖核心代码文件也少。我拆过之后目录结构大概是这样的golay_decode/ ├── CMakeLists.txt ├── README.md ├── include/ │ └── golay23.h └── src/ ├── golay23.cpp ├── table_build.cpp ├── golay24.cpp └── main.cppinclude 下的 golay23.h 放对外接口golay23.cpp 实现编码、伴随式计算和译码table_build.cpp 单独拆出来做错误图样表和伴随式表的构建golay24.cpp 是对扩展 Golay(24,12,8) 的增强main.cpp 只负责读入测试数据并打印结果。把建表单独放一个文件是因为建表跑一次就够了没必要每次译码时重建也不太适合放进构造函数那会让单测和性能测试的权限边界变得很模糊。接口只暴露四个方法encode(uint16_t msg)、syndrome(uint32_t r)、build_table()和decode(uint32_t received, uint32_t corrected)。这样设计是为了让调用方不需要了解 Golay 码的循环移位细节。消息用 uint16_t 但只用低 12 位码字用 uint32_t 但只用低 23 位伴随式用 uint16_t 但只用低 11 位。所有越界位用掩码0x7FFFFF和0x7FF在入口处清掉避免上层传一个带高位脏数据的值把表索引搞坏。2.3 CMake 构建配置不需要第三方库的静态库构建用 CMake 就行C 标准用 C17因为要用 std::array、std::bitset 这些容器。一个最简的 CMakeLists.txt 长这样cmake_minimum_required(VERSION 3.10) project(golay_decode CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_library(golay STATIC src/golay23.cpp src/table_build.cpp src/golay24.cpp ) target_include_directories(golay PUBLIC include) add_executable(golay_decode src/main.cpp) target_link_libraries(golay_decode PRIVATE golay)这里故意用 STATIC 库因为 Golay 译码是链路层里很小的一段逻辑静态库方便后续直接嵌进调制解调工程如果你要把它做成动态库或独立服务改成 SHARED 也不影响接口。编译命令就三条mkdir build cd build cmake .. make。我在实际调试时会加-DCMAKE_BUILD_TYPEDebug这样 assert 会生效表格构建阶段如果有伴随式冲突能立刻崩出来而不是带着脏数据在线上跑。位序也要在这里统一约定。代码里约定bit 0对应多项式里的常数项bit 22对应最高次项 x^22。生成多项式 g(x) x^11 x^10 x^6 x^5 x^4 x^2 1 用整数 0xC75 表示最高位 bit11 为 1。所有位移操作都基于这个约定。如果换一套“左边是低位”的位序不仅生成多项式的常数要跟着反转表构建出来的伴随式和错误图样也会整体乱七八糟这一点到第 5 章还会单独说。3. 核心模块拆解编码、伴随式计算与查表译码的完整链路3.1 系统码编码信息位在前校验位在后Golay(23,12,7) 用系统码形式组织码字高 12 位直接放原始信息低 11 位放校验位。编码的本质是求m(x) * x^11 mod g(x)的余数这个余数就是校验位。代码可以写成非常短的形式// include/golay23.h #pragma once #include cstdint #include array namespace golay { inline constexpr uint32_t POLY 0xC75; inline constexpr int N 23; inline constexpr int K 12; inline constexpr int R 11; inline constexpr uint32_t MASK23 0x7FFFFF; inline constexpr uint16_t MASK11 0x7FF; uint32_t encode(uint16_t msg); uint16_t syndrome(uint32_t r); void build_table(); bool decode(uint32_t received, uint32_t corrected); }// src/golay23.cpp uint32_t encode(uint16_t msg) { uint32_t c (static_castuint32_t(msg) 0xFFF) R; uint32_t rem c; for (int i N - 1; i R; --i) { if ((rem i) 1u) { rem ^ (POLY (i - R)); } } return c | (rem MASK11); }逻辑说明先把 12 位信息左移 11 位高 12 位变成信息位低 11 位补零。然后对整体用生成多项式做模 2 长除法循环从最高位 i22 一路除到 i11每次发现当前位为 1就用 POLY 左移对齐后异或把该位消掉。最终 rem 里剩下的低 11 位就是余数拼回 c 的低 11 位完成系统编码。参数说明msg 只取低 12 位传超过 0xFFF 的值会被掩码POLY 是 0xC75即生成多项式去掉常数项后的 11 位系数循环起点是 22因为一个 23 位码字最高次项是 x^22终点是 11因为余数次数必须低于 g(x) 的次数 11。如果你把这段代码和 CRC 的软件实现放在一起对比会发现它们几乎是同一个结构。3.2 伴随式计算同一个除法函数复用伴随式是接收码字是否能通过校验的“指纹”。对循环码来说接收多项式 r(x) 对 g(x) 取余余数就是伴随式。合法码字取余一定是 0有错误时余数非零且与错误图样一一对应。计算函数和编码里的除法几乎一致uint16_t syndrome(uint32_t r) { uint32_t rem r MASK23; for (int i N - 1; i R; --i) { if ((rem i) 1u) { rem ^ (POLY (i - R)); } } return rem MASK11; }逻辑说明先把 23 位以上的脏位移除然后从高位到低位逐项消去最终余数就是伴随式。由于(23,12)的伴随式只有 11 位所以返回值用 uint16_t 足够。这个函数同时被编码、建表和译码调用所以生成多项式必须全局唯一否则编码和译码会各自拿到一套不相容的伴随式。参数说明r 可以是编码结果也可以是带错误的接收字返回值等于 0 表示接收字是一个合法码字不等 0 表示存在错误。这里有个容易踩的细节伴随式非零并不代表错误位数等于伴随式里 1 的个数伴随式重量和错误重量没有直接关系。很多人第一次写 Golay 译码时在这里绕进去后面避坑章会展开。3.3 错误图样表2048 个条目的构建因为 Golay(23,12,7) 是完备码我们只需要把重量 0 到 3 的所有 23 位错误图样枚举出来算好每个图样对应的伴随式反查时就能通过伴随式拿到错误图样。这个表只有 2048 个条目构建代码可以直接暴力枚举std::arrayuint32_t, 2048 syn_table; void build_table() { syn_table.fill(0); auto add [](uint32_t e) { uint16_t s syndrome(e); assert(syn_table[s] 0 || syn_table[s] e); syn_table[s] e; }; for (int i 0; i N; i) add(1u i); for (int i 0; i N; i) for (int j i 1; j N; j) add((1u i) | (1u j)); for (int i 0; i N; i) for (int j i 1; j N; j) for (int k j 1; k N; k) add((1u i) | (1u j) | (1u k)); }逻辑说明三次嵌套枚举覆盖所有 1 位、2 位、3 位错误组合。add函数把错误图样当作一个“虚拟接收字”用同一个 syndrome 函数算出伴随式然后以伴随式为下标错误图样为值写进全局表。因为完备码的性质2048 个错误图样正好对应 2048 个伴随式不会有空槽也不会有两个不同错误图样挤在同一个伴随式上。如果 assert 触发说明生成多项式或位序选错了这是最快的一次自检。参数说明e的低 23 位中每个 1 bit 表示一个错误位置syn_table的索引是伴随式类型是 uint16_t但 C 数组下标会按 int 提升所以表长必须写 2048不能写成 4096。建表只需要一次应用启动时或静态初始化时执行即可。3.4 译码主流程查表、异或、返回收到一个 23 位码字后译码要做的事情只有三步算伴随式、查错误图样、异或纠正。完整实现如下bool decode(uint32_t received, uint32_t corrected) { uint16_t s syndrome(received); uint32_t e syn_table[s]; if (e 0 s ! 0) { return false; } corrected (received MASK23) ^ e; return true; }逻辑说明先算伴随式 s接着直接用 s 当数组下标拿到错误图样 e。如果 s 为 0说明没有错误e 也是 0修正结果等于原码字。如果 s 非零且 e 也是 0说明伴随式没有对应的可纠错误图样这在基本码里理论不会发生但保留这个分支能让同一个函数扩展到(24,12,8)时使用。参数说明corrected 是引用传出调用方不需要再手动处理位掩码。由于接收字可能带有上层协议的高位脏数据函数内部统一用 received MASK23 取低 23 位避免表索引被高位置 1 后越界。3.5 扩展 Golay(24,12,8)奇偶校验位怎么处理扩展码比基本码多一个全局奇偶校验位最小距离从 7 提到 8于是除了纠正 3 位错误还能检测 4 位错误。工程上最常见的做法不是直接做 24 位查表而是“先译后查”bool decode_ext(uint32_t r, uint32_t c) { uint32_t parity (r 23) 1u; uint32_t c23 0; if (!decode(r MASK23, c23)) return false; uint32_t p __builtin_parity(c23); if (p ! parity) return false; c c23 | (parity 23); return true; }逻辑说明先把第 23 位的全局奇偶位单独取出来对低 23 位走一遍标准 Golay 译码。译码完成后用纠正后的 23 位码字重新计算奇偶位与收到的奇偶位比对。一致时认为纠错成功把奇偶位原样拼回去不一致说明错误可能落在奇偶位本身也可能是发生了 4 位错误超出纠错能力返回 false 交给上层重传。参数说明奇偶位存储在码字第 23 位与低 23 位不重叠__builtin_parity是编译器内置函数如果编译环境不支持可以用一个 5 行的小循环代替。这个扩展码的处理方式在遥测链路里非常实用因为你往往宁可在接收端丢一帧也不要把已经纠正了一半的数据错判成对的。4. 三种译码思路对比查表法、捕错译码与代数搜索的取舍4.1 查表法速度最快工程首选第 3 章实现的查表法本质是把 2048 种可纠错误图样离线算好译码时一次多项式除法加一次数组访问。在 C 里数组访问是 O(1)所以译码一个码字的速度主要由三十次左右的移位异或决定。内存占用也只有 2048 乘 4 字节等于 8KB对 MCU 来说完全能接受。适合任何追求确定性时延的场合比如帧同步、遥测帧头、数传文件片段。这也是我会优先推荐给项目集成的方案。查表法的缺点是如果错误图样表在内存紧张的平台上也是负担8KB 虽然不大但换到只有 2KB RAM 的芯片上就得想别的办法。另外查表法只能纠正最多 3 位错误4 位以上错误会出现伴随式“映射到别的错误图样”的可能这在完备码上叫误纠。工程上通常搭配 CRC 来做二次校验而不是让 Golay 独自承担所有错误处理。4.2 捕错译码循环移位的小型化方案捕错译码是循环码的经典硬件算法它不需要错误图样表只依赖伴随式。思路是不断循环移位接收码字直到伴随式的汉明重量不大于 3这时认为错误图样已经集中在校验位伴随式本身就可以当作错误图样来纠正。核心循环bool decode_capture(uint32_t r, uint32_t c) { for (int shift 0; shift N; shift) { uint16_t s syndrome(r); if (std::popcount(s) 3) { uint32_t corrected (r MASK23) ^ s; c rotate_right(corrected, shift); return true; } r rotate_left(r, 1); } return false; }逻辑说明第一次循环先算伴随式如果伴随式重量不大于 3就认为错误已经落在低 11 位校验区。这时伴随着本身就是错误图样直接异或到当前接收字上。但此时纠正出来的是“循环移位后的码字”必须再按 shift 次循环右移回去才能得到最终码字。循环往复最坏 23 次所以速度比查表慢一个量级。参数说明rotate_left 和 rotate_right 必须在 23 位范围内操作不要碰到第 23 位否则把无关数据卷进来了。std::popcount是 C20 标准库函数如果在 C17 环境可以用编译器内置的__builtin_popcount。这个算法的前提条件是“所有可纠错误图样在某个循环移位后能落入校验区”Golay(23,12) 满足这个性质但如果你换一个生成多项式或非循环码这个条件不再自动成立上线前必须做全量错误图样验证。4.3 代数搜索两错伴随式表加逐位扣除不想枚举全部 2048 个 3 位错误图样但又想保留查表的确定性可以用“两错表加逐位扣除”。只预编码重量 1 和重量 2 的错误图样共 276 条遇到 3 位错误时逐个假设一个错误位置把它的伴随式从总伴随式里扣掉剩下部分的伴随式如果能查到一个重量 2 的错误图样就凑齐了三位错误。核心代码std::arrayuint32_t, 2048 pair_table; void build_pair_table() { pair_table.fill(0); auto add [](uint32_t e) { pair_table[syndrome(e)] e; }; for (int i 0; i N; i) add(1u i); for (int i 0; i N; i) for (int j i 1; j N; j) add((1u i) | (1u j)); } bool decode_search(uint32_t r, uint32_t c) { uint16_t s syndrome(r); if (s 0) { c r MASK23; return true; } if (pair_table[s] ! 0) { c (r MASK23) ^ pair_table[s]; return true; } for (int i 0; i N; i) { uint32_t si syndrome(1u i); uint32_t two_err pair_table[s ^ si]; if (two_err ! 0) { uint32_t e (1u i) | two_err; c (r MASK23) ^ e; return true; } } return false; }逻辑说明pair_table 的索引仍然是伴随式但值只存重量 1 和 2 的错误图样。3 位错时先扣掉第 i 位单错的伴随式剩余两个错误的伴随式s ^ si应该能在 pair_table 里查到对应图样(1u i) | two_err就是完整的三位错误图样。最坏需要循环 23 次每次查一次 2048 的数组所以速度比纯查表慢但构建表时只需要枚举 276 个图样建表时间短。参数说明如果 s 为 0 要先返回否则 pair_table[0] 等于 0会误进入后面的单错排查。这个方案的表内存和完整查表法一样都是 8KB因为数组大小由伴随式索引空间决定如果你改用 std::unordered_map 只存 276 条内存能降下来但最坏访问时间不再是常数实时性会变差。4.4 性能对比与选择建议三种方法各有取舍我用一张表总结它们的参数差异算法译码最坏耗时建表时间内存占用失败判断查表法1 次除法加 1 次查表枚举 2048 条8KB几乎不失败捕错译码23 次除法无几百字节循环结束仍无解代数搜索最多 23 次查表枚举 276 条8KB 或哈希变体查不到对应图样如果做产品我会选查表法理由是时延可预估代码可读性最好。捕错译码适合硬件实现因为它不需要存储表适合做在 FPGA 或专用译码芯片里。代数搜索适合你对 3 位错误图样枚举这件事非常敏感、想在代码里减少枚举逻辑的场景但它本质还是在时间和空间之间做交换。Golay 码的译码场景通常不是超高频三种方法都能满足速率真正的瓶颈往往是上层通信协议里的交织和去交织。5. 避坑记录实现Golay译码时最容易翻车的5个细节5.1 伴随式表开成 4096一半空间是空的现象译码结果偶尔正确偶尔把正确码字纠正成另一个合法码字但查表时数组越界不崩程序像个玄学故障。原因基本码(23,12,7) 的伴随式只有 11 位范围 0 到 2047所以表长必须 2048。有人把扩展码(24,12,8) 的 12 位校验位混进来以为伴随式范围是 4096结果表填了一半空槽另一半未初始化查表落到随机地址上。解决用std::arrayuint32_t, 2048定死长度建表时加 assert 检查每个伴随式都被填过且只被填一次。5.2 生成多项式 0xC75 和 0xAE3 混用现象编码用一套多项式译码用另一套结果伴随式永远是乱的错误图样表建不出来断言直接崩。原因二进制 Golay 码有两个合法生成多项式一个是 0xC75另一个是 0xAE3。两者都能生成(23,12,7) 循环码但产生的校验矩阵位权不同不能混用。网上能找到的 Golay 译码表不一定和你的多项式来自同一个体系。解决整个代码库只允许出现一个 POLY 常量编码、伴随式、建表全部引用同一个常量。从外部拷贝表时先用encode(0xABC)再syndrome(code)验证结果必须为 0。5.3 位序约定不一致bit0 和 bit22 方向反了现象build_table 不冲突但传给译码的真实数据总是差一个镜像错误的 bit 位置全部左右颠倒。原因有人把多项式十六进制转成整数时习惯把打印出来的 MSB 当最高位但实际代码里的位移方向却按 LSB 处理。两者并不等价生成多项式一旦反转整个表就变成“镜像表”。解决在头文件注释里写死“bit0 常数项bit22 x^22 项”并写一个自检函数对任意 12 位消息 msyndrome(encode(m))必须恒等于 0。这个断言会在每次 Debug 构建时自动跑一遍。5.4 std::vector 当普通数组用现象编译全过但运行到赋值语句时数据莫名被截断有时候改了一个 bit相邻 bit 也跟着变。原因std::vectorbool是 C 里出了名的位压缩容器它的operator[]返回的是一个代理对象不是bool不能和 uint32_t 的位操作直接混用。用auto去接一个元素拿到的是代理引用赋值和转换语义都和你预期不一样。解决码字、错误图样、表一律用std::arrayuint32_t, 2048或std::vectoruint32_t。只在打印或者做可视化调试时才把 uint32_t 临时转成std::bitset23展示。5.5 扩展 Golay 先做奇偶校验把 3 位错误直接丢了现象基本码译码正常扩展码译码时明明只有 3 位错误也能纠正却被上层判定为“数据错误”丢掉丢包率反而更高。原因3 位错误是奇数个错会让 24 位码字的整体奇偶位翻转。如果先拿接收码字的整体奇偶校验和自己的全局奇偶位比对此时一定不匹配于是提前返回失败根本走不到译码环节。但纠正后的码字是合法码字奇偶校验应该重新计算。解决调整流程先对低 23 位做基本 Golay 译码再用纠正结果重新计算奇偶位。这样既保住了 3 位纠错能力又能顺带处理奇偶位本身出错的情况。这五个坑里最坑的是位序和多项式混用因为它们不会让程序崩溃只会让数据错得很有规律。每次改完代码我都会强制跑一遍“先编码、再随机注入 3 位错、再译码”的往返测试确认无误后才会提交。6. 二次开发与改造把固定译码器变成可配置模块要做二次开发第一步是把散落的常量和依赖关系收敛。目前 POLY、N、K、R 都是 namespace 里的 constexpr如果你只需要一个固定配置这个设计已经够好。但如果要同时支持(23,12,7) 和(24,12,8)建议把译码器包装成一个类构造时传入是否使用扩展码的开关内部共用同一套基本译码表。这样调用方只依赖一个接口不需要关心奇偶位处理逻辑。第二个值得加的是自测函数。Golay 译码最怕的不是算法复杂而是改着改着把位序改坏了。我一般会在 main 里加一个全量验证遍历所有 12 位消息编码后分别注入 1 到 3 位错误再译码比对原始消息。代码可以这样写bool self_test() { build_table(); for (uint16_t m 0; m 0x1000; m) { uint32_t codeword encode(m); if (syndrome(codeword) ! 0) return false; for (int i 0; i 23; i) { uint32_t corrupted codeword ^ (1u i); uint32_t decoded 0; if (!decode(corrupted, decoded)) return false; if (decoded ! codeword) return false; } // 2位和3位错误注入同理这里省略循环展开 } return true; }这段测试会在几分钟内跑完它能保证你改完任何一行位移操作后表、编码、译码、掩码仍然是一个整体。再加一层业务封装时可以把译码结果和上层 CRC 校验结果捆绑只有当 CRC 通过时才认为这一帧可信否则标记为不可纠正。第三个改造重点是配合交织器使用。Golay 码擅长纠正随机分布的单比特错误如果信道里是突发错误比如一连串 5 个 bit 被噪声打掉Golay 的 3 位纠错能力会立刻失效。常见做法是在 Golay 之前加一个行写列读的交织器把连续错误拆散到不同码字里让每个 Golay 码字最多只承担 1 到 2 个错误。这个改动的数据流顺序是消息先按行写入交织缓冲区再按列读出送入 Golay 编码接收端先 Golay 译码再按列写入、按行读出。改动只发生在 buffer 索引计算上和译码核心完全解耦。从那以后我每次改完译码器都会先跑一遍全错误图样的往返测试再合代码因为纠错码这东西平时不显眼真到链路上丢包时再后悔就晚了。希望帮到你。本文还有配套的精品资源点击获取
