咬尾卷积码实战：从生成多项式到循环维特比译码

简介：围绕（13，17）卷积码与咬尾卷积码，这份MATLAB实现包面向通信工程、信号处理及信息论方向的学习者和研究者，用于理解卷积编码、软输出解码及系统性能评估等核心问题。压缩包共11个文件，以10个m脚本为主，另含1个Excel状态转移图，涵盖RSC编码器、LLR计算、Log-MAP迭代解码、主程序等模块，便于从编码到解码完整跑通仿真流程。包体仅16KB，脚本短小精悍，适合逐行阅读和二次修改。全站已有1091人学习下载，说明其在卷积码学习场景中有一定参考价值。借助资源中的状态转移图和多种编码率对比脚本，读者可直观观察不同参数对纠错性能的影响，并基于Log-MAP解码逻辑进一步拓展至SOVA等算法，是初学者入门与进阶均能获益的实用代码集。

1. 做短帧信道的人，迟早会被这 4 个状态卡住

做物理层的人都有这个体感：帧长只有几十比特时，卷积码为了把编码器状态收干净而补的尾比特，直接吃掉 5%~10% 的码率，这比任何编码增益都来得心疼。(13，17)卷积码是一个约束长度 3 的经典小码，本身不新鲜，但把它和咬尾卷积码放一起，能在不损失码率的前提下把帧边界处理干净。咬尾卷积码解决的就是"编码器启动状态不确定、又不想花钱归零"这个实际问题，LTE、WiMAX 里都在用同一种机制。这篇文章从生成多项式拆到循环维特比译码的迭代收敛，附完整可跑代码和 5 个我实际踩过的坑。适合正在做短帧物理层、想验证咬尾卷积码思路、或者准备把算法搬进 FPGA/DSP 的人。

2. 拆开 (13，17) 卷积码：生成多项式、状态表与手算验证

2.1 八进制生成多项式怎么拆成抽头

(13，17) 是八进制写法，表示一个 (2,1,2) 卷积码：每输入 1 个信息比特，输出 2 个码字比特，记忆深度 m=2，约束长度 K=m+1=3，状态数 2^m=4。八进制 13 转二进制是 001 011，取低 m+1=3 位得到 011，对应生成多项式 g0(D)=1+D；八进制 17 转二进制是 001 111，取低 3 位得到 111，对应 g1(D)=1+D+D^2。

这里最容易翻车的是位宽。八进制的一位对应三位二进制，所以 13 必须写成 001 011 再看低三位，而不是随手转成 0b1011 四位。抽头是从多项式系数直接搬的：g0 的抽头是"当前输入"和"第一级寄存器"，g1 的抽头是"当前输入、第一级、第二级寄存器"全用。寄存器排列顺序我习惯按"reg1 表示更早的比特、reg0 表示最近的比特"，这样状态 s = reg1*2 + reg0，0~3 四个状态编号和网格图一一对应。

这个码的自由距离 dfree=5，比同约束长度的 (5,7) 码略好一点，但选它做咬尾验证的真正理由是状态少。4 个状态可以手算、穷举、画网格图，咬尾译码的迭代逻辑和状态数无关，验证通过后直接换成 K=7 的 LTE 码，状态数变 64，算法框架一行不用改。

2.2 状态转移表和一次完整手算

根据 g0=1+D、g1=1+D+D^2，加上状态定义 s=(reg1, reg0)，输入比特 b 时：

• 输出 c0 = b XOR reg1，c1 = b XOR reg0 XOR reg1
• 新状态 = (reg0, b)，也就是 new_s = reg0*2 + b

四个状态的手算转移表如下：

拿这个表手算一遍，输入序列 1 0 1 1，从状态 00 出发：第一个比特 1 输出 11、进状态 01；第二个比特 0 从状态 01 输出 01、进状态 10；第三个比特 1 从状态 10 输出 00、进状态 01；第四个比特 1 从状态 01 输出 10、进状态 11。整帧码字是 11 01 00 10。这一步一定要自己算一遍，后面写编码器、对状态转移表、排查编码输出，全部依赖这张表。

注意编码输出是"状态相关"的，不是简单的异或。同一个输入比特 1，在状态 00 下输出 11，在状态 10 下输出 00，完全相反。这正是咬尾编码要小心的地方：编码器从哪个状态启动，直接决定码字内容。

2.3 为什么拿这个码验证咬尾

