位与编码.pdf

第 2 章 编码 上一章中我们研究了信息的基本单元——位，及其多种抽象表示：数学位，标准位和量 子位。 如果一个问题确实有两个可能的答案，那么单个位是有用的。这方面的例子有掷硬币的 结果（正面或反面）、人的性别（男性或女性）、审判结果（有罪或无罪）和一个论断的真实 性（真的或假的）。生活中大多数情形更加复杂。本章涉及的表示复杂事物的方法，这些事 物不是由单个位，而是由多个位表示。 集中精力研究一个系统的简化模型是很容易的，系统中的输入是一组预定事物或“抽象 实体”中的一个，所选特定抽象实体的含义用一列位被编码；这些位通过空间或时间传输， 一段时间之后或在另外一个地方被解码，这样就确定了最初选择的抽象实体。后面的几章中 我们要建立这个模型来论述鲁棒性和效率问题。 输入 编 通 解 输出 码 码 路 器 （符号） 器 （多个位） （多个位） （符号） 图 2.1：广义通信系统 本章中我们将从几个方面研究编码设计，并从这些方面讨论几个例子，看看它们是否已 经足够好了。几个笔记描述了说明什么是重点的编码： z 字母：BCD，EBCDIC，ASCII，Unicode，莫尔斯编码 z 整数：二进制，灰色，2 的反码 z 数字：浮点 z 蛋白质：遗传代码 z 电话：北美编码计划（NANP），国际编码 z 主机：以太网，IP 地址，域名 z 图像：TIFF，GIF 和 JPEG z 音频：MP3 z 视频：MPEG 2.1 抽象实体空间尺寸 决定编码的抽象实体数目有几点很重要的考虑因素。编码中的抽象实体数目称为抽象实体空 间尺寸。我们考虑几种不同的抽象实体空间尺寸： z 2 z 2 的整数幂 z 有限的 z 无限的，可数 z 无限的，不可数 如果抽象实体个数是 2 个，那么可以选择编码为单个位。如果抽象实体的可能个数位 4，8， 16，32，64 或是其他的 2 的整数幂，那么可以选择编码为抽象实体空间尺寸的对数，以 2 为底。 所以两位可以指定一副拍的花色（梅花，方块，红桃或黑桃），五位可以把 32 个学生的班级中每 个学生编码。dreidel 是一种四边刻有希伯来字母的玩具。在孩子游戏时特别是光明节里，它可以 像一个陀螺似的旋转。每次旋转的结果可以编码为 2 位。 作者：Paul Penfield, Jr. 版本 1.0.2，2003 年 1 月 30 日。版权?2003 麻省理工学院 如果抽象实体个数是有限的，但不是 2 的整数幂，则可以选择 2 的下一个更高的整数幂 作为位的个数，还有几种位数编码方法不怎么使用。这样的例子有 10 位数字，六面体的 6 个面，一副拍的 13 中命名和英文 26 个字母。其中，每种情形都有剩余容量（4 位表示的数 字有 6 个未用到的模式，3 位表示的六面体有 2 个未用到的模式等等）。在下一节中，如何 处理这个空间剩余是一个重要的主题。 如果抽象实体个数有限，但可数（可以和整数形成一一对应的关系），那么一个既定长 度的位串可以唯一地表示这个有限集中有限个数的项目。所以一个正整数的 4 位编码可以