Искусство большего. Как математика создала цивилизацию - Майкл Брукс

него, поскольку на следующие три месяца Галлагера отправили тянуть лямку на должности охранника в военной тюрьме. Впрочем, тот этому только обрадовался: “Делать мне было нечего, и все время я посвящал научным изысканиям и решению задач, – вспоминает он. – Среда там располагала к академической работе гораздо более любой из тех, в которых я оказывался впоследствии”.

Это вряд ли так, поскольку после увольнения из армии Галлагер устроился на работу в MIT. Там ему в голову и пришла идея корректировать ошибки с помощью “кода с малой плотностью проверок на четность”[228]. При использовании этой схемы биты, переносящие данные, сопровождаются “четными” битами, которые выполняют защитную функцию, почти как надпись “верх” на коробках при переезде. Увидев, что коробка стоит вверх ногами, вы проверите, не повредилось ли ее содержимое. Точно так же, если четные биты искажены, нужно проверить и биты данных. Это сложно – настолько сложно, что в то время ни у кого не было для этого достаточной вычислительной мощности, – но позволяет почти достичь предела Шеннона при передаче данных.

Изобретение Галлагера не применялось и впоследствии забылось. Но в 1993 году два французских специалиста по телекоммуникациям опубликовали идею, которую назвали турбокодами. Эти коды работали по схожей схеме с проверкой на четность, предложенной Галлагером, и давали схожие результаты. Сходство было настолько сильным, что в 1996 году оно натолкнуло двух ученых на воспоминания. Рэдфорд Нил и Дэвид Маккей откопали диссертацию Галлагера и обнаружили, что применение кода с малой плотностью проверок на четность уже возможно, а патент на него уже истек. Зачем платить за использование французских турбокодов, когда изобретение Галлагера доступно бесплатно? Несомненно, именно так и решили многие конструкторы, включая тех, которые внедрили стандарт 802.11 для Wi-Fi, наладили спутниковое вещание множества телеканалов и создали программу Skype для видеосвязи[229].

Справедливости ради отмечу, что кое-кто все же решил заплатить за использование турбокодов. Например, они применяются в технологиях мобильной связи 3G и 4G и для защиты данных, передаваемых с Марсианского разведывательного спутника (МРС), запущенного NASA в 2005 году и по-прежнему остающегося на связи с Землей. Предполагается, что МРС станет первым звеном в сети, которую в NASA называют “межпланетным интернетом” и которая будет передавать сигналы с множества международных космических кораблей, улетающих все дальше в Солнечную систему[230]. Турбокоды также используются в Сети дальней космической связи, куда входят радиостанции, играющие важнейшую роль в коммуникации со многими межпланетными космическими кораблями NASA. Теперь, когда скорость связи приблизилась к пределу Шеннона, это может показаться прозаичным, но в момент публикации теории, лежащей в основе турбокодов, никто не верил, что такое вообще возможно. Всерьез их приняли лишь тогда, когда у скептиков не получилось доказать, что они не работают.

При этом скепсис был вполне обоснован. Не было никакого математического подтверждения тому, что турбокоды окажутся функциональными. Как и код с малой плотностью проверок на четность, предложенный Галлагером, они были инженерным решением: набором инструкций, в котором не объяснялось, почему соответствующие действия дадут нужный результат. Хотя оба кода позволяли приблизиться к пределу Шеннона, на математиков их работа особого впечатления не производила. А вот с “полярными кодами”, родившимися в голове Эрдала Арыкана, все обстояло иначе.

Арыкан – турецкий профессор электрической и электронной инженерии. В 2008 году он работал над алгоритмом декодирования информации и понял, что используемые им техники можно также применить для достижения предела Шеннона. У него ушло два года на проработку деталей, но теперь эти техники используются в новейшем протоколе шифрования мобильной связи в цифровых сетях. Этот протокол пятого поколения (5G) называется стандартом передачи данных 5G NR (New Radio, “новое радио”). Приятно, что он работает параллельно с проверками на четность Галлагера, предложенными в 1960 году и также входящими в стандарт передачи данных 5G[231]. 5G – чудесная вещь: в ней плечо к плечу работают математика “бумеров” и математика “зумеров”.

Секретная служба Шеннона

Иметь математически доказуемую схему для коррекции ошибок неплохо, но вовсе не обязательно. Как выяснили первые пользователи турбокодов, если система работает, этого вполне достаточно. Но есть в теории информации такая область, в которой без математических доказательств никак не обойтись. Это криптография.

Криптографию – науку о шифровании и дешифровании секретных сообщений – можно, пожалуй, назвать самым недооцененным разделом математики. Наша свобода и наше благополучие зависят от нашей способности обеспечивать конфиденциальность связи. В конце концов, конфиденциальность имеет принципиальное значение как в работе правительства, так и при совершении покупок в интернете. Она лежит в основе безопасного мобильного банкинга, который позволяет фермерам в Руанде вести дела и зарабатывать на жизнь. Она играет ключевую роль при подготовке облав на торговцев кокаином, помогая колумбийским агентствам по борьбе с оборотом наркотиков проводить операции. Разоблачителям, которые пытаются привлечь внимание к проблеме коррупции, нужно шифровать свою переписку в мессенджерах. Шифрование – важнейший ресурс, который сродни кислороду информационной эпохи.

Полученный во время войны опыт быстро подсказал Шеннону, что математика теории информации может показывать, насколько хорошо – или плохо – будет работать система шифрования. В 1949 году он изложил свои идеи в статье “Теория связи в секретных системах”, которая представляла собой переработанную версию засекреченного документа, составленного им в 1945 году[232]. В статье разбирается ситуация, когда “сообщение, подлежащее шифрованию, состоит из последовательных дискретных символов, каждый из которых выбран из некоего конечного множества. Эти символы могут быть буквами или словами некоторого языка, амплитудными уровнями «квантованной» речи или видеосигнала и так далее”. Шеннон отметил, что секреты, зашифрованные символами, – в отличие от тех, что скрываются с помощью невидимых чернил или шифруются с применением специальных технологий, например аппарата, способного в обратном порядке воспроизводить записанную речь, – можно проанализировать математически. Но главное – он продемонстрировал, что математический анализ может показать, есть ли вообще смысл взламывать шифр. Иными словами, он вывел математику криптоанализа и того, стоит ли игра с шифром свеч.

Это невероятно важно, поскольку говорит вам, куда лучше всего направить свои силы. Если следовать указаниям Шеннона, можно изменить ход истории, как показывает Специальное донесение о шифре “Фиш”.

Оно было отправлено в военное министерство США в декабре 1944 года под грифом “совершенно секретно” и содержало свежие данные о том, как обстоят дела с получением доступа к зашифрованным сообщениям, которые немецкие радисты отправляли во время Второй мировой войны[233]. Британские криптографы прозвали этот канал связи “Фиш”. Донесение составил Альберт Смолл из войск связи армии США, которого командировали в британский шифровальный центр в Блетчли-парке, чтобы помочь коллегам