咬尾卷积码的译码核心是"首尾状态一致但未知"，验证这个特性需要一个状态空间小到能穷举、但结构完整保留的码。(13，17) 刚好满足：4 个状态让每轮维特比的加比选只有 8 次转移，迭代 6 轮也才 48 次，Python 纯循环跑几千帧毫无压力；而 LTE 的 K=7 咬尾码有 64 个状态、3 个生成多项式，中途调试时网格展开一次就是 128 条分支，连打日志都是噪音。

另外，咬尾收敛性在小状态空间下更容易观察。你很快会看到，迭代轮数对误帧率的影响、终态稳定判据、度量初始化的方向，这些行为在 (13，17) 上表现得非常明显，调明白了再放大到大码上，思路完全一致。不少工程做法是先写一个小码模型验证咬尾闭环，再移植到目标码，这个码就是做这件事最顺手的载体。

3. 咬尾卷积码的编码端：省掉归零比特的两种做法

3.1 普通卷积码的收尾开销有多大

传统卷积码为了保证译码器有确定的终态，编码完一帧后要补 m 个 0 把寄存器推回全零。这个开销在长帧下无所谓，但在短帧场景非常痛：信息比特 L=40 时损失 2/(40+2)=4.8% 的码率，L=20 时 9.1%，L=10 时直接 16.7%。短帧通信里每一项开销都在挤压有效吞吐，这个占比是省不掉的。

咬尾卷积码的思路是：不要求终态为零，只要求终态等于初态。初态是信息比特的函数，编码器根据帧内容自己决定从哪个状态启动。这样帧尾不需要任何收尾比特，码率 100% 用在信息上，代价是译码端从"已知初态"变成"求首尾一致的状态"，复杂度转移给译码器。

这个取舍在短帧场景几乎总是划算的。我做过一个低速率遥测链路的设计对比：L=64 的帧，普通收尾损失约 3%，咬尾译码多迭代两轮增加的时延在几十微秒量级，相比吞吐收益完全可接受。所以咬尾卷积码在 LTE、WiMAX、WCDMA 的控制信道里被大量采用，不是因为它编码增益高，而是因为码率实在。

编码器本身没有任何新结构，还是那个 (13，17) 卷积码，只是帧边界处的状态装配方式变了。

3.2 循环预载法：两次编码求终态

最常见的编码落地做法叫循环预载：第一遍从全零状态扫描整帧信息比特，只推进状态、不输出码字，得到帧尾状态 s_end；第二遍把状态寄存器预置为 s_end，重新扫一遍信息比特，这次正常输出码字。因为第二遍的初始状态等于第一遍的终态，而状态推进只依赖输入序列，所以第二遍结束时的状态自然还是 s_end，首尾一致。

# 状态转移表：(next_state, out0, out1) # 状态编码 s = reg1 * 2 + reg0，对应 (13,17)_8 码 TRANS = [ [(0, 0, 0), (1, 1, 1)], # state 0 = 00 [(2, 0, 1), (3, 1, 0)], # state 1 = 01 [(0, 1, 1), (1, 0, 0)], # state 2 = 10 [(2, 1, 0), (3, 0, 1)], # state 3 = 11 ] def tailbiting_encode(info_bits): L = len(info_bits) # 第一遍：从全 0 状态扫描，求出终态 s = 0 for b in info_bits: s = TRANS[s][b][0] # 第二遍：以终态为初始状态，正式编码 code = [] s = s # 注意这里初态不再是 0 for b in info_bits: ns, c0, c1 = TRANS[s][b] code.append(c0) code.append(c1) s = ns return code

这段代码里 TRANS[s][b][0] 是次态，TRANS[s][b][1] 和 [2] 是两个码字比特。第一遍循环里只取次态，码字输出被丢弃，这是刻意为之：先探出终态再装填。第二遍才真正产生发送序列。这个方案实现简单、逻辑直观、不容易出错，代价是编码需要两遍扫描，对短帧来说多跑一遍的时间开销可以忽略。

如果你连第一遍扫描都想省，可以预计算一个映射表：对 4 个初始状态、给定信息序列，终态可以按状态转移迭代得出，本质是相同的，只是把"跑一遍状态机"换成查表。工程上两种做法都有，我更推荐上面这种直接的两遍法，因为一眼能看出咬尾约束在哪，出了问题好排查。

3.3 和尾比特清零、直接截断的本质区别

直接截断是另一个极端：编码器从全零启动，帧尾不归零、不咬尾，把状态悬在任意位置。这种做法的译码器无法利用任何终态信息，帧尾最后 m 个信息比特的路径失去约束，误码率明显升高，还会有错误平层。咬尾卷积码不是直接截断，它把"首尾一致"作为先验信息交给译码器，信息量完全不同。

