CN101369817B - 咬尾卷积码的译码方法和装置 - Google Patents

Abstract

本发明的实施例公开了一种咬尾卷积码的译码方法和装置。该方法包括：对同一个传输块重复多次后首尾相连得到的序列进行维特比译码，所述序列中每一个传输块译码结束后，根据所述译码得到的最大路径判断是否满足输出条件；判断满足输出条件时，将所述最大路径作为回溯路径，输出所述序列的译码数据。本发明的实施例中，根据传输块译码得到的最大路径的首末状态，对多个传输块相连得到的长序列进行的维特比译码情况进行判断，在满足预设的输出条件时不必等到对所有的传输块都计算完成即可直接获得译码数据，因此只用较少个传输块即可以得到正确的译码输出，节约了计算量和译码时延。

Description

咬尾卷积码的译码方法和装置

技术领域

本发明涉及通信技术领域，尤其涉及一种咬尾卷积码的译码方法和装置。

背景技术

现有技术中提出了咬尾卷积码的编码调制方式，以LTE(Long TermEvolution，长期演进)系统中用到的咬尾卷积码为例进行说明，(3，1，6)编码器如图1所示。

编码器的约束长度为7，码率为1/3。图1中生成多项式G_i(i＝0，1，2)的二进制序列表示输入数据及6个移位寄存器与编码器第i路输出的连接状态。二进制0表示不连接，二进制1表示连接。图1中加法器在GF(2)域中进行。移位寄存器初始状态为输入比特序列的最后6个比特，令η₀，η₁，η₂，...，η₅依次表示这6个移位寄存器。信道编码的输入比特序列记为c₀，c₁，c₂，c₃，...，c_K-1，比特序列长度为K。编码后的第i路输出比特序列记为

其中D为序列长度，对于咬尾卷积码而言D＝K。在初始状态时有η_i＝c_(K-1-i)(i＝0，1，…5)，这样在输入比特序列结束时移位寄存器的状态与编码开始时的初始状态相同。

咬尾卷积码的译码以维特比译码算法(Viterbi Algorithm)为基础。下面先介绍卷积码的维特比译码算法。

假设卷积码编码器一次输入一比特数据。设编码器的状态集合为S＝{s₁，s₂，…，s_N}，N为总状态数，并且有N＝2^M，其中M为编码器中移位寄存器的个数，移位寄存器记为η₀，η₁，η₂，...，η_M-1。设C＝{c₀，c₁，c₂，c₃，...，c_K-1}为编码输入序列，其中K为序列长度。比特c_k(取值0或1)在时刻t＝k送入编码器(k＝0，1，…，K-1)，编码器中时延为1，这样在t＝k+1时刻，比特c_k的编码完 成并且比特c_k+1进入编码器。c_k的编码输出为

其中R为卷积码码率的倒数。编码器的输出序列记为：

$D=\{d_0^{\left(1\right)},d_0^{\left(2\right)},\·\·\·,d_0^{\left(R\right)},d_1^{\left(1\right)},\·\·\·,d_{K-1}^{\left(1\right)},d_{K-1}^{\left(2\right)},\·\·\·,d_{K-1}^{\left(R\right)}\}.$

经过映射0→-1，1→1后的发射序列为(发射能量为1)：

$E=\{e_0^{\left(1\right)},e_0^{\left(2\right)},\·\·\·,e_0^{\left(R\right)},e_1^{\left(1\right)},\·\·\·,e_{K-1}^{\left(1\right)},e_{K-1}^{\left(2\right)},\·\·\·,e_{K-1}^{\left(R\right)}\}.$

其经过AWGN(Additive White Gaussian Noise，加性高斯白噪声)信道后接收的数据序列为

$Y=\{y_0^{\left(1\right)},y_0^{\left(2\right)},\·\·\·,y_0^{\left(R\right)},y_1^{\left(1\right)},\·\·\·,y_{K-1}^{\left(1\right)},y_{K-1}^{\left(2\right)},\·\·\·,y_{K-1}^{\left(R\right)}\}.$

并且满足：  $y_k^{\left(i\right)}=e_k^{\left(i\right)}+n_k^{\left(i\right)},$ 其中

为独立噪声，满足期望为0方差为σ²的实高斯分布。

输出端按照ML(Maximum Likelihood，最大似然)准则译码，即最大似然序列  $\hat{C}=\arg \underset{C\∈\mathrm{\Ω}}{\max }\ln \mathrm{Pr\Σ}\mathrm{\μ}\left(Y\right|C)$ 为译码输出。Ω为所有码字组成的集合。假设信道无记忆，则：

