Turbo编码

Turbo编码简介

Turbo的编码器由两个并行的分量编码器组成。分量编码器的选择一般是卷积码，所谓卷积码，即输出为输入和一段已知序列的卷积。与其对应的分组码则是将序列分段，每段序列和编码矩阵相乘得到输出序列。在Turbo码中，输入序列在进入第二个编码器时须经过一个交织器 ，用于将序列打乱。两个编码器的输出共同作为冗余信息添加到信息序列之后，对抗信道引起的错误。
Turbo编码器原理图如下所示：

分量编码器

• Turbo码的设计的关键就是 分量编码器 和 交织器， 通常使用递归系统卷积码作为分量码。
  根据线性代数知识，通过对码字生成矩阵 G 进行初等变换，可以得到具有相同秩的标准生成矩阵 G’ 。由于分组码的最小距离由生成矩阵的最大线性无关组矢量个数（与矩阵的秩相同）决定，因此，在不改变码字最小汉明距离的前提下通过对生成矩阵进行初等变换，可以得到标准生成矩阵，以此对输入信息序列编码，得到的码字为系统吗的形式。同样，对于卷积码，也可以在不改变码字最小汉明距离条件下，将其变换为系统码的形式。
  如果将生成矩阵、信息序列和码字均用多项式形式表示，其中码字前馈生成多项式为 g_f(D) ，反馈生成多项式为 g_b(D) （通常将这样的生成多项式记作 G=[g_b(D) g_f(D) ] 或者写成八进制形式，例如（7，5）系统卷积码的生成多项式为 G=[ 1 1 1 1 0 1] = [ 7 5]），信息序列多项式为 m(D) ，码多项式为 c(D) ，其中 D 为延时算子。对于码率为 1/2 的非系统卷积码而言，系统化的第一步是计算多项式除法 m(D)/g_b(D) 的余式 a(D) ，然后利用多项式乘法运算来计算码字的校验输出 y(D)=a(D)g_f(D) ，而系统输出就为 x(D)=m(D) 。由前馈多项式和反馈多项式共同决定的系统卷积码成为递归系统卷积码（RSC码）。
• 在 RSC 码的编码过程中，首先计算反馈变量：
  校验输出为由于传统卷积码的编码器由移位寄存器构成且不存在反馈，因此可以等效为一个有限冲激响应（FIR）滤波器，而递归系统卷积码编码器中存在反馈，可以等效为一个无限冲激响应（IIR）滤波器。
• 示例：如图所示，生成多项式为（7，5）【G=[1 1 1，1 0 1]】的递归系统卷积码的编码框图，其编码速率为 1/2。由可以看出，递归系统卷积码是一个有限状态机，因此可以用状态转移图和网格图来表示。（7，5）递归系统卷积码编码器所对应的状态转移图如下所示。从图中可以看出，它与不存在反馈的卷积码的状态转移图是非常相似的。事实上，唯一区别是从个状态节点发生状态转移的触发信息比特有所不同。对于传统的卷积码而言，使得从这两个分支接入其他节点的比特是不同的，但是对于递归系统卷积码而言，使得从这两个分支接入其他节点的比特是不同的。由于卷积码系统化时没有改变生成矩阵的秩，因此该系统卷积码的最小汉明距离与其相应的非系统卷积码的最小距离是相同的。
• 对于传统卷积码，通过在数据帧的末尾嵌入 m_c（编码器的移位寄存器的个数）和 0 比特可迫使编码网格图在结束时回到全零状态。但是对于递归系统卷积码，由于具有无限冲激相应特性，因此仅依靠嵌入 m_c 个 0 比特一般无法使其编码网格图在编码结束时回到全零状态。为此，必须通过选择信息输入 m_i 来使得余式对应的系数 a_i=0(n-m_c<= i <=n-1)。这样，对于递归系统卷积码，输入信息序列中的最后 m_c 个比特必须满足：
  
• 一般情况下，Turbo码的两个分量编码器的选择为两个相同的系统卷积码。

交织器

• 交织实际上就是将数据序列中元素的位置济宁重置得到交织序列的过程。其逆过程就是在交织序列的基础上将元素恢复到原来的位置顺序上，一般称该过程为解交织过程。例如，设交织器 I 的输入为：其中，u_i = {0, 1}，i = 1, 2, … , N。交织映射输出序列记为：其中，v_j = {0, 1}，j = 1, 2, … , N。序列 v 与 序列 u 仅仅是元素位置的顺序不同。如果把输入序列和交织输出序列看成是一对含有 N 个元素的集合，则交织过程就是从集合 u 到集合 v 的一一映射过程，即：若定义集合：则交织过程可以用一一映射索引函数描述为： 其中，i 和 j 分别是原数据序列 u 和 v 中的元素索引。映射函数可以用交织矢量表示，如下所示：
  下面介绍几种常用的交织器。
• 1、分组交织器
  分组交织器是最简单的一类交织器。它的交织映射过程可以描述为：将数据序列按行写入 m*n 矩阵，然后按列读出，交织过程如下图所示：相应的解交织过程就是将交织后的数据序列按列写入，然后按行读出。分组交织的映射函数可以表示为：其中，N 为交织长度。分组交织能够使原序列中相邻比特经过交织后相距一定的距离，在实际应用中，信息序列长度较短时使用分组交织器可以获得较好的性能。
• 2、循环移位交织器
  循环移位交织器按照如下循环移位映射来实现交织，其交织的映射函数可以表示为：其中，a 为不长，是与交织长度 N 互素的正整数，且 步长 a 的值决定了原序列中相邻比特在交织后序列中的距离。
• 3、分组螺旋交织器
  分组螺旋交织器首先将数据序列按行写入 m*n 矩阵，其中 m 与 n 互素。在交织时从矩阵的左上角开始向右下方向读取数据，每向下一行同时右移一位（即行索引递增的同时列索引也递增，增量步长为1），同时在行方向和列方向分别对索引取模 m 和 n。
  若令 r_i 和 c_i 分别表示第 i 个比特的行索引和列索引，则分组螺旋交织器的数据读取顺序为：其中，i = 0，1，…，N-1，且初始值 r₀ 与 c₀ 均为 0 。另外，还可以从交织矩阵的左下角开始读取数据，其读取数据顺序为：其中，i = 0，1，…，N-1，且初始值 r₀ = N-1 ， c₀ = 0 。
  交织过程示意图如下所示：注意：在使用分组螺旋交织器时，一定要满足 m 与 n 互素，即 m 与 n 互为质数。
• 4、伪随机交织器
  伪随机交织器是指在交织映射随机生成的交织器。每个长度为 N 的伪随机交织器共有 N！ 种可能的交织形式。伪随机交织的实现步骤如下（交织长度为 N）。
  （1）从集合 S = {1，2，…，N} 中随机选择一个整数 i₁ ，相应的选取到 i₁ 的概率为 p(i₁) = 1/N，将选择的 i₁ 记为 I(1) ，同时将 i₁ 从集合 S 中删除，得到新的集合，记为 S₁。
  （2）在第 k 步，从集合 S_k-1 中随机选择一个整数 i_k ，其相应的选取概率为 p(i_k) = 1/(N-k+1) ，将选择的 i_k 记为 I(k)，同时将 i_k 从集合 S_k-1 中删除，得到新的集合，记为 S_k。
  （3）当 k = N时，得到 I(N) ，相应的选取概率为 p(i_N) = 1，S_N为空。
  交织过程结束。