一种基于GPU的卷积码高速并行译码方法及译码器

摘要

本发明公开一种基于GPU的卷积码高速并行译码方法及译码器，属于通信领域。本译码方法先将码流信息进行分段，通过异步传输方式发送到GPU上，在GPU上按照维特比算法对每个分段并行进行前向路径量度计算和路径回溯，实现全并行译码，最后合并每个分段的译码结果，输出译码码流信息。本发明的译码器包括位于主机和GPU设备上的初始化模块、位于主机的串并转换器、位于GPU设备的前向计算内核和回溯内核。主机与GPU设备之间通过异步传输通道实现数据的传输。本发明在保证抗误码性能不变的情况下，提升了译码并行度，并挖掘卷积码网格图蝶形结构的特性，降低了运算复杂度，所适用的卷积码范围广泛，实现难度低，灵活性和兼容性强。

说明书

技术领域

本发明属于通信领域，具体涉及一种基于GPU(图形处理器)的卷积码译码方法及译码器装置。

背景技术

卷积码于1955年由Elias提出，是一种不同于分组码的信道编码方式，其编码器具有一定的记忆性。一个码率为1/R，编码约束长度为K的卷积码称为(R，1，K)卷积码。卷积码具有良好的译码性能，被广泛应用于各种通信标准中。例如，IEEE 802.11和IEEE 802.16通信标准中均使用了(2，1，7)卷积码，CDMA2000标准中使用了(3，1，9)卷积码，4G LTE标准中使用了(3，1，7)卷积码等。卷积码最常用的译码算法是维特比算法。维特比算法等价于求在一个加权图里寻找最短路径问题的动态规划解。维特比算法实际上就是卷积码的最大似然(ML)译码算法。传统的维特比译码是一种串行译码方式，译码速率低，延时大。如何设计一种基于维特比算法的高速并行译码方式是非常有意义的。

本领域内公知，基于FPGA(现场可编程门阵列)、ASIC(专用集成电路)等大规模集成电路设计的译码器，译码速率高，但研发周期长，成本高，灵活性差；而于DSP、x86-CPU和ARM等处理器设计的译码器，虽然兼容性和灵活性较好，但受限于硬件资源，通常只能达到兆级的译码速率，不能满足高速通信系统中的应用需求。近年来，随着GPU的发展，其作为通用处理器的能力得到了挖掘。基于GPU设计的译码器架构继承了CPU的灵活性和通用性，开发难度低，且译码速率能达到百兆级以上。

发明内容

基于上述需求，本发明提出一种基于GPU的卷积码分段并行维特比译码方法，并设计一种基于GPU平台的译码架构，以实现卷积码的高速并行译码。

本发明提供了一种基于GPU的卷积码高速并行译码方法，包括初始化阶段和译码阶段。初始化阶段包括步骤1～步骤3，译码阶段包括步骤4～步骤7。

步骤1，主机初始化；主机启动系统线程，分配内存空间；

步骤2，GPU设备初始化；主机发送控制信号，激活GPU设备，在GPU设备上分配GPU全局内存空间，创建异步流；

在GPU设备上设置有网格图存储器和蝶形分组器；网格图存储器对卷积码对应的网格图进行存储；蝶形分组器对卷积码的蝶形结构进行分组，对于码率为1/R，约束长度为K的卷积码(R，1，K)，蝶形分组器对该卷积码网格图中的N/2个蝶形结构进行分组，同一组蝶形结构具有完全相同的分支路径，组数N_c＝2^R，N表示编码器状态总数，N＝2^K-1。GPU设备上还设置幸存路径存储区用于存储译码过程中的幸存路径，设置路径量度存储区用于对前向路径量度计算中得到的路径累积量度进行存储。

步骤3，给定信道模型和卷积码接收码流信息，选择合适的分段长度D和交叠深度L，对接收的码流信息进行分段和交叠处理，得到若干分段；

步骤4：GPU设备为本次译码分配异步流，主机将分段码流通过异步传输方式传送给GPU设备；

步骤5：对每一个分段，按照维特比算法，进行长度为L+2D的前向路径量度计算；

步骤6：对每一个分段，在前向路径量度计算结束后，进行状态估计；对每一个分段，按照估计得到的状态，选择一条幸存路径进行长度为L+D的路径回溯，并判决输出长度为D的译码结果；

步骤7：合并每个分段的译码结果，得到译码输出码流信息。

