当前位置:首页 >> 工学 >>

编码理论复习题答案


1、 (1)A、B、C、E 编码是唯一可译码。 (2)A、C、E 码是及时码。 (3)唯一可译码的平均码长如下:
6 1 1 1 1 1 1 l A ? ? p( si )li ? 3 ? ( ? ? ? ? ? ) ? 3 码元/信源符号 2 4 16 16 16 16 i ?1 6 1 1 1 1 1 1 lB ? ? p(si )li ? ?1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? 2.125 码元/信源符号 2 4 16 16 16 16 i ?1 6 1 1 1 1 1 1 lC ? ? p(si )li ? ?1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? 2.125 码元/信源符号 2 4 16 16 16 16 i ?1 6 1 1 1 1 1 1 lE ? ? p( si )li ? ?1 ? ? 2 ? ( ? ? ? ) ? 4 ? 2 码元/信源符号 2 4 16 16 16 16 i ?1

(1) 2、霍夫曼编码: 对 X 的霍夫曼编码如下: 信源 符号 符号概 率 码 字 2 2 3 3 3 4 4

编码过程

码长

Si
S1 S2 S3 S4 S5 S6 S7

p(Si )
0.2 0.19 0.18 0.17 0.15 0.10 0.01 0 1 0.2 0.19 0.18 0.17 0.15 0.11 0 1 0.26 0.2 0.19 0.18 0.17 0 1 0.35 0.26 0.2 0.19 0 1 0.39 0.35 0.26 0 1 0.61 0.39 0 1 10 11 000 001 010 0110 0111

l ? 0.2 ? 2 ? 0.19 ? 2 ? 0.18 ? 3 ? 0.17 ? 3 ? 0.15 ? 3 ? 0.1? 4 ? 0.01? 4 ? 2.72 码元/信源符


H ( X ) ? ? pi log pi ? 2.61 码元/符号 ? ?
i ?1

7

H ( X ) 2.61 ? ? 0.9596 2.72 l

11、 (1).以下两种都可以
00/0 11/1 01/0 1 10/1 1
00/0 0 01/0 11/1 10/1 1

0

0

(2) .3

Y 的二元霍夫曼编码: 信 源 符 号 符号 概率

p(Si )

编码过程

码字

码 长

Si
0.4 9 0.1 4 0.1 4 0.0 7 0.0 7 0.0 4 0.0 3 0 1 0.0 2 0 1 0.4 9 0.1 4 0.1 4 0.0 7 0.0 7 0.0 5 0.0 4 0 1 0.4 9 0.1 4 0.1 4 0.0 9 0.0 7 0.0 7 0 1 0.4 9 0.1 4 0.1 4 0.1 4 0.0 9 0 1 0.4 9 0.2 3 0.1 4 0.1 4 0 1 0.4 9 0.2 8 0.2 3 0 1 0.5 1 0.4 9

S1 S2 S3 S4 S5 S6 S7 S8 S9

0.49 0.14 0.14 0.07 0.07 0.04 0.02 0.02 0.01

0 1

1 000 001 0100 0101 0111 01101 01100 0 01100 1

1 3 3 4 4 4 5 6 6

平均码长:

l ? 0.49 ?1 ? 0.14 ? 3? 2 ? 0.07 ? 4 ? 2 ? 0.04 ? 4 ? 0.02 ? 5 ? 0.02 ? 6 ? 0.01? 6 ? 2.23
码元/信源符

H (Y ) ? ? pi log pi ? 2.31 码元/符号
i ?1

9

编码效率: ? ?

H (Y ) 2.31 ? ? 0.9914 2.33 l

(2) 香农编码: 对 X 的香农编码: 信源符号 S i 符号概率 p(Si ) 和概率 码长 码字

S1 S2 S3 S4 S5 S6 S7 平均码长:

0.2 0.19 018 0.17 0.15 0.10 0.01

0 0.2 0.39 0.57 0.74 0.89 0.99

3 3 3 3 3 4 7

000 001 011 100 101 1110 1111110

l ? 0.2 ? 3 ? 0.19 ? 3 ? 0.18 ? 3 ? 0.17 ? 3 ? 0.15 ? 3 ? 0.1? 4 ? 0.01? 7 ? 3.14
码元/信源符

??
对 Y 的香农编码: 信源符号 S i S1 S2 S3 S4 S5 S6 S7 S8 S9 平均编码长度: 符号概率 p(Si ) 0.49 0.14 0.14 0.07 0.07 0.04 0.02 0.02 0.01

