高性能维特比在卫星导航接收机中FPGA实现

摘要：卫星定位接收机中卷积码译码即维特比译码器，在处理器中面临占有资源较多、处理时间过长等问题，为了减少处理器资源的占用和提高处理速度，采用并行加比选蝶形单元的的方法，在FPGA平台上用硬件描述语言设计一种高性能维特比译码器，作为GPS L2频点和GALILEO E1频点接收机的通用译码器，在GPS和GALILEO接收机上运用，大大减少资源使用，提高接收机的处理速度。
关键词：Viterbi译码器；GPS／GALILEO接收机；卷积码；FPGA

0 引言
    在现代通信系统中，要使信号能够更可靠地在信道中传输，往往需要在信道编码中采用纠错码来降低信号受噪声的影响，以降低传输的误码率。卷积码及其Viterbi译码是常用的信道编码方案。卷积码在GNSS接收机中得到应用，其中约束长度K=7，码率为1／2的卷积码已经成为商业卫星通信系统中的标准编码方法。在卫星定位系统中，GPS L2频点和GAILILEO E1的电文均采用卷积码编码，目前在定位接收机中用软件进行Viterbi译码较多，为了提高处理速度通用性，本文设计一种基于FPGA的通用高速Viterbi译码器，能作为GPS L2和GALILEO E1的电文的译码器，大大减少资源使用，提高接收机的处理速度和减少软件复杂度，从而节约处理器的资源。

1 卷积编码及Viterbi算法基本原理
    卷积码包含由K个寄存器组(每组包括k个比特，k通常取1)构成的移位寄存器和n个模2加法器，其中K是约束长度，编码器的输出由当前输入数据和寄存器组中的数据共同决定。对于GPS L2和GALILEOE1均为(2，1．7)卷积码，其生成多项式为G=(171，133)，电路图如图1所示。(2，1，7)卷积码编码器由6个延时器(图1中的q-1模块，可用寄存器实现)和两个模2加法器组成，它的编码约束度为7，码率为1／2，即输入端输入1 b信息，输出端输出2 b编码信息，并分为上、下两路并行输出。

    对信号进行卷积编码后，通常采用Viterbi算法(VA)译码。Viterbi算法是对于卷积码的最大似然译码，即利用概率译码。1967年Viterbi第一个提出了这个算法，Forney对这种算法及其性能做了可读强、见解深刻的描述。最大似然译码函数，就是在已知收到的信道输出序列，找到最有可能的传输序列，即通过网格图找出一条路径对应，要求路径输出的码序列具有对数最大值。对于二进制对称信道来说，函数的最大化等价于在网格图中找到与接收序列之间有最小汉明距离的路径。
    Viterbi算法是通过动态规划的方法找出网格图中具有最大度量的最大似然路径，即局部最优等效全局最优。在每一步中，它将进入每一状态的所有路径进行比较，并存储具有最大度量值的路径，即幸存路径，步骤为：
    (1)从时刻l=m开始，计算进入某一状态的单个路径的部分度量值，并存储每一状态的幸存路径及其度量值。
    (2)l增加1，l=m+1，将进入某一状态的分支度量值与前一段时间的幸存度量值累加，然后计算进入该状态的所有最大度量的路径，决定并存储新的幸存路径及度量，并删除所有其他路径。
    (3)若l<l+m，重复步骤(2)，否则结束。
    该算法主要包括两个工作：计算度量并比较，其决定幸存路径；另一个是记录幸存路径及其相关的度量值。

2 基于硬件描述语言的Viterbi算法
    Viterbi算法一般采用回溯法和寄存器交换法。为了减少控制的复杂度，本文采用回溯法，译码器由分支度量(BMU)、加比选(ACS)蝶形运算、存储单元、回溯(TB)单元4个基本部分组成，见图2。

    利用二元卷积来说明VA译码过程如图3所示。

    图4为用实线表示输入为0时走的分支，虚线表示输入为1走的分支，任意给定一个序列，在网格图中就有一个特定路径，图4中，u=(1011100)，输出的编码为c={11_10_00_01_10_01_11}。

2．1 分支度量单元
    路径度量单元是计算实际接收到的码元与期望码元之问的差别。G1与g1比较，G2与g2比较，若接收信号为0，期望值为0时，度量值为0，期望值为1时，度量值为1；若接收信号为1，期望值为0时，度量值为1，期望值为1时，度量值为0。两个比较结果和作为最终度量结果输出。按此规律计算当前状态下进入下一个状态的度量值。
2．2 加比选蝶形单元
    加比选(ACS)单元是完成幸存路径的延伸和判决向量的生成，计算过程包括度量值的累加、比较、选择路径操作。对(2，1，3)卷积码而言，共4个状态，组成2个蝶形运算单元；而(2，1，7)卷积码则64个状态，组成32个蝶形单元。在K=7的卷积码中，有64个状态的路径，所以根据待译码的长度，适当增加累加值的位宽，防止度量值溢出。
