一种高效咬尾卷积码译码器的设计与仿真

摘要：介绍了咬尾卷积码的最优和次最优译码算法的实现细节。给出了采用新的蝶形图计算方法和环形内存来节省硬件资源的实现方法，最后给出了次最优算法在FPGA上的实现结果。
关键词：咬尾卷积码；次最优译码算法；蝶形图；FPGA

0 引言
    自1955年Elias发明卷积码以来，卷积码作为一种高效的信道编码已被用在许多现代通信系统中。卷积码分为零比特卷积码(Zero Tail CC，简称ZTCC)和咬尾卷积码(Tail Biting CC，简称TBCC)两种。ZTCC是指在编码的时候，码字后面要另外加上K(K为约束长度)个0将编码寄存器的最后状态打出，而TBCC则是直接用码字的最后K个比特将编码寄存器初始化，从而提高编码率。现在的3G和4G通信标准中(比如WiMAX或LTE)都采用了TBCC信道编码。关于TBCC的译码算法很多，其中比较经典的译码算法有循环维特比算法(CVA)和BCJR算法。但上述算法由于解码时延不固定和复杂度的原因，均不便于硬件实现。为此，本文提出了一种便于硬件实现的次优解码算法。

1 TBCC译码算法
1．1 最优译码算法
    TBCC的理论最优译码算法是，对于每一个可能的初始状态(3k)用维特比译码算法对所有可能的状态进行搜索，最后再根据最好的状态进行解码。但是，这种算法的复杂度太高，不利于硬件实现。
1．2 次最优译码算法
    次最优译码算法的经典代表是CVA算法，此外还有其改进的算法比如环绕维特比算法(WAVA)和双向维特比算法(BVA)。它们的主要思路是利用圆形buffer将码字扩展成多个相同码块首尾相接的长码块进行译码。当检测到首尾状态相等或者满足自适应迭代的停止条件时，即完成译码；否则继续进行迭代。但该算法或其改进的WAVA和BVA算法都存在这样一个问题。那就是解码的延迟不是固定的，而这非常不便于硬件实现。
    所以，本文中提出固定延迟的译码算法，其基本思路是在码块的前Lt个符号补在符号的后面，将码块的后Lh个符号补在码字的前面，这样就构成一个长度为Lt+N+Lh的新码块(假设原码字长度为N)，图1所示是重构的码块示意图。该新码块可以按照ZTCC解码一样去解码，然后从具有最小路径度量(path metric)的状态进行回溯。

    图2所示是其译码算法流程图。其中Lt和Lh参数的选择应根据仿真来确定。这里采用典型值：Lt=72，Lh=96。

2 TBCC译码算法的实现
2．1 分支度量(branch metric)的计算
    维特比译码算法采用ML准则，其分支度量可通过下式计算：
   
2．2 加-比较-选择器(ACS)
    图3所示是ACS的状态转移蝶形图。实际上，卷积码的Trellis图具有如下性质(LTE中TBCC编码约束长度为7)：

    对于每一个状态，其前面的状态为i<<1和(i<<1)+32；而对于每一个状态，其后面的状态为(i>>1)％64和(i>>1+1)％64。
    上述性质在硬件实现时非常好用。由上述性质可以给出路径度量的计算式：
    
    从上面的公式可以看出。计算一个蝶形图需要4次加法和2次比较。图4所示是ACS路径度量蝶形图。此外，操作时还可采用Andries的简化方法来减小硬件开销，其公式如下： 

    计算出需要2次加法。对于LTE中约束长度为7的TBCC来说，总共有64个状态，可以分别在两个蝶形图里面使用(符号会有所变化)，这样，加法器就减小为32，加上每个路径度量更新还需要一个加法器，这样共需要的加法器为32+64=96，比之前未简化的算法少用了32个加法器。
2．3 回溯
    回溯的深度(Trace back Depth)必须大于编码深度(Coding Depth)，这是因为，经过回溯CD的长度，所有的幸存路径均会收敛。每次回溯时，所有幸存路径都需要从内存里面读出TD个状态，同时将有TD-CD个判断之后的比特送入LIFO。回溯之后，会有TD-CD的内存空间可写，另外在回溯时，还需要TD-CD个内存空间来保存进来的数据，这样，内存空间就共需TD+(TD-CD)=2TD-CD。在此可取典型值TD=96，CD=72。
2．4 FPGA的实现
    本设计采用的FPGA芯片为Altera的StratixIIIEP3SL340系列器件，其在QuartusII9．0下综合出来的RTL视图如图5所示。其布线后所占用的资源如表l所列。

3 仿真验证

    本文采用的开发流程是先在matlab下仿真出浮点算法的性能，然后根据系统要求用C实现定点模型，在和浮点的版本比较后，再采用Ver-ilog实现。由于用verilog做性能仿真比较慢，本文采用的仿真和验证方法是在定点C下做性能仿真，然后将C版本的输入输出作为黄金参考数据，再用modelsim仿出vetilog版本的数据和参考数据做对比，如果数据完全一样，则验证通过，否则调试verilog语言并追踪错误。
    验证选择的码长为1080，将TBCC解码器放在4×4 MIMO接收机里，可得到如图6所示的SNR曲线。

    由图6可知，在SNR很小的时候，TBCC解码器的性能反而较硬判决会下降，这是由于SNR太小，TBCC已经无法从很少的已知信息中纠正其他的错误信息。而当SNR较大时，TBCC解码器就可以从相对多的已知信息中纠正错误信息。由图6可见，在误码率为10-3以下时，TBCC能够获得约2l dB的增益。

4 结束语
    该解码器已经用在MIMO接收机的FPGA版本中。并且经过实验室测试，能够成功的解码出咬尾卷积编码，并具有较好的性能。另外，该解码器在实现上用的硬件资源很少，这可为整个系统的集成奠定基础。