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

编码理论复习题答案


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


相关文章:
信息论与编码理论复习题(一)
信息论与编码理论复习题(一)_计算机软件及应用_IT/计算机_专业资料。信息论与编码...参考答案: 填空(1)香农(2)0 (3)N 倍(4) 信源符号等概分布 (5)香农...
信息论与编码试题集与答案考试必看
? 2 ? 信息理论编码试卷A答案 中南大学考试试卷时间 100 分钟 200 -- 2010 学年 上学期期末考试试题 信息论基础专业年级: 课程 32 学时 学分 考试形式: ...
编码员考试题
编码考试题_金融/投资_经管营销_专业资料。中国医院协会病案管理专业委员会 ...2、疾病编码、损伤性质和肿瘤的形态学编码都要在第一个索引中查找,该索引 是...
信息论与编码考试试题
信息论与编码考试试题_工学_高等教育_教育专区。兰州理工大学题号 得分 一二三...信息论与编码答案 暂无评价 51页 1下载券 信息论与编码_第4章 暂无评价 31...
信息论与编码考试题(附答案版)
11.算术编码是(非)分组码。 12.游程编码是(无)失真信源编码。 13.线性分组码的(校验矩阵)就是该码空间的对偶空间的生成矩阵。 14.若(n,k)线性分组码为 ...
2011湖南理论规范试题答案
2011湖南理论规范试题答案_从业资格考试_资格考试/认证_教育专区。第三届湖南省...二、单项选择(每题 0.5 分,共 10 分。请将答案编码填写在括号内) 1、我...
信息论与编码期末考试题(全套)
《信息论基础》参考答案 一、填空题(共 15 分,每空 1 分) 1、信源编码的...4、无失真信源编码的平均码长最小理论极限制为信 源熵(或 H(S)/logr= ...
数电复习题(含答案)
数电复习题(含答案)_其它课程_高中教育_教育专区。数 电 复 习 题) 选择题...D.寄存器 D 进制计数 B.编码器 C.全加器 38、把一个五进制计数器与一个...
2014年武汉理工大学信息理论与编码期末复习资料(计算题...
2014年武汉理工大学信息理论编码期末复习资料(计算题含答案)_工学_高等教育_教育专区。老师勾画的重点,自己整理的答案不确定性与信息 2.3 一副充分洗乱的牌(含...
国际疾病分类与手术操作编码培训考试题答案
国际疾病分类与手术操作编码培训考试题答案_临床医学_医药卫生_专业资料。国际疾病分类与手术操作编码培训考试题一 填空(30分) 1.双重分类指星号和剑号编码。剑号表...
更多相关标签: