一种维特比译码方法及维特比译码器

摘要

本发明实施例公开了一种维特比译码方法及维特比译码器，其中，一种维特比译码方法包括接收输入的两路数据；根据状态转移蝶形对的状态转移规则，对接收到的两路数据进行计算，得到各状态的分支度量值；利用计算得到的分支度量值，每次针对8个状态转移蝶形对，并行地对16个状态前一时刻的路径度量值进行加比选ACS处理；存储经ACS处理后得到的各状态的路径度量值及所述路径度量值的状态转移关系标记；比较存储的各状态的路径度量值，搜索出最大的路径度量值；根据存储的状态转移关系标记，对所述最大的路径度量值进行回溯，并输出译码结果。本发明实施例提供的技术方案在保证维特比算法译码效果的前提下，有效提高了译码速度。

说明书

技术领域

本发明涉及无线信息传输领域，尤其涉及一种维特比译码方法及维特比译码器。

背景技术

无线信息传输系统普遍采用RS编码和卷积编码级联的方式作为信道编码部分来对抗无线信道产生的差错。卷积码是一种常用的差错控制编码，对于卷积码(n₀，k₀，m)，表示该卷积码编码器将k₀比特信息段编成n₀比特的码组，即每一时刻送至卷积编码器的输入信息元为k₀个，相应地卷积编码器输出n₀个码元，并且输出的n₀比特码组不仅与当前k₀比特信息段有关，还与之前输入的(m-1)个信息段有关联，其中，m为大于1的整数，m(又称约束长度)等于移位寄存器的个数加1，卷积码用生成序列来表示输入与输出间的关系，其中，表示第K个移位寄存器的输入端到第j个模2加法器输入端的连接线情况，若有连线，则若无连线，则如图1所示为卷积编码(2，1，7)对应的卷积编码器，1个比特输入对应有2比特输出，约束长度为7，移位寄存器个数为6个，根据各个移位寄存器的输入输出端与各个模2加法器输入端的连接线关系，其生成序列g₁＝(1111001)₂和g₂＝(1011011)₂，因此，该卷积编码器生成的多项式为(171，133)₈。

维特比(Viterbi)算法是目前运用得最广泛的卷积编码的译码算法，Viterbi译码方法主要从2^m-1种(m为卷积编码器约束长度)可能状态中更新最佳状态和传输的最可能位序列，其将接收到的编码信号与内建的参考值做运算，找出最可能的路径，并依此路径还原正确的数据，以完成译码流程。由于维特比算法的复杂性，其一直是卷积编码在工程实现的设计重点。

对于(2，1，7)卷积编码，编码过程存在2^7-1(64)种可能状态，如图1的卷积编码器，若当前时刻寄存器1～6中的值为000000时，表明当前状态为S0，若此处输入1，则寄存器1～6中的值变为100000时，当前状态从S0转变为S1，以此类推，当寄存器1～6中的值为111111时，表明当前状态为S63。由此，各状态转移图可由类似蝴蝶形状的蝶形图表示，其中，Si和Si+32构成一对蝶形图，根据不同的输入，蝶形图的两个目的状态分别对应于S2i和S(2i+1)，其中，i为0到31的任一整数。图2所示为i为0的一个蝶形对，如图所示，若当前状态为S0，则当输入0时，状态S0经由状态转移方向转移至状态S0，输出XY为00，当输入1时，状态S0经由状态转移方向转移至状态S1，输出XY为11；若当前状态为S32，则当输入0时，状态S32经由状态转移方向转移至状态S0，输出XY为11，当输入1时，状态S32经由状态转移方向转移至状态S1，输出XY为00。Viterbi译码即为上述卷积编码的逆过程。

传统的Viterbi译码的实现方法是：先计算输入的两路数据的分支度量值，然后进行加比选处理(即ACS，加法-选择-比较)，最后回溯输出译码结果。在ACS处理中，每个周期针对一个蝶形图进行处理，当经过多个周期完成所有状态的路径度量值计算后，对所有状态进行最大径搜索，最后通过状态转移标识寄存器的数值，回溯输出的上述输入的两路输入的译码结果。

上述方法适用于状态数量较少的卷积编码(如(2，1，2)卷积编码)，但对应于状态数量较多的卷积编码(如(2，1，7)卷积编码)，则需要较长的时间才能完成译码，译码速度慢。

