信息论与编码第6章-4

信道编码 第6章 2 6 2线性分组码 3 7 3 循环码 4 循环码的生成多项式 满足 g0 0常数项为1r n k次多项式是xn 1的一个因式循环码的码多项式C x 都是g x 的倍式 5 循环码的生成矩阵 7 4 循环码 非标准 6 系统循环码 系统循环码构造过程步骤 信息多项式乘xr xrm x 对xrm x 求余式 求码多项式 C x xrm x r x 7 例 7 4 循环码的生成多项式 求 消息 1001 对应的系统循环码解 1001 1001000 1001110 8 g x x4 x3 x2 1 的除法电路 D D D D 1 x K2 x2 x3 x4 K1 1 2 1 2 m0m1m2m3 移位寄存器的级数r 4当某个抽头 0时 对应的反馈断开 当某个抽头 1时 对应的反馈接通 本题m x 从x4的位置进入 相当于x4m x 运算后除以g x 9 伴随式译码 伴随式译码设发送码组C x 接收码组R x 差错图样E x R x C x E x 定义R x 的伴随多项式为S x 10 伴随式译码 S x 0 传输中一定有错误发生S x 0 传输中无差错发生或差错图案恰好为一个码字 11 6 4卷积码 12 6 4 1卷积码的基本概念 分组码 n k k nn k r各n长码组是分别编码 各码组之间没有约束关系译码时各码组是分别独立地进行卷积码 n k L 所编的n长码组不但与当前的k比特信息段有关联 而且与前面L个信息段有关联 N L 1 编码约束长度 13 卷积码的基本概念 卷积码 n k L 卷积码 又称连环码 首先由麻省理工学院于1955年提出 卷积码与分组码的不同之处 在任意给定单元时刻 编码器输出的n个码元中 每一个码元不仅和此时刻输入的k个信息元有关 还与前连续L个时刻输入的信息元有关 在同样的编码效率R下 卷积码的性能优于分组码 至少不低于分组码 14 卷积码的基本概念 设待编码的信息序列为m 在对信息序列m进行编码之前 先将它每k个码元分成一组 在每单元时刻内 k个码元串行输入到编码器 编码器由 L 1 个移位寄存器组构成 每个移位寄存器组内有k级寄存器 15 信号输入 编码输出 m 二元 3 1 2 卷积码 ci0 ci1 ci2 mi0 mi 10 mi 20 输入1110 输出111101101010 输入mml m2 m3 输出Cmlc11c12 m2c21c22 m3c31c32 16 信号输入 编码输出 m ci0 ci1 ci2 对信息序列进行分组 使每个信息组只含一个信息位 两个校验位满足 当前的校验位与当前的信息位和过去的二个信息位有关 该卷积码的约束长度为3个分组 mi0 mi 10 mi 20 二元 3 1 2 卷积码 17 由 18 卷积码的解析表示 G 卷积码的生成矩阵 它是半无限的 因为输入的信息序列本身是半无限的 19 信号输入 输出Ci m ci0 ci1 ci2 m0i m0i 1 m0i 2 表示记忆阵列第k行 第l列对第n个码元影响 20 系数矩阵 系数矩阵 21 生成矩阵 任何时刻i的输出码字 22 转移函数矩阵 23 信号输入 编码输出 m ci0 ci1 ci2 mi0 mi 10 mi 20 D 移位算子 延迟算子 24 卷积码的图形描述 卷积码的状态转移图卷积码与分组码的明显区别 卷积码编码器要存储L段消息这些消息数据既要因新的输入而改变 又要影响当前的编码输出 因此称存储表达此数据的参量为卷积编码器的内部状态 一个 n k L 卷积编码器 有效的存储单元数为MM kL 二元 n k L 卷积码共有2M个不同的状态 S0 S1 25 D1 D2 例 2 1 2 卷积码 共有2kL 22 4种状态 二个移位寄存器 S0 00 S1 01 S2 10 S3 11 每一时刻可能的输入有二个 2k 2 0 1 ci0 ci1 编码输出 信号输入 26 2 1 2 码状态转移图 闭合型 闭合型的状转移态图 直接地描述了卷积编码器在任一时刻的工作状况 27 2 1 2 码状态转移图 开放型 开放型的状态转移图 更适合去描述一个特定输入序列的编码过程 28 状态转移图 设输入信息序列m m0m1m2m3m4 10110 首先 对移位寄存器清零 移位寄存器状态 00 S0 输入m0 1 寄存器状态 1 0 01 输出C c01c02 11 输入m1 0 寄存器状态 0 1 10 输出C c11c12 10 输入m2 1 寄存器状态 1 0 01 输出C c21c22 00 输入m3 1 寄存器状态 1 1 11 输出C c31c32 01 输入m4 0 寄存器状态 0 1 10 输出C c41c42 01 29 输入10110 输出1110000101 D1 D2 例 2 1 2 卷积码 ci0 ci1 编码输出 信号输入 30 卷积码的网格图 对卷积码的分析与有记忆信源的分析很相似 网格图 一种能清楚显示状态转移的时间依赖性状态图以状态为纵轴 以时间为横轴 将状态转移展开于时间轴上网格图有助于发现卷积码的性能特征 有助于译码算法的推导 是分析研究卷积码的最得力工具之一 31 卷积码的网格图 网格图 对编码器的描述 本时刻的各状态可以转移到下一时刻的哪些状态对编码过程的记录 一根半无限的水平线 纵轴上的常数 标志某一个状态 一个箭头代表一次转移 每隔时间T 移存器一位时延D 转移一次 转移的轨迹称为路径 32 网格图 红实线表示m 0时输入产生的转移分支 黄虚线表示m 1时输入产生的转移分支 33 34 维特比译码 VB算法 维持比 Viterbi 译码属于概率译码 VB算法是1967年由Viterbi提出 近年来有大的发展目前在数字通信的前向纠错系统中用得较多 而且在卫星深空通信中应用更多 该算法在卫星通信中已被采用作为标准技术 概率译码 把已接收序列与所有可能的发送序列做比较 选择其中码距最小的一个序列作为发送序列 VB算法 建立在栅格图上的一种算法 35 维特比译码 VB算法 维特比提出了一种算法 译码器不是在网格图上一次就计算和比较2Lk条路径 而是接收一段 就计算 比较一段 从而在每个状态时 选择进入该状态的最可能的分支维特比译码的基本思想 将接收序列R与网格图上的路径逐分支地比较 然后留下与R距离最小的路径 称为幸存路径 而去掉其余可能的路径 并将这些幸存路径逐分支地延长并存储起来 幸存路径的数目等于状态数 2kL 36 D1 D2 例 2 1 2 卷积码 设输入编码器的信息序列为 1011100 编码器输出序列C 11100001100111 若收到的序列R 10100001110110 ci0 ci1 编码输出 信号输入 38 收到的序列 R 10100001110110 00 11 00 10 11 01 00 11 10 01 11 00 01 10 黄实线表示m 0时输入产生的转移分支 绿虚线表示m 1时输入产生的转移分支 39 收到的序列 R 10100001110110 00 11 00 10 11 01 00 11 10 01 11 00 01 10 000000d 2 111011d 3 40 维特比译码 VB算法 经过比较后选择 部分路径000000为到达S0状态的幸存路径 部分路径111010为到达S1状态的幸存路径 部分路径001110为到达S2状态的幸存路径 部分路径001101为到达S3状态的幸存路径 按照上述方法 接收序列的诸码组依次进入译码器 每个时刻进入一个码组 沿着网格图对每个状态按部分路径值 累加距离 的大小 选择一条幸存路径 在每个状态上进行判决时 可能出现进入这一状态的两条路径的距离值相同 这时可以任选其一 因为对以后的判决而言 无论选择那一条路径 累加距离是相同的 41 收到的序列 R 10100001110110 00 11 00 10 11 01 00 10 01 00 42 收到的序列 R 10100001110110 00 11 00 10 11 01 00 10 01 00 00 11 10 01 43 收到的序列 R 10100001110