在《GNSS导航电文比特解码》里，我写过 GPS L1 C/A 的校验：30 比特一个字，末尾 6 比特做扩展汉明码的奇偶校验。校验失败，这个字通常就直接丢掉。

这套做法在 open-sky 环境下够用，弱信号时就不太够了。一套完整星历要在子帧 1~3 里凑齐，播发一遍 30 秒；反复丢字，首次定位时间（TTFF）会被拖得很长。城市峡谷、室内窗边、树荫下，跟踪环路还能锁住，电文却凑不齐，是很常见的情况。

现代 GNSS 电文换了一条路：GPS CNAV、SBAS、Galileo I/NAV 和 F/NAV，都在发射端用卷积码加入冗余，接收端用 Viterbi 译码把翻转的比特纠回来。同样的跟踪信噪比，电文误比特率可以再降几个数量级；配合软判决，大约还能换来 4~5 dB 的编码增益。对接收机来说，这往往是弱信号下电文能不能解出来、星历能不能更快凑齐的区别。

这篇就从这里展开：先把卷积码和 Viterbi 的关系理清，再用一个能手算的最小示例走完编解码，最后落到各 GNSS 电文的工程差异，以及硬件里常用的 Radix-2 蝶形加速。

Viterbi 算法在 GNSS 导航电文中的应用

一、先把名字理清楚

工程里偶尔会听到”Viterbi 编码”这种说法。严格讲，这个词不成立。

Andrew Viterbi 在 1967 年提出的是一种解码算法，用来求卷积码的最大似然序列。编码侧叫卷积码（Convolutional Code），由生成多项式定义，跟 Viterbi 本人没有直接关系。实践中卷积码几乎总是配 Viterbi 解码，两个词就经常被连着说，久而久之才有了”Viterbi 编码”这个口头简称。

后面为了准确，我统一写成”卷积编码”和”Viterbi 解码”。

导航电文为什么需要前向纠错

LNAV 的奇偶校验主要在做检错：发现错误，丢掉这个字。星历跨 30 秒播发，丢字会直接拖长 TTFF。通信领域一种常见的做法是重传机制，即错了就再发一次。卫星导航是单向广播，没有重传通道，发射端不能靠”再发一遍”把错误补回来。

前向纠错（FEC, Forward Error Correction）解决的就是这个问题：在发射端加入冗余，让接收端在不重传的情况下把翻转的比特纠回来。卷积码是 GNSS 里用得最广的一种 FEC，Viterbi 则是它最常用的解码算法。

编码带来的收益到底有多少

先把这一小节的边界说清楚。下面这张表来自一段理想化 Monte Carlo 仿真，用来回答一个很窄的问题：同样的信息比特能量下，卷积码 + Viterbi 相对未编码 BPSK，能把误比特率压低多少。

实验条件如下：

• 码：rate 1/2、约束长度 K=7、G1=171(oct)、G2=133(oct)，尾码补 6 个零；这是 GPS CNAV、SBAS、Galileo 共用的那组卷积码。
• 信道：AWGN + BPSK，符号边界已知，没有跟踪环抖动、多径、干扰，也没有交织 / NH 码等上层结构。
• 对比对象：软判决 Viterbi、硬判决 Viterbi、未编码 BPSK；三者在同一 Eb/N0 下比较。
• 样本量：每个信噪比点 20 万个信息比特。放大样本量是为了把平均误比特率测准，并不表示 GNSS 一次会发这么长的电文。
• 表中数字是 BER（Bit Error Rate，误比特率）：平均每个信息比特解错的概率。“20 万比特无错”表示该点实验中错误计数为 0，只能说明 BER 低于约 $5\times10^{-6}$ 量级，不能写成真实 BER=0。

Eb/N0 和接收机里常见的 C/N0 差一个信息比特率：

表中另外两列按此换算，分别对应 Galileo I/NAV（$R_b=125$ bps，约加 21 dB）和 GPS L5 CNAV（$R_b=50$ bps，约加 17 dB）。这里的 C/N0 应理解成数据支路上、理想换算得到的等效值；真实接收机还要扣掉导频分功率、环路损失、量化等，有效值通常会再低一点。

三个结论值得单独拎出来：

软判决的编码增益在 1e-3~1e-5 这一段大约是 4~5 dB。 未编码 BPSK 要达到 1e-5 需要约 9.6 dB，软判决 Viterbi 在 4.5 dB 附近就能做到。对 I/NAV 大约对应 C/N0 25~26 dB-Hz，对 L5 CNAV 大约对应 21~22 dB-Hz。这已经是偏弱但仍可能跟踪上的区间，往往就是电文能不能解出来的分界。

低信噪比下卷积码会放大错误。 表里 1 dB 那一行，硬判决 Viterbi 的 BER（2.5e-01）比不编码还差四倍多。原因是每个符号错误都会通过约束长度扩散到相邻的几个比特上，信噪比低到路径判决基本靠猜的时候，扩散效应压倒了纠错收益。硬判决的交叉点在 3~4 dB 之间。

