信息论与编码理论习题课.pdf

信息论与编码理论习题课信息论与编码理论习题课 一一 王哲 pkuwangzhe 2016 05 10 1501214343 肖同学 1501214321 邵同学 1501214345 杨同学 0 3 计算 7 4 汉明码第一个分量x0出错的概率 1 假设发送的是x 0000000 2 假设发送的是x 1111111 3 假设 x 任意情形 000000 1000000 0100000 0010000 0001000 0000100 0000010 0000001 1010001 0010001 1110001 1000001 1011001 1010101 1010011 1010000 1110010 0110010 1010010 1100010 1111010 1110110 1110000 1110011 0100011 1100011 0000011 0110011 0101011 0100111 0100001 0100010 0110100 1110100 0010100 0100100 0111100 0110000 0110110 0110101 1100101 0100101 1000101 1110101 1101101 1100001 1100111 1100100 1000110 0000110 1100110 1010110 1001110 1000010 1000100 1000111 0010111 1010111 0110111 0000111 0011111 0010011 0010101 0010110 1101000 0101000 1001000 1111000 1100000 1101100 1101010 1101001 0111001 1111001 0011001 0101001 0110001 0111101 0111011 0111000 0011010 1011010 0111010 0001010 0010010 0011110 0011000 0011011 1001011 0001011 1101011 1011011 1000011 1001111 1001001 1001010 1011100 0011100 1111100 1001100 1010100 1011000 1011110 1011101 0001101 1001101 0101101 0011101 0000101 0001001 0001111 0001100 0101110 1101110 0001110 0111110 0100110 0101010 0101100 0101111 1111111 0111111 1011111 1101111 1110111 1111011 1111101 1111110 2534435267 9 1 19 1 16 1 12 1 7 1 Pppppppppppp 2534435267 9 1 19 1 16 1 12 1 7 1 Pppppppppppp 0000000 1000000 0100000 0010000 0001000 0000100 0000010 0000001 1010001 0010001 1110001 1000001 1011001 1010101 1010011 1010000 1110010 0110010 1010010 1100010 1111010 1110110 1110000 1110011 0100011 1100011 0000011 0110011 0101011 0100111 0100001 0100010 0110100 1110100 0010100 0100100 0111100 0110000 0110110 0110101 1100101 0100101 1000101 1110101 1101101 1100001 1100111 1100100 1000110 0000110 1100110 1010110 1001110 1000010 1000100 1000111 0010111 1010111 0110111 0000111 0011111 0010011 0010101 0010110 1101000 0101000 1001000 1111000 1100000 1101100 1101010 1101001 0111001 1111001 0011001 0101001 0110001 0111101 0111011 0111000 0011010 1011010 0111010 0001010 0010010 0011110 0011000 0011011 1001011 0001011 1101011 1011011 1000011 1001111 1001001 1001010 1011100 0011100 1111100 1001100 1010100 1011000 1011110 1011101 0001101 1001101 0101101 0011101 0000101 0001001 0001111 0001100 0101110 1101110 0001110 0111110 0100110 0101010 0101100 0101111 1111111 0111111 1011111 1101111 1110111 1111011 1111101 1111110 习题习题1 GF 24 域本原元为 a 本原多项式为p x x4 x3 1 写出域中元素的共轭类共轭类及最小多项式最小多项式 1 r qq f xxxx L 定理定理 设GF qm 上元素 在GF q 上的最小多项式f x 则 q在 GF q 上的最小多项式也是f x 定理定理 设GF qm 上元素 在GF q 上的最小多项式f x deg f x r 则 共轭类共轭类最小多项式最小多项式 0 248 361224 510 7141311 15 1 43 1xx 432 1xxxx 2 1xx 4 1xx 1x x 4324843 10 1xxxxxx 本原多项式本原多项式 15 1 本原元性质本原元性质 非零元素非零元素阶阶 2 4 8 16 3263 3 6 12 24 48 3321 5 10 20 40 17 3463 7 14 28 56 49 359 9 18 367 11 22 44 25 50 3763 13 26 52 41 19 3863 15 30 60 57 51 3921 21 423 23 46 29 58 53 4363 27 54 457 31 62 61 59 55 4763 63 11 1 域的定义 2 群的陪集分解性质 3 子域 1 设子域元素个数n 非零元素个数n 1 2 加法子域 n 2 6 乘法子域 n 1 2 6 1 n 2 4 8 64 3 n 2 最小子域是 0 1 4 0 1分别是加法和乘法群的单位元素 各子域均含 5 n 4 4 3 1 3是质数 三阶元素或1 6 n 8 8 7 1 7是质数 七阶元素或1 非零元素非零元素阶阶 2 4 8 16 3263 3 6 12 24 48 3321 5 10 20 40 17 3463 7 14 28 56 49 359 9 18 367 11 22 44 25 50 3763 13 26 52 41 19 3863 15 30 60 57 51 3921 21 423 23 46 29 58 53 4363 27 54 457 31 62 61 59 55 4763 63 11 GF 22 子域元素 GF 23 子域元素 子域子域子域元素子域元素 2 0 1 22 0 1 21 42 23 0 1 9 18 27 36 45 54 26 即该域本身 26 全体元素 11 2给 7 4 H C 增加一位奇偶校验位c7 使码矢满足 c0 c1 c6 c7 0 写出H G 求最小距离d 最 小重量w 根据H x T 0 有 对任意u有 u G 0 则G 0 因此 G 的每一行为偶数个1 c0 c1 c6 c7 0 c0 c1 c6 c7 0 0 0 11 H H M L 8 1 1 1 M 8 1 1 1 M 7 4 H C的H G如下 则 1001011 0101110 0010111 H 1101000 0110100 1110010 1010001 G 10010110 0101110 0 00101110 1111111 1 H 11010001 01101001 11100100 10100011 G 1 7 4 H C的最小重量为3 2 c0 c1 c6 c7 0 码字重量为偶数 3 存在最小重量w 4 d w 4 系统码的系统码的 形式形式 11 5令H 是 n k 线性码的一致校验矩阵 它既有奇数重量 的码矢也有偶数重量的码矢 构造具有下列一致校验矩阵 的新的线性码C1 1 证明C1 是一个 n 1 k 线性码 C1 称作C 的一个扩展 码 2 C1 的每个码矢都有偶数重量 1 0 0 11 H H M L 1 证明H1的n k 1行向量是线性无关线性无关的 而不是不是说明C1是码长n 1信息比特为k就可以了 2 设码字x c0 c1 cn 由于H1 xT 0 有 c0 c1 cn 0 因此 每个码字有偶数个1 即C1 的每个码矢都有 偶数重量 4 15 例如 100011111110000 010010011011101 001001010111011 000100101111110 H 汉明界汉明界 普罗特金普罗特金界界 证明题 证明这两个界在二进制下的特例 不是拿来用证明题 证明这两个界在二进制下的特例 不是拿来用 证明 最小距离为2t 1或大于2t 1的任意二元 n k 线性码 可 以纠正不多于t个错误的图案 因此要求所有不多于t个错误的图 案所对应的伴随式各不相同 而一个二元 n k 线性码共有2k个码字 最多有2n k个伴随式 并 且含t个及t个以下错误的图案总个数为 所以 即 11 9 1 12 nnn t L 21 12 n k nnn t L 证明 11 10 对偶码的定义 讲义ch 11 在此处键入公式 1 1 2 2 0 0 1 2 2 生成矩阵对应于生成多项式 校验矩阵不对应不对应于校验多项式 而对应其反多项式反多项式 对偶码是由校验矩阵定义的 kxn n k xn 1 11 8 7 5 3 2 1 3 系统形式的生成矩阵和校验矩阵 作业中应该把每作业中应该把每 一个都计算出来一个都计算出来 12 2 设计一个由g x 1 x3 x4 循环汉明码的编译码器电路 编码器电路 g0 g3 g4 1 1 2 输出输出 输入输入 前前11拍连接拍连接1 后后4拍连接拍连接2 前前11拍闭合拍闭合 后后4拍断开拍断开 g g0 0g g3 3g g4 4 1 牢记高低位顺序 2 选择寄存少的编码器 3 标明切换条件 译码器电路 15 11 汉明码能纠正1bit错 e14 x x14 s x e x mod g x x2 x3 s0 s1 s2 s3 0 0 1 1 捕获译码电路如下 S0S1S2S3 门门门门 合路器合路器缓冲寄存器缓冲寄存器 15位位 门门 输出输出 输入输入 高位先进高位先进 12 8设计一个由g x x 1 x3 x 1 生成的 7 3 汉明码的 译码电路 该译码电路应能纠正所有单个错误图样及所有 相邻双重错误图样 解题思路 错误图案多项式 伴随多项式 捕获译码电路 计算伴随式 可以看出任意单个错误任意单个错误和所有相邻双重错误所有相邻双重错误图案所对应的伴随式都不相同 于是说明 此码可以纠正以上提到的错误图案 译码电路如上图所示 上半部分是mod g x 电路 下半部分是mod x n 1电路 初始状态寄存器内容都是0 前N拍 接收符号R6 R5 R0依次输入 7拍之后 上方计算出了伴随式S0 x 此时断开A 闭合B 若有单个错误 则经过m拍 上方寄存器内容为1000 与门C输出1纠正下方的错误 再经过7 m拍 下方寄存器经过一个循环恢复成原有顺序 完成译码 若有相邻双重错误 经过n拍 上方寄存器内容1100 与门C和D同时输出1纠正下方 的错误 再经过7 n拍 下方寄存器经过一个循环恢复成原有顺序