编码理论：轻松有趣的入门

# 编码理论：趣味入门篇 #SoME5 来源：https://paramrathour.github.io/blog/coding-theory/ > 本文专为对编码理论毫无概念的朋友设计。如想跳过基础部分，请参阅简介 (https://paramrathour.github.io/blog/coding-theory/#introduction)。切换至浅色模式并使用更大屏幕可获得更佳阅读体验。 ### 一个难题 https://paramrathour.github.io/blog/coding-theory/#a-problem 想象你是个20世纪初的小娃娃；深夜想和对面邻居的好友说话。既不想吵到别人（或许想说悄悄话），于是尝试小声说话，但距离太远听不清。幸好，你们都能从卧室窗户看到对方。问题在于：如何沟通？每人手电筒 🔦 一只。请思考！ ## 通讯编码 https://paramrathour.github.io/blog/coding-theory/#codes-for-communication ### 尝试一：涂鸦式 https://paramrathour.github.io/blog/coding-theory/#attempt-1-drawing 当然，你打开手电筒开始"画"字母：用一次竖直照射构成 \(\\textrm\{I\}\)，朋友看到线条就明白了。接着画 \(\\textrm\{L\}\)——一竖加底部横线，但意识到朋友会看到 \(\\textrm\{L\}\) 形状，于是重新画出标准的 \(\\textrm\{L\}\)。然后画椭圆 \(\\textrm\{O\}\) 却担心被误认为数字 \(\\textrm\{0\}\)，发送 \(\\textrm\{V\}\) 时用两道简单光线，当发送 \(\\textrm\{E\}\) 时发现更大问题：多笔画符号实在难辨，毕竟旧笔画不会在空中留存到字母完成。因此需要更*精确*的方法。 ### 尝试二：闪烁式 https://paramrathour.github.io/blog/coding-theory/#attempt-2-blinking 此前手电筒一直亮着，你突然发现开始后从未关过——灵光一现：试试闪烁（开关手电筒）？简化起见，你*规定* \(\\textrm\{A\}\) 代表 \(1\) 次闪烁，\(\\textrm\{B\}\) 代表 \(2\) 次，依此类推 \(\\textrm\{Z\}\) 代表 \(26\) 次。这能用！发送 \(\\textrm\{I LOVE\}\) 时，先闪 \(9\) 次，停顿后依次闪 \(12, 15, 22, 5\) 次。朋友统计闪烁次数（\(\\#\)闪烁数）即可推断字母。当然，闪烁间需足够停顿，否则 \(\\textrm\{I L\}\) 可能被误读为 \(9+12=21\) 次闪烁的 \(\\textrm\{U\}\)。此外，\(\\textrm\{I\}\) 与 \(\\textrm\{L\}\)、\(\\textrm\{L\}\) 与 \(\\textrm\{O\}\) 间的停顿应不同，前者分隔单词，后者分隔字母。此刻 \(\\textrm\{I LOVE\}\) 对应 \(9+12+15+22+5=63\) 次闪烁，成功传递信息！我们还能优化，但先庆祝你刚发现了编码理论 🎊 ### 引言 https://paramrathour.github.io/blog/coding-theory/#introduction 你开发的是一套*编码*，即传输*信息*的系统（此处指人际通信）。该编码将*消息*（待发送内容）转换为*编码消息*（实际发送内容）。消息由*符号*（此处为字母）构成，编码消息则由*码字*（此处为闪烁次数）组成。将字母转为闪烁次数的过程称为*编码*，朋友将闪烁次数还原为字母的过程称为*解码*。*编码理论*正是研究此类编码的学科。 > 注意别与同名流行术语"编程"混淆，后者指编写计算机程序（即计算机指令）。现在回到问题本身。 ### 尝试三：频率分析法 https://paramrathour.github.io/blog/coding-theory/#attempt-3-frequency-analysis 此发现太棒了，于是你想发送 \(\\textrm\{I LOVE CODING THEORY\}\)，猜猜看？结果显示需要 \(206\) 次闪烁，太长了 :( 但此时迎来首个突破：无需将 \(\\textrm\{A-Z\}\) 按顺序映射为 \(\\textrm\{1-26\}\)。凭借玩Scrabble的未来经验，你知道英语中字母 \(\\textrm\{E\}\) 出现最频繁，何不分配给它 \(1\) 次闪烁（而非 \(5\) 次）？继续将次高频字母 \(\\textrm\{T\}\) 设为 \(2\) 次，第三高频 \(\\textrm\{A\}\) 设为 \(3\) 次，直至最低频的 \(\\textrm\{Q\}\) 和 \(\\textrm\{Z\}\) 分别为 \(25\) 和 \(26\) 次。这样高频字母用更少闪烁，信息传递更快。下图展示各字母频率。请自行验证：对任意两个字母，将高频字母用更少闪烁表示，能最小化*预期*总闪烁次数。 英文字母频率（按字母顺序） (https://paramrathour.github.io/website-assets/frequency-analysis-letters-english-light.svg) (https://paramrathour.github.io/website-assets/frequency-analysis-letters-english-dark.svg) *英文字母频率分布（百分比）* （图片来自 Nandhp (https://commons.wikimedia.org/wiki/User:Nandhp) 公共领域，Wikimedia Commons） | 字母 | #闪烁数 | 字母 | #闪烁数 | |---|---|---|---| | \(\\textrm\{A\}\) | \(3\) | \(\\textrm\{N\}\) | \(6\) | | \(\\textrm\{B\}\) | \(20\) | \(\\textrm\{O\}\) | \(4\) | | \(\\textrm\{C\}\) | \(12\) | \(\\textrm\{P\}\) | \(19\) | | \(\\textrm\{D\}\) | \(10\) | \(\\textrm\{Q\}\) | \(25\) | | \(\\textrm\{E\}\) | \(1\) | \(\\textrm\{R\}\) | \(9\) | | \(\\textrm\{F\}\) | \(16\) | \(\\textrm\{S\}\) | \(7\) | | \(\\textrm\{G\}\) | \(17\) | \(\\textrm\{T\}\) | \(2\) | | \(\\textrm\{H\}\) | \(8\) | \(\\textrm\{U\}\) | \(13\) | | \(\\textrm\{I\}\) | \(5\) | \(\\textrm\{V\}\) | \(21\) | | \(\\textrm\{J\}\) | \(23\) | \(\\textrm\{W\}\) | \(15\) | | \(\\textrm\{K\}\) | \(22\) | \(\\textrm\{X\}\) | \(24\) | | \(\\textrm\{L\}\) | \(11\) | \(\\textrm\{Y\}\) | \(18\) | | \(\\textrm\{M\}\) | \(14\) | \(\\textrm\{Z\}\) | \(26\) | 利用此表，\(\\textrm\{I LOVE CODING THEORY\}\) 缩短至 \(138\) 次闪烁，减少高达 \(33\%\)！ ### 标点 https://paramrathour.github.io/blog/coding-theory/#punctuation 优化编码前，先探讨重要的标点问题。发送闪烁信号时，为确保准确解码，实际上需要在闪烁间设置三个层级的*停顿*： - 同一字母内闪烁间的停顿 - 不同字母间闪烁间的停顿 - 不同单词间闪烁间的停顿 技术上将这些停顿称为标点，它一直是编码的重要组成部分。 ### 尝试四：摩尔斯电码 https://paramrathour.github.io/blog/coding-theory/#attempt-4-morse-code 让我们将之前的系统形式化。不必反复书写闪烁次数，可用码字代表编码消息：\(\\textrm\{A\}\) 表示 \(\\bullet\)，\(\\textrm\{B\}\) 表示 \(\\bullet\\bullet\)，\(\\textrm\{C\}\) 表示 \(\\bullet\\bullet\\bullet\)，依此类推。这本质上是 \(1\) 进制计数系统——\(\\bullet\) 的数量（码字长度）等于闪烁次数，类似古人用木棍计数羊群。 > 注意：这种方式下，消息和编码消息可用不同符号集表示——消息符号是字母表，编码消息符号是点，特定点的集合构成码字。此处仅使用 \(\\bullet\) 符号，但若改用两个符号呢？那就是 \(2\) 进制！ 使用两个符号（例如 \(\\bullet\) 和 \(-\)，称为*比特*），可能性呈爆炸式增长。原本每个长度仅一个码字，现在长度 \(n\) 可产生 \(2^n\) 个码字。例如长度 \(2\) 时，可能码字为 \(\\bullet\\bullet\)、\(\\bullet-\)、\(-\\bullet\) 和 \(--\)。由于短码字数量大增，*平均*码字长度将缩短，从而可能减少 \(\\#\) 闪烁数。 但符号 \(\\bullet\) 和 \(-\) 代表什么？在摩尔斯电码中，\(\\bullet\) 用短闪（点）表示，\(-\) 用长闪（划）表示，其中划的闪烁时长是点的**三倍**。每个字母可表示为点划组合的码字，如下表所示： | 字母 | 符号 | 字母 | 符号 | |---|---|---|---| | \(\\textrm\{A\}\) | \(\\bullet-\) | \(\\textrm\{N\}\) | \(-\\bullet\) | | \(\\textrm\{B\}\) | \(-\\bullet\\bullet\\bullet\) | \(\\textrm\{O\}\) | \(---\) | | \(\\textrm\{C\}\) | \(-\\bullet-\\bullet\) | \(\\textrm\{P\}\) | \(\\bullet--\\bullet\) | | \(\\textrm\{D\}\) | \(-\\bullet\\bullet\) | \(\\textrm\{Q\}\) | \(--\\bullet-\) | | \(\\textrm\{E\}\) | \(\\bullet\) | \(\\textrm\{R\}\) | \(\\bullet-\\bullet\) | | \(\\textrm\{F\}\) | \(\\bullet\\bullet-\\bullet\) | \(\\textrm\{S\}\) | \(\\bullet\\bullet\\bullet\) | | \(\\textrm\{G\}\) | \(--\\bullet\) | \(\\textrm\{T\}\) | \(-\) | | \(\\textrm\{H\}\) | \(\\bullet\\bullet\\bullet\\bullet\) | \(\\textrm\{U\}\) | \(\\bullet\\bullet-\) | | \(\\textrm\{I\}\) | \(\\bullet\\bullet\) | \(\\textrm\{V\}\) | \(\\bullet\\bullet\\bullet-\) | | \(\\textrm\{J\}\) | \(\\bullet---\) | \(\\textrm\{W\}\) | \(\\bullet--\) | | \(\\textrm\{K\}\) | \(-\\bullet-\) | \(\\textrm\{X\}\) | \(-\\bullet\\bullet-\) | | \(\\textrm\{L\}\) | \(\\bullet-\\bullet\\bullet\) | \(\\textrm\{Y\}\) | \(-\\bullet--\) | | \(\\textrm\{M\}\) | \(--\) | \(\\textrm\{Z\}\) | \(--\\bullet\\bullet\) | 再次注意 \(\\textrm\{E\}\) 仅用单个 \(\\bullet\)，是最短码字；\(\\textrm\{T\}\) 和 \(\\textrm\{A\}\) 也获得较短码字（分别为 \(-\) 和 \(\\bullet-\)），而 \(\\textrm\{Q\}\) 由三划一点构成，成为闪烁次数最多的字母。这表明设计该编码时已考虑某种频率分析。 > 总共有 \(2+2^2+2^3+2^4=30\) 种四字符摩尔斯组合，但英语仅26个字母。这为Ä、Ö、Ü、Ş等带重音字符留出了获得更短码字的空间。与早期编码相比，解码摩尔斯码略有挑战（但不太难 :)）。下图解码树将接收到的码字还原为消息，本质上是前述表格的树状化：从最左侧*根*节点出发，遇点走上方分支，遇划走下方分支；码字结束时所处节点对应的即为消息符号。 摩尔斯电码解码树 (https://paramrathour.github.io/website-assets/morse-code-decoding-light.svg) (https://paramrathour.github.io/website-assets/morse-code-decoding-dark.svg) *摩尔斯电码解码树* 尝试解码以下文本，我添加了长度分别为 \(1\) 点、\(1\) 划和 \(2\) 划的标点 (https://paramrathour.github.io/blog/coding-theory/#punctuation)，以区分符号、字母和单词： $$\\bullet\\bullet\\,\\,\\,\\,\\,\\,\\bullet\-\\bullet\\bullet\\,\\,\\,\-\\,\-\\,\-\\,\\,\\,\\bullet\\bullet\\bullet\-\\,\\,\\,\\bullet\\,\\,\\,\\,\\,\\,\-\\bullet\-\\bullet\\,\\,\\,\-\\,\-\\,\-\\,\\,\\,\-\\bullet\\bullet\\,\\,\\,\\bullet\\bullet\\,\\,\\,\-\\bullet\\,\\,\\,\-\\,\-\\bullet\\,\\,\\,\\,\\,\\,\-\\,\\,\\,\\bullet\\bullet\\bullet\\bullet\\,\\,\\,\\bullet\\,\\,\\,\-\\,\-\\,\-\\,\\,\\,\\bullet\-\\bullet\\,\\,\\,\-\\bullet\-\\,\-$$ 首先是 $\\bullet\\,\\bullet$，代表 \(\\textrm\{I\}\)；接着是分隔单词的标点；然后 $\\bullet\-\\bullet\\,\\bullet$ 是 \(\\textrm\{L\}\)。依此类推，可推断出消息为 \(\\textrm\{I LOVE CODING THEORY\}\)，且已缩短至 \(91\) 次闪烁，再降 \(33\%\)！ #### 摩尔斯码的局限 https://paramrathour.github.io/blog/coding-theory/#issues-with-morse-code 尽管我们认识到标点在系统中的巨大作用，但它也带来一些问题。标点增加了通信延迟，导致发送消息时存在无用时间。若能连续闪烁点划会更高效。这种延迟本质上充当了码字的第三符号（如“空白”）。因此摩尔斯码无法用于现代存储器，后者严格仅支持两种符号（记为 \(0\) 和 \(1\)）。 那么能否去除延迟？方案是否仍可行？ 观察 \(\\textrm\{E\}\)、\(\\textrm\{A\}\)、\(\\textrm\{R\}\) 的码字：\(\\bullet\)、\(\\bullet-\)、\(\\bullet-\\bullet\)。发现规律了吗？每个码字都是下一个的前缀。这意味着若收到 \(\\bullet-\\bullet\)，在没有标点时无法判断它是 \(\\textrm\{R\}\)、还是 \(\\textrm\{EN\}\) 或 \(\\textrm\{AE\}\)。这种码字前缀重叠现象导致唯一解码无法实现。 #### 潜在解决方案 https://paramrathour.github.io/blog/coding-theory/#potential-solutions 有两种去除标点的方案，我们逐一探讨： ##### 尝试五：定长编码 https://paramrathour.github.io/blog/coding-theory/#attempt-5-fixed-length-coding 第一种是采用定长编码方案（如ASCII，美国信息交换标准代码），其中 \(\\textrm\{A\}\) 到 \(\\textrm\{Z\}\) 所有字母均为 \(8\) 比特（亦称*字节*），如下表所示： | 字母 | 符号 | 字母 | 符号 | |---|---|---|---| | \(\\textrm\{A\}\) | \(01000001\) | \(\\textrm\{N\}\) | \(01001110\) | | \(\\textrm\{B\}\) | \(01000010\) | \(\\textrm\{O\}\) | \(01001111\) | | \(\\textrm\{C\}\) | \(01000011\) | \(\\textrm\{P\}\) | \(01010000\) | | \(\\textrm\{D\}\) | \(01000100\) | \(\\textrm\{Q\}\) | \(01010001\) | | \(\\textrm\{E\}\) | \(01000101\) | \(\\textrm\{R\}\) | \(01010010\) | | \(\\textrm\{F\}\) | \(01000110\) | \(\\textrm\{S\}\) | \(01010011\) | | \(\\textrm\{G\}\) | \(01000111\) | \(\\textrm\{T\}\) | \(01010100\) | | \(\\textrm\{H\}\) | \(01001000\) | \(\\textrm\{U\}\) | \(01010101\) | | \(\\textrm\{I\}\) | \(01001001\) | \(\\textrm\{V\}\) | \(01010110\) | | \(\\textrm\{J\}\) | \(01001010\) | \(\\textrm\{W\}\) | \(01010111\) | | \(\\textrm\{K\}\) | \(01001011\) | \(\\textrm\{X\}\) | \(01011000\) | | \(\\textrm\{L\}\) | \(01001100\) | \(\\textrm\{Y\}\) | \(01011001\) | | \(\\textrm\{M\}\) | \(01001101\) | \(\\textrm\{Z\}\) | \(01011010\) | 该方案中，每个字母恰好占 \(8\) 比特，因此解码时无需标点——固定长度让接收方能自动分割比特流。但这也导致高频字母（如 \(\\textrm\{E\}\)）与低频字母（如 \(\\textrm\{Z\}\)）占用相同资源，效率不高。更优方案是采用*变长*编码，为高频字母分配更短码字，同时保证唯一解码性。 ##### 尝试六：前缀码 https://paramrathour.github.io/blog/coding-theory/#attempt-6-prefix-codes 这正是前缀码的核心思想：设计码字集合，使得任意码字都不是其他码字的前缀。例如，若 \(\\textrm\{E\}\) 编码为 \(0\)，则 \(\\textrm\{A\}\) 不能编码为 \(01\)（因 \(0\) 是其前缀），但可编码为 \(10\)。这样，接收方收到比特流时，可从左至右扫描，一旦匹配某个码字就立即解码，无需等待额外符号。 赫夫曼编码便是构建最优前缀码的经典算法，它根据符号出现概率，为高频符号分配短码字，低频符号分配长码字。该算法生成的编码在平均码字长度方面达到理论最优。 ### 总结 https://paramrathour.github.io/blog/coding-theory/#conclusion 从最初的手电筒涂鸦，我们经历了闪烁计数、频率优化、摩尔斯电码，最终抵达现代编码理论的门前。这个旅程揭示了信息传输的核心挑战：如何在有限资源下高效、可靠地传递消息。编码理论不仅是通信的基石，更渗透到数据压缩、错误校验、加密等众多领域。下次当你发送信息时，或许会想到：这背后正进行着一场精妙的编码舞蹈！