尾比特清零是"终态硬约束为零"，咬尾是"终态软约束等于初态"。前者初态已知是零、终态也已知是零，译码器一路确定；后者初态终态都不知道，但要满足闭环。所以咬尾译码器的复杂度比普通维特比高就高在这里：多了一个"找出哪个状态构成闭环"的搜索过程。

还有一种常见误解是"咬尾卷积码的码字就是普通卷积码码字的循环移位"。对线性码不成立，对卷积码也不成立。咬尾编码的码字长度和普通卷积码加了尾比特后的码字长度不一样，且码字集合不是简单循环移位。判断一个实现是否正确，我给你一个土办法：编码前先打印第一遍扫描的终态，编码后再打印第二遍的终态，两者必须相等；再用全零输入序列测试，此时四个状态初始值产生的输出应该各不相同。这个断言写在单元测试里，能挡住大半的编码端错误。

4. 咬尾译码怎么做：循环维特比算法与完整 Python 实现

4.1 普通维特比为什么译不了咬尾码

普通维特比译码器需要两个先验：初始状态已知（通常为零）和终态约束（通常靠尾比特归零）。咬尾卷积码把两个都用不了，初始状态取决于帧内容，终态是首尾一致的未知状态。如果强行用全零初态跑普通维特比，帧头几十比特会错，因为真实编码器可能不是从零状态启动的。

解决思路是循环维特比算法（CVA）。核心不复杂：既然真实路径是一个"圆环"而不是一条线段，那就把网格图卷起来跑。第一轮先假设所有 4 个初始状态等概率，路径度量全部初始化为 0，跑完一帧后，每个终态 s 的路径度量其实就代表"以 s 为初态的最优路径的似然"。下一轮把这份终态度量直接当作初态度量，这等于让信息在圆环上转了一圈。迭代下去，当 argmax 终态稳定下来，这个状态就是最可能的首尾状态，沿着幸存路径回溯就得到译码比特。

这个算法的收敛性在实际工程里靠的是"首尾一致性"这个约束足够强。帧长越长，度量累积越可信，收敛越快；帧长短或者信噪比低时，可能需要 4~6 轮才稳定。所以迭代轮数和收敛判据要一起设计，不能拍脑袋固定轮数。

4.2 循环维特比的迭代流程与关键参数

每一轮维特比内部就是标准的加比选：对每个状态、每个输入比特，计算分支度量，更新路径度量并记录幸存路径。分支度量我用相关度量，也就是 rx 软值和码字极性的乘积之和，最大化相关等价于最小欧氏距离，省掉平方运算。

迭代循环里有一个容易忽略的点：第二轮初始化时，是把上一轮返回的终态度量数组整个拿来用，不是只把最优终态的度量加到对应状态上。整个数组搬过来才是"圆环"语义，只改一个状态会让路径畸变。代码里我用init = pm[:]，切片就产生新数组，避免引用共享。

4.3 可复现的完整实现：编码、循环维特比译码、FER 仿真

下面这段代码可以直接存成tbcc.py运行。它包含咬尾编码、单轮维特比、多轮循环维特比和 BPSK-AWGN 误帧率仿真。生成多项式、状态数、迭代轮数都是参数，后续换大码只需要改 TRANS 表。