$\ln \mathrm{Pr}\left(Y\right|C)=\underset{i,k}{\mathrm{\Σ}}\ln \mathrm{Pr}\left(y_k^{\left(i\right)}\right|e_k^{\left(i\right)}).---\left(1\right)$

定义lnPr(Y|C)为输入序列为C的路径度量，  ${\mathrm{\μ}}_k\left(C\right)=\underset{i=1}{\overset{R}{\mathrm{\Σ}}}\ln \mathrm{Pr}\left(y_k^{\left(i\right)}\right|e_k^{\left(i\right)})$ 为支路度量。根据噪声的概率密度函数

$p\left(y_k^{\left(i\right)}\right|e_k^{\left(i\right)})=\frac{1}{\sqrt{2\mathrm{\π}}\mathrm{\σ}}\exp [-\frac{1}{2{\mathrm{\σ}}^2}{|y_k^{\left(i\right)}-e_k^{\left(i\right)}|}^2],$

略去路径的公共项，可将支路度量简化为：

${\mathrm{\μ}}_k\left(C\right)=\underset{i=1}{\overset{R}{\mathrm{\Σ}}}{y}_k^{\left(i\right)}{e}_k^{\left(i\right)}.---\left(2\right)$

则ML译码输出为  $\hat{C}=\arg \underset{C\∈\mathrm{\Ω}}{\max }\underset{k=0}{\overset{K-1}{\mathrm{\Σ}}}{\mathrm{\μ}}_k\left(C\right).$

一般采用维特比算法实现卷积码的最大似然译码。在时刻t＝0为各状态赋 初始累积路径度量值，如果初始状态不确定，则初始时刻各状态的累计路径度量值相等。在时刻t＝k只有两条支路指向时刻t＝k+1的相同状态s_n，这两条路径的累积度量等于前一时刻状态的累积度量加上当前的分支度量。在t＝k+1时刻对指向s_n的这两个路径进行比较，选取路径度量较大者作为幸存路径，其度量值作为新时刻状态s_n的累积路径度量。维特比译码算法的加比选过程如图2所示。随着时间推移直至最后时刻，此时对各状态的幸存路径选取最大者做为回溯路径。进而得到译码输出。

对咬尾卷积码而言，由于已知首末时刻编码器状态相同，因此译码时可以利用这一特性提高性能。设TB Block(传输块)对应一个接收数据块，由于编码器首末状态相同，因此可以将一个接收数据块重复L次，即串联后对长序列进行译码。

现有的译码方法中以L＝3为例，译码时三个数据块都用于计算幸存路径，最后回溯时只将回溯路径对应于第二个数据块的数据作为译码输出。第一个TB Block可以看成为第二个TB Block提供正确初始状态，第三个TB Block可以看成为第二个TB Block提供正确的回溯状态。

发明人在实现本发明的过程中，发现现有技术中的实现方式存在以下问题：现有的咬尾卷积码的维特比译码算法译码时延和计算量固定，即使当信道质量很好，接收序列发生错误很少时也一定要计算L个TB块后才会产生译码输出，而实际上可能只用较少个TB块就可以得到正确的译码输出，因此现有方法增加了计算量和译码时延。

发明内容

本发明的实施例提供一种咬尾卷积码的译码方法和装置，用于减小现有技术中咬尾卷积码的维特比译码算法译码的时延和计算量。

本发明的实施例提供一种咬尾卷积码的译码方法，包括：

对同一个传输块重复多次后首尾相连得到的长序列进行维特比译码，所述长序列中每一个传输块译码结束后，根据所述译码得到最大路径的首尾状态相同，则判断满足输出条件；

判断满足输出条件时，将所述首尾状态相同的最大路径作为回溯路径，根据所述回溯路径获得所述长序列的译码数据并输出；

所述译码得到的最大路径为：

对每一个传输块的译码结束后，获取对所述传输块进行译码的过程中得到的幸存路径，获取具有最大路径度量的幸存路径作为对所述传输块译码得到的最大路径。

本发明的实施例还提供一种咬尾卷积码的译码装置，包括：

译码单元，用于对同一个传输块重复多次后首尾相连得到的长序列进行维特比译码；

判断单元，用于当所述译码单元对长序列中每一个传输块译码结束后，根据所述传输块译码得到最大路径的首尾状态如果相同，则判断满足输出条件；

译码输出单元，用于在所述判断单元判断满足输出条件时，将所述首尾状态相同的最大路径作为回溯路径，根据所述回溯路径获得所述长序列的译码数据并输出；

