线性分组码的网格

缘起…… 如何用图形来表示和构造码 成功的例子：维特比发明卷积码译码算法 线性分组码的网格表示和应用？

编码器的有限状态机模型 1、存储器容量有限，存储i时刻状态si和若干以前时刻的输入信息Ii 2、存储器中存储的信息和i时刻状态si决定了i时刻到i+1时刻的输出Oi 3、当新输入信息来临时会替换某个存储器中的信息 根据上述模型，画出编码器的动态行为，是一个随时间变化的状态图，称为网格图或网格(trellis)

网格图的组成 初态s0 终态sf 第i时刻的状态si，第i时刻所有可能到达的合法状态构成的集合为 网格图的每个状态构成图的一个节点，每条边代表一次状态转移，用线性分组码的一个分量标注，从s0出发，沿时间前进，达到第i时刻，得到码分量(v0,v1,…,vi) 线性分组码中，从初态到终态经过n条边，得到一个码字(v0,v1,…,vn-1)，网格图显示了所有码字路径

网格图的例子

网格图的特点 初态没有输入，终态没有输出 任何中间态至少有一个输入分支，至少一个输出分支 编码过程就相当于从初态出发，走一条到终态的路径，走的时候依据是待编码信息序列和每一时刻的编码器状态 问题：每一时刻有多少可到达状态，相邻时刻的状态如何转移，编译码中如何利用网格图？

状态转移和输出 有限状态机模型中，输出是当前状态si和输入Ii的函数：Oi=fi(si,Ii) 状态转移是当前状态和输入所决定的： si+1=gi(si,Ii) 时不变码网格：存在一个时刻t，过了这个时刻t，所有可能到达的状态空间不再随时间变化，同时状态空间达到最大，包含以前任一时刻的状态空间，fi和gi也不再变化 分组码是时变的，卷积码常为时不变

(n,k)二进制线性分组码的网格 k比特的信息逐次一个一个地移入编码器的存储器（不一定是每时刻1个比特），被编码输出成n个比特，这n个比特每一时刻输出一个，顺序移送到信道被发送出去 故状态转移次数为n次，共0，1，…，n共n+1个时刻，码比特vi在i到i+1时刻产生 s0,s1,s2,…,sn+1个状态 有向图，初始节点1个，终态节点1个，中间节点有1个或2个输入分支，1个或两个输出分支，不同的分支表示不同的状态转移

(n,k)二进制线性分组码的网格 相邻状态,边（分支），标记 每一时刻能达到的合法状态的数目记为 全体时刻合法状态的数目称为状态空间复杂度分布： 因 是2的整数次幂，所以就用 的2次幂指数代替状态空间复杂度分布，得到状态空间维数分布 ，

网格图的例子，（8，4）RM码

构造二进制线性分组码的网格 设生成矩阵是G，矩阵变换G，使得： 上述矩阵称为TOF形式的生成矩阵，即面向网格的生成矩阵（不一定是系统形式） 每一行的第一个1（首1）出现在其下面各行的第一个1（首1）出现之前，即首1所在列的序号小与下面行的首1列序号 每一行最后一个1（尾1）不会和其他任何行的尾1同列 上述矩阵称为TOF形式的生成矩阵，即面向网格的生成矩阵（不一定是系统形式）

TOFM的例子

对TOFM的进一步分析 数字跨度：每一行首1和尾1的列下标（比特位置）构成的区间 时间跨度：数字跨度占据的时间跨度，记作： 有效时间跨度：首1和尾1在外的两个时刻构成区间

对TOFM的进一步分析 计算每个时刻i所有可能到达的合理状态数目的2次幂指数 构建n+1个空集合Gis，每个空集合对应一个时刻

例子 数字跨度：[0,3] [1,6] [2,5] [4,7] 时间跨度： [0,4] [1,7] [2,6] [4,8] 数字跨度：[0,3] [1,6] [2,5] [4,7] 时间跨度： [0,4] [1,7] [2,6] [4,8] 有效时间跨度： [1,3] [2,6] [3,5] [5,7]

研究跨度的意义 一个输入比特，在什么时间会影响编码的计算！ 存储器，编码器 假设Φ(gl) = [i,j],信息比特al在时刻i输入，直到时刻j+1，影响才消失，移出存储器；在i+1时刻，被移入存储器，停留j-i个时间单位 i时刻，存储器内有多少个有效的信息位？（生成矩阵决定存储器）

几个记号 GTOGM 面向网格的生成矩阵 Gip，i时刻，比特跨度在[0,i-1]内的GTOGM中的行 Gif，i时刻，比特跨度在[i,n-1]内的GTOGM中的行 Gis，i时刻，有效时间跨度包含i的GTOGM中的行 换个角度看，时刻i， Gis中的行都需要用，怎么用？存储器中的信息位对这些行进行加权和

比特跨度在[i,n-1]区间内的行集合Gif 例子：续TOFM例子 比特跨度在[0,i-1]区间内的行集合Gip 比特跨度在[i,n-1]区间内的行集合Gif

几个记号续 GTOGM 面向网格的生成矩阵 Aip，i时刻，和 Gip中行对应的信息比特的集合 过去的信息 Aif，i时刻，和 Gif中行对应的信息比特的集合 还没用到的信息 Ais，i时刻，和 Gis中行对应的信息比特的集合 正在使用的信息

对TOFM的进一步分析 设g*表示 内的某一行，若其首1的位置是i， g*是唯一的；设 ，则有 设按上式a*和g*对应，则有： 信息比特a*在i时刻开始影响编码器，称为当前输入信息比特

对TOFM的进一步分析 公式 的后一项同当前状态相关，当前输入a*的不同取值决定了输出码分量，每个不同的值都会引起状态转移到其他状态，二进制只有两种状态 如果 里没有首1为i的行，则 此时可认为输入信息比特恒为0，输出也只有1个值，只有一个分支或状态转移

编码器中存储器的状态 时刻i到时刻i+1，产生vi，设 对应有存储器保存的信息比特： 状态的转移：若 中g0的尾1位置在i,设a0是与g0对应的输入信息比特，则状态转移发生后，a0被替换，增加a*,（可能a0和a*都不存在）

标记状态 （n,k）线性分组码，用k维向量表示状态，记录当前存储器中保存的信息比特 也就是在i时刻，除了 上的信息比特分量外，其他的信息比特都是0 上的 个分量的各种组合构成了时刻i的各种状态

网格构造的例子

网格构造的步骤 对每一时刻求 绘制出所有的节点，并标记节点 求状态变化，计算每一输出分支的下一状态，链接相邻状态 用公式 计算每一个输出分支标记

网格的复杂性 和 相关，对任意i， 码C和其对偶码有相同的复杂度 循环码具有最差的网格复杂性 循环码具有镜像对称性 码的最小网格，一个码C可能有多个网格，若存在一个网格T，其复杂性 的每一个分量都不大于比其他网格的相应分量，则这就是最小网格 （生成矩阵G）

网格的分段 选不同的时刻做边界，将网格分段，或者说在原网格上去掉某些时刻间的状态，将剩下的网格段再重新连接起来 设时刻集合 ，它的一个子集为： 删除 中的所有状态及其边，若 若原网格中存在标记为x的路径从 到 则用x标记s到s‘的新连边

网格的分段和并行分解 合理地选择分段点，可能会产生有用的网格结构特性，给译码等带来方便