软判决和硬判决差了大约 2 dB，这是白送的 2 dB。 软判决只要求跟踪环路把相关器输出的幅度信息保留下来，而不是提前压成 0/1。表里软判决在 1 dB 就已经优于未编码，硬判决要到 3.5 dB 左右才追平。工程上没有理由放弃软判决。

代价当然也有：符号率翻倍（rate 1/2 意味着 1 个数据比特变 2 个信道符号）、固定的解码延迟、接收机侧的算力和存储开销。这也是为什么 GPS L1 C/A 至今没有加 FEC —— 向后兼容的包袱太重，改不动。

二、卷积编码器的构成和工作流程

卷积编码器就是一个带移位寄存器的组合逻辑，三个参数把它完全确定下来。

码率 k/n：每输入 k 个比特输出 n 个符号。GNSS 里清一色是 rate 1/2。

约束长度 K：一个输出符号受多少个连续输入比特影响，等于移位寄存器长度加 1。GNSS 里清一色是 $K=7$，寄存器 6 级，状态数 $2^{K-1}=64$。

生成多项式：每个输出分支从哪些位置抽头，习惯用八进制写。GNSS 用的这一组是 G1 = 171(oct)、G2 = 133(oct)，最早来自 NASA 深空任务，后来被 CCSDS、IS-95、802.11a/g、DVB 广泛沿用。

展成二进制看抽头位置：

   u_k
    |
    v
  +----+----+----+----+----+----+
  | D1 | D2 | D3 | D4 | D5 | D6 |    6 级移位寄存器，每拍右移一位
  +----+----+----+----+----+----+

  抽头表（1 表示接入该分支的异或树）:

              u_k   D1   D2   D3   D4   D5   D6
  G1 = 171o    1     1    1    1    0    0    1
  G2 = 133o    1     0    1    1    0    1    1

  G1 = u_k ^ D1 ^ D2 ^ D3 ^ D6
  G2 = u_k ^ D2 ^ D3 ^ D5 ^ D6

  编码器状态 = (D1 D2 D3 D4 D5 D6)，共 64 种
  每输入 1 bit，按 G1、G2 的顺序输出 2 个符号

读生成多项式的时候注意对齐：最高位对应当前输入 u_k，最低位对应最老的 D6。171(oct) 写成 7 位二进制是 1111001，所以抽头在 u_k、D1、D2、D3、D6 上。这个对齐关系搞反是移植代码时最常见的错误，症状是解出来的比特全是噪声，而且没有任何中间提示。

自由距离决定纠错能力

卷积码的纠错能力由自由距离 dfree 描述，定义是所有非全零码字序列里最小的那个汉明距离。我在网格上做宽度优先搜索算了一遍，(171,133) 这组的 dfree = 10。

dfree = 10 意味着在一个错误事件窗口内，理论上可以纠正 $\lfloor(10-1)/2\rfloor = 4$ 个符号错误。作为对比，后面示例要用的 K=3 (7,5) 码 dfree = 5，只能纠 2 个。约束长度每加 1，状态数翻倍，dfree 增长则慢得多，这就是 K=7 成为工业标准的原因：再往上加，硬件成本涨得比收益快。

三种收尾方式，直接影响解码器结构

编码器有 64 个状态，解码结束时如果不知道终止在哪个状态，回溯就没有确定的起点。处理方式常见有三种。（GNSS 导航电文里真正用得多的是前两种，第三种主要出现在其他通信标准里）

补零冲刷（Flush / Tail Bits）：数据末尾追加 K-1 = 6 个零，把寄存器强行推回全零状态。解码器可以确定地从状态 0 开始回溯。Galileo F/NAV 和 I/NAV 用这种，ICD 里明确写了”tail bits 由 6 个零值比特组成，用于让接收机完成 FEC 解码”。代价是每个数据块多花 6 比特。

连续编码（不冲刷）：编码器状态跨消息边界一路带过去，永不复位。SBAS 的 MOPS 里这一项写明，Flush = No；GPS CNAV 的 IS-GPS-705 写的是”FEC 编码把相继的消息卷在一起”，每条新消息开始时寄存器里装的是上一条消息的最后 6 比特。好处是省掉 tail 开销，代价是解码器必须维护跨块状态，而且回溯要用滑动窗口。

尾咬（Tail-biting）：让编码器初始状态等于末尾状态，形成环。省掉 tail 开销又保持分块独立，代价是解码器要么猜初始状态，要么做环形 Viterbi。GNSS 导航电文里基本见不到；802.11n / LTE 控制信道用得更多。

三、Viterbi 的内核是动态规划

问题本身是指数级的

解码要做的是最大似然序列检测（MLSD）：在所有可能的发送序列里，找出与接收到的符号序列距离最小的那一条。

对于 N 个数据比特，候选序列有 $2^N$ 条。SBAS 每秒 250 比特，$2^{250}$ 这个数字没有任何计算意义。

让问题塌缩的两个性质

Viterbi 算法的关键洞察是，卷积编码器是一个有限状态机：当前输出只取决于（当前输入，当前状态），而状态只有 $2^{K-1}$ 个。由此得到两条性质。

无后效性：只要当前落在状态 s，以后怎么走就只跟 s 有关；此前是经哪条路径进到 s 的，对后面没有影响。

