最近在看G. Gallager所著的《Principles of Digital Communication》,第一章(数字通信概论)零零散散的讲了很多东西,主要描述了数字通信通信的发展以及现阶段主要采用的方法,标准化接口和分层。信源经过信源编码器转化成二进制序列,二进制序列通过信道编码器映射为信道波形,波形通过信道,再依次经过信道译码器,信源译码器,信号就得到了还原。大体过程是这样,但实际应用中应当速率匹配问题,差错问题等,要复杂得多。

离散信源是三种重要信源中的一种,输出是符号序列。这些符号取值于某个已知的符号集χ,χ可以是字符、汉字、音符等,并且认为符号序列是按照固定的时间节奏从信源输出,因此不引入时间因素。例如对一个文件进行编码,可以离线处理。

对离散信源进行二进制编码,一种最简单的方式是将字符集χ中的每一个符号x映射为一个二进制数组,每个符号的二进制数组等长。这里通信人口中的二进制数组就是我们码农眼中的二进制数位,很容易理解。

另外一种方式是变长编码,也比较直观,即把出现机会高的符号序列映射为较短的二进制序列。可以用p1, l1, p2, l2,做个简单反证,例如p1 > p2, l1 > l2,会发现交换l1, l2会使得结果更好,即p1l1 + p2l2 > p1l2 + p2l1。那么在知道符号序列的情况下,应该如何编码呢?无前缀编码!写过霍夫曼树的应该能想到这一点。

除了上述“技术”性的知识,书中花了很长的篇幅介绍理论和证明定理。如对于无前缀码的克拉夫特不等式,对于给定的字符集和码长集,可以判断是否存在无前缀码,存在无前缀码的情况下还可以进一步判断是否是满的(公式编辑还没有调好,暂时先不写公式了)。数学的东西也真是太多了,离散信源的概率模型和无前缀码的最小平均长,前者用到无记忆信源的独立同分布,后者在求解的时候用到拉格朗日乘法,随后引出香浓熵并展开了超级一大坨定理,当时我就看醉了。

章节的最后,看到一个LZ77算法,可以对通用数据进行压缩。算法设置了一个滑动窗,对于尚未编码的符号,编码器在滑动窗中搜寻最长的匹配序列,然后巧妙地对当前匹配的长度和偏移量进行编码。算法的复杂性和效率随着窗口长度的增大而提高。算法背后的理论是信息论,书中讨论的时候我又看醉了。

好好的一个人,怎么现在成数学渣了呢。