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

编码理论复习题答案


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).以下两种都可以


相关文章:
信息理论与编码基础复习题
信息理论编码基础复习题 - 信息理论编码基础复习题 1.从通信的实质意义来讲,如果信宿收到的消息是已知的, 则等于没有收到任何消息。 2. 当一个信源中...
信息与编码理论课后习题答案
信息与编码理论课后习题答案_哲学_高等教育_教育专区...log 2 1960 =3.822 比特 2.7 某校入学考试中有 ...课堂教学例题 课堂教学例题 19 4.8 解:该题概率有...
编码理论复习题
编码理论复习题 - 1、有一信源,它有六个可能的输出,其概率分布如下表所示,表中给出了对应的码 A、 B、C、D、E 和 F (1)求这些码中哪些是唯一可译码;...
信息论与编码理论习题(三)
信息论与编码理论复习题(一... 信息论与编码理论习题(二)1/2 相关文档推荐 ...参考答案: 一.填空(1)有效性,可靠性,安全性 (2)1.75bit/符号(3) ? m ?...
通信原理期末复习题答案复习资料
通信原理期末复习题答案复习资料 - 一、填空题 1. 信源编码的两大任务为__提高信息传输效率_和__完成 A/D 转换__。 2.为使基带脉冲传输获得足够小的误码...
简答题及答案
通信原理复习题答案 一、单项选择题 1. B 11. B 21. B 31. D 41. C ...差分编码 53、抽样,量化,编码 55、时间上的离散,幅度上的离散 57、模拟,数字...
信息论与编码理论2A卷 答案
信息论与编码理论2A卷 答案 - 院、系领导 审批并签名 A 卷 广州大学 2013-2014 课程 学院 题次 分数 评分 一 15 二 15 学年第 2 学期考试卷 信息论与...
信息论与编码试题集与答案考试必看
信息论与编码试题集与答案考试必看 - 信息基础论必备考卷 1. 在无失真的信源中,信源输出由 R(D) 来度量。 信源 编码, H(X) 来度量;在有失真的信源中,...
2012春理论练习题答案
2012春理论练习题答案 - 第 1 章 计算机信息技术概述 1.1 计算机信息技术概述 1. 下列关于信息的叙述中错误的是___D___。 A.信息是指事物运动的状态及...
计算机考试思考题答案
计算机考试思考题答案_院校资料_高等教育_教育专区。...人们的意志自动进行工作,最直接的原因(工作原理)是...6566H 和 E5E6H (10)汉字编码与 ASCII 码在...
更多相关标签: