一、什么是DMS信源编码DMS是Discrete Memoryless Source离散无记忆信源的缩写。拆开解释离散信源输出的符号是有限的比如英文字母、汉字、0/1比特无记忆每次输出符号互不影响就像抛硬币这次抛的和下次抛的没关系信源编码把信源符号转换成0/1比特流的过程一句话总结DMS信源编码就是要把一个个独立的符号用最少的比特数表示出来。二、为什么要做信源编码想象你要发一份电报原文AAAAAAAAAB10个字符一种编码每个字母用8比特总共80比特聪明编码9A1B用数字代表重复次数只需要很少的比特信源编码的目的就是去掉冗余压缩数据。三、核心思想用更短的码表示更常见的符号举个生活中的例子假设一个信源只输出A、B、C、D四个字母概率分别是A50%最常见B25%C12.5%D12.5%笨办法等长编码每个字母用2比特A00, B01, C10, D11平均码长 2比特/符号聪明办法变长编码A最常见→ 01比特B → 102比特C → 1103比特D → 1113比特平均码长 0.5×1 0.25×2 0.125×3 0.125×3 1.75比特/符号结果节省了12.5%的比特四、重要概念熵Entropy熵是信源的理论极限表示每个符号最少需要多少比特。公式H -Σ p(i) × log₂ p(i)上面例子的熵H -(0.5×log₂0.5 0.25×log₂0.25 0.125×log₂0.125 0.125×log₂0.125)H -(0.5×(-1) 0.25×(-2) 0.125×(-3) 0.125×(-3))H 0.5 0.5 0.375 0.375 1.75比特发现了吗我们的聪明编码正好达到了熵的极限五、香农第一定理无失真信源编码定理这个定理告诉我们平均码长 ≥ 熵不能比熵更短可以无限接近熵通过更好的编码方法就像熵是行李箱的最小体积编码是怎么把东西装进去理论上可以装到刚好满但永远不能超过六、常见的DMS信源编码方法1. 香农-范诺编码将符号按概率排序分成概率相近的两组分别给0和1递归进行直到每个符号都有唯一编码2. 霍夫曼编码最常用从概率最小的两个符号开始合并它们形成新的节点重复直到只剩一个节点反向得到每个符号的编码霍夫曼编码是最优的能给出最短的平均码长。七、生活中的例子例子1莫尔斯电码E最常见用 .最短Q罕见用 --.-长这就是一种直观的信源编码例子2文件压缩ZIP、RAR都用了类似原理出现多的字符用短编码出现少的用长编码例子3H.264视频编码运动少的画面用短码复杂画面用长码但保证解码后能完全恢复八、Mermaid总结框图九、核心启示信源编码就是数据压缩要去掉冗余熵是理论下限告诉我们最多能压缩多少常见符号用短码罕见符号用长码霍夫曼编码是最优的变长编码方法可以无限接近熵但永远不能低于熵打个比方就像整理行李箱熵告诉你箱子最小能有多小而信源编码就是各种巧妙的叠衣服方法让你尽可能装进更多东西。霍夫曼编码就是那个最聪明的叠衣服高手