import numpy as np # ---- (13,17)_8 咬尾卷积码 ---- TRANS = [ [(0, 0, 0), (1, 1, 1)], [(2, 0, 1), (3, 1, 0)], [(0, 1, 1), (1, 0, 0)], [(2, 1, 0), (3, 0, 1)], ] def tailbiting_encode(info): s = 0 for b in info: s = TRANS[s][b][0] code = [] for b in info: ns, c0, c1 = TRANS[s][b] code += [c0, c1] s = ns return np.array(code) def viterbi_once(rx, init_metric): L = len(rx) // 2 pm = np.array(init_metric, dtype=float) prev_state = np.zeros((L, 4), dtype=int) # 每时刻每状态的最佳前驱 prev_bit = np.zeros((L, 4), dtype=int) # 对应的输入比特 for t in range(L): r0, r1 = rx[2*t], rx[2*t+1] new_pm = np.full(4, -1e30) for s in range(4): for b in (0, 1): ns, c0, c1 = TRANS[s][b] # 相关度量：+1 对应发送 0，-1 对应发送 1 bm = r0 * (1 if c0 == 0 else -1) + r1 * (1 if c1 == 0 else -1) m = pm[s] + bm if m > new_pm[ns]: new_pm[ns] = m prev_state[t][ns] = s prev_bit[t][ns] = b pm = new_pm return pm, prev_state, prev_bit def tailbiting_decode(rx, max_iter=6): L = len(rx) // 2 init = [0.0] * 4 # 第一轮：所有初态等概率 best_end = 0 prev_state = prev_bit = None for it in range(max_iter): pm, prev_state, prev_bit = viterbi_once(rx, init) new_end = int(np.argmax(pm)) if it > 0 and new_end == best_end: break best_end = new_end init = pm[:] # 环绕：终态度量作为下一轮初态度量 # 从最优终态回溯 bits = [] state = best_end for t in range(L - 1, -1, -1): bits.append(int(prev_bit[t][state])) state = int(prev_state[t][state]) bits.reverse() return bits def simulate_fer(ebno_db, L=40, frames=2000, max_iter=6): ebno_lin = 10 ** (ebno_db / 10) noise_sigma = np.sqrt(1.0 / ebno_lin) # BPSK 码率 1/2，N0/2 = 1/EbN0 err = 0 for _ in range(frames): info = np.random.randint(0, 2, L) code = tailbiting_encode(info) tx = 1.0 - 2.0 * code # 0 -> +1, 1 -> -1 rx = tx + noise_sigma * np.random.randn(2 * L) dec = tailbiting_decode(rx, max_iter) if not np.array_equal(dec, info): err += 1 return err / frames if __name__ == "__main__": for e in (3, 4, 5, 6): fer = simulate_fer(e, L=40, frames=2000) print(f"Eb/N0 = {e} dB, FER = {fer:.4f}")

代码里的关键点在三个地方。viterbi_once的new_pm每一时刻初始化为极小的负值，这是路径度量累加的起点，不能取 0，否则会污染真实度量。prev_bit和prev_state是回溯的凭据，回溯从最优终态倒着走，取出的比特是逆序的，最后必须reverse。信噪比换算这里用的是码率 1/2 的前提：Es = Eb/2，所以噪声方差 N0/2 = 1/EbN0，代码里noise_sigma直接取平方根。

跑这个仿真你会看到几个现象：3 dB 时误帧率在 10% 量级甚至更高，6 dB 时掉到 1% 以下；迭代轮数从 2 加到 4 有明显改善，从 4 加到 6 改善变缓；把max_iter改成 1，帧头帧尾会持续报错。这些现象都是咬尾译码的正常行为，可以作为你实现的自检基准。

5. 咬尾卷积码的 5 个常见坑：现象、原因与解决办法

5.1 编码器第二遍忘了用终态做初态

现象：编码输出的长度、极性都正常，但译码后误比特率直接 50%，和随机猜测一样。

原因：把咬尾编码误写成"第一遍扫出终态，第二遍仍然从全零启动"。这种写法的码字和普通卷积码完全一样，终态悬空，不满足"首尾一致"，译码器按圆环约束去找路径，当然找不到。

解决：编码函数里加断言，第一遍返回的终态必须和第二遍的起始状态相等。我习惯把尾比特编码写成一个状态机类，状态是成员变量，两遍扫描复用同一个状态推进函数，这样第二遍从哪个状态启动在代码里一眼可见。

5.2 循环维特比只迭代一轮就回溯

现象：帧中间部分译码正确，帧头和帧尾各有几比特错，降低迭代轮数后错误反而减少。

原因：第一轮初始化把所有初态看成等概率，跑完一轮后终态度量虽然出来了，但如果直接回溯，帧头的路径是从"错误初态假设"生长的，帧尾又受到终态约束不足影响，两边都不干净。咬尾路径本质是闭环，必须让度量转一圈以上才能消除边界效应。

解决：至少迭代两轮再回溯，并且用"终态序号连续两轮一致"作为收敛判据。工程上我会把 max_iter 设成 6，低信噪比下多跑几轮不亏，高信噪比下通常在第二轮就收敛提前跳出。

5.3 第二轮初始化复制了错的度量数组

现象：迭代 4 轮的误帧率比 2 轮还差，而且每次运行结果波动很大。

原因：第二轮初始化时把上一轮的pm直接赋值而不是拷贝，Python 里init = pm是引用共享，下一轮pm = new_pm会让 init 指向的数组被覆盖，等于迭代链断了。更隐蔽的错法是init[0] = pm[0]只搬最优终态，其他状态保持全零，网格的圆环语义被破坏。