H ( X ) 2.61 ? ? 0.8312 3.14 l

和概率 0 0.49 0.63 0.77 0.84 0.91 0.95 0.97 0.99

码长 2 3 3 4 4 5 6 6 7

码字 00 011 101 1100 1101 11101 111100 111110 1111110

l ? 0.49 ? 2 ? 0.14 ? 2 ? 0.07 ? 4 ? 2 ? 0.04 ? 5 ? 0.02 ? 6 ? 2 ? 0.02 ? 6 ? 0.01? 7 ? 2.89 码
元/信源符 编码效率: ? ?

H (Y ) 2.31 ? ? 0.7993 2.89 l

(3) 费诺编码: 对 X 的费诺编码: 信源符号 S i S1 S2 S3 S4 S5 S6 符号概率 p(Si ) 0.2 0.19 0.18 0.17 0.15 0.10 1 0 编码 0 1 0 1 0 1 0 0 1 码字 00 010 011 10 110 1110 码长 2 3 3 2 3 4

S7 平均编码长度:

0.01

1

1111

4

l ? 0.2 ? 2 ? 0.19 ? 3 ? 0.18 ? 3 ? 0.17 ? 2 ? 0.15 ? 3 ? 0.1? 4 ? 0.01? 4 ? 2.74
码元/信源符号 编码效率: ? ?

H ( X ) 2.61 ? ? 0.9526 2.74 l

对 Y 进行费诺编码: 信源符号 S i S1 S2 S3 S4 S5 S6 S7 S8 S9 平均码长: 符号概率 p(Si ) 0.49 0.14 0.14 0.07 0.07 0.04 0.02 0.02 0.01 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 编码 码字 0 100 101 1100 1101 1110 11110 111110 111111 码长 1 3 3 4 4 4 5 6 6

l ? 0.49 ?1 ? 0.14 ? 2 ? 3 ? 0.07 ? 4 ? 2 ? 0.04 ? 4 ? 0.02 ? 5 ? 0.02 ? 6 ? 0.01? 6 ? 2.33
码元/信源符号 编码效率: ? ?

H (Y ) 2.31 ? ? 0.9914 2.33 l

(4) 由三种编码的编码效率可知: 仙农编码的编码效率为最低,平均码长最长;霍夫曼编码的编码长度最短,编码效率最 高,费诺码居中。 3、由三元编码方式可知:R=D-B=RD-1(K-2)+2 由本题可知 D=3,K=8,R=2,所以,首先合并最后两个信源概率,其中一种编码方式 如下: 信源符号 S i S1 S2 S3 S4 S5 符号概率 p(Si ) 0.4 0.2 0.1 0.1 0.05 0.4 0.2 0.1 0.1 0.1 0 编码 0.4 0.2 0.2 0.1 0.1 0 1 2 0.4 0.4 0.2 0 1 2 码字 0 2 11 12 101 码长 1 1 2 2 3

S6 S7 S8 4、见书上 5、解:

0.05 0.05 0.05 0 1

0.05 0.05

1 2

102 1000 1001

3 4 4

(1)线性码 C 的生成矩阵经如下行变换:

?1 ?0 ? ?0 ? ?1 ?0 ? ?0 ?

1 0 0 1? ?1 ? ?????? ?0 将第2、加到第1行 3 1 1 0 1? ?? ?0 0 1 1 1? ? ? 0 0 1 1? ?1 ? ?????? ?0 将第3加到第2 行 1 1 0 1? ?? ?0 0 1 1 1? ? ?

0 0 1 1? 1 1 0 1? ? 0 1 1 1? ? 0 0 1 1? 1 0 1 0? ? 0 1 1 1? ?

得到线性码 C 的系统生成矩阵为
?1 0 0 1 1 ? G S ? ?0 1 0 1 0 ? ? ? ?0 0 1 1 1 ? ? ?

(2)码字 c ? (c 0 , c1 , ? , c n ?1 ) 的编码函数为 生成了的 8 个码字如下 信息元 000 001 010 011 100 101 110 111

c ? f (m) ? m0 ?1 0 0 1 1? ? m1 ?0 1 0 1 0? ? m2 ?0 0 1 1 1?

系统码字 00000 00111 01010 01101 10011 10100 11001 11110

(3) 最小汉明距离 d=2,所以可检 1 个错,但不能纠错。 (4) 由 G ? [I n?k , Ak?(n?k ) ], H ? [ Ak?(n?k ) , I n?k ] ,得校验矩阵
T