发明内容

本发明实施例提供了一种维特比译码方法及维特比译码器，用于实现对无线信息传输信道中的卷积编码码流的快速译码。

为解决上述技术问题，本发明实施例提供以下技术方案：

一种维特比译码器，包括：

分支度量值计算单元，用于接收输入的两路数据，并根据状态转移蝶形对的状态转移规则，对接收到的两路数据进行计算，得到各状态的分支度量值；

加比选单元，用于利用上述分支度量值计算单元计算得到的分支度量值，对各状态前一时刻的路径度量值进行加比选ACS处理，其中，上述加比选单元由8个并行执行的加比选模块组成，其中，每个加比选模块处理的4个状态转移蝶形对的相应分支具有相同的输入输出特性；

存储单元，用于存储经上述加比选单元处理后得到的各状态的路径度量值及上述路径度量值的状态转移关系标记；

最大值搜索单元，用于对上述存储单元存储的各状态的路径度量值进行比较，搜索出最大的路径度量值；

回溯输出单元，用于根据上述存储单元存储的状态转移关系标记，对上述最大的路径度量值进行回溯，并输出译码结果。

一种维特比译码方法，包括：

接收输入的两路数据；

根据状态转移蝶形对的状态转移规则，对接收到的两路数据进行计算，得到各状态的分支度量值；

利用计算得到的分支度量值，每次针对8个状态转移蝶形对，并行地对16个状态前一时刻的路径度量值进行加比选ACS处理；

存储经ACS处理后得到的各状态的路径度量值及上述路径度量值的状态转移关系标记；

比较存储的各状态的路径度量值，搜索出最大的路径度量值；

根据存储的状态转移关系标记，对上述最大的路径度量值进行回溯，并输出译码结果。

由上可见，本发明实施例中，利用各个状态转移蝶形对的状态转移规则，利用并行执行的8个加比选模块组成的加比选单元对各状态转移蝶形对进行处理，在同一周期完成8个状态转移蝶形对的加比选处理过程，在保证维特比算法译码效果的前提下，极大的提高了译码速度。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为(2，1，7)卷积编码器的结构示意图；

图2为本发明实施例中的状态转移蝶形对的示意图；

图3为本发明实施例中的译码方法的一个实施例流程示意图；

图4为本发明实施例中的维特比译码器的一个实施例结构示意图。

具体实施方式

本发明实施例提供了一种维特比译码方法及维特比译码器。

为使得本发明的发明目的、特征、优点能够更加的明显和易懂，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而非全部实施例。

实施例一，请参阅图3，本发明实施例中的维特比译码方法包括：

301、接收输入的两路数据；

原始数据是通过卷积编码后会被分成并行的两路数据(包含信道软信息，即编码后数据和信道噪声的叠加)后通过信道传输到维特比译码器中进行解码。

302、对接收到的两路数据进行计算，得到各状态的分支度量值；

根据状态转移蝶形对的状态转移规则，对接收到的两路数据进行计算，得到各状态的分支度量值。

由于原始数据在(2，1，7)卷积编码器处理的过程中，有64种可能状态出现，因此，维特比译码过程需要针对64种可能的状态(对应于32个状态转移蝶形对)进行计算并搜索出最大概率路径，以还原出原始的数据。

维特比在接收到输入的两路数据后，对两路数据进行计算，以求得各状态的分支度量值。

通过观察状态转移蝶形对发现，每条分支对应的两个软判决符号只存在四种组合：00，01，11，10。假设输入的两路数据为X1Y1，则相应的分支度量值的计算以下存在四种结果：

BM11＝X1+Y1；

BM10＝X1-Y1；

BM01＝-X1+Y1＝-(X1-Y1)＝-BM10；

BM00＝-X1-Y1＝-(X1+Y1)＝-BM11；

可见，通过计算两路数据的和与差，便可计算得到所有分支的分支度量值。

因此，本发明实施例中优化了分支度量值的计算方法，进一步提高了分支度量值的计算速度，其具体实现方法如下：

根据状态转移蝶形对的状态转移规则，得到每个状态的两条分支的软判决符号d1d2；

