第五章信源编码-习题答案

格式：pdf
大小：265.22 KB
文档页数：5

下载文档原格式

第五章信源编码习题课 PPT课件

将信源符号按概率从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn) 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和
“1”，将这两个信源符号合并成一个新符号，并用这两个最小的
概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源
符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，
它们的出现概率分别为P(x1) = 1/2，P(x2) = 1/4，P(x3) = 1/8，…， P(xi) = 1/2i，…。（1）用香农编码方法给出各个符号消息的代码组；（2）计算该信源编码的效率。
解（1）信源消息的概率分布呈等比级数，按香农编码方法，其码长集合为自然数数列1, 2, 3, ···, i, ···；对应的编码分别为：0, 10, 110, ···, 111…110 ( i – 1个1), ···。
可以编m进制码，但m越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。
2019/11/21
8
二元游程编码
第五章信源编码
游程变换减弱了原序列符号间的相关性。
2019/11/21
9
L-D编码
第五章信源编码
L－D编码方法是一种分帧传送的方式；编码方法
在冗余位序列中取N个符号作为一帧，编成一个码字，码字中含有信息位的数量和位置信息，在接收端依据这些信息进行译码；
每个码字传送两个数：Q和T，由下式计算
2019/11/21

信息论第五章答案

信息论第五章答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March设信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X (1) 求信源熵H(X)； (2) 编二进制香农码；(3) 计算平均码长和编码效率。

解： (1)symbol bit x p x p X H i i i /609.2)01.0log 01.01.0log 1.015.0log 15.017.0log 17.018.0log 18.019.0log 19.02.0log 2.0()(log )()(2222222712=⨯+⨯+⨯+⨯+⨯+⨯+⨯-=-=∑=%1.8314.3609.2)()(14.301.071.0415.0317.0318.0319.032.03)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X 编二进制费诺码，计算编码效率。

%2.9574.2609.2)()(74.201.041.0415.0317.0218.0319.032.02)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X 编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。

