一、实验概述1.1 实验目的掌握离散无记忆信源熵、平均码长、编码效率、码长方差的理论计算公式熟练掌握香农-范诺Shannon-Fano编码、哈夫曼Huffman编码的完整构造步骤通过两组典型信源均匀等概率信源、非均匀概率信源手工推演两种编码从平均码长、编码效率、码长方差三个维度对比两种前缀码的压缩性能分析哈夫曼编码性能优于香农-范诺编码的底层原理解释工程压缩算法普遍选用哈夫曼编码的原因。1.2 核心理论公式1信源熵无损压缩理论下界H(X) -求和i从1到n[ p_i × log₂(p_i) ]单位bit/符号p_i第i个信源符号的出现概率。2平均码长L平均 求和i从1到n[ p_i × l_i ]l_i符号x_i对应的码字二进制长度。3编码效率衡量压缩性能越接近100%越好η [ H(X) ÷ L平均 ] × 100%4码长方差衡量码字长度均匀程度方差越小硬件实现越友好σ² 求和i从1到n[ p_i × (l_i - L平均)² ]1.3 两种编码构造规则1.3.1 香农-范诺编码步骤将全部信源符号按照概率从大到小降序排序将符号集合划分为概率总和尽可能接近相等的上下两组上一组所有符号码字首位填0下一组填1对划分后的两组递归执行分组操作直至每组仅剩余单个符号停止递归。1.3.2 哈夫曼编码步骤符号按概率降序排列选取概率最小的两个符号合并为一个新父节点父节点概率为两子节点概率之和两条分支分别标记0、1将新节点放回符号序列重新排序重复合并操作直到仅剩唯一根节点从根节点向叶子节点反向读取路径0/1序列得到每个符号的唯一前缀码字。二、两组信源编码手工推演实验2.1 实验一4符号均匀等概率信源信源符号集合 X{x₁,x₂,x₃,x₄}概率分布 P{0.25,0.25,0.25,0.25}2.1.1 计算信源熵H(X) -4 × 0.25 × log₂0.25 2 bit/符号2.1.2 香农-范诺编码推演排序x₁(0.25),x₂(0.25),x₃(0.25),x₄(0.25)第一次分组{x₁,x₂}总概率0.5码前缀0、{x₃,x₄}总概率0.5码前缀1二次分组后码字x₁:00x₂:01x₃:10x₄:11全部码长l_i2平均码长L平均(SF)0.25 × (2222)2编码效率η(SF)(2÷2)×100%100%码长方差所有码长相等σ²(SF)02.1.3 哈夫曼编码推演多次合并最小概率节点后最终所有符号码字长度均为2。平均码长 L平均(Huff)2编码效率100%码长方差σ²(Huff)0。2.1.4 本组实验小结均匀等概率信源下香农-范诺编码与哈夫曼编码性能完全一致均达到无损压缩理论极限。