递归系统卷积代码

对于未在信息序列中分组的纠错码，其校验元素不仅与当前信息元素有关，而且与先前有限时间段内的信息元素有关. 它是由P. Elias在1955年提出的. 尽管经过了多年的努力，编码方法尚未找到有效的数学工具和系统理论作为分组代码. 然而，在解码方面，卷积码在理论上和实践上都超过了块码，因此在错误控制和数据压缩系统中得到了广泛的应用.

编码以二进制代码为例，编码器如图1所示. 输入信息序列为u =（u0，u1，...），其多项式表示为u（x）= u0 + u1x + ... + ux + ...编码器的连接可以表示为多项式（x）= 1 + x + x2和（x）= 1 + x2，这被称为代码的子生成多项式. 它们的系数向量=（111）和=（101）被称为代码的子. 由子生成多项式作为数组元素组成的多项式矩阵G（x）= [（x）（x）]被称为代码的生成多项式矩阵. 由发生器组成的半无限矩阵

生成矩阵称为代码. 其中（11,10,11）由交叉连接组成. 编码器的输出序列为c = u·G，称为代码序列，其多项式表示为c（x），可以看作两个子代码序列c（x）和c（x）的合成通过组合开关S，其中c（x）= u（x）·（x）和c（x）= u（x）g（x），它们是信息序列和相应的子的卷积，分别得到卷积码的名称.

通常情况下，输入信息序列通过时分开关分为k0个子序列，分别用u（x）表示，其中i = 1、2，... k0，即u（x）= [u（x），...，u（x）]. 编码器的结构由k0×n0阶多项式矩阵组成

给. 输出代码序列由n0个子序列组成，即

c（x）= [c（x），c（x），...，c（x）]和c（x）= u（x）·G（x）.

如果m是所有子生成多项式g（x）中最高次数的次数，则此代码称为（n0，k0，m）卷积代码.

输出子序列中的每个数字与存储在移位寄存器中的每个输入子序列的（m +1）位数字有关，与n =（m +1）k0个信息数字有关，n编码约束长度.

可以将编码器视为有限状态线性网络，可以将存储在移位寄存器中的数字视为状态. 例如，（2,1,2）代码具有四个状态: ɑ= 00，b = 01，c = 10和d =11. 有向图可用于表示输出，输入和状态之间的关系（图2）. 为了显示所有可能的输入和输出情况，可以将状态图显示为树形图（图3）. 图中的粗线表示当输入序列u =（1011100 ...），而对应的输出序列c =（111000011001111）时，编码器沿树形图移动的路径. 未编码q时，每个节点的分支数为q. 卷积码的分支之间是线性关系，卷积码是常规树码的子类.

如果在树图中的相同级别节点上具有相同状态的所有分支被合并，则图3中的网格图将被合并. 形成图4. 会更好吗？

使用cL表示代码树中带有长L分支的路径或代码段，而d（cL，c'L）表示同一段上两条不同路径cL和c'L之间的汉明距离. 称重

是L个长码段上的最小距离； dmin（nA）称为代码的最小距离，以dmin表示，它等于分组代码的最小距离. 将dmin（∞）称为代码的自由距离递归系统卷积码，以df表示. 通常，在上述示例中，df≥dmin，df = 5，dmin = 3. 自由距离在卷积码的研究中起着重要作用. 但是没有系统的代数方法. 在给定的n0，k0和m的条件下，构造尽可能大的dmin和df码，这在实践中通常用于计算机搜索.

分类与卷积码类似，卷积码可分为系统码和非系统码，独立纠错和突发纠错码以及多数逻辑可翻译卷积码.

解码在其中，如果存在信道干扰序列. 接收顺序是中和. 这里的“ +”是模2运算（q = p元素代码是模p运算）. 解码是一种根据编码规则和信道干扰的统计特性估计信息序列u（x）的方法. 常用的解码方法有三种，即代数解码，维特比解码和顺序解码.

代数解码将卷积码的受代码约束的代码段视为[n0（m + 1），k0（m + 1）]个线性块代码，每次根据（m + 1）个分支Long接收数字，估计相应最早分支上的信息位数，然后向前推进一个分支. 在上面的示例中，信息序列=（10111），而相应的代码序列c =（11100001100111）. 如果接收到的序列R =（10100001110111），则首先根据R的前三个分支（101000）和代码树中的前三个分支，所有可能的8条路径（000000 ...），（000011 ...），比较（001110 ...），（001101 ...），（111011 ...），（111000 ...），（110101 ...）和（110110 ...），我们可以看到（111001 ... ）和接收序列的距离（101000）最小，因此将第0个分支的信息位数确定为0. 然后以相同的方式判断R的第一个至第三个分支编号（100001），并且依此类推，最后信息序列的估计值为=（10111），并实现了纠错. 在这种解码方法中，解码时使用的接收到的数字或解码约束的长度为（m +1）n0，因此它只能校正不超过（dmin-1）/ 2个错误（n long）. 在实践中，通常采用反馈多数逻辑解码的方法.

维特比解码是一种算法，它根据接收到的序列在代码的网格上从接收到的序列中找到最小的距离（或其他度量）. 它类似于在运筹学中寻找最短路径的算法. 如果接收序列为R =（10100101100111），则从某个状态开始，例如从状态ɑ开始，并且每次向右扩展一个分支（对于l

维特比的复杂度随m呈指数增长. 实际上，m不大于10. 它在卫星和深空通信中具有广泛的应用. 它也可以用于解决跨代码干扰和数据压缩.

顺序解码是一种算法，它根据接收到的序列和编码规则搜索整个代码树（向前和向后），以找到与接收到的序列之间的最小距离（或其他度量）. 由于其的复杂度随着m值的增加而线性增加，因此，实际上，可以选择更大的m值（例如20-40）以确保更高的可靠性. 许多深空和海上通信系统都使用顺序解码.

参考

S.Lin和D.J. Costello递归系统卷积码，《错误控制编码: 基本原理和应用》，PrenticeHall，Englewood Cliffs，新泽西州，1982年.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-182217-1.html