附图说明

所述译码得到的最大路径为：

对每一个传输块的译码结束后，获取对所述传输块进行译码的过程中得到的幸存路径，获取具有最大路径度量的幸存路径作为对所述传输块译码得到的最大路径。

与现有技术相比，本发明的实施例具有以下优点：

根据传输块译码得到的最大路径的首末状态，对多个传输块相连得到的长序列进行的维特比译码情况进行判断，在满足预设的输出条件时不必等到对所有的传输块都计算完成即可直接获得译码数据，因此只用较少个传输块即可以得到正确的译码输出，节约了计算量和译码时延。

图1是现有技术中咬尾卷积码编码器的示意图；

图2是现有技术中维特比译码算法的加比选过程示意图；

图3是本发明的实施例中咬尾卷积码的译码方法流程图；

图4是本发明的实施例中咬尾卷积码的译码方法的SNR曲线；

图5是本发明的实施例中咬尾卷积码的译码方法的BLER曲线；

图6是本发明的实施例中咬尾卷积码的译码装置的结构示意图；

图7是本发明的实施例中咬尾卷积码的译码装置的另一结构示意图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

本发明的实施例中提供一种咬尾卷积码的译码方法，如图3所示，包括：

步骤s301、对同一个传输块重复多次后首尾相连得到的序列进行维特比译码，所述序列中每一个传输块译码结束后，根据所述译码得到的最大路径判断是否满足输出条件。

步骤s302、判断满足输出条件时，将所述最大路径作为回溯路径，获得所述长序列的译码数据。

本发明的实施例中，根据传输块译码得到的最大路径的首末状态，对多个传输块相连得到的长序列进行的维特比译码情况进行判断，在满足预设的输出条件时不必等到对所有的传输块都计算完成即可直接获得译码数据，因此只用较少个传输块即可以得到正确的译码输出，节约了计算量和译码时延。

具体的，本发明的实施例提供了三种Viterbi译码算法的改进方法，以下分别以Viterbi-a、Viterbi-b以及Viterbi-c表示，并对每种改进方法进行详细描述。

对于本发明实施例中的译码算法Viterbi-a：对同一个传输块重复多次后首尾相连得到长序列，对长序列中的多个传输块依次进行维特比译码，第一个传输块的维特比译码结束时，获取幸存路径中的最大路径，若所述最大路径的首末状态相同，则判断满足输出条件；并将所述第一个传输块的最大路径作为回溯路径，根据回溯路径获得该序列的译码数据并输出，具体的：输出与该最大路径对应的传输块的译码数据。

具体的：将L个TB块重复相连后得到长序列，对长序列进行Viterbi译 码。当对于第一个TB块的计算结束时，在幸存路径中寻找最大路径，记此最大路径为

，假设第一个TB块对应的时刻为t＝0至t＝k，则若在时刻t＝0和时刻t＝k的首末状态相同，则直接返回

作为回溯路径，此路径为最优路径，进而得到译码数据。否则完全按照现有的Viterbi算法进行，即在计算完L个TB块后产生译码输出。

对于本发明实施例中的译码算法Viterbi-b：对同一个传输块重复多次后首尾相连得到长序列，对长序列中的多个传输块依次进行维特比译码，若一个传输块译码得到的最大路径相应于所述传输块的首末状态相同，则判断满足输出条件；并将所述首末状态相同的最大路径作为回溯路径，根据回溯路径获得该序列的译码数据并输出，具体的：该最大路径相应于哪一个传输块的首末状态相同，则输出该最大路径相应于该传输块的译码数据。

具体的：对同一个传输块重复L后首尾相连得到长序列，对长序列进行Viterbi译码。当对于第一个TB块的计算结束时，在幸存路径中寻找最大路径，记此最大路径为

，假设第一个TB块对应的时刻为t＝0至t＝k，则若

在时刻t＝0和时刻t＝k的的首末状态相同，则直接返回

作为回溯路径。否则继续计算第二个TB块，当第二个TB块结束时，寻找此时的最大路径

假设第二个TB块对应的时刻为t＝k至t＝2k，则若

在时刻t＝k和时刻t＝2k的首末状态相同，即此最大路径

中相应于第二个TB块的首末状态相同，则返回作为回溯路径，进而得到相应于第二个TB块的译码数据。否则，继续计算第三个TB块，直至达到第L个TB块。如果最后一块结束时最大路径

对应于第L个TB块的首末状态相同，则返回最大路径

作为回溯路径，进而得到相应于第L个TB块的译码数据。否则，返回最优路径

