兼容卷积码生成多项式确定方法、编码方法及编码器

摘要

本发明公开了一种兼容卷积码生成多项式确定方法、编码方法及编码器。该方法通过如下步骤来确定1/(k+1)码率的目标卷积码生成多项式，k为正整数：若k=1，则通过遍历1/2码率卷积码的所有卷积码生成多项式并计算其自由距离，将所遍历得到的卷积码生成多项式中自由距离较大的预设数量个卷积码生成多项式矢量或自由距离最大的卷积码生成多项式矢量至少之一作为目标卷积码生成多项式矢量；若k>1，则先确定1/k码率卷积码的目标卷积码生成多项式矢量，记为矢量组Ak，再基于矢量组Ak来确定1/(k+1)码率卷积码的目标卷积码生成多项式矢量。本发明减少了计算量，降低了对硬件的要求，通用性强，非常适合HARQ。

说明书

技术领域

本发明涉及通信技术领域，尤其涉及一种兼容卷积码生成多项式查找方 法及卷积码编码方法。

背景技术

现代信息论和编码理论的奠基人Shannon在1948年提出了有噪信道编 码定理，定义给出了数字通信系统实现可靠通信方法以及在特定信道上实现 可靠通信的信息传输速率上限。同时Shannon还给出了有效差错控制编码的 存在性证明，从而促进了信道编码领域研究的快速发展。

卷积码是Elias于1955年提出的一种线性纠错码。与分组编码不同，在 卷积码编码过程中，充分利用了各码元之间的相关性，本组的信息元不仅决 定本组的监督元，而且也参与决定以后若干组的监督元。同时在译码过程中， 不仅从该时刻所收到的码组中提取译码信息，而且还利用以后若干时刻内所 收到的译码来提取有关信息。Viterbi译码算法提出之后，卷积码因其编码增 益高、译码延迟小以及具有很强的纠正随机错误的能力而在移动通信、卫星 通信、深空通信和数据压缩系统中得到广泛的应用。在现在通信中有着广泛 的应用，尤其是卫星通信中大量采用卷积码作为信道编码方式，在第三代移 动通信中也把卷积码作为主要编码方式之一。

虽然性能优于分组码，但卷积码没有分组码那样严密的数学结构和数学 分析手段。在卷积码的分析过程中，至今仍未找到像分组码那样有效的数学 工具，以至性能分析非常困难。迄今为止，从分析上得到的成果比较少，而 往往是借助于计算机查找具有最大自由距离的生成多项式来构造卷积码。自 由距离是衡量卷积码性能的一个重要的因素，自由距离的计算方法主要集中 在查找。

卷积码的性能取决于所采用的解码方法及码的距离特性。当使用相同的 解码方法时，为提升卷积码的性能，需采取使用较优的距离特性的办法。在 代数解码时，解码约束度等于码的约束度，这时，卷积码的距离度量是最小 距离d_min。而在概率解码（维特比解码）时，解码约束度大于码的约束度， 这时，码的距离度量是最小自由距离。

设待编码序列M是个半无限序列，如果截取M的前(i+1)个信息码组， 并称之为第i级截短(从第0级起计)，且用M_i表示，经编码器编码后，得到 一个由(i+1)个子码构成的码字列C_i，称C_i为码序列C的第i级截短。利用码 的生成矩阵，C_i可以写作：

C_i=M_i[G_i]

第i阶列距离定义为：

d_i=min{d(C_i′,C_i″)}

G_i表示码的生成矩阵，d_i是单调非减的有界正整数序列。由于卷积码为 线性码，所以任意两个码字之和必是另一个码字，即C_i′与C_i″之间的距离必是 另一个码字的重量。因此，第i阶列距离就是第0个子码为非零的、长为(i+1) 个子码的码字的最小重量。当i＝m(寄存器长度)时，C_i=C_m，C_m为初始截短 码组，称d_m为卷积码的最小距离，也用d_min表示。所以，卷积码的最小距离 就是第0个子码不为全零时，初始截短码组C_m中码字的最小重量。由于在代 数解码情况下，采用反馈解码时解码的约束度等于码的约束度，因此，反馈 解码时码的度量就是最小距离，记为d_min。

当i→∞时，d_i是第0个信息码组不全为零时编码器输出的长为任意无穷 长度的码序列的最小重量，定义

$\underset{i\to \infty }{\lim }{d}_i=d_f$