最优子结构：如果两条路径在时刻 t 汇聚到同一个状态，那么度量较大的那一条，无论未来怎么走，都不可能成为全局最优。它可以被立刻丢掉。

这两条凑齐了动态规划的全部前提条件。于是每个状态只需要保留 1 条幸存路径（Survivor Path）。rate 1/2 的码每个状态恰好有两个前驱，记作 a 和 b，状态转移方程就是：

其中 $M$ 是累积路径度量，$BM$ 是这一级的分支度量。

复杂度从 $O(2^N)$ 变成 $O(N \cdot 2^{K-1} \cdot 2^k)$，对 $N$ 是线性的。$K=7$、rate 1/2 的情况下，每个数据比特固定 128 次加法、64 次比较，跟消息长度无关。

对照一下动态规划的标准术语：

ACS：算法的计算内核

每一级对每个状态做的事情固定为三步，合称 ACS（Add-Compare-Select）：

1. Add：前驱状态的路径度量加上对应分支度量；
2. Compare：比较进入该状态的两条候选；
3. Select：留下小的那条，记录判决位。

Viterbi 解码器的性能、功耗、面积，基本全部由 ACS 决定。第七节的硬件优化谈的也全是 ACS。

分支度量：硬判决还是软判决

硬判决：接收符号先量化成 0/1，分支度量取汉明距离。实现最简单，度量是小整数，纯查表加法。

软判决：接收符号保留幅度，分支度量取欧氏距离，或者等价地取相关值的负数。第一节的仿真表已经给出结论，软判决大约值 2 dB。

工程上通常不做浮点，而是把相关器输出量化成 3 比特（8 级）左右的定点数。3 比特量化与无限精度的差距一般在 0.25 dB 以内，再加位宽收益很小。这里要留意 AGC 和量化区间的匹配：如果量化区间设得太宽，弱信号全挤在中间几级，软判决的信息量就损失掉了，实测会表现为”软判决比硬判决只好了 0.5 dB”。

回溯深度：理论要等到结尾，工程不能等

严格的 MLSD 要等整个序列收完，从最终度量最小的状态开始回溯。这对连续码流不可行，延迟无穷大，存储也无穷大。

好在幸存路径有个很有用的统计性质：各状态的幸存路径往回追溯若干级之后，会以极高概率汇聚到同一条路径上。因此只要回溯深度够，从哪个状态起回溯都不影响结果。

经验值是 5 倍约束长度左右。IS-GPS-705 里直接给了这个数字：”用户的卷积解码器会引入一个固定延迟，取决于各自的算法（通常是 5 个约束长度，即 35 比特）”。

工程上取 35~64 都常见，取大一点更保险，代价是判决位存储和延迟线性增长。K=7 时判决位存储量是 64 × 回溯深度比特，深度 35 就是 280 字节，深度 64 是 512 字节 —— 对 MCU 来说都不算负担。

这个延迟必须在时间标记上补偿掉，这一点极其重要。IS-GPS-705 特意强调用户”必须对此进行补偿，才能从接收信号得到系统时间”。如果忘了补 35 比特，CNAV 解出来的 TOW 会对应到错误的符号边界上，进而污染发射时刻，最终变成伪距里一个稳定的偏差。这类问题查起来很痛苦，因为电文内容全对，CRC 全过，只有定位结果不对。

度量归一化

先分清两样东西：会越跑越大、可能溢出的是 64 个路径度量；判决位 / 回溯缓冲一般是环形覆盖写，本身不靠“清零”来防溢出。

路径度量每级累加。SBAS、CNAV 这类连续编码若跨消息一直保留状态，定点整数跑久了必定顶满位宽。处理方式常见两种：

减最小值：每级（或每若干级）把所有状态的度量减去当前最小值。绝对数值回到 0 附近，状态之间的差值不变，判决不变。逻辑直观，代价是要先求 64 个数的最小值。软件实现里最常见。

模归一化：利用补码回绕特性，什么都不做，直接让它溢出。前提是任意两个状态的度量差有上界（对 K=7、rate 1/2 大约是分支度量最大值乘以若干个约束长度），只要位宽能容纳两倍的这个上界，用带符号差值比较就永远正确。硬件实现偏爱这一种，因为完全省掉了显式归一化。

还有一种看起来能躲溢出的做法：每组电文译码后把路径度量重置。算术上，单组只有几百比特，16 位度量往往溢出不了；但要看编码是否允许你重置。

对 SBAS / CNAV，规范意义上更干净的做法仍是：路径度量跨组保留，用归一化防溢出。有 tail 的分块电文，才适合单纯按组复位。

省内存近似：重置度量 + $\sim 5K$ 级预热

跨帧真正该连续的，是解码器对 64 个可能编码器状态的打分（路径度量），不是单独拷贝 6 个寄存器比特。若实现上不想长期挂着一整套跨帧 PM / 长回溯窗——例如按消息切开的任务结构、多通道要省 RAM、或者通道刚重同步——可以用下面这套组合拳近似“连续信念”：