若某分支的d1d2为11，则将接收的两路数据相加，并将得到的值作为该分支分支度量值；

若某分支的d1d2为10，则将接收的两路数据相减，并将得到的值作为该分支分支度量值；

若某分支的d1d2为00，则将接收的两路数据相加后取反，并将得到的值作为该分支分支度量值；

若某分支的d1d2为01，则将接收的两路数据相减后取反，并将得到的值作为该分支分支度量值。

通过上述方法可更快地完成各状态的分支度量值的计算。

303、根据各状态的转移关系进行ACS处理；

通过采用分时复用的方式，每个周期完成8个状态转移蝶形对的ACS处理，经过4个周期完成所有32个状态转移蝶形对的ACS处理。

在实际应用中，维特比译码器的ACS处理过程可由8个加比选模块完成，通过预先设置每个加比选模块所要处理的状态转移蝶形对，使每个加比选模块每个周期处理一个状态转移蝶形对，利用分时复用实现8个加比选模块的并行执行，缩短ACS处理时长，提高整体的译码速度。

单个加比选模块中的ACS处理过程如下：

假设该加比选模块当前处理的状态转移蝶形对为如图2所示的状态转移蝶形对。则加比选模块首先将步骤302得到的状态S0、S1的分支度量值(每个状态包含两条分支，即存在两个分支度量值)，与状态S0、S1前一时刻的路径度量值相加，得到状态S0、S1当前时刻的路径度量值；状态S0比较其两条分支的路径度量值，选择较大的路径度量值保留，同样的，状态S1比较其两条分支的路径度量值，选择较大的路径度量值保留，完成该状态转移蝶形对的ACS处理。

304、存储各状态的路径度量值及各路径度量值的状态转移关系标记；

存储经步骤303处理后得到的各状态的路径度量值，即上述保留的各状态的较大的路径度量值，并且，对该路径度量值的状态转移关系标记进行存储，以便最后可利用该状态转移关系标记进行回溯。

如在步骤303中，经过一个周期完成8个状态转移蝶形对的ACS处理，则将经ACS处理后得到的16个状态的路径度量值进行存储，同时存储相应路径度量值的状态转移关系标记。

由于每个周期各加比选模块需要读取相应状态的路径度量值进行“加”操作，同时将“选”后的相应状态的路径度量值进行存储，为了避免在进行加比选处理时，先处理的状态转移蝶形对运算修改了后处理的状态转移蝶形对初始状态的路径度量值，本发明实施例利用两个路径度量值存储单元(两组寄存器)，分别对前一时刻经上述ACS处理后得到的各状态的路径度量值，和当前时刻经上述ACS处理后得到的各状态的路径度量值进行交替存储(即乒乓存储)。如，假设两组寄存器命名为REGA，REGB，则在加比选模块进行ACS处理时，第i个周期内，可从REGA中读出相应状态前一时刻的路径度量值，同时将经ACS处理后得到的该状态当前时刻的路径度量值N存入REGB中，在第i+1个周期，从REGB中读出相应状态前一时刻的路径度量值N，同时将经ACS处理后得到的该状态当前时刻的路径度量值存入REGA中，以此类推。

305、比较上述存储的各状态的路径度量值，搜索出最大的路径度量值；

对步骤304经ACS处理后得到的各状态的路径度量值进行比较，搜索出最大的路径度量值。

在实际应用中，可在每个周期，对ACS处理得到的16个状态的路径度量值进行两两比较，得到该周期中的最大的路径度量值，在4个周期之后，对得到的4个最大的路径度量(对应于4个周期)再进行两两比较，得到1个最大的路径度量值。进一步的，本发明实施例的译码方法还可判断比较得出的路径度量值是否超过预置的门限值，若超过，则将存储的所有路径度量值同时减去相同的数值，如可将存储的所有路径度量值同时减去2048，以避免用于存储的寄存器溢出。

可理解，由于编码过程中状态转移是由低状态向高状态转移，基于该规律下，当在最大值搜索过程中，通过比较得到两个或两个以上相等的最大路径度量值，则选择较低状态的路径度量值作为此次最大值搜索的结果。

306、回溯输出译码结果；

根据步骤305中搜索出的最大的路径度量值，可从寄存器中找出相应的状态转移关系标记，通过该状态转移关系标记进行回溯，则可得到相应的原始数据，即译码结果。

