西电通院考研复试资料(试题课件).ppt

2020 4 1 1 第七章 线性分组码 7 1分组码的概念 7 2线性分组码 7 4循环码 7 5卷积码 2020 4 1 2 7 4一些特殊的线性分组码 本节介绍几种重要的线性分组码 一 二元Hamming码N 2m 1 L 2m 1 m 即二元 2m 1 2m 1 m 线性分组码 其一致校验矩阵是如下的m 2m 1 阶矩阵H H的 2m 1 列恰好是 2m 1 个非全0的m维向量 2020 4 1 3 7 4一些特殊的线性分组码 定义6 2 1如果任一个接收向量y 都有唯一的码字u满足d y u t 则称该码为t阶完备码 命题当一个 N L 线性分组码是t阶完备码时 所有不同伴随式所对应的陪集首恰好是所有重量不超过t的N维向量 注意 不同伴随式的个数为2N L 重量不超过t的N维向量的个数为定理6 2 1二元Hamming码 它是二元 2m 1 2m 1 m 线性分组码 是1阶完备码 2m 1 2m 1 2020 4 1 4 7 4一些特殊的线性分组码 二 Hadamard码从Hadmard矩阵的行中选择码字可以构造出Hadamad码 Hadmard矩阵Mn是一个n n阶矩阵 其中n 2m 该矩阵满足有一行为全0行 其余的行有2m 1个0 2m 1个1 任意两行有2m 1个位置不同 2m 1个位置相同 2020 4 1 5 7 4一些特殊的线性分组码 2020 4 1 6 7 4一些特殊的线性分组码 以Hadmard矩阵Mn的所有行作为所有的码字 得到的码就是Hadamad码 Hadamad码的参数如下 共有n个码字 因此共有n个信息 因此信息长为logn m 码长为n 编码效率为R m n m 2m dmin 2m 1 n 2 生成矩阵为Mn的任意m个非全0行构成的m n阶矩阵 2020 4 1 7 7 4一些特殊的线性分组码 三 Golay码Golay码是线性 23 12 码 最小距离为7 将其增加一个全校验位扩展为二元线性 24 12 码 最小距离为8 表6 4 1给出了Golay码和扩展Golay码的重量分布 2020 4 1 8 循环码要求掌握的内容 根据多项式会写循环码的生成矩阵和校验矩阵会写循环码生成和校验矩阵的系统形式会画循环码的编码电路由生成多项式的根定义循环码 7 4一些特殊的线性分组码 2020 4 1 9 定义循环码的生成多项式和校验多项式循环码的生成矩阵和校验矩阵循环码的系统码形式 7 4一些特殊的线性分组码 2020 4 1 10 定义1 设CH是一个 n k 线性分组码 C1是其中的一个码字 若C1的左 右 循环移位得到的n维向量也是CH中的一个码字 则称CH是循环码 2020 4 1 11 问题一如何寻找k维循环子空间 如何设计 n k 循环码 利用多项式和有限域的概念 2020 4 1 12 注 1 GF p 上的n维向量与GF p 上的多项式之间有一一对应的关系 注 1 GF p 上的n维向量与GF p 上的多项式之间有一一对应的关系 2 模n多项式F x 的剩余类构成一个多项式剩余类环Fp x F x 若在环中再定义一个数乘运算 即 则模F x 的剩余类构成一个n维线性空间 定义为剩余类结合代数 2020 4 1 13 问题一转化为如何从模多项式xn 1的剩余类结合代数中寻找循环子空间 2020 4 1 14 定理 以多项式xn 1为模的剩余类线性结合代数中 其一个子空间Vn k为循环子空间 或循环码 的充要条件是 Vn k是一个理想 循环码是模xn 1的剩余类线性结合代数中的一个理想 2020 4 1 15 问题二如何从多项式剩余类环中寻找理想 2020 4 1 16 由于1 多项式剩余类环中任何一个理想都是主理想 主理想中的所有元素可由某一个元素的倍式构成2 在主理想的所有元素中 至少可找到一个次数最低的首一多项式g x 即生成多项式 2020 4 1 17 问题三如何寻找生成多项式g x 2020 4 1 18 循环码 模多项式xn 1剩余类线性结合代数中的理想 生成多项式 2020 4 1 19 生成多项式和校验多项式 2020 4 1 20 两个定理 定理1 p147 GF q q为素数或素数的幂 上的 n k 循环码中 存在唯一的n k次首一多项式g x 每一个码多项式C x 必是g x 的倍式 每一个小于等于 n 1 次的g x 的倍式一定是码多项式 2020 4 1 21 两个定理 定理2 p148 GF q q为素数或素数的幂 上 n k 循环码的生成多项式g x 一定是xn 1的n k次因式 xn 1 g x h x 反之 若g x 为n k次多项式 且xn 1能被g x 整除 则g x 一定能生成一个 n k 循环码 2020 4 1 22 两个结论 结论1 找一个 n k 循环码 即是找一个n k次首一多项式g x 且g x 必是xn 1的因式 结论2 若C x 是一个码多项式 则 反之 若 则C x 必是一个码多项式 2020 4 1 23 ExamplesGF 2 上 x7 1 x 1 x3 x 1 x3 x2 1 试求一个 7 4 循环码 g x xg x x2g x x3g x 2020 4 1 24 循环码的生成矩阵和校验矩阵 2020 4 1 25 g x 决定生成矩阵 h x 决定校验矩阵 2020 4 1 26 2020 4 1 27 2020 4 1 28 循环码的系统码 模g x 的除法问题 2020 4 1 29 2020 4 1 30 由于生成矩阵G中的k行要求线性无关 因此在求余式时 可选择k个线性无关的信息组 1 0 0 0 xk 1 0 1 0 0 0 xk 2 0 0 0 0 1 1 2020 4 1 31 表示ri x 的系数 2020 4 1 32 2020 4 1 33 循环码的编码原理 1 基本步骤 n k 1 分解多项式xn 1 g x h x 2 选择其中的n k次多项式g x 为生成多项式 3 由g x 可得到k个多项式g x xg x xk 1g x 4 取上述k个多项式的系数即可构成相应的生成矩阵 5 取h x 的互反多项式h x 取h x xh x xn k 1h x 的系数即可构成相应的校验矩阵 2020 4 1 34 可选择k个线性无关的信息组 1 0 0 0 xk 1 0 1 0 0 0 xk 2 0 0 0 0 1 1 循环码的编码原理 2 2020 4 1 35 表示ri x 的系数 2020 4 1 36 循环码的编码 多项式乘法和除法电路循环码的编码电路 乘法和除法 2020 4 1 37 多项式乘法和除法电路 2020 4 1 38 2020 4 1 39 乘B x 运算电路 利用校验多项式h x 编码时会用到 2020 4 1 40 2020 4 1 41 除B x 运算电路 a0 a1 ak 除式B x 构成电路 被除式A x 的系数依次送入电路 2020 4 1 42 2020 4 1 43 循环码编码电路 2020 4 1 44 2020 4 1 45 n k级编码器 基本原理 利用生成多项式g x 若要求编成非系统码形式 则利用乘法电路 若要求编成系统码形式 则利用除法电路 2020 4 1 46 n k级乘法电路 非系统码形式 取g x xg x xk 1g x 的系数可构成生成矩阵G 2020 4 1 47 n k级乘法电路 非系统码形式 若信息序列m mk 1 mk 2 m0 则mG对应的n维向量为 该n为向量正是多项式m x g x 的系数 2020 4 1 48 2020 4 1 49 ExamplesGF 2 上 x7 1 x 1 x3 x 1 x3 x2 1 试画一个 7 4 循环码的n k级乘法编码电路 2020 4 1 50 n k级除法电路 系统码形式 1 0 0 0 xk 1 0 1 0 0 0 xk 2 0 0 0 0 1 1 2020 4 1 51 表示ri x 的系数 2020 4 1 52 n k级除法电路 系统码形式 对任意信息多项式m x xn km x 除g x 可得余式r x m x 的系数为信息序列mr x 的系数为m对应的校验比特 2020 4 1 53 n k级除法电路 系统码形式 若信息序列m mk 1 mk 2 m0 对应的多项式m x mk 1xk 1 mk 2xk 2 m0 2020 4 1 54 n k级除法电路 系统码形式 综上 循环码的系统码电路是信息多项式m x 乘xn k 除g x 的实现电路 2020 4 1 55 输入m x m0 m1 mk 1 gn k 1 g0 gn k 1 gn k 2 乘xn k除g x 运算电路 2020 4 1 56 k级编码器 基本原理 利用校验多项式h x 为系统码编码电路 2020 4 1 57 k级编码器 若信息序列m mk 1 mk 2 m0 对应的多项式m x mk 1xk 1 mk 2xk 2 m0 码多项式C x m x g x 且C x 为系统码 h x C x h x m x g x m x xn 1 m x xn m x mk 1xn k 1 mk 2xn k 2 m0 xn mk 1xk 1 mk 2xk 2 m0 2020 4 1 58 k级编码器 h x C