2．3 幸存路径存储单元
    幸存路径存储是用来存储每次蝶形运算完成单元后所选择的路径，存储单元的大小为译码深度乘以状态个数。对每一个加比选过程的存储，实际就是对幸存路径的存储。
2．4 回溯单元
    由VA算法可知，在网格图上经过大约5倍的约束长度之后，所有幸存路径将汇聚到一起。因此选择合适的回溯长度L，并从任一条路径开始(比如0状态)开始回溯，当回溯到L个节点时开始输出译码比特。

3 GPS L2和GALILEO E1接收机的高性能Viterbi译码具体模块设计
    根据GPS和GALILEO的接口文件，L2频点电文采用(2，1，7)卷积码的形式，码多项式为(171，133)o，且与GALILEO E1的卷积码格式相同，GALILEO采用分段卷积的形式，参与卷积的为每页中不包含同步头的部分，即120位进行卷积。为了能同时作为GPS和GALILEO的译码器，设计译码深度为120的译码器。

    接收机的Viterbi译码模块包括：地址译码模块、数据加载模块、Viterbi译码模块、输出控制模块。为了提高译码器的性能，Viterbi译码模块的加比选蝶形单元采用32个并行结构，提高运算速度。
3．1 地址译码及数据加载
    地址译码包括总线读写译码，由于Viterbi模块作为一个独立模块，内部地址采用自己的译码设计。
    深度为120的Viterbi译码器，需要输入240个卷积码，对于总线32位CPU，需要8次写入完成数据输入。最少需要8个地址单元，Viterbi译码输出最少需要4个地址单元，译码状态中断输出，状态位清除，即整个译码器模块需要14个地址单元。地址线需要4根即可。
    地址译码电路采用组合逻辑设计。译码状态中断输出、状态位清零采用不同时钟域同步。
    数据加载模块是加载寄存器内数据，然后按照顺序，1次按2位串行输出。
3．2 Viterbi译码模块
    Viterbi译码模块采用的译码深度为120的(171，133)o译码设计，译码器结构如图6所示，由译码控制单元、度量值计算单元、蝶形运算、幸存路径存储、回溯输出单元构成。

    (1)蝶形运算单元。按照(2，1，7)，多项式为(171，133)卷积码特点，基本蝶形单元分布见图7。对于约束长度为7的卷积码，共计64个状态，形成32个基2的蝶形运算单元见图8。

    蝶形单元的输入信号为上次的度量和，与接收码本蝶形单元中理论输出码的码距度量，如图9所示。

    输出信号为幸存路径、度量值和，选择输出为1，不选输出为0，如表1所示。

    (2)幸存路径存储。经过蝶形单元运算的输出，幸存路径，64个状态，幸存路径为64位，表示该状态有或无，每进行一次蝶形运算，存入一个64位路径信息，存储器的写入控制信号和地址信息由状态控制单元发出，存储空间为120×64 b。

    (3)回溯及输出。回溯过程即从地址最后向前一次读取幸存路径的值，得出译码电文。如图10所示。

    (4)状态控制单元。状态控制单元是对整个译码过程的控制，复位后，系统处在空状态，收到输入的待译数据后，进入加比选状态，按照数据流顺序进行加比选蝶形运算操作，进入到译码深度的长度的加比选后，转入译码回溯输出单元，从最后一个回溯到第一个时，即完成回溯，同时输出译码电文和译码完成中断，系统再次进入等待状态，如图11所示。

4 仿真及接收机测试结果
    GPS／Galileo接收机通用的Viterbi译码器设计通过Modelsim仿真，能够得出正确译码结果，编码后在240个码序列的228之前加入1位或2位错误码，均能正确纠错，得到正确的译码结果。
    译码延时260个时钟周期。最大译码数据吞吐率达240×(150×1 000 00／260)=138 Mb／s。如图12所示。

    译码模块在Altera StratixⅡ系列EP2S180F1020I4 FPGA平台上，利用QuartusⅡ8．0进行综合和时序分析，最大速度可以达到150 MHz，资源使用量为：ALUTs占用2 679．Logic Registers占用1 465，与文献相比，资源消耗大大减少。如图13，图14所示。

5 结语
    本文所述基于FPGA的Viterbi译码器用于GPS／GALILE-O接收机，能对GPS L2和GALILEO的电文进行译码，纠错能力达到预期效果，FPGA资源使用量较低，主时钟速度最大可达到150 MHz，译码处理延时达260个时钟周期，译码深度为120，最大译码数据吞吐率达138 Mb／s，完全满足GPS／GALILEO接收机电文接收译码速度要求。