1. 本帧解完后重置路径度量（以及本帧用完的判决位缓冲）。单帧只有几百比特，定点度量通常溢出不了，也可以不做跨帧归一化。
2. 保留上一帧末尾约 $5K$ 级的软符号。对 $K=7$，大约 35 级网格，rate 1/2 对应约 70 个信道符号。长度和回溯深度同一量级；只留最后几个 symbol 往往热不透。
3. 解下一帧之前先预热：度量从全相等（或等价冷启动）出发，用这段尾部软符号先跑 ACS，再接到本帧符号上继续解。

预热的目的，是让网格在进入本帧有效数据前，幸存路径大致并拢到“若连续解码会到达的状态附近”。它复用的是上一帧已经收过的符号，边界附近会多算一遍，换来的是：

• 不必跨帧保存 64 路度量的长期数值策略（减最小值 / 模宽核算可以收敛到单帧内）；
• 任务可以按消息切分，PM 生命周期跟帧绑定，内存更好估。

这仍是近似，不是连续保留 PM 的等价物。差别主要在：

• 预热只用尾部一段历史，信息量少于“整段历史都压进 PM”；
• 上一帧末尾若已经解错或软符号很脏，预热会把偏差带进下一帧开头；
• 算力上边界符号重复跑一遍。

还有一种更省的硬交接：若上一帧 CRC 通过，用末尾 $K-1=6$ 个信息比特反推编码器状态 $s^$，下一帧只把 $PM[s^]$ 置优、其余置劣。它不占用软符号缓冲，但对“末尾 6 比特必须正确”更敏感；弱信号下不如 $\sim 5K$ 级软预热稳。

实务上可以这样选：

• 内存和结构都允许：跨帧保留 PM + 归一化；
• 必须按帧重置：重置 + 尾部约 $5K$ 级软符号预热；
• 切忌：连续编码上只重置、不预热，又指望交界处和连续网格一样稳。

位宽算错、该归一化却没做、或预热过短时，典型症状类似：强信号正常，弱信号偶发整段跑飞或边界附近 CRC 不过，很难复现。

四、最小示例：K=3 (7,5) 的完整编解码

64 个状态没法手算，换个玩具尺寸：rate 1/2，K = 3，G1 = 7(oct) = 111b，G2 = 5(oct) = 101b。寄存器 2 级，状态数 4。

状态记作 (D1 D2)，D1 是较新的那一位。

编码器状态转移表

状态     输入 u=0                输入 u=1
(D1D2)   输出   下一状态         输出   下一状态
  00      00      00              11      10
  01      11      00              00      10
  10      10      01              01      11
  11      01      01              10      11

把它按目的状态重排，网格图的结构就出来了：

    输入 0                        输入 1
  00 ──00──▶ 00                00 ──11──▶ 10
  01 ──11──▶ 00                01 ──00──▶ 10
  10 ──10──▶ 01                10 ──01──▶ 11
  11 ──01──▶ 01                11 ──10──▶ 11

这张图里有个值得留意的规律：状态 00 和 01 这一对，去向永远是 00 和 10 这一对；状态 10 和 11 这一对，去向永远是 01 和 11 这一对。 源状态两两成组，目的状态也两两成组，组间不交叉。这就是第七节要展开的 Radix-2 蝶形结构，它在 K=3 上已经完整存在了。

再看每组内部四条分支的输出：00→00 是 00，01→00 是 11，00→10 是 11，01→10 是 00。四条分支只有两种输出，而且互为反码。这个性质后面会用来把分支度量的计算量砍掉四分之三。

编码

取 4 个数据比特 1011，末尾补 2 个零冲刷寄存器，输入序列 101100：

输入   起始状态   输出   新状态
 1       00       11      10
 0       10       10      01
 1       01       00      10
 1       10       01      11
 0       11       01      01
 0       01       11      00

码字：11 10 00 01 01 11，12 个符号。

注入错误

假设信道翻转了第 3 个和第 8 个符号：

 sym#   1  2 | 3  4 | 5  6 | 7  8 | 9 10 | 11 12
 sent   1  1 | 1  0 | 0  0 | 0  1 | 0  1 |  1  1
 recv   1  1 | 0  0 | 0  0 | 0  0 | 0  1 |  1  1
               ^              ^

第 2 组和第 4 组各错了 1 个比特。两个错误分别落在不同的组里，这种分散的错误对卷积码来说比较好处理，第六节讲交织时还会回到这一点。

逐级 ACS

初始状态 00，度量 0；其余状态置为不可达。每一级对四个状态做 ACS，汉明距离作分支度量。

以 t=2（接收 00）为例，手算一遍：

• 从状态 00（度量 2）：输入 0 输出 00，距离 0，到 00，候选度量 2；输入 1 输出 11，距离 2，到 10，候选度量 4。
• 从状态 10（度量 0）：输入 0 输出 10，距离 1，到 01，候选度量 1；输入 1 输出 01，距离 1，到 11，候选度量 1。

四个状态各自只有一个候选，直接落下来：[00]=2, [01]=1, [10]=4, [11]=1。

完整的度量表：

t=4 那一行四个状态度量全是 2，出现了大面积并列。这是低信噪比下的典型状态，算法本身不受影响，因为后续几级会把并列打破。

回溯

