3.2不等长编码.pdf

等长编码 消息集 码字集 {uL } {}v N 无失真 D N ≥ K L N log D ≥ L log K 几乎无失真 N log D LH (U ) R H (U ) N log D 典型序列R = L Morse电码 A ·– J ·––– S ··· B –··· K –·– T – C –·–· L ·–·· U ··– D –·· M –– V ···– E · N –· W ·–– F ··–· O ––– X –··– G ––· P ·– –· Y –·–– H ···· Q ––·– Z ––·· I ·· R ·–· 特点：经常出现的字母变换为较短序列， 不经常出现的字母变换为较长序列。 平均码长 设信源随机变量U的概率分布为 ?U ? ?a1 , a 2 , , a K ? ? ? = ? ? ?P ? ?P(a1 ), P(a 2 ), , P(a K )? 若事件ak对应的码字长度为nk，则平均码字长度为 K n = ∑ n k p (a k ) k =1 希望n 小。 解决方案：概率大的事件用短码字。 不等长码实例 事件 概率 码A 码B 码C 码D a1 0.5 0 0 0 0 a2 0.25 0 1 10 01 a3 0.125 1 00 110 011 a4 0.125 10 11 111 0111 奇异码：码A 非奇异码 非奇异的必要条件：D元编码中，长度为 m的码字数不超过Dm个 3.3 离散无记忆信源的不等长编码 例 扩展编码 U a1 a2 a3 C 0 1 00 2 U a1a1 a1a2 a1a3 a2a1 a2a2 a2a3 a3a1 a3a2 a3a3 C2 00 01 000 10 11 100 000 001 0000 3.3 离散无记忆信源的不等长编码 定义 一个编码的扩展编码非奇异，则该码称为唯一可译 码。 如图的非唯一可译编码，3次扩展编码奇异。 U a1 a2 a3 C 0 1 01 3.3 离散无记忆信源的不等长编码 定义3.3.2 若 ①事件与码字一一对应； ②每个码字的开头部分都是一个相同的字母串； 称此码为逗点码。 逗点码显然是唯一可译的，识别码字的方法 为： 见到逗号就识别为一个码字的开始。 等长码是唯一可译的。 定义3.3.4 若 ①事件与码字一一对应； ②每个码字都不是另一个码字的字头(前缀)。 则称此码为异字头码。 异字头码也是唯一可译的，识别码字的方法为： 见到一个码字就识别为一个码字。 判断码的唯一可译性的方法：Sardinas- Patterson测试 可将码作所示的分类 不等长码实例 事件 概率 码A 码B 码C 码D a1 0.5 0 0 0 0 a2 0.25 0 1 10 01 a3 0.125 1 00 110 011