本发明的另一个目的是设计一种基于GPU的卷积码高速并行译码器，包括位于主机和GPU设备上的初始化模块、位于主机的串并转换器、位于GPU设备的前向计算内核和回溯内核。所述的主机与GPU设备之间通过异步传输通道实现数据的异步交换。

初始化模块，用于对主机和GPU设备进行初始化操作；在主机上设置数据接收缓存区、数据发送缓存区、第一分段信息存储器和第一分段译码结果存储器。主机发送控制信号，激活GPU设备。在GPU设备上分配GPU全局内存空间，创建异步流，在GPU设备上设置第二分段信息存储器、第二分段译码结果存储器、路径量度存储器、幸存路径存储器、网格图存储器和蝶形分组器。数据接收缓存区对主机接收的码流信息进行存储；数据发送缓存区对主机发送的译码输出码流信息进行存储；分段信息存储器对串并转换后的各分段进行存储；分段译码结果存储器对分段译码结果进行存储。路径量度存储器对前向路径量度计算中得到的路径累积量度进行存储；幸存路径存储器对前向路径量度计算中筛选出的幸存路径进行存储。网格图存储器对卷积码对应的网格图进行存储。蝶形分组器对卷积码的蝶形结构进行分组，对于码率为1/R，约束长度为K的卷积码(R，1，K)，蝶形分组器对该卷积码网格图中的N/2个蝶形结构进行分组，同一组蝶形结构具有完全相同的分支路径，组数N_c＝2^R，N表示编码器状态总数，N＝2^K-1。

串并转换器，位于主机，对接收的码流信息进行分段和交叠处理，将各分段存入第一分段信息存储器。串并转换器还将第一分段译码结果存储器中存储的分段译码结果进行合并，输出给数据发送缓存区。

所述的GPU设备译码时，首先分配一条异步流，主机通过异步传输方式将第一分段信息存储器内的各分段传入GPU设备的第二分段信息存储器。然后，启动前向计算内核，前向计算内核从第二分段信息存储器中获取各分段，对每个分段的每个状态进行前向路径量度的计算，得到各状态的路径累积量度和幸存路径。在前向计算内核执行结束后，启动回溯内核。回溯内核对每个分段以估计的状态为起点沿幸存路径进行回溯，同时完成译码判决，输出译码结果，存储在第二分段译码结果存储器中。在GPU设备译码完成后，GPU设备通过异步传输方式将第二分段译码结果存储器中的分段译码结果传入主机的第一分段译码结果存储器中。

所述的前向计算内核中启动32·N_c·N_c·N_bl条线程，其中包括N_c·N_bl个线程块，每个线程块由N_c个线程束组成，每个线程束由32个线程组成。所述的回溯内核中启动32·N_c·N_bl条线程，其中包括N_bl个线程块。每个前向计算内核和回溯内核均映射N_t＝32·N_c·N_bl个并行处理分段。N_c、N_bl和N_t均为正整数。

本发明的优点与积极效果在于：

(1)本发明在保证抗误码性能不变的情况下，提升了译码并行度，对维特比算法进行简化，并挖掘卷积码网格图蝶形结构的特性，对译码过程进行优化处理，降低了运算复杂度。本方法适用的卷积码范围广泛，实现难度低，灵活性和兼容性强，适用于所有基于CUDA架构开发的GPU硬件。

(2)本发明提出的基于GPU的译码架构，有效地结合了分段并行维特比译码方法和GPU的硬件特点，对译码并行度、数据存储和数据传输等进行了优化设计，最大限度提升了GPU硬件资源利用率，提升了译码速率。通过大规模并行译码处理，在保证较低的译码延时条件下，提升了译码吞吐率，达到Gbps量级的译码信息速率。

附图说明

图1为本发明的卷积码码流分段方式示意图；

图2为本发明的分段维特比译码方法示意图；

图3为本发明的分段并行译码处理示意图；

图4为本发明所涉及的卷积码网格图蝶形示意图；

图5为本发明所提出的基于GPU的卷积码译码器架构的工作框图；

图6为本发明所提出的基于GPU的卷积码译码器内核线程网格映射示意图；

图7为本发明所提出的全局内存中数据合并存储方式设计图；

图8为本发明所涉及的卷积码编码器的一个具体示例；

图9为本发明所涉及的卷积码网格图蝶形的一个具体示例；

