Turbo 译码SOVA 算法的研究与实现*

王丹飞，宋俊慷，夏慧宁

（1.北京航天驭星科技有限公司，河南 郑州 450018；2.广西民族师范学院，广西 崇左 532200）

0 引言

低轨道通常指150 km～300 km 高度的轨道，相较于中高轨道具有空间链路损耗和时延小的特点。低轨道卫星通常是小卫星，依靠数量众多的小卫星可以很容易组成卫星星座[1]，更适合军事侦察、遥感应用和实现个人卫星通信等。

小卫星重量轻[2]、结构小，便于发射制造的同时对星载设备的集成化和数据可靠性传输又是一个挑战。为此，CCSDS 空间数据链路业务标准规定了包括卷积码、Turbo 码在内的一系列信道码标准，用于近地和深空通信。Turbo 码是以卷积码为基础的并行级联码[3-4]，在低信噪比条件下展现出优越的译码性能，几乎接近于香农理论极限，因而广泛应用于卫星通信中。

1 Turbo 码网格图

网格图既可以用来说明编码过程，也可以用来分析译码过程。当Turbo 码编码器的结构固定，网格图也固定。CCSDS 标准推荐的Turbo 编码器如图1 所示，其分量编码器的移位寄存器个数为4，因此是24=16 状态（S0～S15）的Turbo 编码器，再结合其反馈位置，得到网格图如图2 所示。

网格图的横轴是时间轴，纵轴是状态值；网格图既可以反映从当前时刻某一状态出发，输入为0 或1 时，下一时刻的到达状态和下一时刻的输出；也可以反映从前一时刻的某一状态出发，输入为0 或1 时，当前时刻能够到达的状态以及到达当前时刻（的分支路径上）的输出。

编码时，每输入1 个比特的信息位mk，得到一个输出码字，共6 个比特，因此CCSDS Turbo码的基本码率是1/6，经过打孔删余可由基本码率得到其他码率。其中分量编码器1 输出3 个校验位，同时分量编码器2 输出2 个校验位，mk为未编码位。对于特定的编码输入序列，由网格图可以得到固定的编码路径，对应唯一的编码输出序列。

图3 是网格图的图表表示法，也是MATLAB 中trellis 函数的输出，使用图表表示方法更易于软件实现。图表法和图2 的网格图是一致的，例如，当前时刻从状态S5 出发，当编码输入为0（或1），则下一时刻的到达状态为next_state(0)=S10（或next_state(0)=S2），且对应状态转移路径上的输出为 next_out(0:3)=0011(或next_out(4:7)=1100);再比如，前一时刻从状态S5 出发，当输入为0 时，当前时刻到达的状态为S10 且转移路径上的输出last_out(0:3)=0011，即虚线状态转移路径上0/0111。

图3 网格图的图表表示法

对于16 状态网格图在t=4 时刻之后达到全状态，到达全状态后，（对于二进制编码）进入每个状态的路径有且仅有两条，从每个状态出发的路径也是有且仅有两条。

值得注意的是，图2 状态转移路径上的输出“/xxxx”对应，因此Turbo 码网格图也可以看作是分量编码器的网格图。但是由于Turbo 码的分量编码器是递归的卷积编码器，存在着反馈输入，因此网格图的状态路径转移路线与非递归卷积码有所不同。

2 Turbo 码通用译码器结构

Turbo 码通用的译码器结构——软输入软输出迭代译码结构(Soft Input Soft Output,SISO)如图4 所示，主要由串并变换、（两个）分量译码器、交织/解交织器和硬判决输出组成。

图4 通用的Turbo 码迭代译码结构图

假定译码器的接收序列Y为：

式中，k=0,1,…,N-1，是过信道后的编码信息位，分别对应两个分量编码器输出的过信道后的校验序列。

经过几轮迭代译码后，交换的先验信息值不再有大的变化，则对分量译码器2 输出的外信息Λ2e(u)经解交织后对符号位进行硬判决输出，即为最终的译码输出。

3 SOVA 译码实现

Turbo 编码器中的分量编码器是一个递归卷积编码器，而卷积编码的典型译码算法(也是最优译码方法)是Viterbi 译码（等价于最大似然译码）。人们自然想到，是否能用Viterbi 译码的方法来实现对Turbo 码的译码，答案是可以的，即软输出Viterbi 算法(Soft Output Viterbi Algorithm,SOVA)。