上式表明，当i →∞时，d_i最终将达到最小自由距离或简称自由距离d_f。 为了确定某个码的自由距离d_f，我们不必要也不可能对无穷长的码序列进行 比较，一般地，当i达到3m或4m时，d_i就不再增加，这时d_i就达到了d_f的 值。我们可以借助状态图，从全零状态又回到全零状态的非零路径有许多条， 其中有一条重量最轻，该最小重量就是码的自由距离d_f。由于列距离的非降 特性，对同一个码而言，自由距离d_f至少等于最小距离d_min。

计算卷积码自由距的方案有很多，用维特比解码算法计算卷积码的自由 距离。以全零序列作为接受序列，那么汉明距离就是网格图上的编码序列的 码重，有下列步骤组成。

第一步：从第0时刻到第m+1时刻，从零状态逐步翻倍扩展到2^m个状态。 1时刻只有一个状态。

第二步：从时间单元j＝m开始，计算进入每个状态的路径的部分度量。 存储每一状态的路径（即幸存路径）及它的度量值。这里存储的路径通常是 该状态所对应的幸存路径上的前一状态值。

第三步：j增加1。计算进入每一状态所有路径的部分度量。这个度量值 是进入该状态的分支度量加上在与该分支相连的前一步的幸存路径的度量 值。对于每个状态，共有2^k个这样的度量值，从中选出并存储具有最大度量 的路径(即幸存路径)及它的度量值，并删除其他路径。

第四步：如果j时刻的非零状态的度量值（有2^k-1个）全部都不小于j 时刻零状态的度量值，那么j时刻零状态的度量值就是自由距离d_f，迭代计 算停止，否则转第三步。

本发明的发明人在实现本发明的过程中，发现现有技术存在计算量大、 对硬件设备要求高的特点。

发明内容

本发明所要解决的技术问题之一是需要提供一种用于速度较快的获得 性能较优兼容卷积码生成多项式确定方法、性能较优的编码方法及结构较简 单的编码器。

为了解决上述技术问题，本发明提供了一种兼容卷积码生成多项式确定 方法。该方法通过如下步骤来确定1/(k+1)码率的目标卷积码生成多项式，k 为正整数：

若k=1，则通过遍历1/2码率卷积码的所有卷积码生成多项式并计算其 自由距离，将所遍历得到的卷积码生成多项式中自由距离较大的预设数量个 卷积码生成多项式矢量或自由距离最大的卷积码生成多项式矢量至少之一 作为目标卷积码生成多项式矢量；

若k>1，则先确定1/k码率卷积码的目标卷积码生成多项式矢量，记为 矢量组A_k，再基于矢量组A_k来确定1/(k+1)码率卷积码的目标卷积码生成多 项式矢量。

进一步，所述基于所述矢量组A_k来确定1/(k+1)码率卷积码的目标卷积 码生成多项式矢量的步骤可包括：

针对所述矢量组A_k中各多项式矢量g，通过先将g的k个乘法多项式作 为前k个乘法多项式再查找第k+1个多项来确定多个1/(k+1)码率卷积码的卷 积码生成多项式矢量；

将针对各个多项式矢量确定的所有1/(k+1)码率卷积码的卷积码生成多 项式矢量确定为用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢量；

将所述用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢量中自由 距离最大的卷积码生成多项式矢量至少之一或自由距离较大的预设数量个 卷积码生成多项式矢量作为目标卷积码生成多项式矢量。

进一步，所述基于所述矢量组A_k来确定1/(k+1)码率卷积码的目标卷积 码生成多项式矢量的步骤可包括：

针对所述矢量组A_k中各多项式矢量g，将g的k个乘法多项式作为前k 个乘法多项式，通过遍历2^L种第k+1个乘法多项式，得到2^L个1/(k+1)码率 卷积码的卷积码生成多项式矢量，其中L为卷积编码器寄存器的个数；

将针对A_k中各个多项式矢量得到的所有1/(k+1)码率卷积码的卷积码生 成多项式矢量确定为用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢 量；

将所述用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢量中自由 距离最大的卷积码生成多项式矢量至少之一或自由距离较大的预设数量个 卷积码生成多项式矢量作为目标卷积码生成多项式矢量。

此外，可通过仿真测试来将所述目标卷积码生成多项式矢量之一确定为 实际编码时要使用的卷积码生成多项式。

根据本发明的又一方面，提供了一种兼容卷积码编码方法。该方法利用 上述任一技术方案确定的目标卷积码生成多项式矢量之一来进行编码。

该方法尤其适用于混合式自动重传请求增量冗余策略。