图10为本发明所提出的译码器译码步骤的流程图；

图11为本发明所提出的异步流译码示意图。

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

本发明提出的基于GPU的卷积码高速并行译码方法及译码架构，适用于采用连续编码方式的卷积码的译码，并且能够对各种常见无线通信标准中所使用的卷积码进行译码。本发明提供的译码方法，通过对接收码流进行分段处理，提升了译码并行度，适用于大规模并行的硬件实现。本发明提供的译码器装置基于GPU架构设计，在减少译码群延时的前提下，实现了GPU资源利用率最大化，最大限度提升了译码的吞吐率。

本发明的基于GPU的卷积码高速并行译码方法，包括初始化阶段和译码阶段。初始化阶段包括步骤1～步骤3。译码阶段包括步骤4～步骤7。

步骤1，主机初始化。主机启动系统线程，分配内存空间。

在主机上设置接收缓存区用于存储接收码流信息，设置发送缓存区用于存储译码结果，设置第一分段信息存储区用于存储分段组，设置第一分段译码结果存储区用于存储分段译码结果。

步骤2，GPU设备初始化。主机发送控制信号，激活GPU设备，在GPU设备上分配GPU全局内存空间，创建异步流。

在GPU设备上，设置如下存储区：设置第二分段信息存储区用于存储分段组，设置第二分段译码结果存储区用于存储分段译码结果，设置幸存路径存储区用于存储译码过程中的幸存路径，设置路径量度存储区用于对前向路径量度计算中得到的路径累积量度进行存储，设置网格图存储器对卷积码对应的网格图进行存储，设置蝶形分组器对卷积码的蝶形结构进行分组，将网格图中N/2个蝶形结构进行分组，同一组蝶形结构具有完全相同的分支路径，用于提供前向计算内核中的线程与状态映射关系。

步骤3，主机根据给定的信道模型和卷积码接收码流信息，选择合适的分段长度D和交叠深度L，对接收的码流信息进行分段和交叠处理，得到若干分段，存入第一分段信息存储区。本步骤中，对信道模型没有特殊要求。

步骤3对接收的码流信息进行分段，以能实现在GPU上的并行执行。如图1所示，为采用连续编码方式在接收端得到的卷积码码流信息。首先，选取合适长度D作为基准，对半无限长码流信息进行分段。然后，对每个长度为D的分段，向前和向后各延伸长度L，使其与前后分段各交叠2L。这样，码流信息被分割成了长度为D+2L的若干分段。本方法中对长度D的选择无特殊要求，建议值为100～1000个符号。长度L与卷积码约束长度K有关，一般选择为约束长度K的4～6倍。对于码流信息首尾不足部分，使用符号“0”将对应的信息进行填充。

步骤4，进入GPU译码阶段，GPU设备为本次译码分配异步流，主机将分段码流通过异步传输方式传送给GPU设备。

步骤5，对每一个分段，按照维特比算法，进行长度为L+2D的前向路径量度计算。

步骤6，对每一个分段，在前向路径量度计算结束后，进行状态估计；对每一个分段，按照估计得到的状态，选择一条幸存路径进行长度为L+D的路径回溯，并判决输出长度为D的译码结果。

下面对照图2叙述分段维特比译码方法。如图2所示，一个长度为D+2L的分段，由同步块、译码块和回溯块三个部分组成。同步块和回溯块的长度均为L，译码块的长度为D。对于该分段的译码过程，进行步骤5和6。

步骤5中，进行长度为D+2L的前向路径量度计算，通过维特比算法中加比选方法更新当前阶段每个状态对应的路径累计量度信息PM和幸存路径信息SP。步骤6中的状态估计，是维特比算法中状态估计的简化，不需要求出最短幸存路径，而是仅需任选一个状态。此处通常选择全零状态。选择全零状态作为回溯过程的起点，沿该起点对应的幸存路径进行长度为L的回溯，再继续回溯长度D，同时进行判决输出，得到长度为D的译码结果。

前向路径量度计算方法和路径回溯方法依据维特比算法。维特比算法为本领域内公开技术，此处不再赘述。

步骤7：合并每个分段的译码结果，得到译码输出码流信息。

下面对照图3叙述GPU设备上分段间并行译码方法。