SOVA 基于图4 结构实现Turbo 迭代译码。其分量译码器的实现原理及过程和Viterbi 译码相比，主要有三个不同点：

(1) 使用修正的度量；

(2) 多了一个可靠性值更新的过程；

(3) 分量译码器的译码输出不再是（二进制0，1 比特序列的）硬判决输出，而是估计比特的外信息值Λ1e(u)(或Λ2e(u))。

3.1 SOVA 度量

SOVA 分量译码器使用修正的Viterbi 度量（也称SOVA 度量），即：

式中，Mt是当前时刻t的累积度量值，Mt-1是前一时刻的累积度量值；表示当前时刻的分支度量值，ct,j是网格图状态转移路径上的输出，yt,j是过信道后对应位的解调软输出值（有符号数），分支度量值是转移分支路径上编码码字和接收码字的点乘，计算的是欧氏距离，不再是汉明距离，这是因为解调软输出值是有符号数，而非0 或1 值。

分支度量值和先验信息可以看作是SOVA 度量的加权值[6-7]，二者共同为t时刻对信息位比特的估计提供判决度量。其中分支度量值反映了信道条件的好坏，当信道条件非常好时，应当主要以分支度量值为判决度量；当信道条件很差时，应当主要以先验信息值为判决度量；也就是说，二者的权重是相对的，而非相同。这就解释了图4 分量译码器输出的外信息Λ1e(u)为什么需要与自身两个输入（先验信息Λ1a(u)和系统信息序列YS）相加减，目的为了是保持两个权重的相对独立性，以兼顾不同信道条件的译码。

使用SOVA 度量进行“加比选”计算如图5 所示，得到最大似然路径（图6 实线）和最大似然路径上的估计比特（图6 与实线相连的比特值，其他比特值为不同时刻下的不同状态值所对应的幸存路径上的估计比特值）。由于每个时刻下到达不同状态的路径有且仅有两条，且这两条路径互为幸存路径和竞争路径，而最大似然路径是不同时刻下SOVA 度量值最大的幸存路径的连线，因此最大似然路径一定是幸存路径，而幸存路径不一定是最大似然路径。

图5 “加比选”单元

图6 最大似然路径（实线）和最大似然路径上的估计比特值（横轴为时间轴，纵轴为状态值）

3.2 可靠性值更新过程

3.2.1 可靠性值的定义

可靠性值Lt定义为“当前时刻竞争路径上和幸存路径上的累积度量值之差的绝对值”。

式中，i=0.1…15，si表示状态值。

图7 网格图中竞争路径与幸存路径对比示意图

通常来说幸存路径累积度量总是优于竞争路径的累积度量，那么这个差值越大，幸存路径是最大似然路径的可能性就越大，输出判决也越可靠。因此，可将最大似然路径上的可靠性值作为先验信息辅助另一个分量译码器进行译码判决，即相当于MAP 类算法中的外部信息。

3.2.2 进行可靠性值更新的原因

SOVA 分量译码器进行可靠性值更新的原因是人们发现这样一种情况，如图7 在t=1 到t=6 这一时间段内，幸存路径（实线）与竞争路径（虚线）先是在t=1 时刻的状态节点S8 处开始分离，又在t=6 时刻的状态节点S5 处重新汇合。又知最大似然路径上t=2、t=5 和t=6 时刻的可靠性值分别是{10,25,0}，对于Viterbi 译码在t=6 时刻会因为幸存路径和竞争路径的累积度量值相同而任意选择其中一条作为幸存路径，这样至少在t-4、t-2 和t这三个时刻的估计比特就存在着50%的误判概率（但整体估计序列仍然是最大似然序列即序列最优）。而Turbo 码两个分量译码器之间存在着迭代，如果没有可靠值更新，迭代译码反而会放大这种错误，恶化译码性能。

3.2.3 可靠性值更新的策略和方法

由于信息和信道传输的随机性，显然无法避免图7情况的出现，但是可以对其进行改善。分析如下：如果没有可靠性值更新，当前分量译码器会告诉下一个分量译码器t=2、t=5、t=6 时刻估计比特{0,0,1}的可信度值分别为{0,25,0}；在可靠性值更新后，当前分量译码器会告诉下一个分量译码器在t=2、t=5、t=6 时刻估计比特{0,0,1}的可信度值分别为{0,0,0}，也就是说对t=2、t=5 时刻的可靠性值进行了更新改善，从而降低不可靠性值在迭代过程中恶性传播的风险。基于这样的思路，本文给出一种工程中使用的滑窗回溯进行可靠性值更新的方法。