末尾补了零，编码器一定终止在状态 00，所以从 00 起回溯，读出每一步的判决：

t=6  状态 00  <- 前驱 01，判决 u=0
t=5  状态 01  <- 前驱 11，判决 u=0
t=4  状态 11  <- 前驱 10，判决 u=1
t=3  状态 10  <- 前驱 01，判决 u=1
t=2  状态 01  <- 前驱 10，判决 u=0
t=1  状态 10  <- 前驱 00，判决 u=1

倒序读出：101100。与原始输入完全一致，两个符号错误被纠正了。

最终度量还带一条附加信息：M(00) = 2，正好等于注入的错误个数。幸存路径的累积汉明距离就是”接收序列偏离最近合法码字多少个符号”，这个数字在工程上很有用，可以直接当作信道质量指标输出，用来做电文可信度加权或者跟踪状态判断。

五、SBAS 电文中的 Viterbi 解码

SBAS（WAAS / EGNOS / BDSBAS / QZSS SLAS 等）是 GNSS 里 Viterbi 解码最典型的应用场景，参数在 RTCA DO-229 和 ICAO SARPs Annex 10 里都有定义。

参数

前导码是 24 比特序列 01010011 10011010 11000110（0x53、0x9A、0xC6），分布在三个连续消息块上，每块 8 比特。SARPs 还规定每隔一个 24 比特前导码的起点要与 GPS 的 6 秒子帧历元同步，这给帧同步提供了额外的一致性检查条件。

处理流水线

相关器输出
    |
    v
符号同步（500 sps 边界）
    |
    v
软判决量化（3 bit）
    |
    v
Viterbi 解码（64 状态，连续网格，滑动窗口回溯）
    |
    v
比特流（250 bps）
    |
    v
前导码搜索 / 极性判定  --> 250 比特块边界
    |
    v
CRC-24Q 校验
    |
    v
消息类型解析 -> 电离层格网、快变改正、完好性...

五个容易踩的坑

第一，编码器不复位，解码器也不能复位。

MOPS 里 Flush = No 这一行的含义是，每秒的 250 比特消息之间，编码器状态一路带过去。很多人第一版实现会在每个消息块开头把路径度量重置为”状态 0 度量 0，其余无穷大”，结果是每块开头几个比特的纠错能力显著下降，弱信号下 CRC 通过率上不来。正确做法是把 64 个路径度量当作解码器的持久状态，跨块保留，再用归一化防溢出。若必须按帧重置以省内存或切开任务，应加上一帧末尾约 $5K$ 级软符号预热，不能裸重置（见第三节“度量归一化”）。

冷启动时也有个小细节：解码器刚开始不知道编码器在哪个状态，应该把 64 个状态的初始度量设成全部相等（而不是只信状态 0），让算法自己在几十级之内收敛到正确状态。

第二，帧同步在 Viterbi 之后，不在之前。

前导码是数据比特，不是信道符号。必须先做 Viterbi 解码得到比特流，再在比特流里滑动搜索前导码。这跟 GPS L1 C/A 的顺序正好相反，那里同步头直接在原始比特流里找。

顺序搞反了会怎样？在 500 sps 的符号流里搜 8 比特前导码，找到的全是虚警。

第三，极性歧义没法靠 Viterbi 解决。

BPSK 载波环锁定后存在 180° 相位模糊，符号流可能整体取反。这里有个容易被忽略的事实：171(oct) = 1111001b 和 133(oct) = 1011011b 各有 5 个抽头，都是奇数。输出比特是抽头位置输入的异或，输入全部取反，输出就会翻转奇数次，也就是全部取反。

结论是这个卷积码是透明的：取反的符号流本身就是一个合法码字，对应取反的数据。Viterbi 会干净利落地把它解出来，路径度量上看不出任何异常，只不过每一个比特都是错的。

我拿 2000 比特的码流实测过：把全部符号取反再送进解码器，输出与原始数据逐位取反完全吻合，一个残差都没有。

所以极性必须在 Viterbi 之外解决。常见做法是同时匹配正向和反向的前导码模式，哪个对上了就按那个极性输出。也有实现是让 CRC 来兜底（取反数据的 CRC-24Q 不会通过），但用前导码更快，也更省算力。

第四，滑动窗口回溯，以及延迟补偿。

连续码流不能等到结尾，标准做法是维护一个深度 D（取 35~64）的判决位环形缓冲区，每收到一级就写入一级，同时从当前度量最小的状态往回追溯 D 级，输出最老的那一个比特。

由此产生 D 个符号的固定延迟，对 SBAS 是 D/500 秒。SBAS 消息本身以 1 秒为单位、且时间信息在消息内容里给出，这个延迟通常不影响时间解算，但在计算”消息接收时刻”用于完好性超时判断（比如快变改正的有效期）时，需要把它算进去。

对 GPS CNAV 就是硬要求了，因为 CNAV 用符号边界来定义发射时刻，35 比特的解码延迟必须显式补偿。

第五，度量位宽和归一化。