如图3所示，以并行处理分段数N_t＝4为例进行说明。首先，按照图1中所示方法对输入卷积码码流信息中长度为N_t×D的部分进行分段，得到N_t个长度为D+2L的分段。然后，译码器启动N_t个译码处理单元，分别映射N_t个分段，进行并行的维特比译码。最后，将各译码处理单元输出的长度为D的译码结果进行合并，得到长度为N_t×D的译码输出，作为此次并行分段译码的输出。之后，对输入码流信息的下一个N_t×D的部分重复上述操作，直至码流末尾。其中，对于并行处理分段数N_t的选择，由GPU硬件条件和对译码器延时的要求共同决定。

下面叙述对卷积码网格图中蝶形结构的分组方法。

首先进行符号定义。一个码率为1/R，约束长度为K的卷积码记作(R，1，K)卷积码；定义N表示编码器状态总数，且有N＝2^v，其中，v＝K-1；定义S₀,S₁,…,S_N-1分别表示N个状态；定义D_v-1,D_v-2,…,D₀分别为编码器的v个移位寄存器的状态，对于状态S_d，其编号d为移位寄存器对应的二进制数，即d＝(D_v-1D_v-2…D₀)₂；定义g⁽¹⁾,g⁽²⁾,…,g^(R)分别表示卷积码的R个生成多项式，其中，r＝1,2,…R；定义x表示编码器当前输入比特信息；定义c(S_d,x)表示在状态S_d时，输入比特x对应的编码器输出符号。

下面对照图4叙述卷积码网格图中的蝶形特征。

对于卷积码N个状态中的四个状态：S_2j，S_2j+1，S_j，S_j+N/2构成一个状态转移图，如图4所示，称为蝶形结构，记作B_j。其中，j＝0,1,2,…N/2-1。定义α，β，γ，θ分别表示四条分支对应的输出符号。在四条分支中，两条上分支表示输入比特x＝0时的状态转移，两条下分支表示输入比特x＝1时的状态转移。即有关系：α＝c(S_2j,0)，β＝c(S_2j,1)，γ＝c(S_2j+1,0)，θ＝c(S_2j+1,1)。经过推到可以得到如下关系式：

$\beta =g_{K-1}\oplus \alpha ---\left(1\right)$

$\gamma =\alpha \oplus g_0---\left(2\right)$

$\theta =g_{K-1}\oplus \alpha \oplus g_0---\left(3\right)$

表示卷积码R个生成多项式的第k次幂系数组成的向量，表示向量按位异或操作。

由公式(1)～(3)可以得到以下结论：对于给定了编码方式的卷积码，一旦确定了α的值，则β，γ，θ的值均可以唯一求得。因此，可以根据α取值的不同，将网格图中N/2个蝶形结构进行分组，同一组蝶形结构具有完全相同的分支路径，组数N_c＝2^R。

对蝶形结构进行分组的一个好处在于，在前向路径量度计算过程的每个阶段中，对于每组蝶形中的状态路径信息的更新，只需计算四条分支量度BM。计算量由原来的2N减少到4N_c，降低了前向路径量度计算过程中的运算复杂度，减少了存储资源消耗。

下面叙述本发明所提出的基于GPU的卷积码高速并行译码架构。所述的基于GPU的卷积码高速并行译码器，主要包括位于主机和GPU设备上的初始化模块、位于主机的串并转换器、位于GPU设备的前向计算内核和回溯内核。

初始化模块，用于对主机和GPU设备进行初始化操作。

主机初始化包括在主机上设置数据接收缓存区、数据发送缓存区、第一分段信息存储器和第一分段译码结果存储器。主机发送控制信号，激活GPU设备。数据接收缓存区对主机接收的码流信息进行存储；数据发送缓存区对主机发送的译码输出码流信息进行存储。

GPU设备初始化包括分配GPU全局内存空间，创建异步流；在GPU设备上设置第二分段信息存储器、第二分段译码结果存储器、路径量度存储器、幸存路径存储器、网格图存储器和蝶形分组器。

分段信息存储器对串并转换后的各分段进行存储；分段译码结果存储器对分段译码结果进行存储。路径量度存储器对前向路径量度计算中得到的路径累积量度进行存储；幸存路径存储器对前向路径量度计算中筛选出的幸存路径进行存储。网格图存储器对卷积码对应的网格图进行存储。蝶形分组器对卷积码的蝶形结构进行分组，对于码率为1/R，约束长度为K的卷积码(R，1，K)，蝶形分组器对该卷积码网格图中的N/2个蝶形结构进行分组，同一组蝶形结构具有完全相同的分支路径，组数N_c＝2^R，N表示编码器状态总数，N＝2^K-1。

