解释：香农极限（2010）

这是1980年代初期，您是新兴的个人计算机市场的设备制造商。多年来，通过电话线发送数据的调制解调器一直以每秒9.6 kb的最大速率被阻塞：如果您尝试提高速率，则数据中将出现无法容忍的错误。然后，一组工程师演示了新设计的纠错码可以将调制解调器的传输速率提高25％。您闻到一个商机。是否有代码可以使数据速率更高？如果是这样，要高多少？这些代码是什么？实际上，到1980年代初，前两个问题的答案已有30多年的历史了。 1948年，克劳德·香农（Claude Shannon）SM ’37，博士’40在一份开创性的论文中提供了这些信息，该论文实质上创建了信息论的学科。麻省理工学院信息与决策系统实验室的副教授戴维•福尼（David Forney）说：“了解香农在整个科学领域工作的人们认为，这只是他们所见过的最辉煌的事物之一。”香农（Shannon）从1956年开始在麻省理工学院任教，直到1978年退休。他的研究表明，任何通信渠道（电话线，无线电频段，光缆）都可以通过两个因素来表征：带宽和噪声。带宽是可用于传输信号的电子，光学或电磁频率的范围；噪声是任何会干扰该信号的东西。给定一个具有特定带宽和噪声特性的信道，Shannon展示了如何计算可以零误差在其上发送数据的最大速率。他称该速率为频道容量，但今天，它通常被称为香农极限。在嘈杂的信道中，接近零错误的唯一方法是为传输增加一些冗余。例如，如果您尝试仅发送三个位（例如001）的消息，则可以发送三遍：001001001。如果发生了错误，而接收方却收到001011001，则她可以合理地确定正确的字符串是001。将此类其他信息添加到消息中以便可以纠正错误的方法称为纠错码。通道越嘈杂，您需要添加更多信息以补偿错误。但是，随着代码变得更长，传输速率会下降：您需要更多的比特来发送相同的基本消息。因此，理想的代码将最大程度地减少纠错的机会，同时减少额外位数。按照该标准，发送消息三遍实际上是一个糟糕的代码。由于每条消息需要三倍的比特率，因此可以将数据传输速率降低三分之二，但是它仍然非常容易出错：正确位置的两次错误会使原始消息无法恢复。但是Shannon知道可以使用更好的纠错代码。实际上，他能够证明对于任何通信通道，都必须有一个纠错码，使传输能够接近香农极限。但是，他的证明并没有说明如何构造这样的代码。相反，它依赖于概率。假设您要在嘈杂的频道上发送一条四位消息。有16种可能的四位消息。香农的证明将为他们每个人分配自己的随机选择的代码-基本上是自己的序列号。考虑这样一种情况，其中信道的噪声足以使四位消息需要八位代码。接收方像发送方一样，将具有将16条可能的四位消息与16条八位代码相关联的密码本。由于共有256个8位的可能序列，因此至少有240个未出现在密码本中。如果接收器接收到这240个序列之一，则她知道错误已蔓延到数据中。但是在16个允许的代码中，很可能只有一个最适合接收的序列，例如相差仅一个数字。香农表示，从统计学上讲，如果您考虑对邮件分配所有可能的随机码，则必须至少有一种接近香农极限。代码越长，您越接近：四位消息的八位代码实际上并不能使您非常接近，而千位消息的两千位代码则可以。当然，Shannon所描述的编码方案是完全不切实际的：对于每个可能的千位消息，具有单独的，随机分配的代码的代码簿将无法适应世界上所有计算机的所有硬盘驱动器。但是Shannon的证明提供了一种诱人的可能性，即由于必须存在容量接近代码，因此可能会有更有效的方法来找到它们。对这种代码的追求一直持续到1990年代。但这仅仅是因为我们现在所知的性能最佳的代码（已由MIT发明）被忽略了30多年。但是，这是下一期《解释的故事》的故事。