3 比特软判决、rate 1/2、K=7 的情况下，16 位有符号度量配每级减最小值是最省心的组合。软判决的分支度量本身有正负，度量数组也要用有符号类型，否则中间结果一旦为负就会回绕，接下来求最小值的逻辑全部失效。如果为了省内存压到 8 位，必须仔细核算度量动态范围，或者改用模归一化。

位宽算错的症状是解码在弱信号下偶发性崩溃：度量回绕导致比较结果反转，幸存路径整段跑偏，而强信号下一切正常，很难复现。

六、各 GNSS 电文的差异，以及优缺点

同一个 (171,133) 码，各系统用起来差别不小。

几点需要单独说明。

Galileo 的 G2 分支末端有一个取反。 OS SIS ICD 的图 13 下面有一行注：”图 13 描述的编码器第二个分支在末端取反”。移植 SBAS 解码器去解 Galileo 时，忘了这个取反的后果是解码完全失败，而且失败得没有任何规律。

Galileo I/NAV 现在还多了一层 RS 外码。 ICD 2.0 之后引入了 FEC2，用 Reed-Solomon 对 I/NAV 字 1~4 的钟差星历数据做保护，校验字放在字 17~20。文档明确写了处理顺序：符号解调 → 解交织 → Viterbi 解码 → （可选）RS 解码。这是一个典型的级联编码结构，内码用 Viterbi 快速纠随机错误，外码用 RS 处理内码漏掉的整字擦除。对首次定位时间敏感的应用值得实现，能在信号断续的场景下明显加快星历凑齐的速度。

连续编码与分块编码的取舍

连续编码（SBAS、CNAV）省掉了 tail 开销。SBAS 每秒 250 比特，6 个 tail 比特相当于 2.4% 的有效载荷，不算多但也比没有强。真正的收益在于消息之间没有编码边界，块交界处的比特同样享受完整的约束长度保护。

代价有三个：解码器要维护跨块状态；随机接入时需要几十级的”预热”才能收敛到正确状态；实现上必须用滑动窗口回溯，比分块回溯稍复杂。

分块编码 + tail bits（Galileo）的好处是每一页完全独立。解码可以并行、可以乱序、可以只解自己关心的页，丢一页完全不影响下一页。对多星多信号并行处理的接收机架构，这种独立性在软件工程上很省事。

代价是 6 个 tail 比特的固定开销（Galileo I/NAV 每 120 比特里 6 个，占 5%），以及必须等整页收齐。

交织的代价

Galileo 加了块交织，I/NAV 是 30 列 × 8 行，F/NAV 是 61 列 × 8 行，按列写入按行读出。

好处很明确：Viterbi 对随机分散的错误很强，对连续突发的错误很弱 —— 一串连续错误落在一个约束长度窗口内，超出 dfree 的纠错能力，路径就选错了。交织把发射端相邻的符号在信道上拉开距离，接收端解交织之后，一段突发错误被打散成多处孤立错误，正好落进 Viterbi 的强项区间。多径闪烁、脉冲干扰、载波瞬时失锁产生的都是突发错误。

代价是延迟和缓存。I/NAV 必须先收齐 240 个符号才能开始解码，也就是必须等完整的 1 秒，无法边收边解。SBAS 没有交织，符号一到就能推进一级网格，这对完好性播发的实时性是有意义的选择 —— 告警消息要在 6 秒量级的时间到警（Time-to-Alert）内送到用户手上，任何一层缓存都要算进预算里。

Viterbi 与 LDPC 的分工

GPS L1C 和 BDS B1C/B2a 都换成了 LDPC，趋势看起来很明显，但把 Viterbi 说成过时并不准确。

LDPC 的解码门限更接近香农极限，同样的码率能省出更多裕量，长码块的优势尤其明显（L1C 子帧 2 的码块有 1200 符号）。它的问题是迭代解码：最坏耗时取决于迭代次数上限，存储量随码块长度增长，硬件面积和功耗都比 Viterbi 大一个台阶。

Viterbi 的优势恰好在这些点上：延迟固定且可算，最坏执行时间确定（每比特 128 次加法 64 次比较，一个数都不会多），存储量只有 64 个度量加上 64 × D 比特判决位。对预算紧张的低功耗接收机，这些确定性很值钱。

所以现状是分层的：新设计的长码块、高数据率信号倾向 LDPC；短消息、低延迟要求、需要确定性的场景仍然是卷积码 + Viterbi。ICAO 的 DFMC SBAS SARPs 到目前为止依然规定 L5 用 rate 1/2、K=7 的卷积码，虽然学术界早有 LDPC(500,250) 的替换方案，标准并没有采纳。SBAS 每秒一条 250 比特消息，码块太短，LDPC 拿不到多少增益，也换不回它带来的复杂度。

七、进阶：Radix-2 Butterfly ACS

蝶形结构从哪来

把状态按 (D1 D2 D3 D4 D5 D6) 编号，D1 是最新的一位，写成整数就是 s = D1*32 + D2*16 + ... + D6*1。

输入一个比特 u 之后，寄存器右移，D6 被挤出去，u 进入最高位：

s_next = (s >> 1) | (u << 5);

关键在于 s >> 1 把 D6 丢掉了。所以状态 2j 和状态 2j+1（只差最低位 D6）的去向完全相同：