串并转换器，位于主机，对接收的码流信息进行分段和交叠处理，将各分段存入第一分段信息存储器。串并转换器还将第一分段译码结果存储器中存储的分段译码结果进行合并，输出给数据发送缓存区。

GPU设备译码时，首先分配一条异步流，主机通过异步传输方式将第一分段信息存储器内的各分段传入GPU设备的第二分段信息存储器。然后，启动前向计算内核，前向计算内核从第二分段信息存储器中获取各分段，对每个分段的每个状态进行前向路径量度的计算，得到各状态的路径累积量度和幸存路径并存入相应的存储器。在前向计算内核执行结束后，启动回溯内核。回溯内核对每个分段以估计的状态为起点沿幸存路径进行回溯，同时完成译码判决，输出译码结果，存储在第二分段译码结果存储器中。在GPU设备译码完成后，GPU设备通过异步传输方式将第二分段译码结果存储器中的分段译码结果传入主机的第一分段译码结果存储器中。

图5是译码器的整体结构图，表明了译码器各个存储单元和计算单元的分布与联系。其中，GPU译码器通过全局内存和主机内存之间数据的异步传输实现分段码流的输入和译码结果的输出。CPU提供控制信号调度GPU内核工作。GPU流多处理器簇依次执行前向计算内核和回溯内核。在前向计算内核执行过程中，读入常量内存中的网格图信息和全局内存中的分段码流信息，计算分支量度并更新路径累积量度和幸存路径信息。在回溯内核执行过程中，读入全局内存中的幸存路径信息，回溯并输出判决码字信息。

下面对照图6叙述GPU内核中线程映射方式，图6以N_c＝4为例。

首先，叙述前向计算内核中的线程映射结构。每个前向计算内核启动32·N_c·N_c·N_bl条线程，其中包括N_c·N_bl个线程块，每个线程块由N_c个线程束组成，每个线程束由32个线程组成，N_bl表示回溯内核中线程块个数。对于每个分段，由N_c条线程共同完成前向计算过程，其中每个线程分别映射一个蝶形分组；对于32个分段，由N_c个线程束完成前向计算过程，其中相同偏移量的N_c条线程映射同一个分段。因此，每个前向计算内核一共映射N_t＝32·N_c·N_bl个分段。

对于回溯内核，每个回溯内核一共启动32·N_c·N_bl条线程，其中包括N_bl个线程块，每个线程块由N_c个线程束组成，每个线程束由32个线程组成。对于每个分段，由一个线程单独完成回溯过程；对于32个分段，由一个线程束完成回溯过程。因此，每个回溯内核一共映射N_t＝32·N_c·N_bl个分段。

下面叙述GPU译码器中各存储单元的设计方法。

首先，阐述幸存路径信息的存储结构。幸存路径信息存储于GPU片外全局内存中，其存储结构如图7所示，由前向计算内核写入，由回溯内核读出，属于读写存储器。GPU中全局内存访问以一个线程束为基本单位，一次读写32个连续存储信息。对幸存路径信息的访问需满足GPU内存合并访问机制，以保证内存带宽。其存储结构可用如下公式表示：

SP[D+2L][N_c][32·N_c·N_bl](4)

在该三维结构中，第一维表示分段长度，第二维表示蝶形分组数，第三维表示分段数。每个存储单元拥有N/N_c个存储比特位，对应每个蝶形分组中的N/N_c个状态，如下所示：

在前向路径量度计算的第s个阶段，内核的第b个线程块的第w个线程束中的第t条线程，更新幸存路径SP[s][w][b·32+t]；则一个线程束组成一次合并的连续访问：SP[s][w][b·32]～SP[s][w][b·32+31]。

在回溯过程的第s个阶段，内核的第b个线程块的第w个线程束中的第t条线程，通过N_c次内存访问依次读取幸存路径

SP[s][0][b·N_c·32+w·32+t],…,SP[s][N_c-1][b·N_c·32+w·32+t]

共N_c个信息；则第g次访问中，一个线程束组成一次合并的连续访问：SP[s][g][b·N_c·32+w·32]～SP[s][g][b·N_c·32+w·32+31]。这样，两个内核中的幸存路径信息操作均满足了合并访问机制。这也是应用蝶形分组的另一个好处。