(1) 滑窗大小

为了兼顾译码时延和译码性能，工程上一般设置滑窗最大长度w=30，对于每个信息位，滑窗长度均是从1逐渐增大到30，滑窗的起始位置及滑窗大小变化过程如图8 所示。图中，{S0,S8,S4,S10,S5,S10,S13,……,S13,S14,S15,S7,S13,S6,S3,S1,S0,S0}为（某次某分量译码器输出的）最大似然路径。

图8 滑窗起始位置及大小变化图示

(2) 回溯

以图6 分量译码器“加比选”单元计算得到的最大似然路径为例，回溯过程如图9 所示。

图9 针对第一个信息位不同滑窗长度的可靠性值更新示意图

对于第一个信息位，第一次回溯时滑窗长度w=1时，从t=2 时刻的状态S4 处开始回溯如图9(a)所示：首先，根据图6 可知t=2 时刻到达状态S4 的最大似然路径上的估计比特值为0，那么与之相应的竞争路径上的估计比特值一定是1，这是因为到达某状态的分支路径有且仅有两条。再根据图3 网格图表，可知输入为1 且当前时刻到达状态S4 的前一状态为S9，这一过程简记为=1，表示t=2 时刻到达状态S4 的竞争路径上的估计比特值为1。接着从t=1 时刻的状态S9向前回溯，根据图6“加比选”计算结果可知t=1 时刻到达状态S9 处的估计比特为1，再根据图3 网格图表，可得到输入为1 且t=1 时刻到达状态S9 的前一状态为S3，记为=1，这样就回溯得到连续的一条竞争路径如图9(a)虚线所示。

其次，比较t=1 时刻最大似然路径上的估计比特值=1 和竞争路径上的估计比特值=1 是否相同，相同则不更新可靠性值。

同样的，增大滑窗长度w=2，从t=3 时刻的状态S10 处开始回溯，回溯到t=1 时刻，并比较最大似然路径上的估计比特值=1 和竞争路径上的估计比特值=1 是否相同，相同则不更新。

当滑窗长度w=3 时，从t=4 时刻的状态S5 处开始回溯，比较=1 和=1 是否相同，相同则不更新。

当滑窗长度w=4 时，从t=5 时刻的状态S10 处开始回溯，比较=1 和=0 是否相同，不相同则更新。更新方法：比较t=1 时刻的可靠性值和t=5 时刻的可靠性值，选择最小值赋值给t=1 时刻的可靠性值实现更新。

当滑窗长度w=5 时，从t=6 状态S5 处开始回溯，比较=1 和=1 是否相同，由于重合一定相同则不更新。

以此类推，逐步增大滑窗长度并回溯比较，从而实现对第一个信息位的可靠性值更新。

同理，对于第二个信息位，则从t=2 时刻开始逐次增大滑窗长度，并比较最大似然路径上的估计值=0 和竞争路径上的估计值是否相同，不相同则更新可靠性值（每次都取最小值）；

依次循环对最大似然路径上每个信息位进行可靠性值更新后，将更新后的可靠性值与估计比特值（0 和1分别映射为-1 和1）相乘后作为分量译码器的软信息输出。

3.3 判决输出和SOVA 分量译码器实现流程图

根据迭代准测（如设置固定的迭代次数），将分量译码器2 输出的软信息的符号位进行硬判决输出即可。SOVA 分量译码器实现流程图如图10所示。

图10 SOVA 分量译码器实现流程图

4 仿真及设备验证

SOVA 译码仿真参数设置如下：帧长8 160 bit，1/3码率，CCSDS 交织方式，迭代3 次，滑窗长度w的最大值为30，仿真结果如图11 所示，可以看出SOVA 与MAP 类算法性能相比仅有1 dB 的损失。

图11 SOVA 算法与MAP 类算法（log-map 算法、max-log 算法）误码率性能对比

5 结论

本文以CCSDS 标准推荐的Turbo 码为例，对SOVA译码的原理及实现进行了介绍，重点研究了网格图的功能及在其译码过程中的应用；同时详细分析了可靠性更新过程，阐明了SOVA 译码与Viterbi 译码的区别和联系，并给出了工程中一种实际的用法，最后对SOVA 译码进行了仿真验证，并成功应用于某数传设备，经过实际测试，该方式在不增加设备复杂度的同时获得良好的信道编码增益，实现简单方便维护。