• u = 0：都去状态 j
• u = 1：都去状态 j + 32

反过来看，进入状态 j 和状态 j+32 的，也只有 2j 和 2j+1 这两个源。四条分支把两个源状态和两个目的状态连成一个封闭的交叉结构，这就是 Radix-2 蝶形：

    源状态                        目的状态

    pm[2j]    o----------------o  npm[j]
               \              /
                \            /
                 \          /
                  \        /
                   \      /
                    \    /
                     \  /
                      \/
                      /\
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
                /            \
               /              \
    pm[2j+1]  o----------------o  npm[j+32]

    水平分支的度量为 +t，交叉分支的度量为 -t

64 状态、rate 1/2 的一级网格，正好由 32 个互不相干的蝶形组成。这个结构和 FFT 的蝶形在数据流形态上是一样的，硬件设计的很多手法可以直接搬过来。

一个蝶形只需要一个分支度量

我把 32 个蝶形的四条分支输出全枚举验证了一遍，规律非常整齐。以 j=0 和 j=1 为例：

j = 0:  2j   -> 0  : (0,0)      2j+1 -> 0  : (1,1)
        2j   -> 32 : (1,1)      2j+1 -> 32 : (0,0)

j = 1:  2j   -> 1  : (0,1)      2j+1 -> 1  : (1,0)
        2j   -> 33 : (1,0)      2j+1 -> 33 : (0,1)

四条分支只有两种输出符号对，而且互为反码。原因很直接：G1 = 1111001b 和 G2 = 1011011b 在最高位（当前输入 u）和最低位（D6）上都有抽头。翻转 u 会同时翻转两个输出，翻转 D6 也会同时翻转两个输出。而蝶形里的四条分支恰好就是 (u, D6) 的四种组合。

于是，把 $t$ 定义成分支 2j -> j 的（有符号）分支度量，另外三条分支的度量分别是 $-t$、$-t$、$+t$，整个蝶形的 ACS 写出来是：

一个蝶形：1 次分支度量查表、4 次加法、2 次比较，同时更新 2 个状态。而分支度量本身每级只有 4 个可能值（两个接收符号的四种符号组合 ±r0 ±r1），32 个蝶形从这 4 个值里查表。

这就是第五节代码里那段 lo0/lo1/hi0/hi1 的来源。

就地更新

蝶形的读写关系是”读 2j、2j+1，写 j、j+32”，源地址和目的地址不重合，看起来必须用两块度量数组来回倒（乒乓缓冲），存储量翻倍。

Biver、Kaeslin 和 Tommasini 在 1989 年 JSSC 上的一篇短文给出了解决办法：对状态索引做循环右移，度量数组可以就地更新，代价是数组下标被置换了一个已知的排列。由于网格结构每 m = K-1 = 6 级重复一次，六级之后置换回到原样。这个技巧被后来大量的 Viterbi 硬件和 SIMD 实现沿用，IBM 那件 SIMD 向量化 Viterbi 的专利（US 6,954,841）在背景技术里就明确引用了它。

对 MCU 软件实现来说，64 个 16 位度量只有 128 字节，乒乓缓冲的额外开销无所谓，就地更新的价值主要在硬件和向量化实现上。

并行度怎么用

32 个蝶形之间没有任何数据依赖，可以完全并行。往下就是一道成本与吞吐的取舍题：

全并行：32 个 ACS 单元，一个时钟周期推进一级网格。SBAS 500 sps 的符号率意味着 500 Hz 的网格推进速度，这种设计在 GNSS 里纯属浪费 —— 它的真实价值是可以把时钟降到极低，靠降频省功耗，而不是拿来提速。

折叠复用：1 个 ACS 单元跑 32 次，或者 4 个跑 8 次。面积和功耗随复用度下降，控制逻辑略复杂。GNSS 基带里通常这样做，一个 ACS 单元在多个通道、多个信号之间分时复用。

SIMD 向量化：这是纯软件实现的主流路子。64 个状态用 8 比特度量装进 8 个 128 位向量寄存器，ARM NEON 的 vmin/vadd/vcgt 或者 x86 的 pminub/pcmpgtb 直接做 16 路并行的 ACS。判决位从比较掩码里用 movemask 类指令提取。8 比特度量需要配模归一化或者饱和运算，位宽核算必须做在前面。

Radix-4：合并两级

把相邻两级网格合并成一级看，就得到 Radix-4 结构：4 个源状态直连 4 个目的状态，比较从 2 路变成 4 路。

好处是网格级数减半，同样的吞吐只要一半的时钟周期，或者同样的时钟能跑双倍吞吐。代价是 ACS 的关键路径变长（4 路比较树比 2 路深），面积增加，而且分支度量的组合数从 4 变成 16。

这个取舍在高速通信（Gbps 级）里很值，在 GNSS 里几乎没必要 —— 500 sps 的符号率下，Radix-2 已经远远够用。了解它的意义在于，如果要在同一套硬件上跑其他协议的 Viterbi（比如车载接收机顺便处理 DAB 或者 DVB），Radix-4 可能就进入视野了。

幸存路径的两种存储方式

