4. 循环码：从代数基础到工程实现
循环码这东西，我第一次接触时觉得挺玄乎。后来在项目中调了三天三夜的译码器，才真正理解它的精妙。说白了，循环码就是线性分组码里的一类特殊子集——它的码字循环移位后，仍然是合法码字。这个性质让编码和译码电路变得异常简洁。
4.1 循环码的代数基础
我们先从多项式说起。你想想看，一个长度为 n 的码字 (cn-1, cn-2, ..., c0)，可以对应一个多项式：
C(x) = cn-1xn-1 + cn-2xn-2 + ... + c1x + c0系数 ci 取自 GF(2) 域，也就是 0 或 1。为什么用多项式？因为循环移位在多项式世界里就是乘以 x 再模 xn-1。举个例子：
码字: (1 0 1 1) → C(x) = x³ + x + 1
左移一位: (0 1 1 1) → x·C(x) = x⁴ + x² + x
模 x⁴-1 后: x² + x + 1 → (0 1 1 1) ✓我在项目中遇到过一个问题：用软件实现时，多项式乘法效率很低。后来改用查表法，把模运算结果预计算好，速度提升了近 10 倍。
核心结论：循环码的代数结构建立在多项式环 GF(2)[x]/(xn-1) 上。所有码字多项式都是某个生成多项式 g(x) 的倍式。
4.2 生成多项式——循环码的灵魂
生成多项式 g(x) 是循环码的核心。它必须满足：
- g(x) 是 xn-1 的因式
- deg(g(x)) = n - k，其中 k 是信息位长度
- g(x) 的最高次项系数为 1
举个例子，对于 (7,4) 循环码：
x⁷ - 1 = (x³ + x + 1)(x³ + x² + 1)(x + 1)
常用的生成多项式：g(x) = x³ + x + 1
信息位: (1 0 1 1) → m(x) = x³ + x + 1
编码: c(x) = m(x)·g(x) = (x³ + x + 1)(x³ + x + 1) = x⁶ + x⁴ + x² + x + 1
码字: (1 0 1 0 1 1 1)我的经验：选择生成多项式时，不仅要考虑纠错能力，还要考虑电路复杂度。我曾经为了追求理论上的最优纠错性能，选了一个高次生成多项式，结果硬件面积超标了。后来改用次优但电路更简洁的多项式，反而整体效果更好。
4.3 循环码的编码电路
编码电路的核心是一个线性反馈移位寄存器（LFSR）。结构如下：
以 g(x) = x³ + x + 1 为例的 (7,4) 编码器：
信息位输入 → [⊕] → [D] → [D] → [D] → 码字输出
↑ ↑ ↑
└─────┴─────g₁────┘
其中 D 表示触发器，⊕ 表示异或门
g₁ 对应 g(x) 中 x¹ 的系数编码步骤很简单：
- 信息位从高位到低位依次输入
- 前 k 个时钟周期，信息位直接输出，同时送入 LFSR
- 后 n-k 个时钟周期，LFSR 中的校验位依次输出
我记得第一次用 Verilog 写这个电路时，把反馈连接搞反了。仿真结果全是错的。后来画了个时序图，一个周期一个周期地推，才找到问题。嗯，这里要注意：反馈系数是从低次到高次排列的，别搞混了。
4.4 循环码的译码
译码比编码复杂得多。经典的译码流程是：
接收码字 → 计算伴随式 → 查找错误图样 → 纠错 → 输出伴随式计算：用接收多项式 r(x) 除以 g(x)，余数就是伴随式 s(x)。
r(x) = c(x) + e(x) （e(x) 是错误多项式）
s(x) = r(x) mod g(x) = e(x) mod g(x)如果 s(x) = 0，说明没有错误（或者错误不可检测）。否则，根据 s(x) 查表得到错误位置。
避坑指南：我曾经在译码器里犯过一个低级错误——把伴随式寄存器的初始值设成了全 1 而不是全 0。结果所有码字都被判定为有错误，系统直接瘫痪。调试了两天才发现这个 bug。
4.5 BCH码简介
BCH码是循环码的一个重要子类。它的厉害之处在于：可以预先指定纠错能力 t，然后构造出相应的生成多项式。
构造方法：
- 在 GF(2m) 上找一个本原元 α
- 取 α, α², ..., α2t 的最小多项式
- 这些最小多项式的最小公倍式就是生成多项式
举个例子，构造一个能纠 1 个错误的 BCH(15,11) 码：
取 m=4, GF(2⁴) 上的本原多项式 p(x) = x⁴ + x + 1
α 的最小多项式 m₁(x) = x⁴ + x + 1
g(x) = m₁(x) = x⁴ + x + 1
码长 n = 2⁴ - 1 = 15
信息位 k = 15 - 4 = 11BCH码的译码比普通循环码复杂，需要用到 Berlekamp-Massey 算法或 Chien 搜索。我在一个卫星通信项目中用过 BCH(63,51) 码，纠 2 个错误，性能相当稳定。
实用建议：BCH码在短码长、中等纠错能力场景下性价比很高。但如果需要纠很多位错误，建议考虑 LDPC 或 Turbo 码。没有万能的编码方案，只有最适合的。
循环码的工程实现，说白了就是多项式运算的硬件化。掌握了代数基础，编码电路就是几个触发器和异或门的事。译码稍微复杂些，但核心思想不变——用生成多项式做除法，用余数判断错误。
我个人觉得，学习循环码最好的方式就是动手搭一个 (7,4) 编码器。用面包板、74 系列芯片，或者用 Verilog 都行。亲手调通一次，比看十遍书都管用。