信息论第5章

5.1某离散无记忆信源的概率空间为采用香农码和费诺码对该信源进行二进制变长编码，写出编码输出码字，并且求出平均码长和编码效率。

解：计算相应的自信息量1)()(11=-=a lbp a I 比特 2)()(22=-=a lbp a I 比特 3)()(313=-=a lbp a I 比特 4)()(44=-=a lbp a I 比特 5)()(55=-=a lbp a I 比特 6)()(66=-=a lbp a I 比特 7)()(77=-=a lbp a I 比特 7)()(77=-=a lbp a I 比特根据香农码编码方法确定码长1)()(+<≤i i i a I l a I平均码长984375.164/6317128/17128/1664/1532/1416/138/124/112/1L 1=+=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯=由于每个符号的码长等于自信息量，所以编码效率为1。

费罗马编码过程5.2某离散无记忆信源的概率空间为使用费罗码对该信源的扩展信源进行二进制变长编码，(1) 扩展信源长度，写出编码码字，计算平均码长和编码效率。

(2) 扩展信源长度，写出编码码字，计算平均码长和编码效率。

(3) 扩展信源长度，写出编码码字，计算平均码长和编码效率，并且与(1)的结果进行比较。

解：信息熵811.025.025.075.075.0)(=--=lb lb X H 比特/符号 （1）平均码长11=L 比特/符号编码效率为%1.81X)（H 11==L η（2）平均码长为84375.0）3161316321631169（212=⨯+⨯+⨯+⨯=L 比特/符号 编码效率%9684375.0811.0X)（H 22===L η（3）当N=4时，序列码长309.3725617256362563352569442569242562732562732256814=⨯+⨯+⨯⨯+⨯⨯+⨯⨯+⨯+⨯⨯+⨯=L平均码长827.04309.34==L %1.98827.0811.0X)（H 43===L η可见，随着信源扩展长度的增加，平均码长逐渐逼近熵，编码效率也逐渐提高。

5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码12345C C C C C 、、、、和6C 。

（1） 求这些码中哪些是唯一可译码； （2） 求哪些是非延长码（即时码）；（3） 对所有唯一可译码求出其平均码长。

解：（1(2)1,3,6是即时码。

5-2证明若存在一个码长为12,,,q l l l ⋅⋅⋅的唯一可译码，则一定存在具有相同码长的即时码。

证明：由定理可知若存在一个码长为Lq L L ,,2,1 的唯一可译码，则必定满足kraft 不等式∑=-qi l ir1≤1。

由定理44⋅可知若码长满足kraft 不等式，则一定存在这样码长的即时码。

所以若存在码长Lq L L ,,2,1 的唯一可译码，则一定存在具有相同码长P （y=0）的即时码。

5-3设信源126126()s s s S p p p P s ⋅⋅⋅⎡⎤⎡⎤=⎢⎥⎢⎥⋅⋅⋅⎣⎦⎣⎦，611i i p ==∑。

将此信源编码成为r 元唯一可译变长码（即码符号集12{,,,}r X x x x =⋅⋅⋅），其对应的码长为（126,,,l l l ⋅⋅⋅）=（1，1，2，3，2，3），求r 值的最小下限。

解：要将此信源编码成为 r 元唯一可译变长码，其码字对应的码长（l 1 ,l 2 ,l 3, l 4,l 5, l 6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即132321161≤+++++=------=-∑r r r r r r ri li所以要满足122232≤++r r r ，其中 r 是大于或等于1的正整数。

可见，当r=1时，不能满足Kraft 不等式。

当r=2, 1824222>++，不能满足Kraft 。

当r=3,127262729232<=++，满足Kraft 。

所以，求得r 的最大值下限值等于3。

5-4设某城市有805门公务和60000门居民。

作为系统工程师，你需要为这些用户分配。

