4. 循环码原理：循环码定义、生成多项式、系统循环码编码、循环码译码
循环码这东西，说白了就是线性分组码里最实用的一类。我当年刚接触通信系统时，总觉得它跟普通分组码没啥区别，直到有一次在卫星通信项目里，发现循环码的移位特性让硬件实现变得极其简单——嗯，从那以后我就再也不敢小看它了。
4.1 循环码的定义
先给个严谨定义：一个线性分组码，如果任意一个码字循环移位后仍然是码字，那它就是循环码。你想想看，这个性质多漂亮。
数学上这么说：设 c = (c₀, c₁, ..., cₙ₋₁) 是一个码字，那么它的循环右移一位 c' = (cₙ₋₁, c₀, c₁, ..., cₙ₋₂) 也必须是码字。就这么简单。
核心性质：循环码是线性分组码 + 循环移位封闭性。这两个条件缺一不可。
我个人习惯把循环码想象成一个环。码字在环上转来转去，始终跑不出这个集合。这在工程上意味着什么？意味着编码器和译码器可以用移位寄存器来实现，成本低、速度快。
4.2 生成多项式
循环码的核心秘密，藏在一个多项式里——生成多项式 g(x)。我建议你把它理解为码字的"基因"。
定义是这样的：g(x) 是 xⁿ + 1 的一个 n-k 次因式。所有码字多项式 c(x) 都是 g(x) 的倍式，即：
c(x) = m(x) · g(x)其中 m(x) 是信息多项式，次数小于 k。
举个例子，对于 (7,4) 循环码，x⁷ + 1 可以分解为：
x⁷ + 1 = (x+1)(x³ + x + 1)(x³ + x² + 1)取 g(x) = x³ + x + 1，这就是一个生成多项式。它的次数是 3，正好等于 n - k = 3。
我的经验：选生成多项式时，记得查一下它的周期。如果周期不够长，码的性能会打折扣。我在一个物联网项目里吃过这个亏，后来改用本原多项式才解决问题。
4.3 系统循环码编码
系统码的意思是：信息位和校验位分开，信息位原封不动出现在码字里。这样做的好处是，译码时可以直接提取信息，不用做额外计算。
编码步骤其实就三步：
- 信息多项式移位：
xⁿ⁻ᵏ · m(x)，给校验位腾出位置 - 求余式：
r(x) = xⁿ⁻ᵏ · m(x) mod g(x)，这就是校验位 - 组合码字：
c(x) = xⁿ⁻ᵏ · m(x) + r(x)
看个具体例子。还是 (7,4) 码，g(x) = x³ + x + 1。假设信息位是 1011，对应 m(x) = x³ + x + 1：
第一步：x³ · m(x) = x⁶ + x⁴ + x³
第二步：做多项式除法
x⁶ + x⁴ + x³ 除以 x³ + x + 1
余式 r(x) = x + 1 → 校验位 011
第三步：码字 = 1011 011你看，信息位 1011 原封不动在前，校验位 011 在后。这就是系统码。
注意：多项式除法用的是模2加法，说白了就是异或运算。千万别用普通加法，否则结果全错。我曾经在调试时犯过这个低级错误，找了半天bug...
4.4 循环码译码
译码比编码复杂一些。核心思路是：用接收到的码字多项式 r(x) 除以 g(x)，看余式是不是零。
具体流程是这样的：
- 计算伴随式：
s(x) = r(x) mod g(x) - 查表或计算： 根据
s(x)确定错误图样e(x) - 纠错：
c(x) = r(x) - e(x)（模2减法就是加法）
为什么能纠错？因为 s(x) 只跟错误有关，跟发送的码字无关。你想想看，r(x) = c(x) + e(x)，而 c(x) 是 g(x) 的倍式，所以 s(x) = e(x) mod g(x)。
对于 (7,4) 码，伴随式有 2³ = 8 种可能。每种对应一个错误图样。比如：
| 伴随式 s(x) | 二进制 | 错误位置 |
|---|---|---|
| 0 | 000 | 无错误 |
| 1 | 001 | 第0位 |
| x | 010 | 第1位 |
| x+1 | 011 | 第2位 |
| x² | 100 | 第3位 |
| x²+1 | 101 | 第4位 |
| x²+x | 110 | 第5位 |
| x²+x+1 | 111 | 第6位 |
这个表怎么来的？其实就是把 xⁱ mod g(x) 算一遍。我建议你手算一次，印象会深很多。
4.5 循环码的工程实现
理论说完了，咱们看看实际怎么用。循环码最经典的应用是 CRC（循环冗余校验）。以太网、USB、WiFi 都在用。
下面是一个简单的 (7,4) 循环码编码器 Python 实现：
def cyclic_encode(info_bits, g_poly, n, k):
"""
系统循环码编码
info_bits: 信息位列表，长度 k
g_poly: 生成多项式系数列表，从高次到低次
n: 码长
k: 信息位长度
"""
# 信息多项式移位
shifted = info_bits + [0] * (n - k)
# 多项式除法求余式
temp = shifted[:]
for i in range(k):
if temp[i] == 1:
for j in range(len(g_poly)):
temp[i + j] ^= g_poly[j]
# 校验位就是余式
parity = temp[k:]
# 组合码字
codeword = info_bits + parity
return codeword
# 示例：g(x) = x³ + x + 1 → [1, 0, 1, 1]
g = [1, 0, 1, 1]
info = [1, 0, 1, 1]
code = cyclic_encode(info, g, 7, 4)
print(f"码字: {code}") # 输出 [1, 0, 1, 1, 0, 1, 1]工程建议：实际项目中别用这种逐位运算，效率太低。用查表法，一次处理一个字节。我在做嵌入式通信协议时，CRC查表法比逐位法快了将近10倍。
译码器实现稍微复杂点，但核心就是伴随式计算和错误定位：
def cyclic_decode(received, g_poly, n, k, syndrome_table):
"""
循环码译码（硬判决）
received: 接收序列
syndrome_table: 伴随式到错误图样的映射表
"""
# 计算伴随式
syndrome = [0] * (n - k)
temp = received[:]
for i in range(k):
if temp[i] == 1:
for j in range(len(g_poly)):
temp[i + j] ^= g_poly[j]
syndrome = temp[k:]
# 查表找错误图样
s_tuple = tuple(syndrome)
if s_tuple in syndrome_table:
error_pattern = syndrome_table[s_tuple]
# 纠错
corrected = [received[i] ^ error_pattern[i] for i in range(n)]
return corrected[:k] # 提取信息位
else:
# 不可纠错，返回原始信息位
return received[:k]这里有个关键点：伴随式查表法只适用于短码。对于长码，表会变得很大。我建议用 Meggitt 译码器或者捕错译码，硬件实现更友好。
4.6 循环码的优缺点
说了这么多，总结一下循环码的工程特性：
- 优点： 编码简单，用移位寄存器就能实现；有成熟的代数理论支撑；纠错能力可预测
- 缺点： 对于随机错误，性能不如 LDPC 和 Turbo 码；长码时译码复杂度高
我个人觉得，循环码在短码场景下依然很有价值。比如控制信道、信令传输这些对延迟敏感、码长较短的应用，循环码的简单性就是最大的优势。
这张图把循环码的核心知识点串起来了。从定义出发，到生成多项式，再到编码和译码，每一步都有清晰的逻辑关系。我个人建议你把这个图打印出来贴在工位上，写代码时瞄一眼，思路会清晰很多。
公众号:蓝海资料掘金营，微信deep3321