信息论基础理论与应用第三版傅祖芸第5章讲义

信息理论基础第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时的平均码长和 编码效率。