基于四阶段并行处理的VDSL2维特比代码解码器

摘要

本发明公开了新的把维特比解码器的解码过程分为4个并行阶段的方法。在系统时钟的切当选择，发明平衡了解码速度和硬件消耗，所以我们设计出来的维特比解码器可以满足VDSL2系统最快速度的参数集，30MHz的解码速度的要求。在同时，4阶段的并行处理正好满足了速度的需求，新维特比解码器的硬件消耗，相比于单阶段解码，已经减少了很多。

说明书

相关申请交叉引用

本申请要求2005年12月22日提交的美国临时专利申请60/753，835的权益，其内容通过引用组合于此。

技术领域

本发明涉及维特比代码解码器，尤其涉及新型基于四阶段并行处理的VDSL2维特比解码器的硬件耗费降低。

背景技术

维特比运算法则被广泛地用于不同的信号处理系统中，例如那些关于通信或存储的，来对通过噪声信道传输的数据解码，并纠正比特错误。

在VDSL2系统中，网格编码调制变成一种必需的功能，必须被发送机和接收机支持。网格编码基本上是一个有规则的卷积编码器。在发送端，每两个子信道，就有一个比特从韦斯16状态四维编码器被提取出来，与未经调制的比特结合，组成编码过的比特，以及每个子载波相应的星座图。在接收机端，基于最小耗费特定轨迹的计算，维特比解码器用来提取原来的比特。相比网格编码，接收器端的维特比解码更难设计，消耗更多的门电路。所以维特比解码在整个VDSL2系统设计中是一个非常重要的设计部分。

发明内容

本发明提出一个新的方法来把整个维特比解码器的解码过程划分为4个并行处理的阶段，本着减少硬件耗费的目的。有了系统时钟的恰当选择，我们以硬件耗费来平衡解码速度，所以我们设计的维特比解码器可以满足VDSL2系统中最高速参数集的解码速度需求，30MHz参数集。在同时，四阶段并行满足速度需求，我们减少了硬件耗费，相比于单阶段的解码更快。

依照本发明，一个VDSL2维特比解码器包含一个分支度量计算及用在所有可能分支中寻找最小耗费的计算方法，计算每个分支耗费的更新模块。以及用先前的节点耗费增加的分支耗费，并寻找所有可能分支的最小耗费的其他路径。解码器还包含一个信息序列更新模块，来存储所有的路径。还有一个判决和信息取回模块，用于寻找所有可能路径中耗费最小的那条。其中度量计算及它的更新处理工作，以及被分成4个并行阶段的更新模块，4个并行阶段是VDSL2网格编码图的4个子组：(0，1，2，3)，(4，5，6，7)，(8，9，A，B)和(C，D，E，F)。其中系统时钟的选择是基于整个VDSL2系统的解码速度需求

附图说明

通过以下相关的描述、声明及附图，本发明的这些以及其他特性、各方面及优势将更容易被理解，其中：

图1展示了VDSL2网格编码调制。

图2展示了韦斯16状态卷积码编码器。

图3展示了VDSL2网格编码图。

图4展示了分支度量耗费计算和适配图。

图5展示了分支度量计算和更新图。

图6展示了最小状态耗费计算。

图7展示了信息序列更新和判决。

具体实施方式

VDSL2网格编码调制介绍

在VDSL2系统中，扩展星座图被分成了子集或者陪集。韦斯编码器中的4维陪集每一个都可以被写作2个二维陪集的笛卡儿积。如下表所示：

表1：四维陪集

星座图点的LSB(v₁，v₀)和(w₁，w₀)包含二维陪集的指数i，在二维陪集中，有星座点，而且实际上就是指数的二进制表示。3比特的(u₂，u₁，u₀)被用来选择8个可能的四维陪集中的一个。8个陪集表示为i是二进制表示(u₂，u₁，u₀)的整数。额外的比特u3决定了两个二维陪集的笛卡尔积中的哪一个，是从四维陪集中选择出来的。

