《伟大的计算原理》一通信系统-阿里云开发者社区

开发者社区> 华章出版社> 正文

《伟大的计算原理》一通信系统

简介:

本节书摘来华章计算机《伟大的计算原理》一书中的第3章 ,[美]彼得 J. 丹宁(Peter J. Denning)
克雷格 H. 马特尔(Craig H. Martell)著 罗英伟 高良才 张 伟 熊瑞勤 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

通信系统

通信系统是最简单的信息系统,在1948年一篇名为《通信的数学理论》的文章中,香农提出了通信系统的第一个理论模型(Shannon 1948)(见图3.3)。其本质是如下过程:消息源发送一条消息,编码器按照编码本规定为这条信息生成一个独有的信号;信道作为中间媒介从源到端运载这个信号;接收端的解码器使用同样的编码本将这个信号转换成初始形式——消息就到达接收处了。香农的模型适用于任何使用编码、解码、传输、存储或是查询信号数据的系统,甚至可以作为科学发现的模型:将自然界看作现象(消息)的源头,而传输媒介(即通道)就是探索的过程(Dretske 1981)。

image


图3.3 克劳德·香农(1916—2001)描述了一个信息系统模型,它是当今信息论的基石。消息源代表所有可能要发送的消息的集合,信道是存储和运载信号的媒介,编码是将消息转换为信号,解码是将信号还原为消息,编码本包含了消息与信号互相转换的规则,噪声是指任何改变信号的事物
噪声是通信模型中的一个重要元素。任何在传输通道中改变信号,从而导致解码出错误消息的干扰都是噪声。通信技术中噪声的例子比比皆是:雾气和黑暗干扰了船只之间的信号通信;电报站之间过长的距离减弱了信号的强度;雷电干扰了调频广播的传输;DVD上的划痕会导致读取失败;环境的声音淹没了演讲的声音。
值得注意的是,在通信系统中,编码和加密是不一样的。加密是一个额外的步骤,在消息到达编码器之前将消息转换成密文,这样只有拥有密钥的接收器才能够读取消息。在这种情况下,通信系统的工作就是将密文准确地传输给接收方,如果接收方具有密钥则可以进行解密。
正如前文所提到的,香农将他的数学模型在二进制位上进行标准化,他认为所有的信号都能够用二进制位表示,这一过程在字面上被称为数字化,即将模拟信号转变为数字信号。数字化并不是生成信息的一个完全拷贝,而是一种近似化过程,因为其常常会丢失一些信息。显而易见的例子有许多,如物体边缘参差不齐的像素化照片,同时也有一些情形是非常微妙不那么直观的。物理现象中的定量分析,比如火星探测器的轨道位置,实际上不能通过计算机的有限运算进行精确表达。舍入误差会随着计算步骤而逐渐累加,导致整个计算的精确度出现问题,使火星着陆器面临危险。更糟糕的是,一些计算步骤会放大错误。如两个几乎相等的数可以认为它们的差近似为零,在用这个近似的差除另一个数时会导致严重错误。数学软件的设计师设计了很多巧妙的技术,来防止这些数字化错误破坏计算结果。
Harry Nyquist可谓当代的香农,他指出了上述普遍规律中的一个重要例外:通信系统可以免受数字化错误的影响(Nyquist 1928)。每一个连续、带宽有限的信号都可以无损地数字化,只要用至于两倍于最高频率的采样率进行采样。例如音频光盘(CD),为了使得质量没有明显损失,要每秒记录44?100(44.1千赫)个采样点,因为几乎没人能听到高于22?000赫兹的声音。
香农认为,由于我们可以对任何信号进行数字采样,同时也由于真实的通信系统具有有限的带宽,那么将通信模型限制为二进制序列,不会有任何损失。这不但简化了数学运算,而且使得这一结论适用于所有实际信道。
作为一个实例,一段简单的编码就可以说明通信模型的各种特性。假设一个消息源只传输消息的1/4,我们把完整的消息定为A、B、C、D,为这些字母分配2位的编码:
**A:11
B:10
C:01
D:00**
只能表示四种消息的编码在自然界中并不少见,我们细胞中的DNA序列就是一种只使用四个字母的自然消息源——G、A、T和C,它们是DNA中四种核苷酸的首字母。
如果消息源想传输序列“CAB”,那么就在信道中传输“011110”这个位序列,接收端会逆向这个过程,即在编码本中查找每一对位码然后输出对应的字母。
在任何关于编码的讨论中,我们都需要在编码长度(码字的位长)和信道抗扰能力间做出权衡。短的编码更高效、传输更快并且占用较小的存储空间,然而短编码非常容易受到噪声的干扰,信道中仅仅一位的改变就会将码字完全改变。例如,如果信道将A的第一个位编码变为0,接收端就会收到01,然后解码成C而不是A。其中一个解决方案就是使用奇偶校验位来提示接收端是否收到错误信息,当原编码中有偶数个1时,奇偶校验位为偶数,反之则为奇数。下述编码就是在原始编码中添加第3位为奇偶校验:
**A:110
B:101
C:011
D:000**
现在信道噪声将A的第一位编码变成0后,接收端收到010时,会发现编码错误,因为010这个编码是无效编码。概括来说,1位的错误会导致1的数量变为奇数,从而标识这是一个未编码的模式。
然而,单一的奇偶校验位并不能标识出哪一位被改变了。上例中,接收端知道010是一个无效的编码,但是并不知道这三个编码(A、C或者D)中的哪一个被这个位错误改变了。通过添加冗余的编码,解码器不仅可以检测是否有错误编码,还可以定位具体受影响的消息位。试想下面的例子,在原来编码的基础上添加了3个位:
**A:11111
B:10010
C:01001
D:00100**
这个编码满足如下准则:加上额外的编码位,每一个码字都与别的所有码字至少有3位不同。若有1位发生错误,接收端收到编码后会发现这个错误编码与正确编码只有1位不同,但是与其他的字母编码却有2位甚至更多的不同。这样解码器就可以检测并修正只有1位发生错误的编码情况。
通信工程师理查德·海明(Richard Hamming)在1950年首先提出码字之间的距离计算方式。两个码字之间的距离就是不同位码的个数,这就是后来有名的“海明距离”。海明指出,若要纠正k个字符,编码就必须包含足够的位使得码字之间的最小距离至少为2k + 1。他也发明了一系列编码,也就是现在的海明码。海明码在2k - 1位的码字中嵌入k个校验码,然后使用一种简单的方法来构造电路用以将受损的比特位转换为原来的编码值。最有名的一种海明编码是(7,4)编码,在4个数据位中嵌入3个校验位,构成7位的编码。在计算机处理器和存储器之间传输数据时,海明码被广泛用于纠错。
当噪声在码位上随机分布时,海明码能够正常工作。然而,在某些信号中噪声可能会爆发性地出现,比如日晕会影响某些深空信号数秒,光碟上的划痕会损坏一系列邻近的凹点,这些噪声被称为突发错误。另一种类型的编码——Reed-Solomon码便是用于检测和消除突发错误的。它的数学计算更加复杂,但是也和海明码一样很容易用高速数字电路实现。
不同于信号,位并没有实际物理意义。1位可以表示可察的任何两种属性之一。比如,工程师可能让“1”代表激光束在DVD表面某点的反射,而“0”则代表没有反射;或者“1”代表晶体管的输出是5V,而“0”则可能代表输出是3V;或者“1”代表一特定频率(比如400Hz)出现在一段音乐录音中,而“0”则代表不是该频率。位是一种抽象表达,用来声明我们想让系统做什么。工程师将这些物理的“东西”(材料)进行组装,用以完成所定义的功能。
物理系统中的信息总是要由物理状态来表达,而读写和变换这些信息也需要花费时间和精力,因此通信和计算从来都逃脱不了物理世界的限制。计算机芯片工程师知道蓄热和尺寸大小(芯片上所有电路元件的平均尺寸)等是影响他们能把电路做成多小的实际限制所在。同时每一个操作的时间消耗量则限制了可用时间内可计算的指令数。尽管新的算法在常规难题优化上有极大的改善,但计算量极大的一些问题仍然非常棘手,因为其物理运算所需要的时间大大超出我们的可等待范围。例如,在目前广泛应用的RSA加密系统中,为了寻找构成600位密钥的两个因子,即使利用目前最快的计算机也需要几百年的时间。
这些年,存储和计算能力呈指数增长。在香农发表其文章的同一年,在同一个地方——贝尔实验室,电子计算机就开始使用新发明的晶体管来取代真空管。电路设计师能够压缩晶体管的大小,每18~24个月的时间就能够无额外费用地将接近两倍的晶体管放在同样大小的物理空间。这种压缩体积的过程已持续了50年,使得每10年就有了100倍计算能力的增加,这个趋势就是广为人知的摩尔定律。英特尔的创始人之一——戈登·摩尔(Gordon Moore)在他1965年的论文中首次描述了摩尔定律(Moore 1965)。
摩尔定律带给人们两种效应和影响。一个是惊人的计算能力,这对于20世纪40年代的计算科学先驱们来说如魔法一般;另一个是正如James Gleick(2011)所称的如洪水般的信息。第一种影响——每一个传输和存储信息的更小物理机制,都会导致第二种影响——信息的极大丰富。人们被巨量的信息淹没,无法消化信息,变得不知所措。
庞大的计算能力导致了一个流行的错觉,那就是计算机所操作的是位而非原子,因此计算结构在尺寸和能量上没有物理限制(Negroponte 1996)。从物理的角度来看,这个概念是完全错误的。因为抽象的位必须依靠物理介质来记录,而且机器要通过介质来获取位信息。这个记录的过程将我们带回了原子世界:没有它们我们无法完成计算。我们可以在极小的物理元件上进行快速的计算、传输和存储,但从来无法消除它们的时间和功耗。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

华章出版社

官方博客
官网链接