回溯（Traceback）：只存判决位，需要输出时反向追溯 D 级。存储量 $2^{K-1}\times D$ 比特（$K=7$、$D=40$ 时是 320 字节），代价是每输出 1 比特要做 D 次内存访问。可以用”多指针回溯”分摊掉这个开销。

寄存器交换（Register Exchange）：每个状态直接维护完整的 D 比特幸存路径，每级把前驱的路径左移一位拼上新判决。省掉回溯，但每级要搬 $2^{K-1}\times D$ 比特数据。功耗高，只在超高速小 K 的场合用。

GNSS 场景下回溯是明确更优的选择：符号率低，内存访问不是瓶颈，功耗才是。

八、Viterbi 专用硬件与专利

Viterbi 解码在 90 年代是通信芯片的核心竞争力之一，留下了大量硬件专利。翻这些专利有个实际好处：它们把 ACS 的优化空间几乎穷举了一遍，做实现时可以少走弯路。

DSP 里的专用指令

TI TMS320C54x 是最典型的例子。它专门为 Viterbi 加了硬件：可拆分的 40 位 ALU（能当两个 16 位 ALU 用）、双累加器、比较选择存储单元 CSSU，以及一个转移寄存器 TRN 用来收集判决位。配套指令 DADST 和 DSADT 做双路加减，CMPS 用 CSSU 做比较、选大、存储，并把判决位移入 TRN。

一个完整的蝶形，C54x 用四条指令四个周期跑完：

DADST *AR5,  A      ; A(39:16) = Old(2j) + T ,  A(15:0) = Old(2j+1) - T
DSADT *AR5+, B      ; B(39:16) = Old(2j) - T ,  B(15:0) = Old(2j+1) + T
CMPS  A, *AR3+      ; New(j)    = max(A 高半, A 低半)，判决位入 TRN
CMPS  B, *AR4+      ; New(j+32) = max(B 高半, B 低半)，判决位入 TRN

这四行和第七节推导出的蝶形公式一一对应。TI 用 max 而不是 min，因为它把度量定义成相关值（越大越好），符号相反，结构完全一样。二十多年前的定点 DSP，指令集设计就已经把蝶形的反码性质吃透了。

ADI Blackfin 走了另一条路，加了一条向量指令 VIT_MAX（Compare-Select），在向量运算章节里单独列了一节，一条指令完成多路比较选择并生成判决位。

几件有代表性的专利

US 5,928,378 的思路值得多说一句：它注意到”使用相同分支度量的处理单元”可以合并，从而把 PE 数量减半。这跟第七节讲的”每级只有 4 个分支度量、32 个蝶形共享”是同一件事的硬件表述 —— 一个在算法层面省计算，一个在电路层面省面积和连线。ASIC 里连线面积往往比逻辑面积更贵，这类共享的收益比看上去更大。

卷积码 + Viterbi 用在哪些地方

同一个 (171,133) 码或者它的近亲，出现在意外多的地方：

• 深空通信：CCSDS 标准，旅行者号用的就是 K=7 rate 1/2；
• 蜂窝：GSM（K=5）、IS-95 CDMA（K=9）、3G/4G 的部分控制信道；
• 无线局域网：802.11a/g/n 的卷积码正是 K=7、(171,133)；
• 数字广播：DVB-S、DAB 的内码；
• 磁记录：硬盘读通道的 PRML 检测器，本质就是在部分响应信道上跑 Viterbi；
• 模式识别：HMM 的最优状态序列求解，语音识别、词性标注、基因序列比对里都叫 Viterbi 算法。

最后这一条经常让人意外。同一套动态规划递推，在通信里叫”最大似然序列检测”，在自然语言处理里叫”HMM 解码”。区别只在状态定义和转移代价怎么算，递推式一模一样。

参考资料

• A. J. Viterbi, Error bounds for convolutional codes and an asymptotically optimum decoding algorithm, IEEE Transactions on Information Theory, 1967.
• RTCA, DO-229 Minimum Operational Performance Standards for GPS/SBAS Airborne Equipment.
• ICAO, Annex 10 / DFMC SBAS SARPs Part B, 卷积编码与消息格式定义。
• U.S. Space Force, IS-GPS-705 (L5 CNAV) 及 IS-GPS-200 (L2C CNAV)。
• European Union, Galileo OS SIS ICD，第 4.1.4 节 FEC 与交织参数、Annex D 数值示例。
• CSNO, BeiDou B1C/B2a Signal In Space ICD，B-CNAV1/B-CNAV2 编码方案。
• M. Biver, H. Kaeslin, C. Tommasini, In-place updating of path metrics in Viterbi decoders, IEEE Journal of Solid-State Circuits, Vol. 24, No. 4, 1989.
• Texas Instruments, Implementing Viterbi Decoders on the TMS320C54x 与 TMS320C54x Functional Overview。
• Analog Devices, Blackfin Processor Programming Reference，VIT_MAX 指令。
• 专利：US 5,928,378（大宇，ACS 处理单元合并）、US 6,333,954（高通，高速 ACS）、US 5,867,408（TI，DSP 专用 Viterbi 存储）、US 5,970,097（松下，回溯优化）、US 6,954,841（IBM，SIMD 向量化）。