比特(v₁，v₀)和(w₁，w₀)是从(u₃，u₂，u₁，u₀)中，用线性方程组计算出来的，如图1所示。

卷积码编码器是韦斯16状态卷积码编码器，如图2所示。

图3展示了网格图，(S₃，S₂，S₁，S₀)是韦斯编码器中的现存状态，(T₃，T₂，T₁，T₀)是下个状态。现存状态(S₃，S₂，S₁，S₀)的左列表示为：(S₃，S₂，S₁，S₀)从顶到底每个分支的输入(u₂，u₁，u₀)。下个状态(T₃，T₂，T₁，T₀)的右列，也表示为(T₃，T₂，T₁，T₀)从顶到底每个分支的输入(u₂，u₁，u₀)。如果我们也考虑输入u₃，每个分支实际上代表两种可能的分支，即u₃＝0 or u₃＝1。然而，基于到输出集(v₁，v₀，w₁，w₀)要达到最小距离，u₃可以被立即解码。

一般的网格编码器的复杂度分析

一个标准的网格编码处理一般包含3个连续部分，分支度量计算及更新，信息序列更新，和判决及信息取回。分支度量计算及更新使用最多的门电路，因为它为每个分支计算耗费，以及用前节点的耗费加到分支耗费上。另外，它需要在所有可能的分支中，寻找最小耗费的路径。信息序列更新处理将为每个末端点上每个路径更新信息数组，基于分支度量计算及更新处理的路径系数。信息序列更新处理需要极大的内存来存储所有的路径。精确的程度取决与节点数量和网格解码深度L。网格解码深度定义了我们需要跟踪返回多少路径分支。L的长度越长，就需要越多的内存。然后路径长度超过网格编码追踪深度L，判决和信息取回用最低耗费寻找一个路径。然后L-step-back分支的相关信息比特被取回，并与分支上未编码的比特一起，发送到下个处理模块。

现在我们分析正规的维特比解码器的复杂度。分支度量计算及更新模块需要最多的芯片面积，因为它主要由加法器和比较器组成。如上面的网格编码图所示，每个节点有4个进来的分支。每个分支实际上代表两个可能性，u₃＝0或u₃＝1。计算每个分支的度量的第一步就是把被接收的矢量(v₁，v₀，w₁，w₀)与所需要的矢量(v₁，v₀，w₁，w₀)进行比较，为了每个分支上的每个可能的路径，这意味着每个分支需要两个4比特的比较器。下一步就是加上现有的分支耗费到前节点的分支耗费，来获得每个进来分支的总的耗费。如果我们用12比特作为总的耗费，我们需要4个12比特的加法器来计算所有的4个进来的分支。然后四个进来分支的总的耗费与寻找节点路径作比较，这需要3个12比特的比较器。这个处理过程在16个节点上重复。现在我们可以算一下我们需要的分支度量计算及更新模块的资源。它需要总共128个4比特比较器，128个单比特计数器，64个2比特比较器，64个12比特加法器，48个12比特比较器。我们可以看到我们要执行度量计算及更新的话，需要极大的数量的资源。

信息序列更新模块不需要很多的逻辑，而需要内存来为每个节点存储一个信息比特序列。对于解码深度为L，每个子载波最大15未编码比特来说，它需要总共29×16×L比特的寄存器，(29比特给每个分支进入，其中26个未编码比特，3个解码比特)。原因就是寄存器用来代替SRAM，因为它需要一次同时更新所有的信息比特序列。这是由于前一个节点的相同的信息比特寄存器也被用于下一个节点了。所以，更新处理需要在一次时钟周期内被完成。

判决和信息取回模块在16条下个节点的路劲中，寻找最小耗费的路劲。这需要总共15个12比特比较器。信息取回是琐碎的，由移位寄存器和寄存复用组成。

总上面的分析，我们可以看到大多数的计算资源被用做分支度量计算及更新模块和判决及信息取回模块。因此，我们提出一个新型的基于并行处理的维特比解码执行方法，来减少3/4的计算资源的使用。下一章会介绍详细的部分。