相应于第

个TB块的译码数据。

对于本发明实施例中的译码算法Viterbi-c：对同一个传输块重复L后首尾 相连得到长序列，对长序列中的多个传输块依次进行维特比译码，若一个传输块译码得到的最大路径相应于任一个传输块的首末状态相同，则判断满足输出条件；并将所述首末状态相同的最大路径作为回溯路径，根据回溯路径获得该序列的译码数据并输出，具体的：该最大路径相应于哪一个传输块的首末状态相同，则输出该最大路径相应于该传输块的译码数据。

具体的：对同一个传输块重复L后首尾相连得到长序列，对长序列进行Viterbi译码。当对于第一个TB块的计算结束时，在幸存路径中寻找最大路径，记此最大路径为

，假设第一个TB块对应的时刻为t＝0至t＝k，则若

在时刻t＝0和时刻t＝k的的首末状态相同，则直接返回

作为回溯路径。否则继续计算第二个TB块，当第二个TB块结束时，寻找此时的最大路径

假设第二个TB块对应的时刻为t＝k至t＝2k，则若在时刻t＝0和时刻t＝k的首末状态相同、或在时刻t＝k和时刻t＝2k的首末状态相同，即此最大路径中相应于第一个TB块、或第二个TB块的首末状态相同，则返回

作为回溯路径，进而得到相应于第一个TB块、或第二个TB块的译码数据。否则，继续计算第三个TB块，直至达到第L个TB块。如果最后一块结束时最大路径

对应于第l(l＝1，...，L)个TB块的首末状态相同，则返回最大路径

作为回溯路径，进而得到相应于第l个TB块的译码数据。否则，返回最优路径

相应于第

个TB块的译码数据。

上述实施例中的译码算法Viterbi-b中：对  $P_{\max }^l(l=\mathrm{1,2},\·\·\·,L)$ 回溯时，只是比较最大路径相应于第l个TB块的首末状态是否相同。在译码算法Viterbi-c中，对  $P_{\max }^l(l=\mathrm{1,2},\·\·\·,L)$ 回溯时，比较最大路径相应于前面l个TB块的每个TB块的首末状态是否有相同的情况。如果有，则返回相应首末状态相同的TB块的译码数据。如果最后一块结束时最大路径相应于各个TB块的首末状态都不同，则返回最大路径

相应于第个TB块的译码数据。

以下分别给出AWGN信道R＝2，K＝88，L＝3和R＝3，K＝88，L＝3情况下咬尾卷积码的Viterbi算法和上述实施例中所描述的三种改进算法(依次对应Viterbi-a/b/c)的SNR(Signal Noise Ratio，信噪比)和BLER(误码率)性能曲线。

如图4所示，为Viterbi(R＝2，K＝88，L＝3)、Viterbi_a(R＝2，K＝88，L＝3)、Viterbi_b(R＝2，K＝88，L＝3)和Viterbi_c(R＝2，K＝88，L＝3)；以及Viterbi(R＝3，K＝88，L＝3)、Viterbi_a(R＝3，K＝88，L＝3)、Viterbi_b(R＝3，K＝88，L＝3)和Viterbi_c(R＝3，K＝88，L＝3)的SNR和BLER性能曲线。从图4和图5可以看出，本发明实施例中的三种改进算法和原有的Viterbi算法具有相同的译码BER和BLER性能曲线。

如表1和表2所示，为本发明实施例中三种改进Viterbi算法(依次对应Viterbi-a/b/c)比原有Viterbi算法“节省”串联长度的计算量比较结果。

表1.Viterbi算法和改进算法的计算量比较(R＝3，K＝88，L＝3)

表2.Viterbi算法和改进算法的计算量比较(R＝2，K＝88，L＝3)

注：仿真运行100000块，原有算法需要300000个串联长度的计算。节省百分比＝节省计算量/300000.

通过以上数据可以容易看出，随着改进算法Viterbi-a/b/c回溯的增加，节省的计算量也呈现递增的趋势。无论编码码率如何，高SNR时各种改进算法 都能很接近节省计算量的极限值(200000)。在低码率(R＝3)时，三种改进算法在较低SNR(0dB)时就可以减少50％左右的译码计算。在高码率(R＝2)时，三种改进算法在中低SNR(2dB)时也可以减少50％左右的译码计算。由于三种改进算法相比原有算法只需要增加较少的资源，因此节省这样的计算量是相当可观的。

