Шеннон преуспел и в области криптографии. В 1945 году он написал засекреченный доклад «Математическая теория криптографии». Во время Второй мировой войны он проанализировал работу системы X-system, которая использовалась для безопасной голосовой радиосвязи между Франклином Д. Рузвельтом и Уинстоном Черчиллем. Шеннон математически доказал, что такую схему шифрования невозможно взломать. Шеннон также играл ключевую роль в изучении передачи данных в условиях помех, как, собственно, и называлась его статья 1949 года. Он показал, как отправлять цифровые сообщения по всей Солнечной системе, чтобы избежать искажений от воздействия космического шума. Именно благодаря идее Шеннона на вашем ноутбуке можно посмотреть видео, переданное с марсохода Curiosity. На фоне столь впечатляющего списка заслуг кажется вполне естественным, что имя Шеннона связано с теоремой отсчетов. Однако сама идея ему не принадлежала, о чем Шеннон не раз упоминал[4].
«Это общеизвестный в теории связи факт, — писал он в статье 1949 года. — Теорема была первоначально дана в других формах математиками, но, несмотря на ее очевидную важность, не приводилась в литературе по теории связи».
Но «в литературе по теории связи» теорема выборки приводилась — в нужной форме и с полным доказательством — задолго до публикации статьи Шеннона. Котельников сделал это еще в 1933 году, более чем на десять лет раньше. Почему Шеннон не упомянул его? Возможно, дело в том, что статья Котельникова вышла в малотиражном издании материалов российской конференции и Шеннон просто не знал о ней. Но, как мы увидим дальше, реальную причину определить почти невозможно. Он мог узнать о теореме Котельникова в контексте секретных разработок, результатами которых СССР и Соединенные Штаты обменивались во время Второй мировой войны. Но последующие ожесточенные разногласия между сверхдержавами, скорее всего, помешали бы Шеннону обнародовать такое знание или получить к нему доступ.
Шеннон и Котельников (рис. 2.9) были лидерами в сфере цифровой связи в своих странах, особенно если дело касалось преодоления помех или шифрования. Оба удостоились высших государственных и научных наград. И оба сформулировали и доказали теорему выборки в том виде, в каком она используется сегодня.
Нельзя не задаться вопросом, оказал ли один влияние на другого. Любопытно, что Шеннон, младший из них, с отставанием на несколько лет повторял интеллектуальные достижения Котельникова, но я не нашел никаких доказательств, что Шеннон знал о засекреченных работах Котельникова. В любом случае не удивительно, что русские называют эту великую идею теоремой отсчетов Котельникова. А разве американцы не должны?
Разбрасывай и складывай
Вторая половина идеи Котельникова — великой теоремы отсчетов — объясняет, как из дискретных пикселей восстановить непрерывную картинку, причем с абсолютной точностью. Самое удивительное, что, похоже, в цифровом изображении почти нет информации — находящаяся между каждой парой пикселей бесконечность аналоговых точек просто отброшена. То же самое с цифровым звуком и каждой парой сокселей. Вторая часть теоремы отсчетов сообщает нам, где найти недостающие бесконечности.
Вот как аналоговое восстанавливается из цифрового. Распределите каждый пиксель в пространстве с помощью «разбрасывателя», ключевой формы этой главы. Сложите результаты. Вот и все. Теорема отсчетов утверждает, что этот процесс «разбрасывания» и сложения полученных результатов точно воспроизводит недостающие бесконечности между пикселями! Как и в случае с другими великими математическими теоремами, такие выводы вовсе не очевидны. Мы должны верить математике.
Здесь нам снова поможет пример с волной, но для простоты мы возьмем только два центральных сокселя (рис. 2.10). (Чуть позже от них мы перейдем к пикселям.) Напомню, что соксель — это отсчет для кривой, изображающей аналоговый звук, а ее высота над нулевой линией обозначает его громкость. Таким образом, высота сокселя представляет собой громкость звуковой волны только в той точке, где сделан этот отсчет. Соксель справа будет менее громким, чем тот, что слева.
Рис. 2.9
Сначала мы разберемся с левым сокселем при помощи «разбрасывателя», изображенного на рисунке 2.1. Напомню, что его колебания той же частоты, что и у волны Фурье с самой высокой частотой исходного фрагмента. Его максимальная амплитуда на центральном выступе соответствует максимальной громкости. Для выполнения операции «разбрасывания» заменим левый соксель копией разбрасывателя (рис. 2.11). Я люблю говорить, что это «разбрасывание» превращает соксель из отсутствия формы (ничего) в показанную на рисунке форму (нечто). Его самая высокая точка — вершина центрального горба — имеет ту же громкость, что и соксель, который он заменяет. Два сокселя показаны пунктиром. В частности, из рисунка видно, что высота разбрасывателя — его максимальная громкость — соответствует высоте левого сокселя. В нашем примере она составляет 80 % от полной громкости. Представьте, что у вас есть переключатель для ее регулирования.
4
После снятия грифа секретности доклад был переработан в статью, опубликованную в 1949 году под названием «Теория связи в секретных системах» в Bell System Technical Journal. —