Мы это сделали！
“本课程的目的是让你为你的技术未来做好准备。”
你好，哈布尔。 记住这篇精彩的文章 （+219、2588 个书签、429k 阅读次数）？
所以汉明（是的，是的，自我监控和自我纠正 ）有一个整体 ，根据他的讲座编写。 我们翻译它，因为这个人说出了他的想法。
这不仅是一本关于 IT 的书，也是一本关于非常酷的人的思维方式的书。 “这不仅能促进积极思考，还能促进积极思考。 它描述了增加完成出色工作的机会的条件。”
感谢安德烈·帕霍莫夫的翻译。
信息论是由 C. E. Shannon 在 1940 世纪 XNUMX 年代末提出的。 贝尔实验室管理层坚持认为他称之为“通信理论”，因为…… 这是一个更准确的名字。 由于显而易见的原因，“信息论”这个名字对公众的影响要大得多，这就是香农选择它的原因，也是我们至今所知道的名字。 这个名字本身就表明该理论涉及信息，这使得它在我们深入信息时代时变得重要。 在本章中，我将触及该理论的几个主要结论，我将提供该理论的一些个别条款的不是严格的，而是直观的证据，以便您了解“信息论”实际上是什么，可以在哪里应用它哪里没有。
首先，什么是“信息”？ 香农将信息等同于不确定性。 他选择事件概率的负对数作为当概率为 p 的事件发生时您收到的信息的定量度量。 例如，如果我告诉你洛杉矶的天气有雾，那么 p 接近 1，这实际上并没有给我们提供太多信息。 但如果我说六月蒙特雷下雨，那么消息中就会存在不确定性，并且会包含更多信息。 可靠事件不包含任何信息，因为 log 1 = 0。
让我们更详细地看看这个。 香农认为，信息的定量度量应该是事件概率p的连续函数，对于独立事件，它应该是可加的——两个独立事件的发生所获得的信息量应该等于由于联合事件的发生而获得的信息量。 例如，掷骰子和掷硬币的结果通常被视为独立事件。 让我们把上面的内容翻译成数学语言。 如果 I (p) 是概率为 p 的事件所包含的信息量，则对于由概率为 p1 的两个独立事件 x 和概率为 p2 的 y 组成的联合事件，我们得到
（x 和 y 是独立事件）
这是函数柯西方程，对于所有 p1 和 p2 均成立。 为了求解这个函数方程，假设
p1 = p2 = p，
这给出了
如果 p1 = p2 且 p2 = p 则
ETC。 使用指数的标准方法扩展此过程，对于所有有理数 m/n，以下是正确的
根据信息测度的假设连续性，可以得出对数函数是柯西函数方程的唯一连续解。
在信息论中，通常取对数底为2，因此二进制选择恰好包含1位信息。 因此，信息可以通过以下公式来衡量
让我们暂停一下并理解上面发生的事情。 首先，我们没有定义“信息”的概念，只是定义了其定量衡量的公式。
其次，这一衡量标准存在不确定性，尽管它相当适合机器（例如电话系统、广播、电视、计算机等），但它并不能反映人类对信息的正常态度。
第三，这是一个相对的衡量标准，取决于你目前的知识水平。 如果您查看随机数生成器中的“随机数”流，您会假设下一个数字是不确定的，但如果您知道计算“随机数”的公式，则下一个数字将是已知的，因此不会包含信息。
所以香农对信息的定义在很多情况下适合机器，但似乎不符合人类对这个词的理解。 正因为如此，“信息论”才应该被称为“传播理论”。 然而，现在改变定义已经太晚了（这使得该理论最初流行，并且仍然使人们认为该理论涉及“信息”），所以我们必须忍受它们，但同时你必须清楚地理解香农对信息的定义与其通常使用的含义相差有多大。 香农的信息涉及完全不同的东西，即不确定性。
当您提出任何术语时，需要考虑以下问题。 提议的定义（例如香农对信息的定义）与您最初的想法有何一致以及有何不同？ 几乎没有术语能够准确反映您之前对某个概念的看法，但最终，所使用的术语反映了该概念的含义，因此通过清晰的定义将某些内容形式化总是会带来一些噪音。
考虑一个系统，其字母表由符号 q 和概率 pi 组成。 在这种情况下 平均信息量 系统中的（其期望值）等于：
这称为概率分布 {pi} 系统的熵。 我们使用术语“熵”，因为相同的数学形式出现在热力学和统计力学中。 这就是为什么“熵”这个词在其周围创造了某种重要的光环，但这最终是不合理的。 相同的数学表示法并不意味着相同的符号解释！
概率分布的熵在编码理论中起着重要作用。 两个不同概率分布 pi 和 qi 的吉布斯不等式是该理论的重要结论之一。 所以我们必须证明
证明基于一个明显的图，如图所示。 13.I，这表明
并且只有当 x = 1 时才实现相等。让我们将不等式应用到左侧总和的每一项上：
如果通信系统的字母表由q个符号组成，则取每个符号的传输概率qi = 1/q并代入q，由吉布斯不等式得到
图13.I
这意味着如果传输所有 q 个符号的概率相同且等于 - 1 / q，则最大熵等于 ln q，否则不等式成立。
对于唯一可解码的代码，我们有卡夫不等式
现在如果我们定义伪概率
当然在哪里 = 1，由吉布斯不等式得出，
并应用一点代数（记住 K ≤ 1，所以我们可以去掉对数项，也许稍后会加强不等式），我们得到
其中 L 是平均代码长度。
因此，熵是任何具有平均码字长度 L 的逐个符号代码的最小界限。这是无干扰信道的香农定理。
现在考虑关于通信系统局限性的主要定理，其中信息作为独立比特流传输并且存在噪声。 据了解，一位正确传输的概率为 P > 1/2，传输过程中该位值发生反转（出现错误）的概率等于 Q = 1 - P。为了方便起见，我们假设错误是独立的，并且每个发送位的错误概率相同，即通信信道中存在“白噪声”。
我们将一长串 n 位编码成一条消息的方式是一位代码的 n 维扩展。 稍后我们将确定 n 的值。 将由 n 位组成的消息视为 n 维空间中的一个点。 由于我们有一个 n 维空间 - 为简单起见，我们假设每个消息具有相同的发生概率 - 有 M 个可能的消息（M 也将在稍后定义），因此发送任何消息的概率为
（发件人）
附表 13.II
接下来考虑通道容量的想法。 在不详细讨论的情况下，信道容量被定义为考虑到最有效编码的使用，可以通过通信信道可靠传输的最大信息量。 毫无疑问，通过通信信道可以传输的信息多于其容量。 这可以通过二进制对称通道（我们在我们的例子中使用）来证明。 发送比特时的信道容量指定为
其中，与之前一样，P 是任何发送位中没有错误的概率。 当发送n个独立比特时，信道容量由下式给出
如果我们接近信道容量，那么我们必须为每个符号ai发送差不多这个量的信息，i=1，...，M。考虑到每个符号ai出现的概率为1/M，我们得到
当我们发送 M 个同等概率的消息 ai 中的任何一个时，我们有
当发送 n 位时，我们预计会发生 nQ 个错误。 实际上，对于由 n 位组成的消息，我们在接收到的消息中大约会出现 nQ 个错误。 对于较大的 n，相对变化（变化 = 分布宽度，）
随着n的增加，错误数量的分布将变得越来越窄。
因此，从发送端，我接收消息 ai 发送并在其周围绘制一个半径为 的球体
它比预期错误数 Q 略大 e2（图 13.II）。 如果n足够大，则消息点bj出现在超出该球体的接收方一侧的概率为任意小。 让我们从发射器的角度来概述一下情况：从发送的消息 ai 到接收的消息 bj 的任意半径，误差概率等于（或几乎等于）正态分布，达到最大值的nQ。 对于任何给定的 e2，n 如此之大，以至于结果点 bj 在我的球体之外的概率与您想要的一样小。
现在让我们从您这边看一下同样的情况（图13.III）。 在接收端，在n维空间中，在接收点bj周围有一个半径为r的球体S(r)，这样如果接收到的消息bj在我的球体内，那么我发送的消息ai在你的球体内领域。
怎么会出现错误呢？ 该错误可能发生在下表所述的情况：
图13.III
在这里我们看到，如果在围绕接收点构建的球体中至少还有一个点对应于可能发送的未编码消息，则在传输过程中会发生错误，因为您无法确定传输的是哪一条消息。 仅当与其对应的点位于球体中时，发送的消息才是无错误的，并且给定代码中不可能有其他点位于同一球体中。
如果发送消息 ai，我们有一个关于错误概率 Pe 的数学方程
我们可以把第二项中的第一个因素去掉，取1，这样我们就得到了不等式
显然，在
因此
重新应用到右侧的最后一项
当 n 足够大时，第一项可以根据需要取小，比如小于某个数字 d。 因此我们有
现在让我们看看如何构造一个简单的替换码来编码由 n 位组成的 M 条消息。 由于不知道如何准确地构造代码（当时还没有发明纠错码），香农选择了随机编码。 为消息中的 n 位中的每一位抛一枚硬币，并对 M 条消息重复该过程。 总共需要抛 nM 次硬币，所以有可能
具有相同概率 ½nM 的代码字典。 当然，创建密码本的随机过程意味着存在重复的可能性，以及彼此接近的代码点，因此可能是错误的来源。 必须证明，如果这种情况发生的概率大于任何选定的小误差水平，则给定的 n 足够大。
关键是香农对所有可能的密码本进行了平均，以找到平均误差！ 我们将使用符号 Av[.] 来表示所有可能的随机码本集合的平均值。 当然，对常数 d 进行平均会得到一个常数，因为平均每一项与总和中的所有其他项相同，
可以增加（M–1 变为 M）
对于任何给定的消息，当对所有码本进行平均时，编码会遍历所有可能的值，因此点位于球体中的平均概率是球体体积与空间总体积的比率。 球体的体积是
其中 s=Q+e2 <1/2 并且 ns 必须是整数。
右边的最后一项是这个总和中最大的。 首先，让我们使用斯特林阶乘公式来估计它的值。 然后，我们将查看前面项的递减系数，请注意，当我们向左移动时，该系数会增加，因此我们可以：（1）将总和的值限制为几何级数的总和这个初始系数，（2）将几何级数从ns项扩展到无限项，（3）计算无限几何级数的总和（标准代数，没什么意义）并最终获得极限值（对于足够大的n):
注意熵 H(s) 如何出现在二项式恒等式中。 请注意，泰勒级数展开式 H(s)=H(Q+e2) 给出了仅考虑一阶导数并忽略所有其他导数而获得的估计。 现在让我们组合一下最终的表达式：
哪里
我们所要做的就是选择 e2 使得 e3 < e1，然后最后一项将任意小，只要 n 足够大。 因此，在通道容量任意接近 C 的情况下，可以获得尽可能小的平均 PE 误差。
如果所有编码的平均值具有足够小的误差，则至少有一种编码是合适的，因此至少存在一种合适的编码系统。 这是香农获得的一个重要结果——“噪声信道的香农定理”，尽管应该指出的是，他证明了这一点是针对比我使用的简单二元对称信道更一般的情况。 对于一般情况，数学计算要复杂得多，但思想并没有那么不同，所以很多时候，通过特定情况的例子，你可以揭示定理的真正含义。
让我们批评一下这个结果。 我们反复重复：“对于足够大的n。” 但n有多大呢？ 如果您确实想要既接近通道容量又确保正确的数据传输，则非常非常大！ 事实上，如此之大，以至于您将不得不等待很长时间才能积累足够位的消息以便稍后对其进行编码。 在这种情况下，随机码字典的大小将非常巨大（毕竟，这样的字典不能以比所有 Mn 位的完整列表更短的形式表示，尽管 n 和 M 非常大）！
纠错码避免等待很长的消息，然后通过非常大的码本对其进行编码和解码，因为它们避免了码本本身并使用普通计算。 从简单的理论上讲，此类代码往往会失去接近信道容量的能力，但仍保持较低的错误率，但当代码纠正大量错误时，它们表现良好。 换句话说，如果你分配了一些信道容量用于纠错，那么大多数时候你必须使用纠错能力，即每发送一条消息就必须纠正大量的错误，否则你就浪费了这个容量。
同时，上面证明的定理仍然不是没有意义的！ 它表明高效的传输系统必须对很长的比特串使用巧妙的编码方案。 一个例子是飞越外行星的卫星； 当它们远离地球和太阳时，它们被迫纠正数据块中越来越多的错误：一些卫星使用太阳能电池板，提供约 5 W 的功率，其他卫星使用核电源，提供大约相同的功率。 电源功率低、发射器碟形天线尺寸小、接收器碟形天线在地球上的尺寸有限、信号必须传播的距离长——所有这些都需要使用具有高水平纠错能力的代码来构建有效的沟通系统。
让我们回到上面证明中使用的 n 维空间。 在讨论中，我们表明球体的几乎整个体积都集中在外表面附近 - 因此，几乎可以肯定，发送的信号将位于围绕接收信号构建的球体表面附近，即使具有相对这种球体的半径很小。 因此，接收到的信号在纠正任意大量的错误 nQ 之后，结果任意接近无错误的信号，这并不奇怪。 我们前面讨论的链路容量是理解这一现象的关键。 请注意，为纠错汉明码构造的类似球体不会相互重叠。 n 维空间中存在大量几乎正交的维度，这说明了为什么我们可以在空间中容纳 M 个几乎没有重叠的球体。 如果我们允许小的、任意小的重叠（这在解码过程中只会导致少量错误），我们就可以获得空间中球体的密集放置。 汉明保证了一定程度的纠错，香农保证了较低的错误概率，但同时保持了实际吞吐量任意接近通信信道的容量，这是汉明码无法做到的。
信息论并没有告诉我们如何设计高效的系统，但它确实为高效通信系统指明了道路。 它是构建机器对机器通信系统的宝贵工具，但如前所述，它与人类如何相互通信几乎没有关系。 生物遗传在多大程度上类似于技术通信系统尚不清楚，因此目前尚不清楚信息论如何应用于基因。 我们别无选择，只能尝试，如果成功向我们展示了这种现象的机器性质，那么失败将指向信息本质的其他重要方面。
我们不要离题太多。 我们已经看到，所有原始定义都或多或少地表达了我们原始信念的本质，但它们具有某种程度的扭曲特征，因此不适用。 传统上认为，最终，我们使用的定义实际上定义了本质； 但是，这只是告诉我们如何处理事物，并没有向我们传达任何意义。 假设方法在数学界如此受到青睐，但在实践中还有很多不足之处。
现在我们将看一个智商测试的例子，其中的定义就像你喜欢的那样循环，因此会产生误导。 创建了一个旨在测量智力的测试。 然后对其进行修改，使其尽可能一致，然后将其发布，并以一种简单的方法进行校准，以便测量的“智能”结果呈正态分布（当然，在校准曲线上）。 所有定义都必须重新检查，不仅是在第一次提出时，而且是在很久以后，当它们被用于得出的结论时。 定义边界在多大程度上适合所解决的问题？ 在一种环境中给出的定义多久会被应用到完全不同的环境中？ 这种情况经常发生！ 在生活中不可避免会遇到的人文学科中，这种情况发生得更频繁。
因此，介绍信息论的目的之一，除了展示其有用性之外，还在于警告您这种危险，或者准确地向您展示如何使用它来获得所需的结果。 人们早就注意到，最初的定义决定了你最终会发现什么，其程度比看起来要大得多。 初始定义需要您投入大量注意力，不仅在任何新情况下，而且在您长期工作的领域也是如此。 这将使您了解所获得的结果在多大程度上是同义反复而不是有用的东西。
爱丁顿的著名故事讲述了人们用网在海里捕鱼的故事。 在研究了他们捕获的鱼的大小后，他们确定了在海里发现的鱼的最小大小！ 他们的结论是由所使用的工具决定的，而不是现实。
待续...
谁想帮助翻译、排版和出版这本书 - 请写在个人信息或电子邮件中 [电子邮件保护]
对了，我们还推出了另一本很酷的书的翻译—— )
我们特别寻找 那些愿意帮忙翻译的人 。 （换乘10分钟，前20名已被占用)
本书内容和翻译章节
- 科学与工程艺术简介：学会学习（28 年 1995 月 XNUMX 日）
- “数字（离散）革命的基础”（30 年 1995 月 XNUMX 日）
- 《计算机史 - 硬件》（31 年 1995 月 XNUMX 日）
- 《计算机史 - 软件》（4 年 1995 月 XNUMX 日）
- 《计算机的历史 - 应用》（6 年 1995 月 XNUMX 日）
- “人工智能 - 第 I 部分”（7 年 1995 月 XNUMX 日）
- “人工智能 - 第二部分”（11 年 1995 月 XNUMX 日）
- 《人工智能III》（13年1995月XNUMX日）
- 《n维空间》（14年1995月XNUMX日）
- “编码理论 - 信息的表示，第一部分”（18 年 1995 月 XNUMX 日）
- “编码理论 - 信息的表示，第二部分”（20 年 1995 月 XNUMX 日）
- “纠错码”（21 年 1995 月 XNUMX 日）
- 《信息论》（25年1995月XNUMX日）
- “数字滤波器，第一部分”（27 年 1995 月 XNUMX 日）
- “数字滤波器，第二部分”（28 年 1995 月 XNUMX 日）
- “数字滤波器，第三部分”（2 年 1995 月 XNUMX 日）
- “数字滤波器，第四部分”（4 年 1995 月 XNUMX 日）
- “模拟，第一部分”（5 年 1995 月 XNUMX 日）
- “模拟，第二部分”（9 年 1995 月 XNUMX 日）
- “模拟，第三部分”（11 年 1995 月 XNUMX 日）
- “光纤”（12 年 1995 月 XNUMX 日）
- 《计算机辅助教学》（16 年 1995 月 XNUMX 日）
- 《数学》（18年1995月XNUMX日）
- 《量子力学》（19 年 1995 月 XNUMX 日）
- “创造力”（23 年 1995 月 XNUMX 日）。 翻译：
- 《专家》（25年1995月XNUMX日）
- “不可靠的数据”（26 年 1995 月 XNUMX 日）
- 《系统工程》（30 年 1995 月 XNUMX 日）
- “你得到你所衡量的”（1 年 1995 月 XNUMX 日）
- （六月2，1995） 翻译成 10 分钟的片段
- Hamming，“你和你的研究”（6 年 1995 月 XNUMX 日）。
谁想帮助翻译、排版和出版这本书 - 请写在个人信息或电子邮件中 [电子邮件保护]
来源： habr.com