解：%9.9572.2609.2)()(72.201.041.0415.0317.0318.0319.022.02)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η%4.913log 8.1609.2log )()(8.1)01.01.015.017.018.019.0(22.01)(22=⨯====+++++⨯+⨯==∑m LKX H R X H x p k K ii i η设信源⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=⎥⎦⎤⎢⎣⎡12811281641321161814121)(87654321x x x x x x x x X P X (1) 求信源熵H(X)；(2) 编二进制香农码和二进制费诺码；(3) 计算二进制香农码和二进制费诺码的平均码长和编码效率； (4) 编三进制费诺码；(5) 计算三进制费诺码的平均码长和编码效率；解： (1)symbolbit x p x p X H i i i /984.1128log 1281128log 128164log 64132log 32116log 1618log 814log 412log 21)(log )()(22222222812=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯=-=∑==127/64 bit/symbol (2)香农编码效率：%100984.1984.1)()(64/127984.17128171281664153214161381241121)(======⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑K X H R X H x p k K ii i η费诺编码效率：%100984.1984.1)()(984.17128171281664153214161381241121)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑K X H R X H x p k K ii i η%3.943log 328.1984.1log )()(328.14128141281364133212161281141121)(22=⨯=⋅===⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑m K X H R X H x p k K ii i η设无记忆二进制信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡1.09.010)(X P X 先把信源序列编成数字0，1，2，……，8，再替换成二进制变长码字，如下表所示。

第5章无失真信源编码定理

5.1 编码器
编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为 S {S1, S2 ,..., Sq }；而信道所能传输的符号集为 X {x1, x2 ,..., xr } 编码器的功能是用符号集X中的元素，将原始信源的符号 S i 变换为相应的码字符号 wi ，所以编码器输出端的符号集为 C :{W1,W2 ,...,Wq }
0
0 0
01
001 0001
树枝数——码的数
节数——码长端点——码字满树——等长码非满树——变长码
码4的树图
码3的树图
在每个节点上都有r个分枝的树称为整树，否则称为非整树。即时码的树图还可以用来译码。
5.5.3 克拉夫特（Kraft）不等式
定理5.4 对于码符号为 X {x1 , x2 ,..., xr } 的任意即时码，其码字为 W1 ,W2 ,...,Wq 所对应的码长为 l1 , l2 ,..., lq ，则必定满
第5章无失真信源编码定理
◆ 编码器 ◆ 等长码 ◆ 等长信源编码定理 ◆ 变长码
◆ 变长信源编码定理
引言
1、信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每
个信源符号的平均比特数或信源的码率。即同样多的信
息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。
但码3和码4也不太一样，码4称作逗点码，只要收到1，就
可以立即作出译码；而码3不同，当收到一个或几个码时，
必须参考后面的码才能作出判断。定义在唯一可译码中，有一类码，它在译码是无须参考后面的码字就可以作出判断，这种码称为即时码。定义如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字后加上若干码元后都不是

信道编码习题解答

第五章信道编码习题解答1．写出与10011的汉明距离为3的所有码字。

解：共有10个：01111，00101，00000，01010，01001，00110，11101，10100，11000，11110。

2．已知码字集合的最小码距为d ，问利用该组码字可以纠正几个错误？可以发现几个错误？请写出一般关系式。

解：根据公式：(1)1d e ≥+ 可发现e 个错。

(2)21d t ≥+ 可纠正t 个错。

得出规律：（1）1d = ，则不能发现错及纠错。

（2）d 为奇数：可纠12d -个码元错或发现1d -个码元错。

（3）d 为偶数：可纠12d-个码元错，或最多发现1d -个码元错。

（4）码距越大，纠、检错能力越强。

3．试计算（8，7）奇偶校验码漏检概率和编码效率。

已知码元错误概率为410e p -=。

解：由于410e p -=较小，可只计算错两个码元（忽略错4或6个码元）的情况：228788!10 2.8106!2!e p C p --==⨯=⨯⨯ 787.5%8η==4．已知信道的误码率410e p -=，若采用“五三”定比码，问这时系统的等效（实际）误码率为多少？解：由于410e p -=较小，可只计算错两个码元的情况1125211283232(1)610e e e p C C p p C C p --=-≈=⨯5．求000000，110110，011101，101011四个汉明码字的汉明距离，并据此求出校正错误用的校验表。

解：先求出码字间距离：000000 110110 011101 101011000000 4 4 4 110110 4 4 4 011101 4 4 4 101011 4 4 4 汉明距离为4，可纠一位错。

由于一个码字共有6个码元，根据公式：21617rn ≥+=+= 得 3r = 即每个码字应有3位监督码元，6-3=3位信息码元。

直观地写出各码字：123456000000110110011101101011x x x x x x 令456x x x 为监督码元，观察规律则可写出监督方程：413523612x x x x x x x x x=⊕⎧⎪=⊕⎨⎪=⊕⎩从而写出校验子方程：113422353126s x x x s x x x s x x x *********⎧=⊕⊕⎪=⊕⊕⎨⎪=⊕⊕⎩列出校验表：6．写出信息位6k =，且能纠正1个错的汉明码。

信息论与编码第五章答案

信息论与编码第五章答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March设信源1234567()0.20.190.180.170.150.10.01X a a a a a a a p X ⎡⎤⎧⎫=⎨⎬⎢⎥⎣⎦⎩⎭(1) 求信源熵H(X)； (2) 编二进制香农码；(3) 计算平均码长和编码效率. 解： (1)721222222()()log ()0.2log 0.20.19log 0.190.18log 0.180.17log 0.170.15log 0.150.1log 0.10.01log 0.012.609/i i i H X p a p a bit symbol==-=-⨯-⨯-⨯-⨯-⨯-⨯-⨯=∑71()0.230.1930.1830.1730.1530.140.0173.141()()/ 2.609 3.14183.1%i i i K k p x H X H X K Rη===⨯+⨯+⨯+⨯+⨯+⨯+⨯====÷=∑对习题的信源编二进制费诺码，计算编码效率.对信源编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率.解：x i p(x i)编码码字k i s61s50s41s30s21x10102 x21112 x300003 x410013 x500103 s11x6001104 x7101114x i p(x i)编码码字k i s31s20s11x1221 x20002 x31012 x42022 x50102 x61112x72122设信源(1) 求信源熵H(X)；(2) 编二进制香农码和二进制费诺码；(3) 计算二进制香农码和二进制费诺码的平均码长和编码效率；(4) 编三进制费诺码；(5) 计算三进制费诺码的平均码长和编码效率；解：(1)(2)x i p(x i)p a(x i)k i码字x1010x2210x33110x441110x5511110x66111110x771111110x871111111xi p(x i)编码码字k i x1001 x210102 x3101103x41011104 x510111105x6101111106x71011111107x8111111117 (3)香农编码效率：费诺编码效率：(4)x i p(x i)编码码字k i x1001 x2111x320202x41212x5202203x612213x72022204x8122214设无记忆二进制信源先把信源序列编成数字0，1，2，……，8，再替换成二进制变长码字，如下表所示.(1) 验证码字的可分离性；(2) 求对应于一个数字的信源序列的平均长度；(3) 求对应于一个码字的信源序列的平均长度；(4) 计算，并计算编码效率；(5) 若用4位信源符号合起来编成二进制哈夫曼码，求它的平均码长，序列数字二元码字10100001110010013101000013101100001411000000015110100000016111000000001711110000000080一个来编写二进制哈夫曼码，求新符号的平均码字长度和编码效率.对题的信源进行游程编码.若“0”游程长度的截至值为16，“1”游程长度的截至值为8，求编码效率.选择帧长N = 64(1) 对00000000000000000000000000000000000000遍L-D码；(2) 对000000000010遍L-D码再译码；(3) 对000000000000000000000000000000000000000000000000000000000000000 0遍L-D码；(4) 对0遍L-D码；(5) 对上述结果进行讨论.。

信息论第五章答案

设信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X (1) 求信源熵H(X)； (2) 编二进制香农码；(3) 计算平均码长和编码效率。

解： (1)symbolbit x p x p X H i i i /609.2)01.0log 01.01.0log 1.015.0log 15.017.0log 17.018.0log 18.019.0log 19.02.0log 2.0()(log )()(2222222712=⨯+⨯+⨯+⨯+⨯+⨯+⨯-=-=∑=%1.8314.3609.2)()(14.301.071.0415.0317.0318.0319.032.03)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η.对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X 编二进制费诺码，计算编码效率。

