Golay码译码C++实现：查表纠错完整链路解析

简介：为满足通信、存储方向学习者掌握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 译码原理的通信方向学生。整份实现不依赖第三方库，任何一个带 C++17 编译器的人都能直接跑起来。

2. 工程结构与技术选型：一台普通电脑就能跑的Golay译码器

2.1 Golay(23,12,7) 的参数决定了代码怎么写

Golay 码是 BCH 码家族里少有的完备码。码长 n=23，信息位 k=12，校验位 r=11，最小汉明距离 d=7，所以它能纠正 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.cpp

include 下的 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++ 标准用 C++17，因为要用 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_TYPE=Debug，这样 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_cast<uint32_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 长除法，循环从最高位 i=22 一路除到 i=11，每次发现当前位为 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::array<uint32_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是 C++20 标准库函数，如果在 C++17 环境，可以用编译器内置的__builtin_popcount。这个算法的前提条件是“所有可纠错误图样在某个循环移位后能落入校验区”，Golay(23,12) 满足这个性质，但如果你换一个生成多项式或非循环码，这个条件不再自动成立，上线前必须做全量错误图样验证。

4.3 代数搜索：两错伴随式表加逐位扣除

不想枚举全部 2048 个 3 位错误图样，但又想保留查表的确定性，可以用“两错表加逐位扣除”。只预编码重量 1 和重量 2 的错误图样，共 276 条；遇到 3 位错误时，逐个假设一个错误位置，把它的伴随式从总伴随式里扣掉，剩下部分的伴随式如果能查到一个重量 2 的错误图样，就凑齐了三位错误。核心代码：

std::array<uint32_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 性能对比与选择建议

三种方法各有取舍，我用一张表总结它们的参数差异：

如果做产品，我会选查表法，理由是时延可预估，代码可读性最好。捕错译码适合硬件实现，因为它不需要存储表，适合做在 FPGA 或专用译码芯片里。代数搜索适合你对 3 位错误图样枚举这件事非常敏感、想在代码里减少枚举逻辑的场景，但它本质还是在时间和空间之间做交换。Golay 码的译码场景通常不是超高频，三种方法都能满足速率，真正的瓶颈往往是上层通信协议里的交织和去交织。

5. 避坑记录：实现Golay译码时最容易翻车的5个细节

5.1 伴随式表开成 4096，一半空间是空的

现象：译码结果偶尔正确，偶尔把正确码字纠正成另一个合法码字，但查表时数组越界不崩，程序像个玄学故障。原因：基本码(23,12,7) 的伴随式只有 11 位，范围 0 到 2047，所以表长必须 2048。有人把扩展码(24,12,8) 的 12 位校验位混进来，以为伴随式范围是 4096，结果表填了一半空槽，另一半未初始化，查表落到随机地址上。解决：用std::array<uint32_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 位消息 m，syndrome(encode(m))必须恒等于 0。这个断言会在每次 Debug 构建时自动跑一遍。

5.4 std::vector 当普通数组用

现象：编译全过，但运行到赋值语句时数据莫名被截断，有时候改了一个 bit，相邻 bit 也跟着变。原因：std::vector<bool>是 C++ 里出了名的位压缩容器，它的operator[]返回的是一个代理对象，不是bool&，不能和 uint32_t 的位操作直接混用。用auto&去接一个元素，拿到的是代理引用，赋值和转换语义都和你预期不一样。解决：码字、错误图样、表一律用std::array<uint32_t, 2048>或std::vector<uint32_t>。只在打印或者做可视化调试时，才把 uint32_t 临时转成std::bitset<23>展示。

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 索引计算上，和译码核心完全解耦。

从那以后，我每次改完译码器，都会先跑一遍全错误图样的往返测试再合代码，因为纠错码这东西平时不显眼，真到链路上丢包时再后悔就晚了。希望帮到你。

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