下面阐述路径累积量度信息的存储结构。路径累积量度信息存储于GPU片上共享内存(SMEM)中，以前向计算内核为生命周期，以线程块为作用域。路径量度存储器使用的是GPU片上共享内存资源，这种存储方式设计避免了共享内存bank冲突。

对于前向计算内核中的每个线程块，共享内存的分配方式如下所示：

PM[N][32](6)

在该二维结构中，第一维表示状态数，第二维表示分段数。由于一个线程块所映射的分段数为32个，因此第二维大小为固定值。由于GPU共享内存中32个存储体(bank)横向排列的特点，使得同一分段中的状态信息属于同一bank。因此，对于线程束中的任意一条线程t，必定只访问第t个bank中的信息PM[*][t]，避免了线程间的bank冲突，保证了共享内存的访问效率达到100％。

GPU全局内存合并访问机制以及共享内存bank机制为本领域内公知常识，可参见文档《CUDA C Programming Guide》，在此不作赘述。

所述的网格图存储器使用的是GPU常量内存(CMEM)资源。

所述的异步流和异步传输通道实现了数据传输之间、内核之间以及数据传输和内核执行之间在时间上的交叠。其中，数据传输之间的交叠是指主机到设备(H2D)和设备到主机(D2H)之间的传输交叠。

所述的分段信息存储器和分段译码结果存储器镜像存在于主机和GPU设备。其中，在主机上使用系统内存，在GPU上使用片外全局内存(GMEM)资源，存储方式设计满足GPU全局内存合并访问机制。

实施例：

以下结合附图，对本发明的一个实施例进行进一步详细说明。

如图8所示，为一个(2，1，7)卷积码的编码器框图。该卷积码的两个生成多项式分别为g⁽¹⁾＝[1111001]和g⁽²⁾＝[1011011]。其中，其蝶形结构中的分支α有4种取值：00，01，10，11，相应的β，γ，θ取值如图9所示，即：

$\beta =g_{K-1}\oplus \alpha =\left[11\right]\oplus \alpha =\bar{\alpha }---\left(1\right)$

$\gamma =\alpha \oplus g_0=\alpha \oplus \left[11\right]=\bar{\alpha }---\left(2\right)$

$\theta =g_{K-1}\oplus \alpha \oplus g_0=\left[11\right]\oplus \alpha \oplus \left[11\right]=\alpha ---\left(3\right)$

对该卷积码的N＝64个状态对应的32个蝶形结构进行分组，组数N_c＝4，每组8个，结果如下表所示：

组号αβγθ蝶形B_j编号j0001111000 2 12 14 21 23 25 271011010011 3 13 15 20 22 24 262100101104 6 8 4 10 17 19 29 313110000115 7 9 11 16 18 28 30

其中，蝶形结构B_j包含两个状态S_2j和S_2j+1。

本发明提出的译码器的译码流程如图10所示。译码过程分为两个阶段，分别为译码初始化阶段和译码阶段。首先介绍初始化阶段。初始化阶段包括以下三个步骤：

步骤1，主机初始化。主机启动系统线程，分配内存空间。设置接收缓存区H_C1，用于存储接收码流信息，大小为N_t·D·R。设置发送缓存区H_C2，用于存储译码结果，大小为N_t·D。设置存储区H_S，用于存储分段组，大小为N_t·(D+2L)·R。设置存储区H_R，用于存储分段译码结果，大小为N_t·D。其中，分段数N_t＝32·N_c·N_bl。

步骤2，GPU设备初始化。主机发送控制信号，激活GPU设备。分配GPU全局内存空间，创建3条异步流，如图11所示。

设置存储区D_R，用于存储分段组，大小为N_t·(D+2L)·R。设置存储区D_S，用于存储分段译码结果，大小为N_t·D。设置存储区SP，用于存储译码过程中幸存路径信息，大小为N_t·(D+2L)·N。设置路径量度存储区PM，用于对前向路径量度计算中得到的路径累积量度进行存储。设置幸存路径存储器，用于对前向路径量度计算中筛选出的幸存路径进行存储。设置网格图存储器，用于对卷积码对应的网格图进行存储。设置蝶形分组器，用于对卷积码的蝶形结构进行分组，将网格图中N/2个蝶形结构进行分组，同一组蝶形结构具有完全相同的分支路径，用于提供前向计算内核中的线程与状态映射关系。