解决：统一用init = pm[:]做副本。调试时可以在每次迭代打印init的前两个值，正常情况下第二轮起每个状态都应该是非零的有限值，如果看到四个全零，说明拷贝逻辑写错了。

5.4 软判决量化位宽不足导致收敛错乱

现象：浮点仿真通过，定点或 DSP 上误帧率比浮点差 0.5~1 dB，尤其是高信噪比下不降反升。

原因：咬尾译码多轮迭代会反复累加路径度量，定点量化后的分支度量误差在每轮都会被继承放大。低信噪比时噪声本身主导，误差不明显；高信噪比时真实路径和竞争对手的度量差很小，量化误差直接翻盘。

解决：接收软值的量化至少给 6 bit，ACS 累加器用 16 bit 有符号整数，路径度量做饱和钳位而不是自然溢出。迭代之间还要考虑度量溢出后的重新归一化：每轮结束时检查最大度量，超标就整帧减去一个常数，保证下一轮累加有充足余量。

5.5 短帧低信噪比下终态在两个状态间抖动

现象：L 小于 20、Eb/N0 在 2 dB 以下时，迭代 6 轮后argmax(pm)还在两个状态间跳，译码输出也跟着跳帧。

原因：帧太短，路径度量累加的信息量不足，两个候选闭环状态的似然差距比噪声还小，收敛判据"连续两轮一致"可能到迭代上限都触发不了。这是咬尾码的固有边界，不是实现 bug。

解决：把 max_iter 给到 8，收敛判据放宽为"最近三轮里出现两次相同终态"；如果业务允许，优先做帧合并或增加冗余。实在不行就在译码前对软值做一次幅度归一化，降低接收增益波动对度量比较的影响。

6. 从仿真到落地：FER 验收、硬件调度与向 K=7 码迁移

6.1 用误帧率曲线验收译码器

咬尾译码的错是突发性的，一帧里错一两比特和错一整帧在协议层面没有区别，所以验收指标必须用误帧率 FER，而不是单看误比特率 BER。仿真时保持帧长连续变化，比如 L=20、40、80、160 四条 FER 曲线，观察码率收益和译码复杂度随帧长的变化趋势。

我建议把第 4 章的仿真脚本跑满 10000 帧每点，打印 Eb/N0 从 3 dB 到 6 dB 的 FER。验收标准就一条：迭代一轮的 FER 必须明显差于迭代四轮以上，如果两者几乎重合，说明要么编码没咬尾、要么译码迭代逻辑没生效。这个反向检查非常灵，值得写进你的自测清单。

6.2 4 状态硬件的调度要点

硬件实现时，单轮维特比的 4 状态贡献了全部并行度。每个时刻做 8 次分支度量计算和 8 次加比选，4 个新状态各有两个候选前驱；冲突的路径用比较器选优，幸存路径和幸存比特写入回溯 RAM。迭代间的"终态度量搬运"就是一次 4×16 bit 的寄存器搬移，一个时钟周期完成。

流水线上我习惯把回溯和累积分开：前向模块算度量、写幸存信息，回溯模块在收敛判据触发后独立从最优终态倒推。收敛判据要放进控制状态机，迭代轮数计数器和终态比较器各占几级逻辑，低信噪比下的抖动帧不会触发提前回溯，因为连续两轮一致才通过。

6.3 迁移到 LTE/WiMAX 的 K=7 咬尾码

(13，17) 验证完闭环以后，往真实系统迁移是顺理成章的。LTE 的咬尾卷积码是约束长度 7、生成多项式 (133,171,165)_8，状态数 64，码率 1/3；WiMAX 的则常见 (171,133)_8 码率 1/2 配置。你需要改的只有三件事：TRANS 表换成对应状态转移表；状态数从 4 改成 64，加比选单元数量增加 16 倍；回溯深度从"整帧 L"改成长度受限滑动窗，毕竟 64 状态的路径存储不再是几行数组。

迭代轮数的经验值是 4 轮起步，高信噪比下两轮就收敛，低信噪比下给到 8 轮也不会有明显收益。我自己的习惯是每个项目都先保留一个"强制迭代 N 轮"的开关，上线后根据线上误帧率统计再决定是否开启提前收敛，避免理论上的收敛判据在真实衰落信道下误判。希望这些经验帮你在咬尾卷积码上少走一段弯路，编码端两遍扫描、译码端至少迭代两轮回卷，这两个习惯养成以后，这类码基本不会再给你添乱。

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