四阶段并行处理简化复杂度的维特比解码器

前一章节的分析给了我们一些基本的计算复杂度的思想。我们需要的维特比解码处理的计算数量，取决于总的比较操作，加法等。然而，仔细选择了比较快的系统时钟，放我们可以分时使用一些比较器，加法器来减少我们实际所需的比较器和加法器的数量。这个系统时钟的选择基于整个VDSL2系统的解码速度的需求。也基于网格编码图上，我们可以找到的结构模式。

首先，让我们看一下速度需求。最大的速度需求限制来自于30MHz参数集，它有8.625KHz的子载波频率，8kHz的帧频，总共4096个子载波。因为维特比解码基于一对子载波的，那么最大的维特比解码处理的重复次数就是2048.实际的需求可以更小，因为子载波被分为上行和下行。所以每个方向上，网格对的数目将少于2048.然而，为了保守一些，灵活一些，我们仍然用2048.我们假设信息序列更新和判定及信息取回各需要一个时钟周期。

现在关键问题是我们如何把分支度量计算及更新处理分成最小的硬件需求，而仍然要满足速度需求。如果我们假设我们在一个时钟周期内完成了度量计算及更新，那么最小的满足速度需求的系统时钟可以这样计算：2048×3×8KHz或者49.152MHz。现在我们看网格图，我们可以看到，每个前节点仅到达四个下面的节点，每个下面的节点，仅与四个前面的节点相连。此外，我可以看到连接到下面四个节点0，1，2，3的分支，来自于相同的前节点0，4，8，C。

连接到下面4个节点4，5，6，7的分支，都来自与同一个前节点：1，5，9，D。连接到下面节点8，9，A，B的分支，都来自于前节点2，6，A，E.连接到下面节点C，D，E，F的分支，都来自于前节点3，7，B，F.这意味着我们可以完全把网格图分为4个独立的子组，并越过复杂的复用方案，探究分时机制。所以，如果我们把度量计算及更新处理分为4个子组：(0，1，2，3)，(4，5，6，7)，(8，9，A，B)，(C，D，E，F)的并行阶段，那么支持VDSL2 30MHz参数集的最小系统时钟就是2048×6×8KHz或者98.304MHz。所以我们选择141.312MHz作为我们的系统时钟，这是基于两倍的70.656MHz(VDSL2 30MHz参数集的采样时钟频率)。这对于满足我们的四阶段并行方案的98.304MHz的最小系统时钟需求已经足够了。

基本的分支度量计算及适应(BMCA)分块图如下，图4。我们用4x强调同时计算所有四个分支到下个单独的节点的度量耗费。mts_vec0，mts_vec1，mts_vec2，mts_vec3是每个分支的输出的希望值，基本上这是由所给的网格树结构所决定的。如图1，2，3和执行中的静态配置值。mts_vec0，mts_vec1，mts_vec2，mts_vec3和(v₁，v₀，w₁，w₀)之间的距离是每一分支的欧几里得距离，在图3的网格图所示。分支度量和比较决定了u₃，这是通过寻找每个分支的最小可能性得到的。因此表1中，两个分支中的一个晶被选为四维陪集。分支度量与前节点的耗费加到一起。三个比较器通过辨别与最小耗费相交的前节点，找到四个分支最小的耗费及相关路径。另外，前节点的代号也被用于在(u₂，u₁，u₀)三个只能够选出一个，作为最后的胜者，并且相关的值，四个分支的最小的耗费，及相关的前节点的代号，传送给调用模块

如我们前面所讨论的，在分支度量计算及更新过程中，16个下节点分支度量计算被分为4阶段并行。图5展示了分支度量计算及更新处理的硬件图。这基本上举出了4个BMCA子模块的例子，来处理每个组中的最小耗费的判决。