?1 1 1 1 0? H ?? ? ?1 0 1 0 1?
(5) 消息序列 m=000,001,010,011,100,101,110,111,由 c=mGs 得码字序列 c0=00000, c1=00111,c2=01010, c3=01101, c4=10011, c5=10100,c6=11001, c7=11110 则译码表如下: 00000 00111 01010 01101 10011 10100 11001 11110 10000 10111 11010 11101 00011 00100 01001 01110

01000 00001

01111 00110

00010 01011

00101 01100

11011 10010

11100 10101

10001 11000

10110 11111

当接收到 r =(11101)时,查找码表发现它所在的列的子集头为(01101),所以将它译为 c=01101。 解: (1)生成矩阵 G 经如下行变换

?0 ?0 ? ?1 ? ?1 ?0 ? ?0 ?

1 0 1 0 1 0? ?1 ? ????? ?0 交换第1、行 3 0 1 0 1 1 1? ? ?0 0 0 1 1 0 1? ? ? 0 0 1 1 0 1? ?1 ? ????? ?0 交换第 2、行 3 0 1 0 1 1 1? ?? ?0 1 0 1 0 1 0? ? ?

0 0 1 1 0 1? 0 1 0 1 1 1? ? 1 0 1 0 1 0? ? 0 0 1 1 0 1? 1 0 1 0 1 0? ? 0 1 0 1 1 1? ?

得到系统生成矩阵:

?1 0 0 1 1 0 1 ? GS ? ? 0 1 0 1 0 1 0 ? ? ? ?0 0 1 0 1 1 1 ? ? ?
(2)由 G ? [I n?k , Ak?(n?k ) ], H ? [ Ak?(n?k ) , I n?k ] ,得校验矩阵为
T

?1 ?1 H ?? ?0 ? ?1

1 0 1 0

0 1 1 1

1 0 0 0

0 1 0 0

0 0 1 0

0? 0? ? 0? ? 1?