在实际应用中，每次可以8比特大小为回溯单位进行回溯，即每次回溯输出8比特的译码结果(即1个字节)，并在最后一次回溯时输出全部译码结果。可根据实际情况设定回溯次数，如对于736bit的编码数据块，则回溯的次数为(736-48)/8+1＝87次。

需要说明的是，本发明实施例的译码方法基于(2，7，1)卷积编码，可实现对(2，7，1)卷积编码输出的编码数据块的译码。

由上可见，本发明实施例中，利用各个状态转移蝶形对的状态转移规则，采用分时复用的方式，在同一周期对8个状态转移蝶形的加比选操作进行并行处理，在保证维特比算法译码效果的前提下，极大的提高了译码速度。

实施例二，为本发明实施例提供的维特比译码器，如图4所示，包括：

分支度量值计算单元401，用于接收输入的两路数据，并对该两路数据进行计算，得到各状态的分支度量值；

通过观察状态转移蝶形对发现，每条分支对应的两个软判决符号只存在四种组合：00，01，11，10。假设输入的两路数据为X1Y1，则相应的分支度量值的计算以下存在四种结果：

BM11＝X1+Y1；

BM10＝X1-Y1；

BM01＝-X1+Y1＝-(X1-Y1)＝-BM10；

BM00＝-X1-Y1＝-(X1+Y1)＝-BM11；

可见，通过计算两路数据的和与差，便可计算得到所有分支的分支度量值。

因此，本发明实施例中的维特比译码器优化了分支度量值的计算方法，对传统的分支度量值计算单元进行的改进，进一步提高了分支度量值的计算速度。本发明实施例中的分支度量值计算单元401具体可包括：

接收单元，用于接收输入的两路数据；

判决单元，用于根据状态转移蝶形对的状态转移规则，得到每个状态的两条分支的软判决符号；

第一计算单元，用于当上述软判决符号为11时，将接收的两路数据相加，并将得到的值作为相应分支的分支度量值；

第二计算单元，用于当软判决符号为10时，将接收的两路数据相减，并将得到的值作为相应分支的分支度量值；

第一取反单元，用于当软判决符号为00时，将上述第一计算单元计算得到的结果取反后作为相应分支的分支度量值；

第二取反单元，用于当软判决符号为01时，将上述第二计算单元计算得到的结果取反后作为相应分支的分支度量值。

通过对计算得出结果进行取反操作，无需重复运行，加快了各状态的分支度量值的计算过程。

加比选单元402，用于利用分支度量值计算单元401计算得到的分支度量值，对各状态前一时刻的路径度量值进行加比选ACS处理；

由图1的编码器可看出，移位寄存器的第4位对编码的结果没有影响，即状态Si和S(i+8)、S(i+16)和S(i+16+8)、S(i+32)和S(i+32+8)以及S(i+48)和S(i+48+8)(i＜8)是等效的。在此规律的基础上，本发明实施例对传统的加比选单元进行的改进，采用8个加比选模块组成加比选单元402，其中，采用分时复用的方式实现8个加比选模块的并行运作，每个周期由8个加比选模块共同完成8个状态转移蝶形对(16个状态)的ACS处理。其中，每个加比选模块处理4个状态转移蝶形对，且4个状态转移蝶形对的相应分支具有相同的输入输出特性。

假设一个状态转移蝶形对采用起始状态中较低的状态进行标记，如将图2所示的状态转移蝶形对标记为B0，则32个状态转移蝶形对可对应标记为B0，B1，B2，....，B31。则加比选模块对应处理的状态转移蝶形的设置可如表1：

表1

  加比选模块  状态转移蝶形对  ACS0  B0，B8，B19，B27  ACS1  B1，B9，B18，B26  ACS2  B2，B10，B17，B25  ACS3  B3，B11，B16，B24  ACS4  B4，B12，B23，B31  ACS5  B5，B13，B22，B30  ACS6  B6，B14，B21，B29  ACS7  B7，B15，B20，B28

上述加比选单元402经过4个周期可完成所有32个状态转移蝶形对的ACS处理，缩短ACS处理时长，从而提高了整体的译码速度。

单个加比选模块中的ACS处理过程如下：

假设该加比选模块当前处理的状态转移蝶形对为如图2所示的状态转移蝶形对。则加比选模块首先将分支度量值计算单元401得到的状态S0、S1的分支度量值(每个状态包含两条分支，即存在两个分支度量值)，与从存储单元403存储的状态S0、S1前一时刻的路径度量值相加，得到状态S0、S1当前时刻的路径度量值；状态S0比较其两条分支的路径度量值，选择较大的路径度量值并存储，同样的，状态S1比较其两条分支的路径度量值，选择较大的路径度量值存储，完成该状态转移蝶形对的ACS处理。

存储单元403，用于存储经加比选单元402处理后得到的各状态的路径度量值及各路径度量值的状态转移关系标记；

由于每个周期各加比选模块需要读取相应状态的路径度量值进行“加”操作，同时将“选”后的相应状态的路径度量值进行存储，为了避免在进行加比选处理时，先处理的状态转移蝶形对运算修改了后处理的状态转移蝶形对初始状态的路径度量值，本发明实施例的存储单元403可包括两个路径度量值存储单元(可由两组寄存器实现)，分别对前一时刻经加比选单元402处理后得到的各状态的路径度量值，和当前时刻经加比选单元402处理后得到的各状态的路径度量值进行交替存储(即乒乓存储)。如，假设两组寄存器命名为REGA，REGB，则在加比选单元402进行ACS处理时，第i个周期内，可从REGA中读出相应状态前一时刻的路径度量值，同时将经加比选单元402处理后得到的该状态当前时刻的路径度量值N存入REGB中，在第i+1个周期，从REGB中读出相应状态前一时刻的路径度量值N，同时将经加比选单元402处理后得到的该状态当前时刻的路径度量值存入REGA中，以此类推。

具体的，存储单元403还包括状态转移关系标记存储单元，用于存储经加比选单元402处理后得到的各状态的路径度量值的状态转移关系标记。在实际应用中，同样可采用两组寄存器交替存储状态转移关系标记，此处不作限定。

最大值搜索单元404，用于对存储单元403存储的各状态的路径度量值进行比较，搜索出最大的路径度量值；

具体的，最大值搜索单元404可包括4个最大值搜索模块，分别对每个周期加比选单元402处理得到的16个状态的路径度量值进行最大值比较，可采用两两比较的方法得到1个最大的路径度量值。

可理解，由于编码过程中状态转移是由低状态向高状态转移，基于该规律下，当最大值搜索单元404在最大值搜索过程中，通过比较得到两个或两个以上相等的最大路径度量值，则选择较低状态的路径度量值作为此次最大值搜索的结果。

回溯输出单元405，用于根据存储单元403存储的状态转移关系标记，对最大值搜索单元404得到的最大的路径度量值进行回溯，输出译码结果；

回溯输出单元405根据中最大值搜索单元404搜索出的最大的路径度量值，可从存储单元403中找出相应的状态转移关系标记，通过该状态转移关系标记进行回溯，则可得到相应的原始数据，即译码结果。

在实际应用中，回溯输出单元405每次可以8比特大小为回溯单位进行回溯，即每次回溯输出8比特的译码结果(即1个字节)，并在最后一次回溯时输出全部译码结果。可根据实际情况设定回溯输出单元405的回溯次数，如对于736bit的编码数据块，则可设定回溯输出单元405回溯的次数为(736-48)/8+1＝87次。

需要说明的是，本发明实施例的维特比译码器基于(2，1，7)卷积编码，可实现对(2，1，7)卷积编码输出的编码数据块的译码。

由上可见，本发明实施例中，利用各个状态转移蝶形对的状态转移规则，利用并行执行的8个加比选模块组成的加比选单元对各状态转移蝶形对进行处理，在同一周期完成8个状态转移蝶形对的加比选处理过程，在保证维特比算法译码效果的前提下，极大的提高了译码速度。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，上述提到的存储介质可以是只读存储器，随机存储器、磁盘或光盘等。

以上对本发明所提供的一种维特比译码方法及维特比译码器进行了详细介绍，对于本领域的一般技术人员，依据本发明实施例的思想，在具体实施方式及应用范围上均会有改变之处，综上，本说明书内容不应理解为对本发明的限制。