在图5中，我们用4xBMCA作为我们的标记，来强调同时计算四个分支到下个单节点的分支耗费这个事实。2比特的计数器被用来产生每个阶段的基准信号。所有16个节点，如图3所示，被分为4个不同的组，它相关的耗费也被分为4个组，取名：

group 1：cost0，cost1，cost2，cost3，

group 2：cost4，cost5，cost6，cost7，

group 3：cost8，cost9，cost10，cost11，

group 4：cost12，cost13，cost14，cost15。

基准信号由2比特计数器产生，它将决定哪个组被接收到分支度量耗费计算及适应模块，如图4.在4阶段处理的最后，每个组的最小耗费的胜出节点，带着相关信息一起输出，这些相关信息包含计算每个组的胜出节点的耗费，组成胜出分支的前节点的标签，相关的解码候选向量(u2，u1，u0).这个耗费的值cost0，与网格图起点相始化到0.

4个下节点的分支度量，在每个时钟周期内计算。对于是时钟周期是0，路径及相关的耗费，及下个节点(0，1，2，3)的解码(u₃，u₂，u₁)比特，在前节点(0，4，8，C)被选作输入的时候计算。对于时钟周期1，下节点(4，5，6，7)的相同的参数，在前节点(1，5，9，D)被选作输入的时候计算。对于时钟周期2，下节点(8，9，A，B)的相同的参数，在前节点(2，6，A，E)被选作输入的时候计算。对于最后一个时钟周期，下节点(C，D，E，F)的相同的参数，在前节点(3，7，B，F)被选作输入的时候计算。因此每个分支的最大欧几里德距离为2.TCM的总长度小于2048。每个阶段我们需要12比特的耗费，所有阶段需要16个12比特寄存器。因此分支度量在4个4阶段组中更新，我们需要2组耗费表，为每个阶段的新旧耗费计算。所以，在存储方面，总共需要32个12比特寄存器。

在判决和信息取回处理上，我们需要找到通过16阶段的最小耗费，来决定快L步的路径。这也可以被分为4阶段来减少3/4硬件复杂度。原理图如图6所示。同样的，2比特计数器产生4阶段的基准信号。前面的耗费被初始化到一个大的数字，比如4096，这基本上在与第一个耗费的值比较时，取代了第一阶段。在每个阶段的最后，最小耗费在相关节点被输入最小寄存器时，将被输入前耗费寄存器。在四个阶段后，最小的耗费及相关的节点指数被转换出来，用作信息序列的更新和判决模块，如图7

在四个周期后，前耗费将包含最小耗费，min_idx将包含相关最小耗费的节点号。min_idx被用作取回早期的L步骤的信息比特(u₃，u₂，u₁)。如果维特比解码器到达最后TCM对，min_idx将强制为0，到达阶段0的分支将被考虑为路径候选，因为发送机上的TCM将确保最后2个网格对的韦斯编码阶段被(u₂，u₁)强制回到0。非常清楚，最后2对的解码器(u₂，u₁)将被丢弃，不送到PMS

我们维特比解码器的最后步骤，就是为所有阶段更新信息序列输出解码信息比特，如图7.网格图中每个节点的被解码的候选向量(u₃，u₂，u₁)，如图3所示，是一个先进先出，基本上保存了每个节点的路径。同时，与分支相关的解码信息比特(u₃，u₂，u₁)，基于最小分支指数，由图6中的最小阶段耗费计算模块决定。

在维特比解码中，仅最后3比特寄存器将输出作解码信息比特。然而，如果维特比解码器到了最后一对，阶段0的除了(u₂，u₁)所有的信息寄存器将被输出。在图7中，为编码比特没有展示。同样，未编码比特将被存储并用同样的方法算作(u₃，u₂，u₁)。

这个发明已经被描述成相关的可被效仿的例子，在不背离发明技术范围的情况下的修改或替代是可以被理解的。另外，可以作许多的修改来适应特定的方案或者作为不违背必要技术范围的教学发明材料。因此，预期这个发明是的不会对以特殊的，以最好方式的具体实现而限制的，但是这个发明将包含所有的附加声明。