此外，可在要进行码率小于1/k大于1/(k+1)的卷积码编码时，先利用权 利要求1或2中查找提到的1/(k+1)码率的卷积码生成多项式矢量组中一个卷 积码生成多项式来进行编码，然后再对编码得到的卷积码进行打孔，进而得 到目标码率卷积码。

根据本发明的又一方面，提供了一种编码器。该编码器包括判断单元、 计算单元和编码单元，其中：

所述判断单元用于，在要确定1/(k+1)码率的目标卷积码生成多项式时， 判断是否要确定1/2码率的目标卷积码生成多项式，k为正整数。

所述计算单元用于，若k=1，则通过遍历1/2码率卷积码的所有卷积码 生成多项式并计算其自由距离，将所遍历得到的卷积码生成多项式中自由距 离较大的预设数量个卷积码生成多项式矢量或自由距离最大的卷积码生成 多项式矢量至少之一作为目标卷积码生成多项式矢量；若k>1，则先查找1/k 码率卷积码的目标卷积码生成多项式矢量，构成矢量组A_k，再基于矢量组 A_k来确定1/(k+1)码率卷积码的目标卷积码生成多项式矢量；

所述编码单元，用于使用目标卷积码生成多项式矢量之一来进行编码。

所述计算单元还可进一步用于：

针对所述矢量组A_k中各多项式矢量g，通过先将g的k个乘法多项式作 为前k个乘法多项式再查找第k+1个多项式来确定多个1/(k+1)码率卷积码的 卷积码生成多项式矢量；

将A_k中针对各个多项式矢量确定的所有1/(k+1)码率卷积码的卷积码生 成多项式矢量确定为用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢 量；

将所述用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢量中自由 距离最大的卷积码生成多项式矢量至少之一或自由距离较大的预设数量个 卷积码生成多项式矢量作为目标卷积码生成多项式矢量。

所述计算单元还可进一步用于：

针对所述矢量组A_k中各多项式矢量g，将g的k个乘法多项式作为前k 个乘法多项式，通过遍历2^L种第k+1个乘法多项式，得到2^L个1/(k+1)码率 卷积码的卷积码生成多项式矢量，其中L为所述编码器的卷积编码器寄存器 的个数；

将针对各个多项式矢量得到的所有1/(k+1)码率卷积码的卷积码生成多 项式矢量确定为用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢量；

将所述用于候选的1/(k+1)码率卷积码的卷积码生成多项式矢量中自由 距离最大的卷积码生成多项式矢量至少之一或自由距离较大的预设数量个 卷积码生成多项式矢量作为目标卷积码生成多项式矢量。

与现有技术相比，本发明的一个或多个实施例可以具有如下优点：

根据本发明的兼容卷积码生成多项式确定方法中，通过基于已生成的1/k 码率卷积码的生成多项式矢量组A_k来确定1/(k+1)码率卷积码的生成多项式， 由于卷积码寄存器状态是相同的，只是分支度量不同，故在应用于HARQ(混 合式自动重传请求)时，减少了计算量，降低了对硬件的要求。

此外，根据本发明的编码方法，由于低码率码字完全兼容高码率码字， 因此通用性强，非常适合HARQ。此外，由于基于相似的网格图设计，具有 较低的编译码复杂度。

本发明的其他优点、目标，和特征在某种程度上将在随后的说明书中进 行阐述，并且在某种程度上，基于对下文的考察研究对本领域技术人员而言 将是显而易见的，或者可以从本发明的实践中得到教导。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本 发明的实施例共同用于解释本发明，并不构成对本发明的限制。在附图中：

图1A是根据本发明实施例的卷积码生成多项式查找方法。

图1B是根据本发明实施例基于矢量组A_k来确定1/(k+1)码率卷积码的目 标卷积码生成多项式矢量的流程图。

图2运行本实施例方法的是1/4码率卷积码编码器示意图。

图3是加性高斯白噪声信道下1/2码率二元卷积码（BCC，Binary Convolutional Code）重复（等效于1/4码率）发送方案和本发明码率兼容发 送方案性能对比示意图。

图4是空间信道模型城市宏下1/2码率二元卷积码（BCC，Binary Convolutional Code）重复（等效于1/4码率）发送方案和本发明码率兼容发 送方案性能对比示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，以下结合附图对本发明 作进一步地详细说明。

另外，在附图的流程图示出的步骤可以在诸如一组计算机可执行指令的 计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情 况下，可以以不同于此处的顺序执行所示出或描述的步骤。

下面参考图1A说明本实施例的卷积码生成多项式(简称生成多项式)的 查找方法的各步骤。在该方法中，通过如下步骤来确定1/(k+1)码率的卷积码 生成多项式，其中，k为正整数。

步骤S110，判断是否要查找1/2码率的卷积码生成多项式，即判断k是 否等于1。若判断结果为是，则进入步骤S120，反之，进入步骤S140。

步骤S120，若要查找1/2码率的卷积码，即k=1，则通过遍历1/2码率 卷积码的所有生成多项式并计算其自由距离，进入步骤S130。

步骤S130，将所遍历得到的生成多项式中自由距离最大的生成多项式矢 量组（记为A₂）作为目标卷积码生成多项式矢量(亦称查找结果)。优选为遍 历2^L×2^L，L表示卷积编码器寄存器的个数。

步骤S140，确定1/k码率卷积码的目标卷积码生成多项式矢量，记为矢 量组A_k，，然后进入步骤S150。

A_k表示可为$A_k=\{(g_{11},g_{12},···,g_{1k}),(g_{21},g_{22},···,g_{2k}),...,(g_{r_{k}0},g_{r_{k}1},···,g_{r_{k}k})\},$其中， 表示矢量组A_k的第r_k个元素(生成多项式矢量)。表示该第r_k个元素的第k个乘法多项式。

步骤S150，基于矢量组A_k来确定1/(k+1)码率卷积码的目标卷积码生成 多项式矢量。

下面结合图1B来详细说明步骤S150的各子步骤。

步骤S251，针对所述矢量组A_k中各多项式矢量g，通过先将g的k个乘 法多项式作为前k个乘法多项式再查找第k+1个多项来确定多个1/(k+1)码率 卷积码的卷积码生成多项式矢量。优选地，通过遍历2^L种第k+1个乘法多项 式，以得到2^L个1/(k+1)码率卷积码的卷积码生成多项式矢量，可将全部2^L个的全部或部分作为前述多个1/(k+1)码率卷积码的卷积码生成多项式矢量， 其中L为卷积编码器寄存器的个数。

步骤S252，将针对各个多项式矢量确定的所有1/(k+1)码率卷积码的卷 积码生成多项式矢量确定为用于候选的1/(k+1)码率卷积码的卷积码生成多 项式矢量。

步骤S253，将所述用于候选的1/(k+1)码率卷积码的卷积码生成多项式 矢量中自由距离最大的卷积码生成多项式矢量至少之一或自由距离较大的 预设数量个卷积码生成多项式矢量作为目标卷积码生成多项式矢量。预设数 量可以通过参数配置来设定或在系统中通过程序代码固定设定。

进一步，可在具体应用环境（如BSC，瑞利衰落等）中进行仿真测试以 选取目标卷积码生成多项式矢量之一作为最终要实际使用的生成多项式。

下面将详细说明k=4时卷积码生成多项式的查找步骤。

以寻找1/4码率卷积码生成多项式、采用6个寄存器为例进行说明。

（1）首先通过计算机查找1/2码率的卷积码生成多项式，通过利用查找 到的卷积码自由距离最大为10，得到生成多项式集合，用八进制表示，设为 A₂。A₂中包含133₈，171₈等；

（2）在A₂中生成多项式的基础上寻找1/3码率的卷积码生成多项式，查 找到1/3码率兼容的卷积码生成多项式。如1/3码率卷积码前两个生成多项 式为133₈，171₈，第3个生成多项式通过传统方法查找得到。如133₈,171₈,117₈， 自由距离为15，同样可以得到相应的在该码率下的生成多项式集合，设为A₃。 其中A₃包括133₈,171₈,117₈等等。

（3）在A₃中生成多项式的基础上寻找1/4码率的卷积码，利用计算自由 距最大原则，查找1/4码率兼容的卷积码生成多项式，第4个生成多项式通 过传统方法查找得到。如133₈,171₈,117₈,165₈，自由距离为20。这样，可以 得到相应的在该码率下的生成多项式矢量集合，设为A₄。其中A₄包括 133₈,171₈,117₈,165₈。

根据本发明的码率兼容卷积码生成多项式可较好的应用于HARQ增量 冗余策略中。

下面详细说明码率兼容卷积码生成多项式在HARQ增量冗余策略中的 应用。

首先根据上述方法查找1/k码率兼容的卷积码生成多项式。以k=4为例。 HARQ增量冗余策略是基于低码率(1/4码率)编码器，然后通过对编码器的输 出进行打孔，从而产生不同的冗余版本。在第一次传输时，只有打孔后的冗 余版本中的一个被传输，这样就等效于高码率传输。由于译码错误而需要重 传时，额外的编码比特需要被传输。

如图2所示，为1/4卷积码编码器，共6个寄存器，与802.11ac协议中 所用1/2卷积码编码器结构类似。在此，假设母码即为1/4码率，有N个信 息比特（信息比特中已加循环冗余编码比特），编码后的数据比特总数为4N， 然后对这4N进行分组，分为4组，每一组代表编码器的一路输出，分别表 示为A、B、C、D。第一次重传时，发送4N比特，即A、B两路，等效于 高码率(1/2码率)传输。当接收方对接收到的数据进行译码，用循环冗余编码 比特进行检测。若译码错误而需要重传时，额外的编码比特则需要被传输， 此时传输C路，结合A、B两路，共3路数据，此时的传输等效于1/3码率 的传输，即传输数据为用1/3码率卷积码编码而得。值得注意的是，该1/3 码率卷积码与1/2码率卷积码兼容。如若接收端译码仍然错误，需要二次重 传时，则传输D路数据比特，这是传输等效于以低码率1/4进行传输，同样， 1/4码率与1/2、1/3码率卷积码有码率兼容的特点。1/4码率卷积码编码后的 数据（用X表示）与1/2、1/3码率卷积码编码后得到的数据（用Y表示） 有包含的关系，X包含Y。从图中我们也可以看出，在3种码率卷积码编码 器中，所用的寄存器是相同，因此卷积码编码器的状态是不变的，只是输出 在之前的两路的基础上增加了两路。这有益于接收端译码算法的实现，因此 简化了硬件设计。

本发明采用扩展的方式可以灵活的搜索低码率兼容卷积码，该方法中的 算法相比于穷举法具有一定的算法优势。而且可以对码率兼容问题可以快速 找到性能较好的卷积码生成多项式。若有穷举法，则需遍历

而用本发明中的方法，则只需遍历

2^L×2^L+r₂×2^L+r₃×2^L+…+r_n-1×2^L次，

其中r₂,r₃,…,r_n-1分别是码率为1/2,1/3,…,1/(n-1)的卷积码最大自由距离的 生成多项式矢量的个数。一般有r_i<<2^L,i＝2,3,…,n-1，故在搜索量和计算量方 面会大大降低。

同时，由于卷积码寄存器状态是相同的，只是分支度量不同，故在应用 于HARQ时，简化了硬件设计。

我们用本专利所提供的方法，搜索了1/4码率生成多项式 g₀=133₈,g₁=171₈,g₂=117₈，g₃=165₈，并且在高斯白噪声（AWGN）信道（如 图3）和城市宏蜂窝空间衰落信道（SCM-UMa）（如图4）下分别进行了仿 真工作，并与IEEE 802.11ah中的MCS0-ARQ重传方案作了对比。MCS0重 复方案是使用的1/2卷积码，重发发送，其他条件相同。802.11ah中1/2码 率卷积码编码器采用工业标准生产多项式，g₀=133₈和g₁=171₈。从图中可以 得到，在高斯白噪声（AWGN）信道下，在误包率PER=0.1处，与ARQ重 传方法相比，1/4码率卷积码方案有0.7dB的增益。在SCM-UMa信道下，在 误包率PER=0.1处，1/4码率卷积码比等增益合并（EGC）ARQ重传方法在 性能上提升1.2dB，比最大比合并ARQ重传方法提升了0.85dB。

根据本发明的另一方面，还提供了一种编码器。该编码器包括判断单元、 计算单元和编码单元。该判断单元用于在要确定1/(k+1)码率的目标卷积码生 成多项式时，判断是否要确定1/2码率的目标卷积码生成多项式。该计算单 元用于执行上述S120至S150中的处理。编码单元使用目标卷积码生成多项 式矢量之一来进行编码。

本领域的技术人员应该明白，上述的本发明的各模块或各步骤可以用通 用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个 计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码 来实现，从而，可以将它们存储在存储装置中由计算装置来执行，或者将它 们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单 个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。

虽然本发明所揭露的实施方式如上，但所述的内容只是为了便于理解本 发明而采用的实施方式，并非用以限定本发明。任何本发明所属技术领域内 的技术人员，在不脱离本发明所揭露的精神和范围的前提下，可以在实施的 形式上及细节上作任何的修改与变化，但本发明的专利保护范围，仍须以所 附的权利要求书所界定的范围为准。