解：%2.9574.2609.2)()(74.201.041.0415.0317.0218.0319.032.02)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.0)(7654321x x x x x x x X P X 编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。

解：%9.9572.2609.2)()(72.201.041.0415.0317.0318.0319.022.02)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η%4.913log 8.1609.2log )()(8.1)01.01.015.017.018.019.0(22.01)(22=⨯====+++++⨯+⨯==∑m LKX H R X H x p k K ii i η设信源⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=⎥⎦⎤⎢⎣⎡12811281641321161814121)(87654321x x x x x x x x X P X (1) 求信源熵H(X)；(2) 编二进制香农码和二进制费诺码；(3) 计算二进制香农码和二进制费诺码的平均码长和编码效率； (4) 编三进制费诺码；(5) 计算三进制费诺码的平均码长和编码效率；解： (1)）symbolbit x p x p X H i i i /984.1128log 1281128log 128164log 64132log 32116log 1618log 814log 412log 21)(log )()(22222222812=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯=-=∑==127/64 bit/symbol (2)二进制香农码：\香农编码效率：%100984.1984.1)()(64/127984.17128171281664153214161381241121)(======⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η费诺编码效率：%100984.1984.1)()(984.17128171281664153214161381241121)(=====⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑KX H R X H x p k K ii i η（%3.943log 328.1984.1log )()(328.14128141281364133212161281141121)(22=⨯=⋅===⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑m K X H R X H x p k K ii i η设无记忆二进制信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡1.09.010)(X P X先把信源序列编成数字0，1，2，……，8，再替换成二进制变长码字，如下表所示。

第五章信源编码

若信源符号数小于16，可以去掉几个节点，若信源符号数小于，可以去掉几个节点，码树为非满树只有部分树枝延伸到最后一级）（只有部分树枝延伸到最后一级）
0
r 进制 ---每个节点长出个树枝。每个节点长出r个树枝每个节点长出个树枝。如r=3,三进制码树三进制码树 2、kraft(克劳夫特不等式、克劳夫特)不等式克劳夫特
(2)若K1 = 1, K 2 = 2, K 3 = 3, K 4 = 3，则： m − K i = 1，满足不等式 ∑
i =1 n
对四元符号进行二进制编码，存在长度为、 3、 1 2、 3的惟一可译码。
用码树验证以上结果：用码树验证以上结果：无论如何也不能构造出长度为1、、、的即时码度为、2、2、3的即时码
v 码长K Li，i = 1,2....n ；平均码长：K L = ∑ K Li P( yi )码元 / 符号序列
L i =1
_
nL
定长编码：K L1 = K L2 = ......K LnL = K L，K L = K L
_
2、码长的意义：衡量码的性能的重要参数、码长的意义：衡量码的性能的重要参数码的性能对于无失真信源编码，越长，对于无失真信源编码，平均码长 K L 越长，说明通过编码压缩去的冗余越少。越短，冗余压缩越多。压缩去的冗余越少。反之平均码长越短，冗余压缩越多。 _ 最小是多少呢？小于此值，平均码长 K L 最小是多少呢？（小于此值，就会产生失）。有下面的定理有下面的定理：真）。有下面的定理：一、定长编码定理：定长编码定理：
若映射规则f 2为：a1 − − > w1 = 0，a 2 − − > w 2 = 01， a 3 − − > w 3 = 001，a 4 − − > w 4 = 011 那么，码字集为 W = {0,01,001,011}，称为码2 v v 当输入序列为x = a 2a1a 4a 3a 2时，输出序列为： y = 01001100101

信息论与编码第5章习题解答

x ˆ x
= λ ( 0) ⋅ p * (1) ⋅ e 2s + 0.5 ⋅ λ (1) ⋅ p * (0) ⋅ e s Rs = s ⋅ Ds + 0.5 ⋅ [log λ ( 0) + log λ (1)]
其中参数 s < 0 。
5.7
x2 X x1 1 设信源 = ( p < ) ，其失真度为 Hamming 失真度，试问当允许 2 p (x ) p 1 − p 1 平均失真度 D = p 时，每个信源符号平均最少需要几个二进制符号表示？ 2
所以转移概率矩阵具有与失真矩阵相同的置换对称。
α a1 a 2 a 3 β b1 γ a α a a β b γ 3 2 1 P= 1 a a α a b β γ 2 3 1 1 a a a α b β γ 3 2 1 1 ˆ ˆ 由于对于使失真 d ( xi , x j ) = ∞ 的 ( xi , xi ) ，相应的转移概率必须为零，即
所以
R( D ) =
β =D − 3 γ ≥0 α =1− D +2γ ≥0 γ ≥0
β = D − 3γ ≥ 0 α = 1 − β − γ = 1 − D + 2γ ≥ 0 γ ≥0 min {2 − D + γ }
= ( 2 − D ) bit
当1 ≤ D ≤ 3 ，
所以
D α + β + γ = 1 β = D − 3γ ≥ 0 γ ≤ 3 β + 3γ = 0 ⇒ α = 2γ − D + 1 ≥ 0 ⇒ D −1 γ ≥0 γ ≥ α , β , γ ∈ [ 0,1] 2 R( D ) = min {2 − D + γ }

第五章信源编码

0001 E
上所对应的符号组成
图5.2
如图中的终端节点E，走过的路径为ABCDE，所对应的码符号
分别为0、0、0、1，则E对应的码字为0001。
• 即时码：它可引用很直观的“码树”概念来说明：
将变长码与码树建立“一一对应”关系：
树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码
0.18 0.17 0.15 0.10 0.01
p(xi )
解：
xi 符号概率 p(xi ) 累加概率 Pi
x1 0.20
0
x2 0.19
0.2
x3 0.18
0.39
x4 0.17
0.57
x5 0.15
0.74
x6 0.10
0.89
x7 0.01
0.99
1〉码字长度计算以 i 为4例，
log2 p(xi ) 码字长度 K i 码字
k 1
(5)取 P二i 进制数的小数点后位K，i 即为该消息符号的二进制码字。
可以证明，这样得到的编码一定是唯一可译码，且码长比较短，接近于最佳编码。严格意义上来说不是最佳码。
例题：设信源共有7个符号组成，其概率如表所示，求其香农码。
信源消息符号
x1 x2 x3 x4
x5 x6
x7
xi 符号概率 0.20 0.19
例1 ：
[X P]: 0s.14
s2 0.2
s3 0.2
s4 0.1
s5 0.1
w1 1 s1 : 0.4 0.4 w2 01 s2 : 0.2 0.2 w3 000 s3 : 0.2 0.2 0 w4 0010 s4 : 0.1 0 0.2 1 w5 0011 s5 : 0.1 1

第四章第5 章习题答案

第四章信息率失真函数-习题答案4.1 一个四元对称信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡4/14/1324/14/110)(X P X ，接收符号Y = {0, 1, 2, 3}，其失真矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101111011110，求D max 和D min 及信源的R(D)函数，并画出其曲线（取4至5个点）。

解：041041041041),(min )(43041141141141),()(min min min max =⨯+⨯+⨯+⨯===⨯+⨯+⨯+⨯===∑∑i j i j i ij i i j j y x d x p D y x d x p D D因为n 元等概信源率失真函数：⎪⎭⎫⎝⎛-⎪⎭⎫ ⎝⎛-+-+=a D a D n a D a D n D R 1ln 11ln ln )(其中a = 1, n = 4, 所以率失真函数为：()()D D DD D R --++=1ln 13ln4ln )(函数曲线：D其中：symbolnat D R D symbolnat D R D symbolnat D R D symbolnat R D /0)(,43/12ln 214ln )(,21/316ln 214ln )(,41/4ln )0(,0==-==-====4.2 若某无记忆信源⎭⎬⎫⎩⎨⎧-=⎥⎦⎤⎢⎣⎡3/113/13/101)(X P X ，接收符号⎭⎬⎫⎩⎨⎧-=21,21Y ，其失真矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=112211D 求信源的最大失真度和最小失真度，并求选择何种信道可达到该D max 和D min 的失真度。

4.3 某二元信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡2/12/110)(X P X 其失真矩阵为⎥⎦⎤⎢⎣⎡=a a D 00求这信源的D max 和D min 和R(D)函数。

解：021021),(min )(202121),()(min min min max =⨯+⨯===⨯+⨯===∑∑i j i j i ij i i j j y x d x p D aa y x d x p D D因为二元等概信源率失真函数：⎪⎭⎫⎝⎛-=a D H n D R ln )(其中n = 2, 所以率失真函数为：⎥⎦⎤⎢⎣⎡⎪⎭⎫ ⎝⎛-⎪⎭⎫ ⎝⎛-+-=a D a D a D a D D R 1ln 1ln 2ln )(4.4 已知信源X = {0, 1}，信宿Y = {0, 1, 2}。

信息理论与编码课后答案第5章

第5章有噪信道编码5.1 基本要求通过本章学习，了解信道编码的目的，了解译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。

掌握信息率与平均差错率的关系，掌握最小汉明距离译码规则，掌握有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念，了解定理的证明方法，掌握线性分组码的生成和校验。

5.2 学习要点5.2.1 信道译码函数与平均差错率5.2.1.1 信道译码模型从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F 。

信道译码模型如图5.1所示。

5.2.1.2 信道译码函数信道译码函数F 是从输出符号集合B 到输入符号集合A 的映射：*()j j F b a A =∈，1,2,...j s =其含义是：将接收符号j b B ∈译为某个输入符号*j a A ∈。

译码函数又称译码规则。

5.2.1.3 平均差错率在信道输出端接收到符号j b 时，按译码规则*()j j F b a A =∈将j b 译为*j a ，若此时信道输入刚好是*j a ，则称为译码正确，否则称为译码错误。

j b 的译码正确概率是后验概率：*(|)()|j j j j P X a Y b P F b b ⎡⎤===⎣⎦ （5.1）j b 的译码错误概率：(|)()|1()|j j j j j P e b P X F b Y b P F b b ⎡⎤⎡⎤=≠==-⎣⎦⎣⎦ （5.2）平均差错率是译码错误概率的统计平均，记为e P ：{}1111()(|)()1()|1(),1()|()s se j j j j j j j ssj j j j j j j P P b P e b P b P F b b P F b b P F b P b F b ====⎡⎤==-⎣⎦⎡⎤⎡⎤⎡⎤=-=-⎣⎦⎣⎦⎣⎦∑∑∑∑ （5.3）5.2.2 两种典型的译码规则两种典型的译码规则是最佳译码规则和极大似然译码规则。

信息论与编码zjh201209zjh第五章习题

1 2 Log( 2) 1 4 Log ( 4) 1 8 Log( 8) 1 16 Log ( 16) 1 32 Log ( 32) 1 64 Log ( 64) 1 128 Log ( 128) 1 128 Log ( 128) 1.984
(2) 每个信源使用3个二进制符号,出现0的次数为出现1的次数为 P(1)=
2013-2-26 2
解：首先，根据克劳夫特不等式，找出非唯一可译码
C1 : 6 23 1 C2 : 21 22 23 24 25 26 63 1 64 C4 : 21 22 4 2 4 1 C3 : C5 : 21 5 23 1 C6 : 22 5 23 1
2
要求译码错误小于10-3，令δ =10-3 ，则需要一起编的符号长度应满足
2 (X ) L 2 5.2 107
2013-2-26
11
5-11信源符号X有6种字母，概率为0.32、0.22、0.18、0.16、 0.08、0.04。（1）求信源熵；（2）用香农编码法编成二进制变长码，计算其编码效率；（3）用费诺编码法编成二进制变长码，计算其编码效率；（4）用哈夫曼编码法编成二进制变长码，计算其编码效率；（5）用哈夫曼编码法编成三进制变长码，计算其编码效率；（6）若用逐个信源符号来编定长二进制码，要求不出差错译码，求所需要的酶符号的平均信息率和编码效率；（7）当译码差错小于10-3的定长二进制码要达到（4）中的哈夫曼效率时，估计要多少个信源符号一起编才能办到？解：（1）信源熵
2.644 3.644 4.644
3
3 4 5
1001Biblioteka 1 1110 11110平均码长：编码效率为

第五章习题参考解答

D=
2R =R log 2 4
5.13 在分别使用 ASK、FSK、PSK 以及 QPAK 的情况下，要达到 1.0 的带宽效率，要求 SNR 的值为多大？假设要求的比特差错率为 10-6。解答由
Eb S BT = N0 N R
推得
S Eb R = N N 0 BT
已知带宽效率 R/BT=1.0，根据 BER= 10-6，查图 5.4，得到 ASK / FSK: SNRdB= Eb/N0=13.5dB SNR=22.39 PSK / QPSK: SNRdB= Eb/N0=10.5dB SNR=11.22 5.14 一个 NRZ-L 信号先通过一个 r=0.5 的滤波器，然后被调制到载波上，其数据率为 2400bps。分别计算在 ASK 和 FSK 情况下的带宽。假设对于 FSK 使用的两个频率分别为 50kHz 和 55kHz。解答
根据归一化信噪比 Eb S = N0 N0 R 得知 Eb = S / R 。
(见教材 P.74和 P.114)
因此，对于 PSK 有 R=1bit/10µs=1x105bps，
Eb =
S 1.25 ×10 −5 = = 1.25 × 10 −10 5 R 1×10
由已知条件知 N=2.5x10-8W，并设 r = 0，由 PSK（同 ASK）的带宽公式 BT = (1+r) R 得到 BT= R 。则推得 N0 以及归一化信噪比 Eb/N0
N N 2.5 ×10 −8 N0 = = 2.5 × 10 −13 = = 5 BT R 1× 10 Eb 1.25 ×10 −10 = 10 log( ) = 10 log 500 = 27 dB N0 2.5 × 10 −13
对于 QPSK，有 R=2bit/10µs=2x105bps，

第五章信源编码(完结)

5.1编码的定义
非分组码奇异码码分组码非唯一可译码非即时码非奇异码唯一可译码即时码 (非延长码)

码树表示各码字的构成
树根—码字的起点 0 0 1 0 A 1 0 1 0 0 1 1 1 0 0 二进制码树节数—码长 01 2 1 2 0 分成r个树枝--r为码的进制数中间节点—码字的一部分终端节点—码字1101
K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得：
2
i 1
4
Ki
2 2
110
10 0 0 0 1 0
1
2
2
2
2
3
9 1 8
111 11
1
不存在满足这种 Ki的唯一可译码这样的码字就存在唯一可译码中间节点

如果将各码字长度改成K1=1,K2=2,K3=3,K4=3,则
信源
X信源编码器Fra bibliotekY信道
码表
5.1编码的定义
如果信源输出的符号序列长度L=1，则信源符号集为：
A {a1 , a2 ,
, an }
an p(an )
信源概率空间为：
X a1 P p(a ) 1
a2 p(a2 )
若要将信源X通过二元信道传输，就必须把信源符号ai变换成由0,1符号组成的码符号序列Y ，这个过程就是信源编码。所编出的码称为二元码。
5.2 无失真信源编码
•信源编码器输入的消息序列: X ( X1, X 2 , , X l , , X L ), X l {a1, a2 , •输出的码序列（码字）为:
, ai ,
, an}
P93 例5-3

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

10 11 000 001 010 0110 0111
2 2 3 3 3 4 4
K ki p( xi ) 2 0.2 2 0.19 3 0.18 3 0.17 3 0.15 4 0.1 4 0.01
i
2.72 H ( X ) H ( X ) 2.609 95.9% R 2.72 K
编码
码字 0 10 110
ki
1 2 3 4 5 6 7 7
0 0 1 0 1 1 0 1
1110 11110 111110 1111110 1111111
(3) 香农编码效率：
1 1 1 1 1 1 1 1 K k i p( xi ) 1 2 3 4 5 6 7 7 2 4 8 16 32 64 128 128 i 1.984
xi x1 x2 x3 x4 x5 x6 x7 x8
(5)
ki
1 1 2 2 3 3 4 4
1 1 1 1 1 1 1 1 K k i p( xi ) 1 1 2 2 3 3 4 4 2 4 8 16 32 64 128 128 i 1.328

(4)
H ( X ) H ( X ) 1.984 100% R 1.984 K
p(xi)
0.5 0.25 0.125 0.0625 0.03125 0.015625 0.0078125 0.0078125 2 2 0 1 0 1 0 1 2 0 1 编码码字 0 1 20 21 220 221 225 x6 x7
(3)
p(xi)
0.2 0.19 0.18 0.17 0.15 0.1 0.01
pa(xi)
0 0.2 0.39 0.57 0.74 0.89 0.99
ki
3 3 3 3 3 4 7
码字 000 001 011 100 101 1110 1111110
(2) 二进制香农码：
xi x1 x2 x3 x4 x5 x6 x7 x8
p(xi)
0.5 0.25 0.125 0.0625 0.03125 0.015625 0.0078125 0.0078125
pa(xi)
0 0.5 0.75 0.875 0.9375 0.96875 0.984375 0.9921875
解：
xi x1 x2 x3 x4 x5 x6 x7
p(xi)
0.2 0.19 0.18 0.17 0.15 0.1 0.01 1 0 0 1 0
编码 0 1 0 1 1 0 1
码字 00 010 011 10 110 1110 1111
ki
2 3 3 2 3 4 4
K ki p( xi ) 2 0.2 3 0.19 3 0.18 2 0.17 3 0.15 4 0.1 4 0.01
ki
1 2 3 4 5 6 7 7
码字 0 10 110 1110 11110 111110 1111110 1111111
二进制费诺码：
xi x1 x2 x3 x4 x5 x6 x7 x8
p(xi)
0.5 0.25 0.125 0.0625 0.03125 0.015625 0.0078125 0.0078125 1 1 1 0 0 0
00000001 00000000
7 8
1111 0
5.6 有二元平稳马氏链，已知 p(0/0) = 0.8，p(1/1) = 0.7，求它的符号熵。用三个符号合成一个来编写二进制哈夫曼码，求新符号的平均码字长度和编码效率。 5.7 对题 5.6 的信源进行游程编码。若“0”游程长度的截至值为 16， “1”游程长度的截至值为 8，求编码效率。 5.8 选择帧长 N = 64 (1) 对 0010000000000000000000000000000001000000000000000000000000000000 遍 L-D 码； (2) 对 1000010000101100000000010010000101001000000001110000010000000010 遍 L-D 码再译码； (3) 对 0000000000000000000000000000000000000000000000000000000000000000 遍 L-D 码； (4) 对 10100011010111000110001110100110000111101100101000110101011010010 遍 L-D 码； (5) 对上述结果进行讨论。
K2 ，并计算编码效率； K1
(5) 若用 4 位信源符号合起来编成二进制哈夫曼码，求它的平均码长 K ，并计算编码效率。序列 1 01 001 0001 00001 000001 0000001 数字 0 1 3 3 4 5 6 二元码字 1000 1001 1010 1011 1100 1101 1110
x3 x4 x5 x6 x7 X x1 x2 5.1 设信源 P( X ) 0.2 0.19 0.18 0.17 0.15 0.1 0.01
(1) 求信源熵 H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率。
解： (1)
H ( X ) p( xi ) log 2 p( xi )
K k i p( xi ) 3 0.2 3 0.19 3 0.18 3 0.17 3 0.15 4 0.1 7 0.01
i
3.14 H ( X ) H ( X ) 2.609 83.1% R 3.14 K
x3 x4 x5 x6 x7 X x1 x2 5.2 对信源编二进制费诺码，计算编码效率。 P( X ) 0.2 0.19 0.18 0.17 0.15 0.1 0.01
各自的平均码长和编码效率。
解：二进制哈夫曼码：
xi s6 s5 s4 s3 s2 x1 x2 x3 x4 x5 s1 x6 x7
p(xi)
编码 1 0.61 0.39 0.35 0.26 0 1 0 1 0 1 0 0.11 1 0 1 0 1
码字
ki
0.2 0.19 0.18 0.17 0.15 0.1 0.01
(1) (2) (3) (4) (5)
解： (1)
求信源熵 H(X)；编二进制香农码和二进制费诺码；计算二进制香农码和二进制费诺码的平均码长和编码效率；编三进制费诺码；计算三进制费诺码的平均码长和编码效率；
H ( X ) p( xi ) log 2 p( xi )
i 1
8
1 1 1 1 1 1 1 1 log 2 2 log 2 4 log 2 8 log 2 16 log 2 32 log 2 64 log 2 128 log 2 4 8 16 32 64 128 128 1.984 bit / symbol

H ( X ) H ( X ) 1.984 100% R 1.984 K
费诺编码效率：
1 1 1 1 1 1 1 1 K k i p( xi ) 1 2 3 4 5 6 7 7 2 4 8 16 32 64 128 128 i 1.984

H(X ) H(X ) 1.984 94.3% R K log 2 m 1.328 log 2 3
1 X 0 P( X ) 0.9 0.1
5.5 设无记忆二进制信源
先把信源序列编成数字 0，1，2，……，8，再替换成二进制变长码字，如下表所示。 (1) 验证码字的可分离性； (2) 求对应于一个数字的信源序列的平均长度 K1 ； (3) 求对应于一个码字的信源序列的平均长度 K 2 ； (4) 计算
i 1
7
(0.2 log 2 0.2 0.19 log 2 0.19 0.18 log 2 0.18 0.17 log 2 0.17 0.15 log 2 0.15 0.1 log 2 0.1 0.01 log 2 0.01) 2.609 bit / symbol
i
2.74 H ( X ) H ( X ) 2.609 95.2% R 2.74 K
x3 x4 x5 x6 x7 X x1 x2 5.3 对信源编二进制和三进制哈夫曼码，计算 P( X ) 0.2 0.19 0.18 0.17 0.15 0.1 0.01
三进制哈夫曼码：
xi s3 s2 s1 x1 x2 x3 x4 x5 x6 x7
p(xi)
编码 1 0.54 0.26 0 1 2 0 1 2 0 1 2
码字
ki
0.2 0.19 0.18 0.17 0.15 0.1 0.01
2 00 01 02 10 11 12
1 2 2 2 2 2 2
K ki p( xi ) 1 0.2 2 (0.19 0.18 0.17 0.15 0.1 0.01)
i
1.8

H (X ) H(X ) 2.609 91.4% R 1.8 log 2 3 K log 2 m L
x7 x8 x x x x x x X 1 2 3 4 5 6 5.4 设信源 1 1 1 1 1 1 1 1 P( X ) 2 4 8 16 32 64 128 128

第五章信源编码-习题答案

合集下载

第五章信源编码习题课 PPT课件

信息论第五章答案

最新信息论与编码第五章答案

第5章无失真信源编码定理

信道编码习题解答

信息论与编码第五章答案

信息论第五章答案

第五章信源编码

信息论与编码第5章习题解答

第五章信源编码

第四章第5 章习题答案

信息理论与编码课后答案第5章

信息论与编码zjh201209zjh第五章习题

第五章习题参考解答

第五章信源编码(完结)

文档推荐

最新文档

第五章 信源编码-习题答案

合集下载

第五章 信源编码习题课 PPT课件

信息论第五章答案

最新信息论与编码第五章答案

第5章 无失真信源编码定理

信道编码习题解答

信息论与编码第五章答案

信息论第五章答案

第五章信源编码

信息论与编码第5章习题解答

第五章信源编码

第四章第5 章习题答案

信息理论与编码课后答案第5章

信息论与编码zjh201209zjh第五章习题

第五章习题参考解答

第五章 信源编码(完结)

文档推荐

最新文档

第五章信源编码-习题答案

第五章信源编码习题课 PPT课件

第5章无失真信源编码定理

第五章信源编码(完结)