祖师爷的开山之作,这篇论文标志着信息论的诞生,也将人类社会拉入了信息时代

PS:这也是我昵称的由来 A.S. 即 After Shannon (一些科幻小说以此记年

杂耍和独轮车是祖师爷的一大爱好

INTRODUCTION

近年来,各种调制方法如 PCM 和 PPM 通过增加带宽换取更低的信噪比,增加了人们对通信一般理论的兴趣。奈奎斯特[^1] 和哈特利[^2] 关于这一问题的重要论文中包含了这种理论的基础。在本文中,我们将扩展该理论,增加许多新的因素,尤其是信道中噪声的影响,以及在原始消息的统计结构和信息最终目的地的性质(不变)而可能的节省(带宽?)。

PCM: Pulse-code modulation 即 脉冲编码调制,一种将模拟信号数字化的方法,详见PCM

PPM: Pulse-position modulation 即 脉冲位置调制,一种调制信号的方法,详见PPM

通信的基本问题是在一个地方上准确或近似地再现在另一个地方上选择(发送)的消息。这些信息往往有意义;也就是说,它们指代或依据 具有某些物理或概念实体的系统,通信的语义方面与工程问题无关。重要的是,实际信息是从一组可能的信息中选择的。系统的设计必须使每个可能的选择都可以运行,而不仅仅是实际的选择,因为在设计系统时选择是未知的。

如果集合中的消息数量是有限的,且所有选择的概率都是相同的,那么一个数字或是一个数字的任何单调函数可以被视为从集合中选择一条消息时所产生的信息的度量。正如哈特利所指出的,最自然的选择是对数函数。但是当我们考虑消息的统计信息,并且有一个连续的消息范围时,这个定义必须被极大地推广,我们将在所有的情况下使用同一个基本的对数度量。

由于以下各种原因,对数度量更方便:

  1. 它实际上更有用。工程中重要的参数,如时间、带宽、继电器数量等,往往随概率的对数线性变化。例如,将一个继电器添加到一个组(group,不知道是什么)中会使继电器的可能状态数翻倍。这个数字对以2为底的对数加1。时间翻倍大致等于可能的消息数的平方,或是其对数翻倍,等等。
  2. 它更接近于我们对正确度量的直觉。这与第一点密切相关,因为我们通过与通用标准的线性变化比较直观地衡量实体。例如,人们认为,两张穿孔卡片的信息存储容量应该是一张穿孔卡片的两倍,(两张穿孔卡片)传输信息的两个相同通道的容量应该是一张穿孔卡片的两倍。
  3. 这在数学上更合适。许多限制操作在对数方面很简单,但在概率方面需要复杂的描述。

选择不同对数底数对应于不同的测量信息的单位。如果使用底数2,结果单位可能被称为二进制数字(binary digits),或是更简洁的 bits,一个由 J.W.Tukey(快速傅立叶变换发明人)建议的单词。具有两个稳定状态的设备,如继电器或触发器电路,可以存储一比特信息。N这样的设备可以存储N比特,因为可能状态的总数是 $2^N$,$log_22^N=N$ 。如果使用底数10,则单位可以称为decimal digits。这样一dit就大致等于 $3\frac{1}3$bit。$$\begin{align*} log_2M &= log_{10}M/log_{10}2 \\ &=3.32 log_{10}M \end{align*}$$ 台式计算机上的数字轮有十个稳定的位置(显然现在的现代计算机不是这样的😂),因此具有一个十进制数字的存储容量。在涉及整合和差异化的分析工作中,基数 $e$ 有时是有用的。由此产生的信息单位将被称为自然单位(即奈特)。从基数 $a$ 到基数 $b$ 的变化只需要乘以 $log_ba$ 即可。

图1

我们所说的通信系统是指图1中示意性指示的系统。它基本上由五部分组成:

  1. 信源,它产生一条消息或一系列消息,并传送给接收终端。信息可以有多种类型:

    • 电传系统电报中的字母序列

    • 时间 $f(t)$ 的单一函数,如在无线电或电话中

    • 时间和其他变量的函数,如在黑白电视中

      在这里,信息可以被认为是两个空间坐标和时间函数 $f(x) , f(y)$ 点 $(x,y)$ 的亮度和拾取管板上的时间 $t$

    • 两个或两个以上的时间函数,例如 $f(t),g(t),h(t)$

      三维声音传输,或系统打算在多路传输中为多个单独的通道提供服务,则也为这种情况

    • 几个变量的函数

      在彩色电视中,信息由三个定义在一个三维连续体中的函数 $f(x,y,t),g(x,y,t),h(x,y,t)$ 组成,我们也可以将这三个函数视为该区域定义的向量场的组成部分,类似地,几个黑白电视源将产生由多个三变量函数组成的“信息”

    • 以上的各种组合也会出现

      例如在具有相关音频频道的电视中。

  2. 以某种方式对信息进行操作以产生适合通过信道传输的信号的发射器。在电话技术中,这种操作仅仅是将声压转换成与之成比例的电流。在电报中,我们有一种编码操作,它在信道上产生一系列与信息对应的点、破折号和空格(摩尔斯)。在多路PCM系统中,必须对不同的语音功能进行采样、压缩、量化和编码,并最终进行适当的插值以构造信号。声码器系统(?)、电视和频率调制是应用于消息以获得信号的复杂操作的其他示例。

  3. 信道仅仅是用来将信号从发射机传输到接收机的媒介。它可能是一对电线、一根同轴电缆、一段无线电频率、一束光束等等(祖师爷的神预言啊,光纤的坑这时候就挖了吗?)

  4. 接收机通常执行与发射机相反的操作,从信号中重构信息

  5. 目的地是消息要传达给的人(或物)

我们希望考虑一些涉及通信系统的一般问题。要做到这一点,首先需要将涉及的各种元素表示为数学实体,并对物理实体进行适当的理想化。我们可以大致将通信系统分为三大类:离散、连续和混合。我们所说的离散系统是指信息和信号都是离散符号序列的系统。一个典型的例子是电报,其中信息是字母序列,信号是点、破折号和空格序列。连续系统是指信息和信号都被视为连续的系统,例如收音机或电视。混合系统是同时出现离散变量和连续变量的系统,例如语音的PCM传输。
我们首先考虑离散情形。这件事不仅在通信理论中有应用,而且在计算机理论、电话交换机设计和其他领域也有应用。此外,离散的情况是连续和混合情况的基础,后两者将在论文的后半部分讨论。

香农的肖像照,此摄影师拍摄过许多伟大的人物

PART I: DISCRETE NOISELESS SYSTEMS

1. THE DISCRETE NOISELESS CHANNEL

电传打字和电报是离散信道传输信息的两个简单例子。通常离散信道指的是能够使一组有限的基本符号 $S_1,\ldots ,S_n$ 中的一系列选择可以从一个点传输到另一个点的系统。假设每个符号 $S_i$ 持续时间为 $t_i$ 秒(对于不同 $S_i$不必相同 ,例如电报中的点和破折号)。不要求 $S_i$ 的所有可能序列能够在系统上传输而仅允许某些序列。这些(序列)将是通道传输的可能信号。因此,在电报中,假设符号是:

  1. 一个点,由一个单位时间的闭合线路和一个单位时间的开放线路组成(即开关闭合与打开时间比为1:1,下同)
  2. 短划,由三个单位时间的闭合和一个单位时间的打开组成
  3. 一个字母间隔,由三个单位时间的打开组成
  4. 一个单词间隔,由六个单位时间的打开组成

我们可能会对允许的序列设置条件,比如不能有空格相互跟随(因为如果两个字母空格相邻,那么它与单词空格相同)。我们现在考虑的问题是应该如何测量这样一个信道传输信息的能力。

在电传打字机的情况下,所有符号的持续时间相同,并且允许 $32$ 个符号的任何排序序列,这使得答案很简单。每个符号代表五比特信息。如果系统每秒传输 $n$ 个符号,那么很自然地说信道容量为每秒 $5n$ 比特。这并不意味着电传打字机信道将始终以该速率传输信息——这只是可能的最大速率,实际速率是否达到该最大值取决于为信道提供信息的信源,稍后将对此讨论。

在更一般的情况下,对于不同长度的符号和允许序列的约束,我们做出以下定义:

定义:离散信道的容量C由下式给出:$$C = \displaystyle\lim_{x \rightarrow 0}\frac{logN(T)}{T}$$ 其中 $N(T)$ 代表 $T$ 时间内允许通过的信号数量

很容易看出,在电传打字机的情况下,就等于之前的结果。可以证明,在大多数我们关心的情况下,这个极限总是存在的,并且是一个有限数。假设所有符号序列$S_1,\ldots ,S_n$都是允许的,并且这些符号的持续时间为 $t_1,\ldots , t_n$ 。那么信道容量是多少?如果使用 $N(t)$ 表示持续时间 $t$ 内的序列数,我们得到 $$N(t) = N(t-t_1) + N(t-t_2) + , \ldots , + N(t-t_n).$$

总数等于以$S_1,\ldots ,S_n$结尾的序列数之和即分别是 $N(t-t_1), N(t-t_2) , \ldots , N(t-t_n)$ ,根据一个众所周知的有限差分的结论,当 $t$ 很大时,$N(t)$ 是 $X_0^t$ 的近似解,其中 $X_0$ 是以下特征方程的最大实解:$$X^{-t_1} + X^{-t_2} + \ldots + X^{-t_n}$$

因此有:$$C = logX_0.$$

如果允许的序列受到限制,我们仍然可以从特征方程中获得这种类型的差分方程并找到 $C$。如上述电报例子中提到的(约束)$$N(t) = N(t-2) + N(t-4) + N(t-5)+N(t-7)+N(t-8)+ N(t-10).$$

PS: 其中 2、4、5、7、8、10 为之前讨论的四种情况的可能组合。

正如我们所看到的,根据最后一个或下一个出现的符号来计算符号序列。这样 $C$ 就是 $-log\mu_0$ ,其中 $\mu_0$ 是 $1 = \mu^2 + \mu^4 + \mu^5 + \mu^7 + \mu^8 + \mu^{10}$ 的正数根。这样我们就可以算出 $C=0.539$ 。

[^1]: Nyquist, H., “Certain Factors Affecting Telegraph Speed,” Bell System Technical Journal, April 1924, p. 324; “Certain Topics in Telegraph Transmission Theory,” A.I.E.E. Trans., v. 47, April 1928, p. 617. ↩
[^2]: Hartley, R. V. L., “Transmission of Information,” Bell System Technical Journal, July 1928, p. 535.


毕竟是55页的paper,分若干次更新吧hh