步骤3，码流初始化。主机接收其他设备(如数据采集卡)传入的码流信息，并存储于内存缓存区H_C1。当缓存区满，对接收信息进行串并转换，生成N_t组分段，并存储于H_S，等待传入GPU进行译码。

译码初始化阶段之后，进行GPU译码阶段。该阶段包括以下几个步骤：

步骤4.1，分配异步流。为本次译码分配一条空闲异步流。若没有空闲异步流，则选择一条最小负荷异步流。

步骤4.2，数据传输H2D。通过异步传输方式将N_t组分段信息由存储区H_S传入存储区D_R中。

步骤5，启动前向计算内核K1。分配线程网格，启动N_c·N_bl个线程块，共32·N_c·N_c·N_bl条线程，完成分段维特比译码的前向路径量度计算过程。

步骤6.1，同步。设置同步点，等待内核K1执行结束。选择全零状态作为回溯过程的起点。

步骤6.2，启动回溯内核K2。分配线程网格，启动N_bl个线程，共32·N_c·N_bl条线程，完成分段维特比译码的回溯过程。

步骤7.1，数据传输D2H。通过异步传输方式将32·N_c·N_bl组分段译码结果由存储区D_S传入存储区H_R中。

步骤7.2，译码结果串并转换。将存储区H_R中的分段译码结果合并转换为长度为N_t·D译码结果，并存储于发送缓存区H_C2，等待传送给下一级设备。

下面进一步说明步骤5中前向计算内核K1的执行过程。

步骤5.1，分配GPU共享内存空间，设置路径累积量度存储区PM，初始化为零。对于每个线程块，PM大小为N·32。分配寄存器资源，定义临时变量。

对于线程块b∈[0,N_bl·N_c)中线程束w∈[0,N_c)中的线程t∈[0,32)，并行执行以下步骤5.2～步骤5.7：

步骤5.2，记s∈[0,D+2L)，初始化s＝0，计算偏移量tid＝b·32+t。

步骤5.3，从存储区D_R中读取一个码字符号信息C_tid(s)。

步骤5.4，根据w的取值选择相应的蝶形分组w，计算四条分支量度，计算方法参照维特比算法：

BM_α＝distance{C_tid(s),α}

BM_β＝distance{C_tid(s),β}

BM_γ＝distance{C_tid(s),γ}

BM_θ＝distance{C_tid(s),θ}

步骤5.5，对于蝶形分组w中的每个蝶形B_j中的状态，完成以下步骤(1)～(3)：

(1)从存储区PM中读取前次路径累积量度信息PM[2j][t]，PM[2j+1][t]。

(2)分别计算PM[2j][t]+BM_α和PM[2j+1][t]+BM_γ值，比较后选择较小值更新PM[j][t]，并标记幸存路径信息sp，上分支标记0，下分支标记1。

(3)分别计算PM[2j][t]+BM_β和PM[2j+1][t]+BM_θ值，比较后选择较小值更新PM[j+2^v-1][t]，并标记幸存路径信息sp，上分支标记0，下分支标记1。

步骤5.6，存储幸存路径信息SP[s][w][tid]＝sp。

步骤5.7，s加一，继续进入步骤5.3执行，直至s＝D+2L时结束。

下面进一步说明步骤6.2中内核K2的执行过程。

步骤6.2.1，分配寄存器资源，定义临时变量。

对于线程块b∈[0,N_bl)中线程束w∈[0,N_c)中的线程t∈[0,32)，并行执行以下步骤：

步骤6.2.2，记s∈[L,D+2L)，初始化s＝D+2L-1。记state表示当前状态，初始化state＝0。计算偏移量tid＝b·N_c·32+w·32+t。

步骤6.2.3，依次读取N_c个幸存路径信息：SP[s][0][tid]～SP[s][N_c-1][tid]。

步骤6.2.4，根据N_c个幸存路径信息计算下一步state值，计算方法参照维特比算法。

步骤6.2.5，若s小于D+L-1，则判决输出1比特译码结果，存储于D_s中。

步骤6.2.6，s减一，继续转步骤6.2.3执行，直至s＝L-1时结束。

综上所示，利用本发明提供的分段并行维特比译码方法和译码器装置，能够充分发挥GPU的特性，实现高速并行的卷积码译码。