本节书摘来自异步社区《计算机科学概论（第12版）》一书中的第1章1.10节通信差错，作者【美】J. 格伦•布鲁克希尔（J. Glenn Brookshear） , 丹尼斯•布里罗（Dennis Brylow）,更多章节内容可以访问云栖社区“异步社区”公众号查看。
*1.10 通信差错
当信息在一台计算机的各个部分之间来回传输，或在月球和地球之间来回传输，又或者只是被保存在存储器中时，最终检索到的位模式有可能和最原始的不一致。灰尘颗粒、磁记录面的油脂或者出了故障的电路，都可能使数据被错误地记录或读取。传输通道上的静电干扰可能会损坏部分数据。在某些技术条件下，普通的背景辐射（background radiation）可以改变存储在机器主存储器中的模式。
为了解决这样的问题，人们开发了许多编码技术来检测甚至校正错误。现在，由于这些技术被大规模地内置于计算机系统的内部构件中，所以计算机的使用者们并不了解它们。不过，它们是很重要的，为科学研究作出了很大的贡献。因此，我们有必要了解其中一些使现在设备可靠的技术。
1.10.1 奇偶校验位
有一种简单的差错检测方法，其依据的原则是：如果被操作的每个位模式都有奇数个1，但却遇到了有偶数个1的模式，那么一定是出错了。要使用这个原则，需要编码系统中的每个模式有奇数个1。这是很容易做到的，首先在已经可用的编码系统中的模式（也许在高位端）上添加一个称为奇偶校验位（parity bit）的附加位。根据不同情况，我们给这个新的位赋值1或0，使整个模式有奇数个1。当我们这样调整了编码系统后，如果出现有偶数个1的模式，就表示出现了错误，被操作的模式是不正确的。
图1-26展示了如何将奇偶校验位加到字母A和F的ASCII码上。注意，A的编码变成了101000001（奇偶校验位为1），F的ASCII码变成了001000110（奇偶校验位为0）。尽管A原始的8位模式有偶数个1，F原始的8位模式有奇数个1，但它们的9位模式都有奇数个1。如果将这种技术应用于所有的8位ASCII模式，我们就能够得到一个9位编码系统，其中任何一个9位模式有偶数个1就表示出错了。
上面描述的奇偶校验系统称为奇校验（odd parity），因为我们设计的系统中每一个正确的模式都有奇数个1。另一种技术称为偶校验（even parity）。在偶校验系统中，每个模式都会被设计成包含偶数个1，因此，如果出现了奇数个1，就表明有错误。
现在，在计算机主存储器中使用奇偶校验位已经不是一件稀奇的事了。尽管我们假设这些计算机存储单元是8位的，但事实上，它们可能是9位，其中一个位被用作奇偶校验位。每次存储器电路收到要存储的8位模式，都会先给其加上一个奇偶校验位，形成9位模式，然后再存储。稍后检索模式时，存储器电路会检查这个9位模式的奇偶性。如果检查没有发现错误，存储器会移除校验位，然后自信地返回余下的8位模式。否则，存储器会返回那8个数据位，并警告返回的模式可能与原本委托给存储器的模式不同。
直接使用奇偶校验位很简单，不过它有局限性。如果一个模式最初有奇数个1，并出现了2次错误，那么它就仍然有奇数个1，这样校验系统就无法检测到这些错误。事实上，直接使用奇偶校验位并不能发现模式中的任何偶数个错误。
有时会对长位模式（如记录在磁盘扇区中的位串）应用一种方法来最大限度地减少这类问题。在这种情况下，模式都有一组奇偶校验位构成的校验字节（checkbyte）。校验字节中的每一个位都是一个奇偶校验位，与散布于整个模式中的一组特殊位相联系。例如，一个奇偶校验位可能与该模式中从第一个位起的每个第8位相关联，而另一个与该模式中从第二位起的每个第8位相关联。用这种方式，更容易检测到集中在原模式某个区域中的一些差错，因为这些差错会在一些奇偶校验位的范围内。这个校验字节概念的演变引出了称为校验和（checksum）及循环冗余校验（cyclic redundancy check，CRC）的差错检测方案。
1.10.2 纠错码
虽然使用奇偶校验位可以检测到差错，但是它不能提供纠正那个差错所需的信息。让很多人感到惊讶的是，居然有人能设计出既能够检测出差错又能够纠正差错的纠错码（error-correcting code）。毕竟，直觉告诉我们，如果不知道信息的内容就无法纠正接收信息中的错误，但图1-27给我们展示了一个具有这种纠错特性的简单编码。
为了明白这个编码是如何运作的，我们先来定义汉明距离（Hamming distance），这个术语是根据R. W. Hamming的姓氏命名的，由于受20世纪40年代早期继电器缺乏可靠性的挫折，他开始开创性地研究纠错码。两个位模式之间的汉明距离指的是这两个模式中不相同位的个数。例如，在图1-27的编码中，表示A和B的模式之间的汉明距离是4，而B和C之间的汉明距离是3。图1-27中的编码的重要特征是，任何两个模式之间的汉明距离至少是3。
如果用图1-27中的某个模式来修改单个位，就能检测到错误，因为结果不会是一个合法的模式。（我们必须至少改变任意一个模式的3个位，这个模式才会像另外一个合法模式。）而且，我们还能够指出原始模式是什么。毕竟，修改过的模式和其原始形式的汉明距离是1，而和其他任何合法模式的汉明距离至少是2。
因此，对最初用图1-27编码的信息解码，我们只需要简单地对比接收到的模式和用此编码表示的模式，直到我们找到一个和接收到的模式之间的汉明距离是1的模式为止。我们将其视为正确的符号进行解码。例如，我们接收到位模式010100，并将其与编码中的模式相比，我们就会得到图1-28中所示的表格。因此，我们得出结论，传输的字符一定是D，因为这是最接近的匹配。
通过观察可以发现，使用图1-27的编码技术，每个模式我们可最多检测出2个错误并改正1个。如果我们能设计出一种编码，使得每个模式和其他任何模式之间的汉明距离都至少是5，那么我们就能最多检测出4个错误并最多改正2个。当然，设计一种具有长汉明距离的编码并不是一件简单的事。事实上，它是称为代数编码理论的数学分支的一部分，这个理论是线性代数和矩阵理论的子领域。
纠错技术被广泛用于提高计算设备的可靠性。例如，它们经常被用于大容量磁盘驱动器，以减少因磁盘表面瑕疵而损坏数据的可能性。此外，最初用于音频盘的CD格式与后来用于计算机数据存储的格式之间的主要差别是纠错的程度。CD-DA格式具有纠错功能，它能把错误率减少到2张CD只有1个错误。这种格式非常适合于音频录制，但是对于用CD向客户交付软件的公司，若50%的盘有瑕疵是令人无法忍受的。因此，附加纠错功能被用在CD中来存储数据，将错误率减少到20 000个盘1个错误。
问题与练习
1．下面的字节最初是用奇校验编码的。你知道它们中哪个出错了吗？
a. 100101101 b. 100000001 c. 000000000 d. 111000000 e. 011111111
2．问题1中没发现错误的字节还会有错误吗？解释你的答案。
3．如果将奇校验换成偶校验，那么问题1和问题2的答案又将如何？
4．用带奇校验的ASCII码对下列语句编码，在每一个字符编码的高位端加一个奇偶校验位。
a. “Stop!” Cheryl shouted.
b. Does 2+3=5?
5．用图1-27的纠错码解码下面的信息。
a. 001111 100100 001100
b. 010001 000000 001011
c. 011010 110110 100000 011100
6．用长度为5的位模式，为字符A、B、C和D构造编码，使得任何两个模式之间的汉明距离至少是3。
复习题
（带*的题目涉及选学章节的内容。）
1．假设上面输入为1，下面输入为0，请确定下面每一个电路的输出值。如果上面输入为0，下面输入为1呢？
2．a. 下面这个电路做的是什么布尔运算？
- 下面这个电路做的是什么布尔运算？
*3．a. 如果要从某个电子元件商店购买触发器电路，我们会发现它有一个额外的输入端，称为反向器（flip）。当反向器的输入从0变成1时，输出将翻转状态（如果原来是0，现在就是1，反之亦然）。但是，当反向器输入从1变为0时，什么都不会发生。虽然我们可能不知道这个电路完成这一行为的细节，但我们仍然可以将其用作其他电路的抽象工具。请考虑使用下面两个触发器的电路。如果在电路的输入端发送一个脉冲，下面的那个触发器将变换状态。但是，另一个触发器不会改变，因为其输入（这一输入是从非门的输出接收到的）从1变成了0。因此，这一电路现在的输出为0和1。在电路输入端发送第二个脉冲将翻转两个触发器的状态，并产生输出1和0。如果在电路输入端发送第三个脉冲，将会产生什么输出呢？发送第四个脉冲呢？
- 计算机中不同组件的活动一般是需要协调的。只需将脉冲信号（称为时钟）连接到类似a中的电路即可。额外的门（如图所示）以协同的方式发送信号到其他连接的电路。研究这一电路时，你应该能够确认这样一个事实，即在第1个、第5个、第9个……时钟脉冲下，输出端A将发送1。哪些时钟脉冲将使输出端B发送1？哪些时钟脉冲将使输出端C发送1？在第4个时钟脉冲下，哪个输出端的输出为1？
4．假设下面电路的两个输入都是1。请描述如果上面输出暂时变为0，会发生什么。如果下面输入暂时变为0，又会发生什么。用与非门重新绘制这个电路。
5．下面表格显示的是（采用十六进制记数法表示的）机器主存储器某些单元的地址和内容。根据这个存储安排，按照下列指令，记录下这些存储单元的最后内容。
步骤1：将地址为03的单元的内容移动到地址为00的单元中。
步骤2：将值01移动到地址为02的单元。
步骤3：将地址01中存储的值移动到地址为03的单元。
6．如果每个单元地址都可以用2个十六进制数字表示，那么一台计算机的主存储器中可以有多少个单元？如果用4个十六进制数字呢？
7．什么位模式可以用下面的十六进制记数法表示？
a. CD b. 67 c. 9A
d. FF e. 10
8．下列用十六进制记数法表示的位模式中，最高有效位的值是什么？
a. 8F b. FF
c. 6F d. 1F
9．用十六进制记数法表示下面的位模式。
a. 101000001010
b. 110001111011
c. 000010111110
10．假设一个数码相机的存储容量是256 MB。如果一张照片每行每列都有1024个像素，而且每个像素需要3个字节的存储空间，那么这个数码相机可以存储多少张照片？
11．假设显示屏上的一张图片是由一个768行×1024列的像素矩阵表示的。如果每个像素的颜色需要用8位进行编码，并且亮度需要用另外8位进行编码，那么要保存整幅图片需要多少字节的存储单元？
12．a．指出主存储器优于磁盘存储器的两个优点。
b．指出磁盘存储器优于主存储器的两个优点。
13．假设个人计算机上120 GB的硬盘只剩下50 GB是空闲的，那么用CD备份硬盘上的资料是否合理？用DVD呢？
14．如果磁盘的每一个扇区包含1024个字节，而且每个字符用2个字节的Unicode字符表示，那么存储一页文本（如50行，每行100个字符）需要多少扇区？
15．如果用ASCII码，每页3500个字符，那么存储一本400页的小说需要多少字节的存储空间？如果用2个字节的Unicode字符又需要多少字节？
16．一个典型硬盘驱动器的转速为每秒3600转，那么它的等待时间是多少？
17．如果一个硬盘驱动器的转速为每秒360转，寻道时间是10 ms，那么它的平均存取时间是多少？
18．假设一个打字员每天打字24小时，每分钟打60个字，那么这个打字员要多久才能填满容量为640 MB的CD？假定一个单词由5个字符构成，每个字符需要1个字节的存储空间。
19．下面是用ASCII编码的信息。内容是什么？
01010111 01101000 01100001 01110100
00100000 01100100 01101111 01100101
01110011 00100000 01101001 01110100
00100000 01110011 01100001 01111001
20．下面信息使用ASCII编码，每个字符一个字节，并用十六进制记数法表示出来。内容是什么？
686578206E6F746174696F6E
21．用ASCII对下面的句子编码，每个字符一个字节。
`javascript
- Does 100/5=20?
b. The total cost is $7.25.
22．将前面问题的答案用十六进制记数法表示出来。
23．列出整数8到18的二进制表示。
24．a. 通过用ASCII表示2和3，写出数字23。
b. 用二进制表示写出数字23。
25．什么值的二进制表示只有一个位为1？列出具有这个特性的最小的6个值的二进制表示。
*26．将下面的每个二进制表示转换成相应的十进制表示。
```javascript
a. 1111 b. 0001`` c. 10101
d. 1000 e. 10011 f. 000000
g. 1001 h. 10001 i. 100001
j. 11001 k. 11010 l. 11011
*27．将下面每个十进制表示转换成相应的二进制表示。
a. 7 b. 11 c. 16
d. 17 e. 31
*28．将下面的每一个余16表示转换成相应的十进制表示。
a. 10001 b. 10101 c. 01101
d. 01111 e. 11111
*29．将下面的每一个十进制表示转换成相应的余4表示。
`javascript
- 0 b. 3 c. -2
d. -1 e. 2
*30．将下面的每个二进制补码表示转换成相应的十进制表示。- 01111 b. 10100 c. 01100
d. 10000 e. 10110
*31．将下面的每个十进制表示转换成相应的二进制补码表示，其中每个值用7位表示。
```javascript
a. 13 b. -13 c. -1
d. 0 e. 16
*32．假定下面这些位串都是用二进制补码记数法表示的值，执行下面这些加法运算。指出哪一个加法的答案是由于溢出而不正确的。
`javascript
- 00101+01000 b. 11111+00001
c. 01111+00001 d. 10111+11010
e. 11111 +11111 f. 00111 +01100
*33 ．解答下面的每个问题：将这些值翻译成二进制补码记数法（用5位模式），把减法问题转换成相应的加法问题，并执行那个加法。将所得答案转换成十进制记数法进行验证。（观察溢出现象。）
```javascript
a. 5+1 b. 5-1 c. 12-5
d. 8-7 e. 12+5 f. 5-11
*34．将下面的每个二进制表示转换成相应的十进制表示。
`javascript
- 11.11 b. 100.0101 c. 0.1101
d. 1.0 e. 10.01
*35．用二进制记数法表示下面每个值。
```javascript
a. $5\frac{3}{4}$ b. $15\frac{15}{16}$ c. $5\frac{3}{8}$
d. $1\frac{1}{4}$ e. $6\frac{5}{8}$
*36．用图1-24中描述的浮点格式对下面的位模式解码。
`javascript
- 01011001 b. 11001000 c. 10101100
d. 00111001
*37．用图1-24中描述的8位浮点格式对下面的值编码。指出出现截断误差的每个情形。
```javascript
a. [-7\frac{1}{2}] b. $\frac{1}{2}$ c. $-3\frac{3}{4}$
d. $\frac{7}{32}$ e. $\frac{31}{32}$
*38．假定你不受使用标准化格式的限制，用图1-24中描述的浮点格式列出所有可以表示值的位模式。
*39．用图1-24中描述的8位浮点格式，求可以表示的最近似于2的平方根的值。如果机器利用这一浮点格式对这个数做平方，实际得到的值是什么？
*40．用图1-24所示的8位浮点格式可以表示的最近似于的数值是什么？
*41．当用浮点记数法记录使用米制系统的度量时，为什么会产生误差？例如，若110cm用米制单位记录情况会怎样？
*42．位模式01011和11011表示的是同一个值，一个是用余16记数法存储的，另一个是用二进制补码记数法存储的。
a. 关于这个公共的值可以确定的是什么？
b. 分别用二进制补码记数法和余码记数法存储同一个值，并且这两个系统采用相同的位模式长度，那么表示此值的这两种模式是一种什么关系？
*43．3个位模式10000010、01101000和00000010表示的是同一个值，采用的是3种不同的表示法：二进制补码记数法、余码记数法和图1-24所示的8位浮点格式。但这3个位模式和这3个表示法的顺序不一定是一一对应的。它们共同表示的那个值是什么？哪个模式对应哪个记数法？
*44．在下面的值中，哪一个不能用图1-24所示的浮点格式精确地表示出来？
a. $6\frac{1}{2}$ b. $\frac{13}{16}$ c. 9
d. $\frac{17}{32}$ e. $\frac{15}{16}$
*45．如果用于表示二进制整数的位串长度由4变成6，那么能够表示的最大整数的值会发生什么变化？用二进制补码记数法又将如何呢？
*46．如果一个4 MB的存储器每个单元可以存储1字节，那么其最大地址的十六进制表示是什么？
*47．如果使用LZW压缩和最初只包含x、y和一个空格（如1.8节所述）的字典，对下面信息编码
xxy yyx xxy xxy yyx
那么编码结果是什么？
*48．下面信息是使用LZW压缩的，其字典的第1、2、3个条目分别是x、y和空格。这条信息的解压缩结果是什么？
22123113431213536
*49．如果信息
xxy yyx xxy xxyy
是用LZW压缩的，并且最初字典的第1、2、3个条目分别是x、y和空格，那么最后的字典里有哪些条目？
*50．我们将在下一章学到，通过传统电话系统传输位的一种方法：首先将位模式转换成声音，然后通过电话线传输声音，最后再将声音转换回位模式。这种技术的传输速率最高可达57.6 Kbit/s。如果视频采用MPEG压缩，那么这种技术能否满足远程会议的需要？
*51．使用ASCII对下面的句子编码，使用偶校验，在每个字符编码的高位端添加一个奇偶校验位。
`javascript
- Does 100/5=20?
b. The total cost is $7.25.
*52．下面信息的每一个短位串，最初都是用奇校验传输的。哪一个位串绝对出现了差错？
```javascript
11001 11011 10110 00000 11111
10001 10101 00100 01110
*53．假如一个24位的编码是这样产生的：将一个符号的ASCII表示连续复制3次，用得到的结果表示该符号（例如，符号A用位串010000010100000101000001
表示）。这个新编码有哪些纠错特性？
*54．用图1-28的纠错码对下面的词语进行解码。
`javascript
a．111010 110110
b．101000 100110 001100
c．011101 000110 000000 010100
d．010010 001000 001110 101111 000000 110111 100110
e．010011 000000 101001 100110
*55．国际货币汇率变化很频繁。研究一下货币汇率，并相应地更新1.8节的货币转换器脚本。
*56. 找出一种1.8节的那个货币转换器里没有的货币。得到它的当前汇率，并在网络上找到它的Unicode货币符号。扩展货币转换器脚本，让它能够转换这个新货币。
*57. 如果你的网络浏览器和文本编辑器能很好地支持Unicode和UTF-8，那么请把实际的国际货币符号复制/粘贴到1.8节的转换器脚本中，替换掉'\u00A3'这样的复杂代码。（如果你的软件处理Unicode有困难，那么当你尝试这样做时，你的文本编辑器里可能会出现奇怪的符号。）
*58. 1.8节的货币转换器脚本在执行每一个乘法之前，使用了一个变量dollars来存储要转换的金额。这使得脚本中每个乘法代码行的长度，比直接键入整数数量1000的长度要长。提前创建这个额外的变量有什么好处？
*59. 编写并测试一个Python脚本，给定一个字节数，输出与其相等的千字节数、兆字节数、吉字节数和太字节数。再编写并测试一个互补脚本，给定一个太字节数，输出与其相等的GB数、MB数、KB数以及字节数。
*60. 编写并测试一个Python脚本，给定一个录音的分秒数，计算对这个时长的未压缩的CD音量的立体声音频数据进行编码所需的位数。（复习1.4节的必要参数和公式。）
*61．指出下面Python脚本中的错误。
days_per_week = 7
weeks_per_year = 52
days_per_year = days_per_week **
weeks_per_year
PRINT(days_per_year)
社会问题
希望下面的问题能引导读者思考一些与计算领域相关的道德、社会和法律问题。回答出这些问题还不够，还应该考虑为什么这样回答，以及你的判断是否对每个问题都标准如一。
1．某个截断错误出现在一个关键时刻，引起了巨大的损失和人身伤亡。如果有人需要对此负责，那么是谁？是硬件设计者？软件设计者？编写那段程序的程序员？还是决定在那个特定应用中使用这个软件的人？如果最初开发这个软件的公司已经修正过这个软件，但是用户没有为那个关键应用购买并应用这个升级版，又将如何？如果这个软件是盗版的呢？
2．对于个人来讲，在开发他自己的应用时忽略截断错误的可能性以及它们的后果，是可以接受的吗？
3．20世纪70年代开发的软件只用2个数字表示年（如用76表示1976年），忽视了这个软件在即将到来的世纪之交会有缺陷这个事实，这道德吗？若现在只用3个数字表示年（如用982表示1982年，用015表示2015年）又是否道德呢？如果只用4个数字呢？
4．许多人认为，对信息进行编码经常会削弱或歪曲该信息，因为这实质上迫使信息必须被量化。他们认为，若一份调查问卷要求调查对象只能用给定的5个等级来发表他们的意见，这份问卷本身就是有缺陷的。信息可以量化到什么程度？垃圾处理场选址的利弊可以量化吗？关于核能源及核废料的辩论是可量化的吗？将结论建立于平均值和其他统计分析上的做法危险吗？如果新闻通讯社在报导调查结果时不使用问题的准确措辞，这道德吗？能够量化一个人的生命值吗？假设一个公司要停止对一个产品改进的投资，尽管知道附加投资可以减少产品使用的危险性，这是可以接受的吗？
5．收集和散发数据的权利是否应该根据数据形式的不同而有所差别？也就是说，收集和散发照片、音频或者视频的权利是否应该与收集和散发文本的一样？
6．无论是有意的还是无意的，记者的报道中通常都会反映出记者本人的偏见。一般只要改几个词语，一个故事就可能被赋予正面或负面的含义。（比较“大多数受访者都反对公民投票。”与“受访者中有相当一部分支持公民投票。”）修改一个故事（删掉某些观点或者仔细选词）和修改一张照片有区别吗？
7．假设数据压缩系统的使用会导致一些微小但重要的信息的丢失。这会产生什么样的责任问题？应该如何解决？
课外阅读
Drew, M., and Z. Li. Fundamentals of Multimedia. Upper Saddle River, NJ: Prentice-Hall, 2004.
Halsall, F. Multimedia Communications. Boston, MA: Addison-Wesley, 2001.
Hamacher, V. C., Z. G. Vranesic, and S. G. Zaky. Computer Organization, 5th ed. New York: McGraw-Hill, 2002.
Knuth, D. E. The Art of Computer Programming, Vol. 2, 3rd ed. Boston, MA: Addison-Wesley, 1998.
Long, B. Complete Digital Photography, 3rd ed. Hingham, MA: Charles River Media, 2005.
Miano, J. Compressed Image File Formats. New York: ACM Press,1999.
Petzold, C. CODE: The Hidden Language of Computer Hardware and Software. Redman, WA: Microsoft Press, 2000.
Salomon, D. Data Compression: The Complete Reference, 4th ed. New York: Springer, 2007.
Sayood, K. Introduction to Data Compression, 3rd ed. San Francisco, CA: Morgan Kaufmann, 2005.
[1] 下面这个Python代码是用该语言的3版本写出来的，本书后面会直接把这个版本的Python称作“Python”。较早的Python版本并不总是要求开括号和闭括号。
.
