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

编码理论复习题答案


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


相关文章:
编码理论复习题答案.doc
编码理论复习题答案 - 1、 (1)A、B、C、E 编码是唯一可译码。 (2)A
信息传输理论与编码复习提纲及习题参考答案 (1).doc
信息传输理论编码复习提纲及习题参考答案 (1) - 《信息传输理论编码复习提纲 第 2 章、信息的统计度量 1、自信息量、条件自信息量、平均自信息量(熵) ...
信息论与编码复习题B答案.doc
信息论与编码复习题B答案 - 《信息论与编码》期末复习题 B 答案 一、填空题(每小题 4 分,共 24 分) 1.根据信息论的各种编码定理和通信系统的指标,编码...
java编码规范考试题答案.doc
java编码规范考试题答案_计算机软件及应用_IT/计算机_专业资料。中软java编码规范考试题满分答案 一、单选题 1. 如下关于集合类的描述错误的是 B A. 含有集合...
信息论与编码期末考试题(全套).doc
信息论与编码期末考试题(全套)_教育学_高等教育_教育专区。编码答案 ...4、 无失真信源编码的平均码长最小理论极限制为信源熵 (或 H(S)/logr= ...
JAVA编码规范考试题答案.doc
JAVA编码规范考试题答案 - 一、单选题 1. 如下关于集合类的描述错误的是
信息论与编码试题集与答案考试必看.doc
信息论与编码试题集与答案考试必看 - 信息基础论必备考卷 1. 在无失真的信源中,信源输出由 R(D) 来度量。 信源 编码, H(X) 来度量;在有失真的信源中,...
信息论与编码考试题(附答案版).doc
信息论与编码考试题(附答案版) - 山东建筑大学 许洪奎 信息论与编码 考试 复习... 信息论与编码考试题(附答案版)_理学_高等教育_教育专区。山东建筑大学 许洪奎...
高级理论复习题答案概要.doc
高级理论复习题答案概要 - (高级)理论复习题 一、多项选择题: 1. 计算放大
复习题参考答案.doc
复习题参考答案 - ★每章后的自测题全部要做(除第 3 章部分题) 简答题 1.2 节 复习题(1) (2) (4) (5)教材 P18 (1)什么是比特?比特是如何表示和...
《密码编码学与网络安全》复习题答案.pdf
《密码编码学与网络安全》复习题答案 - 《密码编码学与网络安全》复习题 1. 信
信息论与编码考试题答案一[1].doc
信息论与编码考试题答案一[1] - 试题答案 20082009 学年第 1 学期 课程名称:信息论与编码 命题系别:_网络工程学院_一、选择题(每题 2 分,共 10 分)...
十九套商品编码练习题及答案.doc
十九套商品编码练习题答案 - 19 套商品编码练习题答案 商品归类(一) 1
国际疾病分类与手术操作编码培训考试题及答案.doc
国际疾病分类与手术操作编码培训考试题答案 - 国际疾病分类与手术操作编码培训考试题 一填 空(30分) 1. 双重分类指星号和剑号编码。剑号表示疾 ...
大学计算机基础理论测试题题库(单项选择题及答案) (1).doc
大学计算机基础理论测试题题库 (单项选择题及答案)一.单项选择题 1.下列叙述中...A.1,4,5,6 B.1,3,4 C.2,4,5,6 D.1,4,6 222.下列关于汉字编码...
信息论与编码期末考试题.doc
信息论与编码期末考试题_工学_高等教育_教育专区。...4、无失真信源编码的平均码长最小理论极限制为信...答案一、 概念简答题 1.答:平均自信息为 表示信...
信息论与编码考试题一答案.doc
信息论与编码考试题答案 - 信息论与编码 复习指导提纲 考试真题 答案... 信息论与编码考试题答案_理学_高等教育_教育专区。信息论与编码 复习指导提纲 考试真题...
信息论与编码考试题答案1.doc
信息论与编码考试题答案1 信息论与编码试题信息论与编码试题隐藏>> 试题答案 20082009 学年第 1 学期课程名称:信息论与编码 命题系别:_网络工程学院_一、选...
《信息理论与编码》,答案,考试重点(1--3章).doc
《信息理论编码》,答案,考试重点(1--3章) - 信息理论编码习题参考 参考答案 《 信息理论编码习题 参考 答案 1. 信息是什么?信息与消息有什么...
信息论与编码考试题二答案.doc
信息论与编码考试题答案 - 信息论与编码 复习指导提纲 考试真题 答案... 信息论与编码考试题答案_司法考试_资格考试/认证_教育专区。信息论与编码 复习指导提纲...