第八章Trellis and Graph Based Codes第一部分

标签：输出 Codes Based 卷积 Graph 序列卷积码节点输入

卷积码的结构

通过传递要通过线性有限状态移位寄存器传输的信息序列来生成卷积码。一般来说，移位寄存器由K (K位)级和n个线性代数函数生成器组成。

编码器的输入数据(假定为二进制数据)每次在移位寄存器中移位k位。每个k位输入序列的输出位数为n位。因此，码率定义为Rc = k/n。

K 代表有几级（多少个移位），k代表一次输入多少比特（几个入口），n代表有一次输出多少比特（几个出口）

描述卷积代码的一种方法是给出它的生成器矩阵，就像我们对分组代码所做的那样。一般来说，卷积码的生成器矩阵是半无穷的，因为输入序列的长度是半无穷。

具体来说，让我们考虑约束长度为 $K = 3, k = 1$ 和 $n = 3$ 的二进制卷积编码器

最初，假定移位寄存器处于全零状态。假设第一个输入位是1。则3位的输出序列为111。假设第二个位是0。然后输出序列将是001。如果第三位是1，输出将是100，依此类推。现在，假设我们将生成每个3位输出序列的函数生成器的输出从上到下依次编号为1、2和3，并同样为每个相应的函数生成器编号（按照序号来生成顺序为123123123）。然后，由于只有第一级连接到第一个函数生成器(不需要模-2加法器)，因此生成器是

第二个函数生成器连接到阶段1和阶段3。因此

最后

那么，如果编码器的输入是信息序列 $\mathbf{u}$ ，则三个输出由

星号代表卷积。对应的代码序列c

卷积的运算可以利用多项式乘法（原理类似z变换）

三个脉冲响应对应为

每一次的输出响应为

最后输出的码字为（三次方代表K= 3）

例子1

对于序列

多项式表达式为

卷积编码器为

每一位输出对应的多项式为

最后输出的码字为

例子2

速率2/3卷积编码器。在这个编码器中，每次2位被移进它，并产生3个输出位。

也可以等价画成

上图系统有两个输入序列，三个输出响应（类似2×3的MIMO结构）可以写成6个输出响应

传递函数

每个输出可以通过下列计算

最终的输出表示为

通过多项式矩阵表示输入

和传递函数

输出多项式为

其中输出多项式的结构为

得到变换域生成矩阵

和之前的矩阵有

树图，Trellis图，和状态图

树图

对于卷积编码器

有树图如下

假设编码器最初处于全零状态，从图中可以看出，如果第一个输入位为0，则输出序列为000，如果第一个输入位为1，则输出序列为111。现在，如果第一个输入位是1，第二个输入位是0，那么第二组3个输出位是001。继续浏览树，我们看到，如果第三位是0，那么输出是011，而如果第三位是1，那么输出是100。给定一个特定的序列将我们带到了树中的一个特定节点，分支规则是，如果下一个输入位是0，则遵循上面的分支，如果输入位是1，则遵循下面的分支。

因此，我们在树中跟踪由输入序列决定的特定路径。

Trellis图

如果我们将树中的每个节点标记为与移位寄存器中的四种可能状态相对应，我们发现在第三阶段有两个标记为a的节点，两个标记为b的节点，两个标记为c的节点和两个标记为d的节点。

现在我们观察到，从具有相同标签(相同状态)的两个节点发出的所有分支都是相同的，因为它们产生相同的输出序列。这意味着具有相同标签的两个节点可以合并。我们会得到另一个更紧凑的图，即网格。实线表示输入位0产生的输出，虚线表示输入位1产生的输出。

可以发现该结构在第三阶段之后重复自身（从第三个状态开始后面的图形都是一致的）。这种行为与约束长度K = 3的事实是一致的。也就是说，每级的3位输出序列由输入位和前2位输入位决定，即移位寄存器的前两级中包含的2位。移位寄存器最后一级的位在右侧移出，不影响输出。因此，我们可以说，每个输入位的3位输出序列是由输入位和移位寄存器的四种可能状态决定的，表示为a = 00, b = 01, c = 10, d = 11。

状态图

每次输入一比特可能得路径有

表示输入位为1时从状态α到状态β的跃迁。状态图中每个支路旁边的3位表示输出位。图中虚线表示输入位为1，实线表示输入位为0。

通过这这种路径关系可以得到状态图

对于有两个输入口的卷积编码器

每次的输入有四种可能00, 01, 10,或11，因此对于树图有四个分支

对于trellis图而言每个状态有四个分支

状态图为

总结，速率为k/n，约束长度为K，卷积码的特征是从树形图的每个节点发出 $2^k$ 个分支。格子和状态图各有 $2^{k(K-1)}$ 种可能的状态。

卷积码的传递函数

传递函数定义

对于之前提到的码率为1/3，K = 3 的卷积码生成器有状态图

其中Z表示各之路对应的输出位序列位和全零之间的汉明距离（有几个1）。

状态方程为

传递函数定义为

可以得到

其中

在给定节点处，存在一条与全零路径合并的单路径，其汉明距离为d = 6。从之前状态图或图8.1-6所示的网格图中可以观察到，d = 6路径为acbe。从节点a到节点e不存在其他距离为d = 6的路径。式8.1-18中的第二项表示从节点a到节点e有两条路径，距离d = 8。同样，从状态图或格子图中，我们观察到这些路径是可接的和可接的。式8.1-18中的第三项表示有四条距离为d = 10的路径，以此类推。由此得到码的最小距离为6。

传递函数作用

传递函数可以用来提供比各种路径的距离更详细的信息

假设我们在由输入位1引起的所有分支转换中引入一个因子Y。因此，当遍历每个分支时，只有当该分支转换是由于输入位1引起时，Y上的累积指数才增加1。

此外，我们在状态图的每个分支中引入一个因子J，以便J的指数将作为计数变量，以指示从节点a到节点e的任何给定路径上的分支数量。对于我们示例中的速率1/3卷积代码，包含附加因子J和Y的状态图如图1所示

传递函数的这种形式给出了卷积代码中所有路径的性质。也就是说，T (Y, Z, J)展开的第一项表示距离d = 6的路径长度为3，三个信息位中有一个是1。T (Y, Z, J)展开的第二项和第三项表明，在两个d = 8的项中，一个长度为4，第二个长度为5。路径中长度为4的四个信息位中的两个和路径中长度为5的五个信息位中的两个为1。因此，因子J的指数表示第一次与全零路径合并的路径的长度，因子Y的指数表示该路径信息序列中1的个数，因子Z的指数表示该路径的编码位序列与全零序列的距离(码序列的权重)。

如果我们传输的是一个有限持续时间的序列，比如m比特，那么因子J就尤为重要。在这种情况下，卷积代码在m个节点或m个分支后被截断。这意味着截断码的传递函数是通过在 $J^m$ 项处截断T (Y, Z, J)得到的.