信息理论基础第13讲北京航空航天大学201教研室陈杰21.编码器—信源符号集S =(s 1,s 2, …s q )—码符号集X =(x 1,x 2…x r )—代码组(Source Code ) C =(W 1, W 2,…W q )—码字(Codeword ) W i =(x l1,x l2,…x li )2. 分组码—奇异性(Non-singular )—唯一可译性(Uniquely decodable )—即时码(Instantaneous )All codesNon-singular codesUniquely decodable codesInstantaneous codesFigure 5.1. Classes of codes343. 定长编码3.1 唯一可译定长码编码速率编码效率log log L ql N r=≥log 1log q r +>log log L r R qN=≥()()log H S H S R qη=≤例:英文字符数q =27,且log 2q=4.754 bit 信源熵H (S )=4.03 bit ,取编码速率R=log 2q 则编码效率η=85%53. 定长编码3.2 定长码编码定理(1)正定理：(2)逆定理：log ()L rR H S Nε=≥+2[()]i E D I s p N ε≤log ()2L rR H S Nε=≤−12N E p ε−≥−0E p →1E p →63. 定长编码3.2 定长码编码定理根据正定理，令p E <δlog ()L rR H S Nε=≥+2[()]i E D I s p N δε≤<2[()]i D I s N εδ≥()H S Rη=()()H s H s ε≤+[]222()()(1)i D I s N H S ηηδ≥⋅−1()H s ηεη−=75.4 变长码•引入1. 变长码无需很长的码长就能实现高效率的无失真信源编码2.变长码必须是唯一可译码，才能实现无失真编码3.变长码是唯一可译码的充要条件：(1)非奇异码(2)任意有限次扩展码是非奇异码4. 变长码必须即时码85.4.1码的分类和主要编码方法信源编码方法：⑴匹配编码：概率大的信源符号，代码长度短；反之，代码长度长⑵变换编码：从一种空间变换成另一种空间，然后进行编码⑶识别编码：对有标准形状的文字、符号和数据进行编码9定理：设信源符号集为S=(s 1,s 2, …，s q,)，码符号集为X=(x 1,x 2, …x r )，对信源进行编码，代码组C=(W 1,W 2, …W q )，相应码长分别l 1,l 2,…l q ，即时码存在（唯一可译码存在）的充要条件为：11≤∑=−qi l ir10释：(1)克拉夫特(Kraft)不等式为即时码存在充要条件(2)麦克米伦(McMilan )不等式为唯一可译码存在充要条件(3)该定理不能作为判别一种码是否为即时码（唯一可译码）的判据(4)当码字长度和码符号满足该不等式时，必可构造出即时码（唯一可译码）115.4.3 唯一可译码判别准则•唯一可译码：如果一个分组码对于任意有限的整数N ，其N 次扩展码均为非奇异码，则为唯一可译码•唯一可译码的充要条件：（见书上128页）121.码平均长度离散无记忆信源为编码后的码子码字的长度因为是唯一可译码，s i 和W i 一一对应则码字平均长度为[]1212()()()q q s s s S P p s p s p s ⎡⎤=⎢⎥⎣⎦""12,,,qW W W "ql l l ,,,21"()()i i p s p W =11()()q qi i i ii i L p W l p s l ====∑∑13释：(1)是每个信源符号编码需要的平均码符号个数；(2) 编码后，每个信源符号s i 平均用个码符号来表示，平均每个码符号携带的信息量是信道的信息传输率(3) 若传输一个码符号需要t 秒，则每秒传输率为故L L L s H X H R )()(==Ls H R t R t )(1==bit/码符号bit/秒L R t 信息传输率高2.紧致码定义：对于某一个信源和某一码符号集，若有一L个唯一可译码，其平均码长度小于所有其它唯一可译码的平均码长度，则称该码为紧致码（也称最佳码）•释：无失真信源编码核心问题是寻找紧致码14153.定理：（平均码长下界）设离散无记忆信源的信源熵为H (S )，用码符号集进行编码，则存在一种编码方式构成唯一可译码，平均码长满足[]1212()()()q q s s s SP p s p s p s ⎡⎤=⎢⎥⎣⎦""},,,{21q x x x X "=L rS H L r S H log )(1log )(+<≤16释：(1) 的极限值为，即下界；小于下界，则唯一可译码不存在(2) 当选择时，才能达到下界(3) 紧致码平均码长不一定达到下界(4) 达到下界的唯一可译码是紧致码(5) 紧致码最短码长L ()log H S r Llog ()log i i p s l r=−rS H L log )(=174 变长无失真信源编码定理（香农第一定理）定理：设离散无记忆信源其信源熵为H (S )，它的N 次扩展信源为[]1212()()()q q s s s SP p s p s p s ⎡⎤=⎢⎥⎣⎦""1212()()()N N qN q S P p p p αααααα⎡⎤⎡⎤=⎢⎥⎣⎦⎢⎥⎣⎦""18扩展信源熵为H (S N )，码符号集X =(x 1,x 2, …x r )，用X 对S N 编码，则总可以找到一种编码方法，构成唯一可译码，使信源S 中的每个信源符号所需要的码字平均长度满足或rS H N L N r S H N log )(1log )(≥>+)(1)(S H NL N S H r N r ≥>+19当时，则其中，是扩展信源中每个信源符号对应的平均码长式中，是对应的码字长度∞→N )(lim S H N L r N N =∞→rS H N L N N log )(lim =∞→N L i α1()Nq N i ii L p αλ==∑i λi α20释：对于平稳遍历的离散有记忆信源（如马尔可夫信源），有其中，为有记忆信源的极限熵N L N L 原始信源平均码长N次扩展信源编码后每原始信源符号的平均码长≥rH N L N N log lim ∞∞→=∞H5.4.4变长信源编码定理5.编码速率、编码效率、剩余度(1) 编码速率：变长编码的编码速率为 LN R= log r N (2) 编码效率：编码效率定义为H ( S ) NH r ( S ) NH ( S ) = = η= R LN LN log r(3) 剩余度：定长码的剩余度为NH r ( S ) γ = 1 −η = 1 − LN21例题 例5.2 设离散无记忆信源Ss2 ⎤ ⎡S ⎤ ⎡ s1 ⎢ P( S ) ⎥ = ⎢0.75 0.25⎥ ⎣ ⎦ ⎣ ⎦ 对信源S及其扩展信源进行二元变长编码， 求当信源扩展次数N＝2,3,4时的平均码长和 编码效率。

信息理论基础第13讲北京航空航天大学201教研室陈杰21.编码器—信源符号集S =(s 1,s 2, …s q )—码符号集X =(x 1,x 2…x r )—代码组(Source Code ) C =(W 1, W 2,…W q )—码字(Codeword ) W i =(x l1,x l2,…x li )2. 分组码—奇异性(Non-singular )—唯一可译性(Uniquely decodable )—即时码(Instantaneous )All codesNon-singular codesUniquely decodable codesInstantaneous codesFigure 5.1. Classes of codes343. 定长编码3.1 唯一可译定长码编码速率编码效率log log L ql N r=≥log 1log q r +>log log L r R qN=≥()()log H S H S R qη=≤例:英文字符数q =27,且log 2q=4.754 bit 信源熵H (S )=4.03 bit ,取编码速率R=log 2q 则编码效率η=85%53. 定长编码3.2 定长码编码定理(1)正定理：(2)逆定理：log ()L rR H S Nε=≥+2[()]i E D I s p N ε≤log ()2L rR H S Nε=≤−12N E p ε−≥−0E p →1E p →63. 定长编码3.2 定长码编码定理根据正定理，令p E <δlog ()L rR H S Nε=≥+2[()]i E D I s p N δε≤<2[()]i D I s N εδ≥()H S Rη=()()H s H s ε≤+[]222()()(1)i D I s N H S ηηδ≥⋅−1()H s ηεη−=75.4 变长码•引入1. 变长码无需很长的码长就能实现高效率的无失真信源编码2.变长码必须是唯一可译码，才能实现无失真编码3.变长码是唯一可译码的充要条件：(1)非奇异码(2)任意有限次扩展码是非奇异码4. 变长码必须即时码85.4.1码的分类和主要编码方法信源编码方法：⑴匹配编码：概率大的信源符号，代码长度短；反之，代码长度长⑵变换编码：从一种空间变换成另一种空间，然后进行编码⑶识别编码：对有标准形状的文字、符号和数据进行编码9定理：设信源符号集为S=(s 1,s 2, …，s q,)，码符号集为X=(x 1,x 2, …x r )，对信源进行编码，代码组C=(W 1,W 2, …W q )，相应码长分别l 1,l 2,…l q ，即时码存在（唯一可译码存在）的充要条件为：11≤∑=−qi l ir10释：(1)克拉夫特(Kraft)不等式为即时码存在充要条件(2)麦克米伦(McMilan )不等式为唯一可译码存在充要条件(3)该定理不能作为判别一种码是否为即时码（唯一可译码）的判据(4)当码字长度和码符号满足该不等式时，必可构造出即时码（唯一可译码）115.4.3 唯一可译码判别准则•唯一可译码：如果一个分组码对于任意有限的整数N ，其N 次扩展码均为非奇异码，则为唯一可译码•唯一可译码的充要条件：（见书上128页）121.码平均长度离散无记忆信源为编码后的码子码字的长度因为是唯一可译码，s i 和W i 一一对应则码字平均长度为[]1212()()()q q s s s S P p s p s p s ⎡⎤=⎢⎥⎣⎦""12,,,qW W W "ql l l ,,,21"()()i i p s p W =11()()q qi i i ii i L p W l p s l ====∑∑13释：(1)是每个信源符号编码需要的平均码符号个数；(2) 编码后，每个信源符号s i 平均用个码符号来表示，平均每个码符号携带的信息量是信道的信息传输率(3) 若传输一个码符号需要t 秒，则每秒传输率为故L L L s H X H R )()(==Ls H R t R t )(1==bit/码符号bit/秒L R t 信息传输率高2.紧致码定义：对于某一个信源和某一码符号集，若有一L个唯一可译码，其平均码长度小于所有其它唯一可译码的平均码长度，则称该码为紧致码（也称最佳码）•释：无失真信源编码核心问题是寻找紧致码14153.定理：（平均码长下界）设离散无记忆信源的信源熵为H (S )，用码符号集进行编码，则存在一种编码方式构成唯一可译码，平均码长满足[]1212()()()q q s s s SP p s p s p s ⎡⎤=⎢⎥⎣⎦""},,,{21q x x x X "=L rS H L r S H log )(1log )(+<≤16释：(1) 的极限值为，即下界；小于下界，则唯一可译码不存在(2) 当选择时，才能达到下界(3) 紧致码平均码长不一定达到下界(4) 达到下界的唯一可译码是紧致码(5) 紧致码最短码长L ()log H S r Llog ()log i i p s l r=−rS H L log )(=174 变长无失真信源编码定理（香农第一定理）定理：设离散无记忆信源其信源熵为H (S )，它的N 次扩展信源为[]1212()()()q q s s s SP p s p s p s ⎡⎤=⎢⎥⎣⎦""1212()()()N N qN q S P p p p αααααα⎡⎤⎡⎤=⎢⎥⎣⎦⎢⎥⎣⎦""18扩展信源熵为H (S N )，码符号集X =(x 1,x 2, …x r )，用X 对S N 编码，则总可以找到一种编码方法，构成唯一可译码，使信源S 中的每个信源符号所需要的码字平均长度满足或rS H N L N r S H N log )(1log )(≥>+)(1)(S H NL N S H r N r ≥>+19当时，则其中，是扩展信源中每个信源符号对应的平均码长式中，是对应的码字长度∞→N )(lim S H N L r N N =∞→rS H N L N N log )(lim =∞→N L i α1()Nq N i ii L p αλ==∑i λi α20释：对于平稳遍历的离散有记忆信源（如马尔可夫信源），有其中，为有记忆信源的极限熵N L N L 原始信源平均码长N次扩展信源编码后每原始信源符号的平均码长≥rH N L N N log lim ∞∞→=∞H5.4.4变长信源编码定理5.编码速率、编码效率、剩余度(1) 编码速率：变长编码的编码速率为 LN R= log r N (2) 编码效率：编码效率定义为H ( S ) NH r ( S ) NH ( S ) = = η= R LN LN log r(3) 剩余度：定长码的剩余度为NH r ( S ) γ = 1 −η = 1 − LN21例题 例5.2 设离散无记忆信源Ss2 ⎤ ⎡S ⎤ ⎡ s1 ⎢ P( S ) ⎥ = ⎢0.75 0.25⎥ ⎣ ⎦ ⎣ ⎦ 对信源S及其扩展信源进行二元变长编码， 求当信源扩展次数N＝2,3,4时的平均码长和 编码效率。

5.1 设信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡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 η5.2 对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡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 η5.3 对信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡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 LK X H R X H x p k K ii i η5.4 设信源⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=⎥⎦⎤⎢⎣⎡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 η(5)%3.943log 328.1984.1log )()(328.14128141281364133212161281141121)(22=⨯=⋅===⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯==∑m K X H R X H x p k K ii i η5.5 设无记忆二进制信源⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡1.09.010)(X P X先把信源序列编成数字0，1，2，……，8，再替换成二进制变长码字，如下表所示。