因此，本发明的实施例中，根据传输块译码得到的最大路径的首末状态，对多个传输块相连得到的长序列进行的维特比译码情况进行判断，只用较少个传输块即可以得到正确的译码输出，在满足预设的输出条件时不必等到对所有的传输块都计算完成即可直接获得译码数据，因此节约了计算量和译码时延。

本发明的实施例中还提供一种咬尾卷积码的译码装置，如图6所示，包括：

译码单元10，用于对同一个传输块重复多次后首尾相连得到的序列进行维特比译码；

判断单元20，用于当译码单元10对序列中每一个传输块译码结束后，根据所述传输块译码得到的最大路径判断是否满足输出条件；

译码输出单元30，用于在判断单元20判断满足输出条件时，将所述最大路径作为回溯路径，输出所述长序列的译码数据。

具体的，如图7所示，：

所述判断单元20包括第一判断子单元21，用于当第一个传输块的维特比译码结束时，获取幸存路径中的最大路径，若所述最大路径的首末状态相同，则判断满足输出条件；

所述译码输出单元30包括第一译码输出子单元31，用于将所述第一个传输块的最大路径作为回溯路径，根据回溯路径获得所述序列的译码数据并输出。

或：

所述判断单元20包括第二判断子单元22，用于若一个传输块译码得到的最大路径相应于所述传输块的首末状态相同，则判断满足输出条件；

所述译码输出单元30包括第二译码输出子单元32，用于将最大路径作为回溯路径，根据所述回溯路径获得所述序列的译码数据并输出。

或

所述判断单元20包括第三判断子单元23，用于若一个传输块译码得到的最大路径相应于任一个传输块的首末状态相同，则判断满足输出条件；

所述译码输出单元30包括第三译码输出子单元33，用于将所述首末状态相同的最大路径作为回溯路径，根据所述回溯路径获得所述序列的译码数据并输出。

另外，所述译译码输出单元30还用于：当所述判断单元20对多个传输块相连得到的长序列进行维特比译码后，未发现满足输出条件时，返回最大路径相应于所述多个传输块中的中间一个传输块的译码数据。

本发明实施例的咬尾卷积码的译码装置中，根据传输块译码得到的最大路径的首末状态，对多个传输块相连得到的长序列进行的维特比译码情况进行判断，在满足预设的输出条件时不必等到对所有的传输块都计算完成即可直接获得译码数据，因此只用较少个传输块即可以得到正确的译码输出，节约了计算量和译码时延。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到本发明可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台设备执行本发明各个实施例所述的方法。

以上公开的仅为本发明的几个具体实施例，但是，本发明并非局限于此，任何本领域的技术人员能思之的变化都应落入本发明的保护范围。

Claims (4)

1.一种咬尾卷积码的译码方法，其特征在于，包括：

对同一个传输块重复多次后首尾相连得到的长序列进行维特比译码，所述长序列中每一个传输块译码结束后，根据所述译码得到最大路径的首尾状态相同，则满足输出条件；

判断满足输出条件时，将所述首尾状态相同的最大路径作为回溯路径，根据所述回溯路径获得所述长序列的译码数据并输出；

所述译码得到的最大路径为：

对每一个传输块的译码结束后，获取对所述传输块进行译码的过程中得到的幸存路径，获取具有最大路径度量的幸存路径作为对所述传输块译码得到的最大路径。

2.如权利要求1中所述咬尾卷积码的译码方法，其特征在于，对多个传输块相连得到的长序列进行维特比译码后，未发现满足输出条件时，还包括：

返回最大路径相应于所述多个传输块中的中间一个传输块的译码数据。

3.一种咬尾卷积码的译码装置，其特征在于，包括：

译码单元，用于对同一个传输块重复多次后首尾相连得到的长序列进行维特比译码；

判断单元，用于当所述译码单元对长序列中每一个传输块译码结束后，根据所述传输块译码得到最大路径的首尾状态如果相同，则判断满足输出条件；

译码输出单元，用于在所述判断单元判断满足输出条件时，将所述首尾状态相同的最大路径作为回溯路径，根据所述回溯路径获得所述长序列的译码数据并输出；

所述译码得到的最大路径为：

对每一个传输块的译码结束后，获取对所述传输块进行译码的过程中得到的幸存路径，获取具有最大路径度量的幸存路径作为对所述传输块译码得到的最大路径。

4.如权利要求3中所述咬尾卷积码的译码装置，其特征在于：所述译码输出单元还用于：当所述判断单元对多个传输块相连得到的长序列进行维特比译码后，未发现满足输出条件时，返回最大路径相应于所述多个传输块中的中间一个传输块的译码数据。

Images