(3)由于校验矩阵 H 的任意两列线性无关,3 列则线性相关,所以最小汉明距离 d=3。 (4) 3)线性码的消息序列 m=000,001,010,011,100,101,110,111,由 c=mGs 得码字序列: (7, c0=0000000,c1=0010111,c2=0101010,c3=0111101,c4=1001101,c5=1011010,c6=1100111,

?7? c7=1110000。又因伴随式有 24=16 种组合,差错图样为 1 的有 ? ? ? 7种 ,差错图样为 2 的 ?1?
有 ? ? ? 21种 ,而由 Hr ? He ,则计算陪集首的伴随式,构造伴随表如下:
T T

?7? ? 2?

伴随式 0000 1101 1010 0111 1000

陪集首 0000000 1000000 0100000 0010000 0001000

伴随式 0101 1001 1111 1100 1110

陪集首 1001000 1000100 0011000 0001100 0100100

0100 0010 0001

0000100 0000010 0000001

1011 0011 0110

0100001 0010100 0000110

7、 (1)证明如下:

?1 ?1 ? ?0 ? ?0 ?1 ? ?1 ?0 ? ?0 ? ?0 ?1 ? ?1 ?0 ? ?0 ? ?0 ?0 ?

1 1 1 0 0 0 0 ? ?1 ?0 0 0 0 1 0 0 0 ? ? ? (1) ? (2) 1 0 0 0 1 0 0 ? ??? ?0 ? ? ? 0 1 0 0 0 1 0 ? ?0 ?1 1 1 0 0 0 0 1 ? ? ? 1 1 1 0 0 0 0 ? ?1 ?0 1 1 1 1 0 0 0 ? ? ? (3) ? (4) ? ??? ?0 0 1 1 1 1 0 0 ? ? ? 0 1 0 0 0 1 0 ? ?0 ?1 1 1 0 0 0 0 1 ? ? ? 1 1 1 0 0 0 0 ? ?1 ?0 1 1 1 1 0 0 0 ? ? ? (4) ? (5) 0 1 1 1 1 0 0 ? ??? ?0 ? ? ? 0 0 1 1 1 1 0 ? ?0 ? ?0 0 0 1 0 0 0 1 ? ?

1 1 1 0 0 0 0 ? 1 1 1 1 0 0 0 ? ? (2) ? (3) 1 0 0 0 1 0 0 ? ??? ? ? 0 1 0 0 0 1 0 ? 1 1 0 0 0 0 1 ? ? 1 1 1 0 0 0 0 ? 1 1 1 1 0 0 0 ? ? (1) ? (5) 0 1 1 1 1 0 0 ? ??? ? ? 0 0 1 1 1 1 0 ? ? 1 1 0 0 0 0 1 ? 1 1 1 0 0 0 0 ? ? 1 1 1 1 0 0 0 ? 0 1 1 1 1 0 0 ? ? 0 0 1 1 1 1 0 ? 0 0 0 1 1 1 1 ? ?

由生成矩阵可知为(8、5)循环码。 (2)生成多项式如下:

g ( x) ? x3 ? x2 ? x ? 1
8、由题目可知代数计算求解过程如下:

m( x ) ? x 3 ? 1 m( x ) ? x n ? k ? x 6 ? x 3 b( x) ? (m( x) ? x n ? k ) mod( x 3 ? x ? 1) ? x 2 ? x c ( x ) ? m( x ) ? x n ? k ? b ( x ) ? x 6 ? x 3 ? x 2 ? x c ? (1001110)
由编码电路进行求解: 编码电路如下所示:

门1

D0

+

D1

D2

+

或门

c(x)

m

编 寄存器码字 D0 D1 D2 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0

码过程如下: 时钟 0 1 2 3 4 5 6 7 可得: c( x) ? x6 ? x3 ? x2 ? x
9、 n ? 2 ? 1 ? 15 ? m ? 4
m

信息元

输出码字

1 0 0 1

1 0 0 1 1 1 0

纠错能力: t ? 2m?1 ? 8 ,所以最多能纠正 7 个错误码。 有限域 GF(24) 次本原多项式 f ( x) ? x4 ? x ? 1 ,α 为 f(x)的一个根,可知: ,4
?4 ? ? ? 1 ? 0 , 计算 2t=14 个连续幂次为 ???????? ??? ??? ???????? 对应的最小多项式:

?? ? m1 ( x) ? x 4 ? x ? 1, ? ? ? m2 ( x) ? x 4 ? x ? 1, ? ? ? m3 ( x) ? x 4 ? x 3 ? x 2 ? x ? 1 ? ? ? m4 ( x) ? x 4 ? x ? 1, ? ? ? m5 ( x) ? x 2 ? x ? 1, ? ? ? m6 ( x) ? x 4 ? x 3 ? x 2 ? x ? 1 ? ? ? m7 ( x) ? x 4 ? x 3 ? 1, ?? ? m8 ( x) ? x 4 ? x ? 1, ? ? ? m9 ( x) ? x 4 ? x ? 1 ??? ? m10 ( x) ? x 2 ? x ? 1, ??? ? m11 ( x) ? x 4 ? x 3 ? x 2 ? x ? 1 ??? ? m12 ( x) ? x 4 ? x 3 ? x 2 ? x ? 1, ??? ? m13 ( x) ? x 2 ? x ? 1, ??? ? m3 ( x) ? x 4 ? x 3 ? 1

(1) t=1 的码字: (15,11)BCH 码

g1 ( x) ? Lcm(m1 ( x)) ? x4 ? x ?1
(2)t=2 的码字:(15,7)BCH 码

g2 ( x) ? Lcm(m1 ( x)m3 ( x)) ? x8 ? x7 ? x6 ? x4 ?1
(3)t=3 的码字:(15,5)BCH 码

g3 ( x) ? Lcm(m1 ( x)m3 ( x)m5 ( x)) ? x10 ? x8 ? x5 ? x4 ? x2 ? x ?1
(4) t=4 的码字:(15,1)BCH 码

g4 ( x) ? x14 ? x13 ? x12 ? x11 ? x10 ? x9 ? x8 ? x7 ? x6 ? x5 ? x4 ? x3 ? x2 ? x ? 1
(5) t=5 的码字:(15,1)BCH 码

g5 ( x) ? x14 ? x13 ? x12 ? x11 ? x10 ? x9 ? x8 ? x7 ? x6 ? x5 ? x4 ? x3 ? x2 ? x ? 1
(6) t=6 的码字:(15,1)BCH 码

g6 ( x) ? x14 ? x13 ? x12 ? x11 ? x10 ? x9 ? x8 ? x7 ? x6 ? x5 ? x4 ? x3 ? x2 ? x ? 1
(7) t=7 的码字:(15,1)BCH 码

g7 ( x) ? x14 ? x13 ? x12 ? x11 ? x10 ? x9 ? x8 ? x7 ? x6 ? x5 ? x4 ? x3 ? x2 ? x ? 1
10、码长:n=q-1, q ? 2m ? 16 ,m=4

dmin ? 2t ? 1 ? 7
n-k=2t=6 k=n-2t=15-6=9 可知 RS 码为: (5,9)码 设α 为本原多项式 f ( x) ? x4 ? x ? 1 的根,即: ?4 ? ? ? 1
t=3,生成多项式 g(x)有 6 个连续的根, ???? ??? ??? ??? ???

g ( x) ? ( x ? ??? x ? ?? ?? x ? ?? ?? x ? ?? ?? x ? ?? ?? x ? ?? ) ? x6 ? ?10 x5 ? ??? x4 ? ?4 x3 ? ?6 x2 ? ?9 x ? ?6
(15,9)的 RS 码的生成矩阵如下:

?1 ? ?0 ?0 ? ?0 ? ?0 ?0 ? ?0 ? ?0 ? ?0

α 10 α 14 α 4 α 6 α 9 α 6 0 0 0 0 0 0 0 0 ? ? 1 α 10 α 14 α 4 α 6 α 9 α 6 0 0 0 0 0 0 0 ? 0 1 α 10 α 14 α 4 α 6 α 9 α 6 0 0 0 0 0 0 ? ? 10 14 4 6 9 6 0 0 1 α α α α α α 0 0 0 0 0 ? ? 0 0 0 1 α 10 α 14 α 4 α 6 α 9 α 6 0 0 0 0 ? 0 0 0 0 1 α 10 α 14 α 4 α 6 α 9 α 6 0 0 0 ? ? 10 14 4 6 9 6 0 0 0 0 0 1 α α α α α α 0 0 ? ? 0 0 0 0 0 0 1 α 10 α 14 α 4 α 6 α 9 α 6 0 ? ? 0 0 0 0 0 0 0 1 α 10 α 14 α 4 α 6 α 9 α 6 ?

11、 (1).以下两种都可以


赞助商链接
相关文章:
信息与编码理论课后习题答案
信息与编码理论课后习题答案_哲学_高等教育_教育专区。信息论与编码理论 课件 课后...科目三实际道路驾驶考试注意事项 驾考新题抢先版文档贡献者 249505463 贡献于2011...
《信息与编码理论》习题答案(高教-王育民-李晖-梁传甲)
《信息与编码理论习题答案(高教-王育民-李晖-梁...精选题 1.傅 P191【5.15】 2.傅 P192【5.16...2014小学教师资格考试《... 2014年幼儿园教师资格考...
信息与编码理论课后习题答案
信息与编码理论课后习题答案_工学_高等教育_教育专区...log 2 1960 =3.822 比特 2.7 某校入学考试中有 ...编码效率为 0.4756/0.469=98.6% 精选题 1.傅...
信息论与编码试题集与答案考试必看
? 2 ? 信息理论编码试卷A答案 中南大学考试试卷时间 100 分钟 200 -- 2010 学年 上学期期末考试试题 信息论基础专业年级: 课程 32 学时 学分 考试形式: ...
商品编码练习题及答案
商品编码练习题答案_从业资格考试_资格考试/认证_教育专区。商品编码的习题及其...其原理是通过极微量的银分子对味觉神经的作用, 使吸烟者对于烟草之烟产 生厌恶...
信息论与编码期末考试题(全套)
信息论与编码期末考试题(全套)_教育学_高等教育_教育专区。编码答案 ...4、 无失真信源编码的平均码长最小理论极限制为信源熵 (或 H(S)/logr= ...
西电考研资料《信息与编码理论》习题答案(高教-王育民-...
2013年考研数学一考试大纲... 考研热点问题全解读 经验分享之2012考研面试时.....西电考研资料《信息与编码理论习题答案(高教-王育民-李晖-梁传甲) 西电复试八门...
商品编码归类练习题及答案(33章)
商品编码归类练习题答案(33章)_其它考试_资格考试/认证_教育专区。HS 编码归类练习 第三十三章 编码归类练习(第三十三章 第三十三章) 1. 茉莉油 2. 不含...
信息论与编码理论-第7章线性分组码-习题解答-20071206
信息论与编码理论-第7章线性分组码-习题解答-20071206_工学_高等教育_教育专区。信息论与编码理论 第7章 线性分组码习 题 1. 已知一个(5, 3)线性码 C 的...
信息论与编码理论复习题(一)
信息论与编码理论复习题(一)_计算机软件及应用_IT/计算机_专业资料。信息论与编码...参考答案: 填空(1)香农(2)0 (3)N 倍(4) 信源符号等概分布 (5)香农...
更多相关标签: