Коды – от Клода Шеннона до наших дней

Григорий Кабатянский Наташа Четверикова/Полит.ру

Публикуем стенограмму и видеозапись лекции Григория Анатольевича Кабатянского, доктора физико-математических наук, главного научного сотрудника Института проблем передачи информации РАН, профессора отделения прикладной математики и информатики НИУ-ВШЭ, с которой он выступил 13 марта 2014 года в рамках цикла «Публичные лекции «Полит.ру».

Текст лекции

Спасибо за приглашение, здравствуйте. Я постараюсь говорить понятно и увлекательно. Во всяком случае, предпосылки для увлекательного рассказа есть. Во-первых, коды, это что-то такое, что мы знаем еще из «Шерлок Холмса» Конан Дойля из его рассказа «Пляшущие человечки». А сегодня мы знаем это через Эдварда Сноудена и крики телевизора о том, что даже Ангелу Меркель подслушивают. Одна из целей моей лекции объяснить, что коды бывают разные, по крайней мере, три разных вида. Все они называются кодами.

Вторая интрига. Первым в названии лекции стоит Клод Шеннон. Мне не повезло поговорить с ним лично – я начал ездить за границу в начале 1990-х годов, когда он был еще жив, но уже никуда не выезжал, у него была болезнь Паркинсона. А мне очень хотелось познакомиться с гением. В своем интервью я сказал, что считаю его последним универсальным гением XX века. Интересно посмотреть на его судьбу. Когда он был школьником, то показывал всяческую одаренность, но он не был таким вундеркиндом как Джон фон Нейман или Норберт Винер.

Шеннона на Западе называют громким именем «отец цифровой эры». Некая направленность «в свое будущее» у него была с самого начала. Он, будучи подростком, сделал «беспроводной телеграф», чтобы общаться со своим приятелем, который жил в миле от него. Так что можно заодно его назвать отцом беспроводной связи. Некая интрига, которая кроется здесь, что, когда он учился, он получал, в свое время, степени бакалавра, магистра и PhD в математике и electrical engineering. Но американские математики его не признали. То есть когда вышли его работы конца 1940-х, то американцы его не признали.

Признали его советские математики. Начало этому положил Андрей Николаевич Колмогоров, которому его идеи очень понравились. Здесь мой рассказ близко примыкает к лекции Александра Шеня. Некоторые работы Колмогорова 1950-60-х годов были вдохновлены результатами Шеннона. А теперь я буду идти по слайдам, и постараюсь говорить, и не очень мучить вас математикой.

Здесь я написал, какие есть значения у слова «код». Одно – это «криптография», то есть, как написать ваше сообщение в таком виде, чтобы получатель мог прочитать, а никто другой не мог. Это нам всем так или иначе знакомо. У Шеннона есть основополагающая работа 1949-го года «Теория связи в секретных системах», на самом деле, она написана в 1945-м году или раньше. Это был такой отчет. Во время войны Шеннон работал, естественно, на оборонку, рассекретили этот отчет через четыре года. Как любят писать, эта работа Шеннона превратила криптографию из искусства в науку. Здесь, пожалуй, единственное место, где он предмет не «дожал». Он мог бы пойти и дальше, через сложность вычислений, он это очень хорошо понимал, но остановился на некоем красивом математическом месте и дальше не стал развивать эту науку.

Второй значения слова «код» – этот средство экономного представления («сжатия») информации. Из прежней жизни для нас такой пример - это азбука Морзе. Из сегодняшней: когда мы что-то архивируем на своем компьютере, то мы чаще всего пользуемся кодом Зива-Лемпеля-Велча или какой-то его очередной модификацией. Начало этому положил опять-таки Клод Шеннон в эпохальной работе «Математическая теория связи» 1948-го года. Там он, в том числе, доказал теорему о потенциальных возможностях «сжатия» информации. Насколько мы можем сжимать информацию при условии, что мы хотим ее точно восстановить. Он пошел дальше: а что, если мы хотим восстанавливать «почти» точно?

И третье, что мне ближе всего, это «код как средство обнаружения и исправления ошибок при передаче информации или при ее хранении». Поначалу люди хотели, чтобы и при обработке можно было исправлять ошибки и их обнаруживать. И были такие попытки при исправлении ошибок в работе сумматора, но оказалось, что для этого дела коды не очень хорошо приспособлены. Но код «с проверкой на четность» – это то, что было уже в самых первых вычислительных машинах (ЭВМ). Машины были огромные и очень ненадежные.

Это потом окажется очень полезным для возникновения теории кодирования. К информации из 7 бит добавлялся 8-ой бит так, чтобы целиком в этих 8-ми битах число единичек было четное (это и есть проверка на четность). Поэтому, если в ЭВМ происходила одна ошибка, то вы исправить ее не могли, но, по крайней мере, видели, что ошибка произошла. И вот в таких древних машинах звучал сигнал тревоги, и когда я учился на военной кафедре в МГУ, то даже такую машину видел, и ее «кормили» перфокартами.

Видеозапись лекции:

Это три темы, о которых я сегодня хочу рассказать. Давайте начнем по порядку, с Шеннона и криптографии. Есть теорема Шеннона, которая называется теорема об идеальном шифре. Она и написана на слайде, там объяснено что такое «одноразовый блокнот».

Много пропущено в этом слайде. Вы хотите обменяться информацией с другим человеком. Здесь есть два разных подхода. Первый подход, что у вас уже есть некая общая секретная информация, которую знаете только вы, и не знает больше никто. Это та задача, которую рассматривал Шеннон, поскольку во время войны он работал в области криптографии. И это то, что больше всего любят в военных приложениях. Есть общая секретная информация, которая называется «ключ», и, с помощью этого ключа тот, кто посылает, превращает имеющееся сообщение во что-то другое, что приемник получив, может снова восстановить исходное сообщение, а вот все другие должны ничего не узнать о сообщении из того, что они перехватят по каналу.

Простейший такой способ, и он здесь описан, называется «одноразовый блокнот». Выглядит он так: информация у нас записана из «0» и «1», это наши сообщения, которые мы хотим передать. Ключ – это случайная последовательность из «0» и «1», но одинаковая в том смысле, что случайно одинаковая и у меня, и у того, кто получает информацию. Например, какое-то физическое устройство ее породило, «0» и «1», независимо друг от друга появляются с вероятностью 1/2.

Мы эту информацию записали, и каждый у себя ее положил в карман. Это, конечно, недостаток. Если вспомнить старые книги о шпионах, то у шпиона обязательно был томик кого-нибудь, в зависимости от того, откуда он был или в какой стране он жил, томик Пушкина или томик Гейне, и надо было просто в соответствующий день открыть соответствующую страничку, это и был ключ, который там написан. Ну а потом, когда приходили его брать, то смотрели книжку, которая наиболее часто читалась. То есть частое чтение книг тоже бывает вредно для делаJ.

Кодирование или шифрование состоит в том, что мы складываем сообщение и ключ, которые у нас есть. Мы складываем «0+1=1», «0+0=0», «1+1=0», чтобы остаться в системе нулей и единиц. Тогда у нас получится некая новая последовательность нулей и единиц, и она передается по каналу. Тому, кто получает, просто: он достает бумажку из кармана, на которой написана последовательность-ключ, и снова складывает с тем? Что пришло из канала. Складывает по модулю «2», как говорят математики. То есть, когда один плюс один равно нулю. Вначале мы к сообщению прибавили ключ, поэтому, сложив второй раз, мы его убрали, так как «1+1=0». То есть, по модулю два что сложить, что вычесть, - это одно и тоже. Если бы мы хотели строить такую же систему для десятичного алфавита, то надо было бы ключ вычитать (но по модулю 10). А здесь мы просто складываем. С легальным пользователем все просто, он, действительно, взял, сложил и получил наше сообщение.

Почему никто третий ничего не узнает о содержимом сообщения, не зная ключа? Я постараюсь это объяснить. Эти сообщения живут на трехмерном кубике, состоящем из нулей и единиц. Если это поможет представить. Это трехмерный кубик, у него восемь вершин, на них написаны «0» и «1». Наш ключ – это случайная последовательность, то есть если мы хотим что-то передать, то случайно выбираем точку на кубике. Поскольку кубик трехмерный, то я получу три бита информации, и сложу их. Все точки для меня одинаково устроены, я любую из них выбираю одинаково вероятно, значит, с вероятностью 1/8. Я выбрал, и теперь складываю со своим сообщением. Но сложение с сообщением означает, что картинка, которая у меня была на кубике (там стояли точки с приписанными вероятностями), теперь подвинулась.

Если бы картинка была бы неравномерной, например, если бы нули появлялись с вероятностью 0.99, зато единички появлялись бы с вероятностью 1/100, то при такой «подвижке» мы бы все сразу увидели. Но здесь все точки одинаково вероятны, поэтому, подвинув картинку, она остается той же самой.

Это означает, что на выходе канала нелегальные пользователи видят одну и ту же «картинку», независимо от передаваемого сообщения. Они видят случайно появляющиеся последовательности последовательность из нулей и единиц. И это никак не зависит от того, с чем это складывалось. Это первая часть теоремы Шеннона, которая говорит, что одноразовые блокноты – это идеальные криптосистемы. Говоря на языке теории вероятностей, это означает, что апостериорная вероятность равна априорной, то есть мы ничего не узнали.

Вторая часть теоремы Шеннона несколько более сложная, она говорит, что если мы захотим сделать так, чтобы ничего о сообщении не узнавалось, то лучше, чем этот одноразовый блокнот, мы не сделаем. Это будет означать, что длина ключа должна быть не меньше, чем длина сообщения.

Почему называется «одноразовый блокнот»? Мысль простая. Мы написали этот ключ на листке блокнота. Использовав его, вы листочек отрываете и выбрасываете, возможно, пропускаете через шредер. В статье википедии про одноразовый блокнот написано, что все знали, что его надо использовать именно таким образом. Но после войны советские шифровальщики все-таки использовали ключ несколько раз, и поэтому их сообщения удавалось раскрывать. Понятно, что будет плохого, если я один и тотже ключ использую два раза. Я получу одно зашифрованное сообщение Х, затем другое сообщение Y, сложу их. Ключи, как я говорил, уничтожатся, и я получу сумму сообщений «М + М’». Я не могу получить ни одно из сообщений, но сумму я их знаю, это уже довольно много.

Но что делать, если у нас нет общего «ключа»? Эту задачу Шеннон почему-то «пропустил», может быть, потому что он был математиком и инженером в одном лице, и он не решал задач, которые не стояли « в повестке дня». Но буквально через 15-20 лет появляются первые компьютерные сети, в них много пользователей и люди начинают понимать, что общий ключ это очень неудобно. Тогда и была придумана так называемая, public key cryptography, то есть криптография с открытым ключом. Современная криптография живет, в основном, в этом мире. То есть криптография с секретным ключом, иногда ее называют ее традиционной, в стиле Шеннона, все еще существует, но после Шеннона там особенно нечего было делать. У него было такое свойство «закрывать задачи».

Когда говорят, что «Шеннон – отец цифровой эры», это не совсем точно, там есть и другие «отцы», но точно, что он единственный отец теории информации. «Теория современной информации вышла из его головы как Афина Паллада в полном боевом облачении», – так написано в одной статье о математической теории связи.

Многие вещи, которые Шеннон сделал, теперь общие для инженеров, для инженеров с математическим образованием, просто для математиков. В частности, это принцип блочного построения системы. Он говорил так: допустим, мы хотим передавать сообщения по каналу связи, мы хотим это делать надежно и быстро. Давайте разобьем эту задачу на подзадачи. Первая подзадача: информацию мы хотим передавать эффективно, то есть затратив поменьше бит. Поэтому давайте мы для начала представим информацию экономно, настолько экономно, насколько можно. А после того, как мы ее экономно представим, давайте мы ее будем передавать так, чтобы мы могли бороться с помехами, которые есть в любом реальном канале. Это уже будет вторая подзадача. Кстати, на русском языке есть классическая книга «Борьба с помехами», это редкий случай, когда русский язык звучит более выразительно, чем английский. Ну а если мы захотим, чтобы нас не подслушали, то это будет уже третья подзадача.

Шеннон предложил вероятностную модель описания сообщений. Допустим у вас есть газетный текст, но что с ним делать, как описать его закономерности? Есть алфавит, есть буквы, знаки препинания, как это все поместить в одну математическую модель? Он предложил делать это понемногу, по кусочкам, начать с простой модели, когда есть множество сообщений.

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

Дальше мы довольно хорошо понимаем, что мы должны делать. Буквы, которые появляются часто, им нужно ставить в соответствие короткие последовательности из нулей и единиц. Ну а буквы, которые появляются редко – на них уже, что останется. Вопрос, что останется? Это называется однозначное декодирование: если мы получим теперь последовательностей из нулей и единиц, то мы должны суметь ее «разрезать» на куски, и однозначно установить, какие же там были буквы.

Шеннон сразу предложил такой способ однозначного декодирования – префиксные коды. Когда мы каждой букве ставим в соответствие слово из нулей и единиц, а эти слова обладают тем свойством, что ни одно слово не является началом другого. Тогда понятно, как нам нужно «резать» нашу выходящую ленту из нулей и единиц. Мы берем и смотрим, начиная с первых двоичных символов (битов), которые появляются, а вдруг это уже слово из нашего словарика, слово из нулей и единиц? Если нет, то добавляем следующий бит и т.д. Когда появилось первый раз слово-буква, то мы эту последовательность из нулей и единиц от общей последовательности отрезаем. Продолжаем «отрезание» дальше.

Ясно, что этот процесс однозначный, если бы кто-то пришел и сказал, что это другая последовательность букв, то мы бы ему ответили: как же это может быть другая? Давайте посмотрим на вашу последовательность, какая у вас первая буква? Если соответствующее ей двоичное слово длиннее слова для нашей первой буквы, то этого не может быть, потому что тогда наше слово является началом вашего. А если же оно короче слова для нашей первой буквы, то опять невозможно, потому что теперь ваше слово является началом нашего.

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

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

Здесь появилась знаменитая формула, что энтропия источника это сумма логарифмов величин, обратных к вероятностям появления букв источника. И эта теорема Шэннона говорила инженеру, что как ни старайся, но «сжать» источник до средней длины, меньше чем энтропия, не получится. С другой стороны, он тут же предложил некий асимптотически оптимальный способ кодирования, у которого средняя длина стремится к энтропии источника, если вы будете кодировать выход источника не по одной букве? А сразу по многим. А именно, если кодировать побуквенно, то можно достичь энтропию «+1». А вот если вы будете от своего источника сообщения собирать слова какой-то большой длины, то там будет стоять та же самая энтропия "+1", но поделенная на длину слова, то есть «излишек» будет стремиться к нулю. То есть можно подходить все ближе и ближе к энтропии как только вы рассматриваете все более длинные слова.

Здесь уже появляется Андрей Николаевич Колмогоров. Он задал естественный вопрос. Всё, что делалось в работах того времени делалось в предположении, что статистика источника известна, в том числе, был придуман написали оптимальный код Хаффмана. Колмогоров спросил, а что делать, если мы знаем, что источник такой, что у него буквы появляются независимо, но мы не знаем, с какими вероятностями. Я думаю, что Андрей Николаевич знал и ответ, и как его получить, но оставил задачу для других, для учеников.

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

То есть, если мы знаем статистику источника, то у Шеннона получалась энтропия «+1» поделить на длину тех последовательностей, которые мы забираем из источника. А в универсальном кодировании « излишек» вырастет в логарифм раз. Конечно, это побольше, но не намного. Первое продвижение в этой задаче было получено Фиттингофом, потом значительные усовершенствования внесли Р.З. Кричевский, Ю.М. Штарьков, Б.Я. Рябко, а на Западе – Т. Ковер и изобретатель арифметического кодирования Дж. Риссанен

Юрий Михайлович Штарьков, сотрудник ИППИ РАН, недавно написал замечательную книгу на тему универсального кодирования. Есть и другие приложения универсального кодирования, не только сжатие информации. Так, в криптографии очень важным является вопрос о том, насколько «случаен» тот или иной датчик псевдослучайных чисел. Борис Яковлевич Рябко, ректор Новосибирского университета телекоммуникаций, первым предложил использовать для тестирования алгоритмы универсального сжатия. А именно, если выход датчика можно заметно сжать, значит датчик не очень случаен (обратное, вообще говоря, неверно).

Следующее приложение еще более любопытное – атрибуция литературных текстов. Здесь работает следующий естественный подход: берутся разные авторы, берутся их тексты, и сжимаются. И оказывается, у разных авторов разная степень сжатия. Это особенно любопытно, если на вход такой программы запускать текст, который состоит из двух разнородных текстов: один текст от одного автора, другой текст от другого автора. Текст идет, и программа говорит, что это все один и тот же автор, потом затихает на время и говорит, что пошел другой автор. Даже полнометражный документальный фильм сняли «Шекспир против Шекспира» по идее профессионального математика М.Б. Малютова.

Это на самом деле это очень популярная вещь и в теории вероятностей, только под названием задача о разладке, когда мы хотим находить момент перехода с одного распределения вероятностей на другое. Приложений тут очень много, например, отток клиентов из банков или если кто-то украл карту, меняется стиль того, что он покупает, с какой частотой он покупает и т.д. То есть мы хотим понять, что что-то «не то» произошло. Еще это все очень близко к предсказательному моделированию – есть на Физтехе лаборатория Премолаб, созданная в рамках мегагрантов, которая всем этим, в том числе, занимается.

Слушатель: В кодировании используются простые числа для шифрования. Как они там используются и почему нужно очень большое число, чтобы расшифровать?

Г.К.: Действительно, я обмолвился, что была открыта криптография с открытым ключом, и люди получили за это престижную премию. Там было две группы: одна группа из двух человек придумала, как распределять ключи с помощью логарифма в конечном поле, а другая – систему шифрования, основанную на том, что разлагать целое число на простые множители видимо (это не доказано) вычислительно очень сложно. Вторая система, известная как RSA (Ривест, Шамир, Адельман), до сих пор очень популярна на практике.

В этой системе открытый ключ порождается как произведение двух больших простых числа (если числа маленькие, то систему тут же сломают), а простые числа держатся в секрете! Открытый ключ знают все, как и то, что он получен как произведение двух простых чисел. Жизнеспособность системы до сих пор базируется на том, что мы не знаем простых алгоритмов разложения числа на простые множители. Алгоритмы, которые мы знаем, имеют почти экспоненциальную сложность, то есть не допускают практическую реализацию в случае больших простых чисел.

Слушатель: Как по Шеннону определить информацию, как по Шеннону определить энтропию? Можно ли связать это математически? Потому что понятие энтропии столь многогранно, столь расплывчатое, понятие информации столь расплывчатое. Примерно сотни определений есть. По Шеннону, если две формулы написать и связать их?

Г.К.: На самом деле, определение – здесь, вот энтропия (показывает на слайды). Что сделал Шеннон, он четко указал границы, где это применять. У него в избранных трудах, переведенных на русский в начале 1960-х годов под редакцией Р.Л.Добрушина, есть статья «Теория информации и общий вагон». В каком-то смысле Шеннон протестовал против того, чтобы с помощью определения, которое он дал, мерили всё, что угодно. То есть он дал математическое определение: если у вас есть простой источник сообщений, то энтропия вычисляется так. Будет у нас другой источник, например, текущий символ будет зависеть от нескольких предыдущих символов, на три символа, тогда нам нужно будет подкорректировать определение. Прежде всего, это определение для вероятностных моделей.

Это не определение энтропии в физике, и не определение смысловой информации, которую мы можем получить из текста (не думаю, что такое определение возможно). Александр Шень в своей лекции объяснял, что задача понять, сколько в данном содержится информации, – это не очень четко поставленная задача. Можно попытаться придать ей какой-то смысл, и вот Колмогоров его придал.

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

Борис Долгин: Вы сказали о том, что Шеннон был склонен закрывать вопросы. В какой степени он же и открывал до того? Или это были ответы на чьи-то вопросы?

Г.К.: Думаю, что в повседневной научной жизни, когда уже процесс пошел, Шеннон ставил задачи себе и кругу своих учеников. У него, кстати, было много учеников, и они все превратились в хороших ученых. Но первоначальный импульс у Шеннона, как мне кажется, был из практики. Он видел задачу и решал ее.

Борис Долгин: То есть он, скорее, инженер в этом смысле?

Г.К.: В этом смысле да. А куда мы запишем Гюйгенса? Масса ученых занималась инженерными задачами. Гюйгенс разрабатывал маятниковый механизм для часов и его классический труд по механике называется «Маятниковые часы». Нужно понимать, что математика стала профессией только в XX веке. Еще у Гильберта были ученики-любители. Еще пример: это основатели и первооткрыватели математического анализа Ньютон и Лейбниц. Про Ньютона более-менее знают, что он закончил жизнь главой Центробанка Великобритании. Но он собирался стать священником, так и поступал в Кэмбридж. Если посчитать суммарный объем того, что он написал про религию и про математику с физикой, так религии будет больше. Но это еще можно понять и принять.

А вот с Лейбницем, если вы не знаете, то никогда не догадаетесь. Лейбниц окончил университет в 19 лет и хотел получить искомую степень, а ему не дали, сказав, что в этом возрасте эту степень так рано не дают. Тогда он стал искать по Германии, и нашел университет, который ему дал степень по этим наукам. Что же это были за науки? По этой специальности он всю жизнь и проработал. Это была юриспруденция. Она его, в основном, и кормила.

А все остальное он делал свободное от работы время. Может быть, мы именно к этому и идем с реформой науки и образования?!

Давайте продолжим. Дальше пойдет «надежная передача информации». Это была наиболее неожиданная вещь. Например, если вы говорите по телефону, и вас плохо слышно, то что вы делаете? Вы начинаете либо повторять всю фразу, либо вы каждую проговариваете буковку "'b' as in 'Bob'". На самом деле, это и есть простейшее кодирование. И этот способ повторения, в том или ином смысле, раскладывания буковки на много букв, он надежный, но нехорош тем, что вы снижаете скорость передачи по вашему каналу. Вы повторили три раза, и вы, тем самым, снизили способность передавать слова (информацию) в 3. И вот что оказалось неожиданно и с математической, и с инженерной точки зрения, что можно передавать информацию со сколь угодно малой вероятностью ошибки и при этом скорость передачи информации падает лишь в константу раз!

Я для примера рассматриваю такой простейший канал, он называется ДСК. Это двоично-симметричный канал, в котором символы искажаются друг о друга независимо с вероятностью p. То есть «0» может перейти в «1» с вероятностью p, «1» можете перейти в «0» с вероятностью p. С вероятностью «1-p» они передадутся без ошибок. И вот мы хотим передавать по такому каналу.

Если p=1/2, то мы ничего передать не можем, потому что появится «белый шум» и «одноразовый блокнот», как я уже сегодня говорил., значит, мы искажаем наш символ на выходе. То есть, при p=1/2 мы складываем то, что мы передали в канал с последовательностью, в которой нули и единички появляются равновероятно, но это рассказанный выше «одноразовый блокнот».

И мы уже убедились, что выход не зависит от входа, то есть, чтобы мы не подавали на вход, выход будет один и тот же. Поэтому мы понимаем, что p должно быть меньше 1/2. Теорема Шеннона звучит так, что для любого сколь угодно маленького e >0 существуют такие способы передачи сообщений со скоростью передачи, меньшей пропускной способности канала C, что вероятность ошибки не превышает e. Если скорость передачи < C, то вероятность ошибки будет стремиться к «0» при росте длины сообщения, и наоборот.

Если мы захотим передавать со скоростью больше, чем пропускная способность данного канала, то вероятность ошибки будет отделена от нуля. Там будет какой-то порожек для вероятности ошибки, и что бы мы ни делали, мы ниже его не опустимся. В качестве примера, пропускная способность двоично-симметричного канала равна 1-h(p). Если мы вернемся к определению энтропии, то для p=1/2 получим h(p) =1/2 log2 + 1/2 log2, и формула в этом случае говорит правду, что здесь пропускная способность «0». Если только мы сделаем p меньше 1/2, то можно надежно передавать информацию, и даже видно, с какой скоростью можно это делать. Шеннон доказал эту теорему не только для такого простого канала, а для целого класса каналов, и связал это с некоторой экстремальной задачей.

С точки зрения математики существование такой константы С это тривиально – надо взять в качестве С верхнюю грань те скоростей, для которых такая передача возможна. Нетривиальность этой теоремы Шеннона в том, что она говорит как надо вычислять С (через энтропию).

Это и является главной математической частью теории Шеннона. Первым, кто признал его работы, был А.Н. Колмогоров. Он с удивлением рассказывал, что когда он говорил американским математикам о работах Шеннона, то они разводили руки, пожимали плечами, и не понимали, что там интересного, ведь он же не математик. Колмогоров спрашивал «Почему?», а они отвечали «он теоремы не доказывает». Это тоже неправда, Шеннон доказывал теоремы. Я об этом расскажу ниже. Он, может быть, не доходил до каких-то деталей и тонкостей, но никаких ошибок у него не нашлось. А поле деятельности для математиков появилось огромное.

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

Всё это подтолкнуло Колмогорова, по крайней мере, к трем замечательным открытиям. Построение нового инварианта в эргодической теории, использование энтропии в задачах аппроксимации, и колмогоровская теория сложности. Это к тому, что не надо свысока смотреть на инженеров, тем более, если у этого инженера есть еще и Ph.D. по математике, вдруг там что за этим кроется.

Теперь я расскажу немножко про коды, исправляющие ошибки. Я пропустил, что такое скорость передачи, не сказал, как исправлять ошибки. У Шеннона все это было, но было в таком странном виде, возможно, это послужило причиной отторжения у математиков того времени. Он доказывал, что существуют такие методы передач. Если бы он построил такой метод, наверное, не было бы такого отторжения. Но он же не так доказывал, так до сих пор и не умеют доказывать. А он говорил, что не предъявит конкретный способ передачи, но вместо этого предъявит класс способов передачи, и докажет, что, в среднем, они все хорошие.

Это означает, что вы можете из этого класса способов передачи вытащить любой, как фокусник зайца из шляпы, и он, с вероятностью, близкой к единице, окажется хорошим. То есть мы не можем предъявить какой-то очень хороший или очень плохой объект, но мы можем доказать, что все объекты, в среднем, вот такие. В математике считается, что этот метод изобрел Пауль Эрдёш, которого часто называли «Эйлером нашего времени». Но если посмотреть на даты, то Шеннон сделал это раньше, а метод, конечно, тот же самый.

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

После войны релейные схемы были безумно популярно, так как компьютеров еще не было, а релейные схемы уже были, и люди делали на них разные устройства, которые реализовывали те или иные, теперь уже не непрерывные, как до войны, а дискретные функции. Возник вопрос, как сделать схему проще, чтобы там было меньше элементов. Было непонятно самое главное, что мы сможем этим добиться? Вот у нас есть Булева функция М-переменных, сколько нам понадобится этих элементов, чтобы эту Булеву функцию реализовать в самом лучшем случае, минимальной? И люди верили, что будет сравнительно несложно, что хватит какого-то полинома от числа переменных.

И вдруг Шеннон доказал, что нет, это минимальная сложность ведет себя как 2 в степени число переменных, поделенное на число переменных. Как он доказал? Вы думаете, он предъявил функцию, которая так плохо реализовывалась? И сегодня мы не умеем этого делать, увы. Лучшее, что мы умеем доказывать, так это квадрат от числа М переменных.

А Шеннон доказал свою формулу довольно просто. Каждой релейной схеме соответствует некоторый граф, а число его вершин и есть сложность реализации. Далее Шеннон сравнил число графов с данным числом вершин с тем сколько есть Булевых функций от М переменных ив се получилось! Такой трюки он придумал первым.

А Хэмминг зашел с другой стороны, он дал первую конструкцию оптимального кода, который исправляет первую ошибку. У этого изобретения интересная история. В конце 40-х годов (прошлого века) Хэмминг занимался численными методами и работал над атомным проектом. Вычислительные машины тогда были большие, ламповые и крайне ненадежные. Поэтому использовался простенький код с обнаружением ошибок, который, если что-то происходило, то выдавал сигнал тревоги. Если сигнал звучал, то тот кусок, где он прозвучал, запускали заново, с того момента, который записали. Но этот сигнал не работал по выходным, а Хэмминг по выходным много работал.

Когда он увидел, что результаты работы пропали, то стал думать, что если можно обнаружить ошибки, то почему бы их и не исправить. Он придумал первый пример, называемый теперь кодом Хэмминга, который породил целую науку под названием теория кодирования. Хэмминг написал книги и по численным методам, и по теории кодирования, но его лучшая работа - это статья на трех страничках 1950 года. В ней он не только построил код, но и ввел понятие двоичного пространства, которое также называется в его честь.

Это пространство последовательностей из нулей и единичек, а расстояние в этом пространстве определяется как число позиций, в которых две последовательности отличаются. Американское научное общество IEEE присуждает золотую медаль им. Хэмминга (the IEEE Richard W. Hamming Medal) за лучшие работы в области теории кодирования. Из советских и российских ученых такую медаль получали Марк Семенович Пинскер и Владимир Иосифович Левенштейн. Первым получателем этой медали был сам Ричард Хэмминг. Я думал, что код Хэмминга это его основное достижение. Но нет, оказалось, что он еще и основатель ACM – Ассоциации по вычислительной технике (Association for Computing Machinery).

Итак, код - это синоним произвольного подмножества пространства Хэмминга. Обычно нас интересует диаметр подмножества, то есть насколько далеко разбросаны его элементы. А здесь – нас интересует противоположная характеристика, и мы спрашиваем, а как близко точки кода могут подойти друг к другу. Минимальное из попарных расстояний и называется расстоянием кода. Слайд.

Код исправляет Т-ошибок тогда и только тогда, когда его расстояние больше, чем 2Т. Почему это так? Мы что-то передаем по каналу, это не произвольные последовательности из 0 и 1, а только последовательность из этого кода. Их миллион, или миллиард, мы их пронумеровали, и когда появляется сообщение с номером 537, то мы вытаскиваем его из кодовой книжки и передаем его в канал.

Почему мы можем исправить Т-ошибок, если минимальное расстояние больше, чем 2Т? Т-ошибок изменят слово в не более, чем Т-позиций, то есть кодовое слово – это начало, центр, а то, что получается в результате ошибок, это шарик в этой метрике радиуса Т. Другое кодовое слово – другой шарик радиуса Т.

Будет плохо, если шарики пересекутся, потому что в точке пересечения мы не будем знать, передавался один центр или другой центр. Но при этом условии шарики радиуса Т пересечься не могут, потому что у нас есть неравенство треугольника. Если расстояние между ними (центрами) 2Т+1, то шарики радиуса Т не пересекаются. Это равносильно тому, что код исправляет ошибки просто потому, что шары радиуса Т с центрами в словах кода не пересекаются.

На языке математики это означает, что нас в этом метрическом пространстве интересуют плотные, а лучше плотнейшие упаковки шаров. То есть как туда «напихать» побольше шаров так, чтобы они не пересекались? Дальше Хэмминг понял, что строить произвольное множество с такими свойствами будет сложно, и решил ограничиться линейными подпространствами, рассматривая пространство всех последовательностей длины n как n–мерное векторное пространство над полем из двух элементов (поле вычетов по модулю 2). Тогда линейный код можно определить как множество решений системы линейных уравнений. Понятно, что если у меня всего N переменных, а уравнений R, то решений у меня будет 2 в степени (N - R), или больше, если среди уравнений есть зависимые.

Сам код Хэмминга устроен очень просто. Его длина выглядит как 2 в степени R минус 1, а показатель R - это число уравнений, задающих код. Матрица коэффициентов соответствующей системы линейных уравнений имеет простой вид. Ее столбцами являются все двоичные векторы длины R, кроме чисто нулевого. Теперь понятно, что когда происходит одна ошибка, то вы берете принятое из канала слово, подставляете его в систему линейных уравнений, и то, что у вас получается в правой части, это в точности столбец, где произошла ошибка.

Собственно, Хэмминг сразу построил алгоритм декодирования, то есть исправления ошибок. Замечательная вещь в этом коде заключается в том, что если посмотреть на шарики, то они заполнят все пространство без дырок. Есть центр шарика, сама точка, и N-координат, по каждой координате можно изменить позицию. Значит, N плюс одна точка в шарике. Но N+1=2 в степени R. А решение у нас было 2 в степени N-R, вот все и сошлось. Мы заполнили все без дырок.

Такие упаковки называют плотными, или совершенными. Оказалось, что есть еще два совершенных кода, придуманных Голеем. Если работа Хэмминга 1950-го года, то работа Голея 1949-го года. О работе Хэмминга знали, она циркулировала, Голей уже опирался на нее. А Хэмминг не публиковал и ждал, пока получит патент – таким прагматичным был человеком. Когда он получил патент, тогда и опубликовал свою статью.

Итак, есть два замечательных кода Голея, двоичный и троичный. Удивительная вещь, что хорошие конструкции используются не раз и возникают не раз и в математике, и в жизни. Оказалось, что троичный код до Голея придумал какой-то финн (извините, забыл фамилию), который хотел выигрывать в «спортлото» по угадыванию результатов футбольных матчей. Там важен не счет, а только результат матча: 0 – ничья, 1 – проигрыш, -1 – выигрыш. Его интересовало, какие результаты поставить в таблицу исходов так, чтобы покрыть все пространство возможных результатов с точностью до возможно неправильного угадывания двух матчей. Оба кода Голея востребованы в математике, потому что с их помощью проще всего построить известную решетку Лича и связанные с ней огромные простые группы. Отмечу, что в начале 1970-х было доказано, что других совершенных кодов нет – результат, которым теория кодирования может гордиться.

Удивительная вещь: какие-то простые, на первый взгляд, вещи, долго не решаются. Люди доказали, что шариками радиуса 2,3,4 и т.д. нельзя плотно запаковать пространство, кроме двух кодов Голея. А про шарики радиуса 1 неизвестно. И здесь такая странная вещь: казалось бы, при чем здесь теория чисел? Она здесь вылезает. Есть гипотеза, что таких плотных упаковок нет, если алфавит нашего кода не равен степени простого числа. Если же он степень простого числа, то из алфавита можно сделать конечное поле и применить обобщенную конструкцию Хэмминга.

И, наверное, последняя тема, связанная с кодами, это коды в дискретной геометрии. Одна из моих идей данной лекции состоит в том, что обмен между чистой математикой и прикладной математикой – это не движение в одну сторону. Представление, что люди из чистой математики приходят в прикладную, решают задачу и уходят, неверно. Так, математические задачи приходят с другой стороны, со стороны приложений. Если посмотреть на историю математики, то есть периоды, когда новые задачи возникали не только из «внутреннего» математического любопытства; но есть и обратные периоды, как, например, Средние века, когда основные математические достижения были мотивированы именно приложениями.

Есть и другое движение – когда прикладная математика привносит новые идеи в «чистую» математику. Как связать коды и дискретную геометрию? Давайте сделаем очень простое преобразование. Допустим, у нас есть двоичные коды, последовательности из «0» и «1» длины N. Давайте «0» заменим на «1», а «1» заменим на «-1». Тогда коды «переедут» из Булева кубика на сферу с центром 0 в евклидовом пространстве. Следующее очевидное соображение – как посчитать скалярное произведение между евклидовыми векторами через расстояние Хэмминга. Получится, что оно равно N–2D, где D – расстояние Хэмминга.

Если мы построили хороший код, то он дает нам какое-то хорошее расположение точек в пространстве. Оказалось, что если технику, которая уже была развита в теории кодирования, применить к задаче о плотной упаковке шаров в евклидовом пространстве, то можно улучшить то, что в математике стояло так долго и незыблемо.

Что же именно? Мы упаковываем шары одного радиуса в n–мерное пространство, и смотрим, какая доля заполняется. Задача про упаковку трехмерного пространства, известная под названием гипотеза Кепплера, решалась четыреста лет, и была решена десять лет назад. Там, кстати, тоже были использованы идеи из теории кодирования как один из инструментов. Но я сейчас говорю не про трехмерное пространство, а про многомерное, я хочу понять, насколько там можно плотно упаковать шары. Зачем это нужно? Например, точки в n–мерном пространстве – это сигналы для телекоммуникаций. Когда мы их «рассовали» далеко друг от друга, это хорошо, значит, сигналы не перепутаются.

Были известны следующие оценки, я тут написал, их можно чуть улучшать, экспоненты написаны правильно. Доля, которую мы заполним в пространстве наилучшим образом она не меньше, чем 2 в степени -N, это граница Минковского. А сверху мы не можем сделать плотность больше, чем 2 в степени -N пополам. Это оценка Блихфельда начала XX века. И геометры верили, что верна оценка Блихфельда, так как она доказывается довольно сложно, а оценка Минковского получается на «раз-два».

А главное, оценка Минковского заключается в том, что если вы бросаете точки в пространство случайно, то как раз и получится плотность равная 2 в степени -N. Но поверить, что случайное бросание может быть плотным, нельзя. Это противоречит всему, что было накоплено до этого. Верхнюю оценку удалось уменьшить, ее «подвинули» с 0,5 до 0,6, и это был большой сюрприз для геометров. Но, главное, что у них и мозги «подвинулись». То есть в теории кодирования люди уже за 50 лет работы свыклись с мыслью, что случайное бросание это очень хороший способ порождения хороших упаковок (кодов).

Одна из гипотез состоит в том, что для двоичных кодов асимптотически лучше не бывает (для недвоичных это неверно). Теперь это уже довольно популярная гипотеза и в геометрии, что, наверное, в асимптотике самая плотная упаковка будет вести себя почти как случайная.

Хочу закончить лекцию возвратившись к жизни Шеннона. Малоизвестная вещь, что он был везунчиком, что он попал в какой-то национальный парк с семьей, и оказался там миллионным посетителем. Естественно, местные газеты написали, что Клод Шеннон с семьей из Массачусетса стал нашим миллионным посетителем. Прошел день, и уже по всей Америке пишут, что изобретатель теории информации стал миллионным посетителем.

Еще он замечательно жонглировал. Есть история, что когда он работал в Bell Labs, ему подарили велосипед с одним колесом, как в цирке. Он сел на него и поехал сразу, а через пару недель он уже ездил по коридорам и жонглировал тремя шариками. Кроме того, что он был математиком, он, несомненно, был и инженером. Если посмотреть, то он придумал какие-то устройства, машинки, которые в Японии выпускали с радиоуправлением. Из больших вещей он придумал первый в современном мире компьютер, который играл в шахматы.

Также придумал и сделал мышку, которая находила выход из лабиринта. Это считается началом искусственного интеллекта. Она ходила, искала, у нее были некие правила, куда ей двигаться. Лекцию я хотел закончить тем, что Шеннон назвал ultimate useless machine. Оказывается, у него было замечательное чувство юмора.

Обсуждение лекции

Борис Долгин: Спасибо большое. Вопросы, реплики?

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

Г.К.: На самом деле, оба вопроса про ИППИ. Первый, про радиационную устойчивость, он у нас уже где-то с год внутри института «гуляет», мы сотрудничаем с Зеленоградом на предмет того, чтобы предложить им новые корректирующие схемы, которые были бы устойчивы к ошибкам радиации. Радиация оказалась очень противной штукой и для вычислительной техники.

Теперь вы сразу спросили, делаем ли мы одно и то же или разное с американцами. В тот момент мы делали с американцами, к сожалению, разное. Американцы делали умно, а мы про это не думали. Они биты одного слова на своей плате разносили, то есть то, что в теории кодирования называется перемежением. Поэтому, если вдруг даже происходил радиационный «пробой», то пробивалось в разных словах, в каждом слове появлялось по одной ошибке, и ничего страшного. А у нас биты одного слова лежали подряд, и поэтому портилось целиком слово, а это может привести к сбою в работе ЭВМ.

Про Владимира Ивановича Сифорова… Говорят, что он был хорошим директором. Я у него никогда не работал, я работал в почтовом ящике, когда был молодым, и долго работал. Я ходил в ИППИ на семинары, так что Владимира Ивановича видел, даже беседовал, потому что я собирал отчеты для Совета по кибернетике. Сифоров интересовался тем, что происходило в тематике передачи информации. В.И. Левенштейн мне рассказывал, как у него получилась первая печатная работа (ее потом американцы переоткрыли, и даже получили премию за эту работу, ну а потом извинялись, говорили, что они не знали – я не верю).

Так вот Сифоров на семинаре, это конец 1950-х годов задал следующий вопрос: «Я строил двоичный код следующим образом: выписывал подряд последовательности из нулей и единиц фиксированной длины, начинал с чистого нуля, хотел построить код, например, с расстоянием пять. И смотрел по словам, я смотрел первое слово, которое на расстоянии пять, выписывал его. Хорошо, потом начинал двигаться дальше по своему списку упорядочения, искал первое слово, которое от этих двух на расстоянии пять или больше. Как только находил, добавлял его к списку, и так далее. В примерах у меня всегда итоговый код – линейный. Это верно всегда?».

Это то, что теперь называют «жадным» алгоритм, и Владимир Иванович его первый придумал.

Слушатель: На прошлой лекции Александра Шеня я вдохновился примером эксперимента с музыкой разных композиторов, где архивировали миди-файлы и складывали сумму, и сравнивали с архивом суммы. Сумма архива больше архива суммы. Это степень сжимаемости показывала похожесть. Вы сравнивали писателей, их похожесть, на Шекспира. Скажите, где об этом можно почитать? Хочется прийти домой и почитать об этом.

Г.К.: Напишите Михаил Малютов по-английски, и вылезет куча всего, включая маленький телевизионный ролик, Малютов очень гордится, что его сняли, где он рассуждает, кто же и что написал (Ред. "Шекспир против Шекспира" на телеканале "Культура").

Слушатель: Спасибо за лекцию. А можно чуть углубить или расширить вопрос? Вы упомянули изыскания г-на Малютова, в том числе по поводу кодирования и сжатия литературных текстов, и то, что можно четко отследить, что это текст одного автора, а потом другого. А вот что касается музыки, получается, что музыку тоже можно кодировать?

Г.К.: Если оцифровать, то да.

Слушатель: А что принимается за единицу музыки?

Г.К.: Здесь такая же ситуация, как с определением отцовства. То есть, если оказалось, что степени сжатия разные, то вероятнее всего исполняли или писали разные люди. Но если степень сжатия примерно одна и та же, то это совершенно не означает, что писали одни и те же люди, это первое замечание. Что касается музыки, как последнюю похвалу Шеннону, если посмотреть, там есть четкий водораздел: до Шеннона все аналоговое, пластинки и т.п. И вдруг все перестроилось, все перешло на цифру, оказалось, что мы, если теряем что-то, то ухо это не слышит.

Откуда мы с вами будем брать музыку? Если это кассетная запись, то это проще простого, там есть алфавит, и его надо закодировать и сжать. Наверное, с этим способом можно было бы даже определять, а кто, собственно, играл. Если, наоборот, брать диск, там все равно уже все оцифровано, и сравнивать одно и то же произведение, как оно играется разными пианистами.

Слушатель: Скажите, а вот разницу между смыслом и информацией вы могли бы прокомментировать?

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

Наш директор, Александр Петрович Кулешов, любит приводит как пример то, что объем информации за последние год-два года удваивается! То есть, за два года было порождено столько же, сколько за всю предыдущую историю человечества. Но это же не значит, что мы удвоили наши знания.

Слушатель: Если заархивировать?

Когда мы заархивируем, это станет ближе к информации, в том смысле, например, что дубли почти исчезнут. Раньше люди стремились экономно записать, сжать, а сейчас нет таких проблем. Я до сих пор помню свой первый ноутбук, у него всей памяти было 8 Гб, и ничего, он работал. Сейчас бессмысленно об этом говорить, потому что никто не думает об объеме памяти , когда пишут программы. Ну иногда, когда задача требует экономить память...

Константин Иванович: Когда выступал Александр Шень, то он сказал грустную вещь, что в МГУ на мехмате сейчас уже перестали преподавать теорию Галуа, ее знают только профессиональные алгебраисты. В вашем институте знают теорию Галуа? Понимают ее? Преподают ли студентам и используют ли в теории кодирования?

Г.К.: Хочется ответить языком того «почтового ящика», в котором я проработал половину своей рабочей жизни. Те, кому нужно, кто с ней работают, те и знают теорию Галуа. Добрушин очень любил приводить пример, что большая часть математиков не знает, что такое конечные поля, как они устроены, а инженеры-связисты, оказывается, знают, так как им это нужно.

Слушатель: Вы сказали про отцовство, отсюда у меня и появился вопрос. Вы ни слова не сказали про генетический код.

Г.К.: Конечно, нет. Это отдельная тема. Я не говорил об этом, потому что, все мы читали Козьму Пруткова и знаем, что «нельзя объять необъятное». Да, есть генетический код, и там много задач, эти задачи чем-то близки к теории кодирования, но, к моему удивлению, это не задачи теории кодирования. Современные математики эти задачи называют комбинаторикой на словах. Но кодов там не оказалось.

То есть, как Бог или кто-то исправляет ошибки в хромосомах, я не знаю, и даже не хочу за это браться. Но могу отметить, что кодов, исправляющих ошибки, в привычном понимании, чтобы это был хороший код, чтобы он был близок к оптимальному, на сегодня там нет. Мы часто думаем, что природа оптимальна. Вот сколько времени в бионике была идея о том, что нужно просто брать, копировать природу и все будет хорошо. Но в природе хорошего кода, исправляющего ошибки, по крайней мере, генетического кода, не оказалось.

Слушатель: Я – биоинформатик. Я сформулирую по-другому, есть два множества. Одно кодируется случайным образом и второе множество – случайным образом. Эти два множества складываются, и в результате получается единственно точный ответ. Чтоб было понятнее: ДНК матери кодируется самостоятельно, ДНК отца кодируется самостоятельно, эти процессы вероятностные. Не конкретно такие-то и такие гены, а в случайном порядке. Когда сливаются эти две клетки, получается ген, который имеет абсолютно четкое расположение, развивается нормально. Вы когда-нибудь видели такие множества, такой способ программирования?

Г.К.: Если в семье не один ребенок, так они что все одинаково устроены?! Получается другой ребенок, другая хромосома, другой набор.

Слушатель: Наборы одни и те же. Абсолютно точно говорю, достоверно.

Борис Долгин: Подождите. Генотипы двух детей одних и тех же родителей одинаковы?

Слушатель: Нет, генотипы родителей для этого ребенка и для другого одинаковы.

Г.К.: Я на этот вопрос не отвечаю, это не по теме моей лекции. Сразу скажу: я не буду отвечать на вопросы по биоинформатике, мне эта область очень интересна, но я в ней не специалист. Я отвечаю только на те вопросы, которые касаются моей области.

Слушатель: Даже если вы не ответите, этот вопрос должен прозвучать. Вы сказали, что хорошего кода для исправления ошибки не оказалось. Почему: нашли, что нет, или не искали?

Г.К.: Не знаю.

Слушатель: Спасибо за прекрасную лекцию, Григорий Анатольевич. У меня вопрос, связанный с развитием систем. Есть такие понятия: саморазвитие, самоорганизация и т.д. Возьмем нашу планету, я читал, что там, якобы уже 4 млрд. лет назад плавали одноклеточные животные. От этих простейших систем мы дошли до homo sapiens. Вопрос: поскольку математические формы – это тоже объективная реальность, и все, что вы сегодня рассказали и о кодах, и сжатии, о вероятностных, случайных процессах, все это происходит в природе, а не только в теории у математиков. Как в природе за эти 4 млрд. лет все эти математические кодирования, все эти свои каналы передачи информации, как это все осуществлялось?

Г.К.: Передача по каналам информации начинала осуществляться с Попова-Маркони, это сто с небольшим лет. Дальше, если это относится к живой природе, то я уже сказал, что это не моя тема. А передача информации в неживой природе – это , кажется, ничья тема.

Борис Долгин: На самом деле, в реплике-вопросе, который только что прозвучал, прозвучал некоторый полу-вопрос, по которому математики иногда самоопределяются. Это вопрос об онтологичности математики. Бывают платоники, неплатоники, те, кто думают, что это что-то, действительно, объективно присутствующее или что это все-таки чистые мыслительные конструкты, которые можно более или менее удобно использовать для описания тех или иных явлений. Хотите ли вы самоопределиться на эту тему?

Г.К.: Нет, я – прикладной математик.

Борис Долгин: Можете ли вы посоветовать какую-то литературу по теме? Предположим, вышли отсюда люди, которые впервые услышали о том, что вы рассказали, и захотели продолжить читать.

Г.К.: У нас в ИППИ есть самый старый сотрудник Юрий Львович Соколович. Ему практически 90 лет, в войну он был командиром взвода разведчиков, и только в этом году он перестал читать лекции. Пару лет назад, когда был некая вечеринка, люди пели песни, и другой немолодой человек говорит: «Юрий Львович, все не знают, но вы должны знать, была такая песня сталинских времен "Простое письмо", напомните слова». Он, опираясь на палочку, сказал: «А причем здесь я, спросите yandex!».

Борис Долгин: Какой смысл в моем вопросе, разумеется, можно посмотреть в поисковике. Но вы, как специалист, наверное, имеете какое-то представление о том, что является адекватным, что является лучшим. Что вы рекомендуете, читая лекции. Что бы вы рекомендовали, на ваш вкус?

Г.К.: Я скажу, но сразу поставлю ограничения. В теории кодирования есть, условно говоря, ее «Библия» это книга Мак-Вильямс и Слоена, русский перевод 1979 года, при этом, как и положено «библии», она почти не устарела. Но это книга для математиков. Есть книга, которая больше про Шенноновскую теорию, про надежную связь, про сжатие, это книга Галлагера «Теория информации и надежная связь». Эта книга для математиков, которым интересны прикладные задачи, или для прикладников, которые достаточно хорошо знают математику.

Популярных книг на эту тему я не знаю. Когда-то была такая книжка в библиотечке «Кванта» Аршинова и Садовского «Коды и математика». Понимаете, как всегда, в популярной книге есть плюс в том, что ее можно читать, но есть минус в том, что, если в ней нет ошибок, то это уже хорошо, но она все-таки дает несколько поверхностный взгляд на предмет. На английском языке книг гораздо больше, в том числе, и популярных, но переводить никто не хочет.

Наталия Демина: У меня вопрос по телекоммуникациям. Сначала было 2G, потом 3G, сейчас 4G, то, что вы делаете, связано с развитием этого?

Г.К.: Я больше теоретик, чем практик, и для меня мобильный телефон по-прежнему загадка. Почему он работает, почему они друг другу не так сильно мешают? Мое убеждение, что там, по существу, нет никаких новых возникающих теоретических задач. Но есть постоянное улучшение уже существующих решений. Что-то меняется, будет 5G, увидим, что оно даст. На самом деле, если вы посмотрите, там всегда есть большая разница между тем, что обещается, и тем, что получается. То есть в Москве уже есть LTE (4G), но реальная скорость передачи информация в разы меньше того, что обещается. Но, тем не менее, правда состоит в том, что связь постоянно улучшается.

Слушатель: Что вы заканчивали? Скажите о себе несколько слов.

Г.К.: Мехмат МГУ. Когда я там учился, я никакими кодами не занимался, там была некая история, почему я не остался в аспирантуре, может быть это и хорошо, что не остался. Я вообще считаю, что Бог ни делает - все к лучшему. Когда я пришел в «почтовый ящик», то мой начальник вынес книжку со словами «Вот ты закончил кафедру алгебры, это очень хорошо, ты теперь с этим разберешься и нам расскажешь». Книжка называлась «Алгебраическая теория кодирования» Э. Берлекэмпа. Вот до сих пор продолжаю разбираться.

Берлекамп – очень хороший математик. Из забавного – он занимался играми и, в том числе, играл на бирже, но и здесь Шеннон – первый! Более того, Шеннону принадлежит изобретение первого переносного компьютера. Шеннон его построил для игры в блэк-джек, и с ним он ездил в Лас-Вегас. Потом это превратилось в некую литературную историю, потом уже и в фильм. То есть в этом смысле Шеннон - такой типичный американец, он везде видел деньги (ну там где они есть). А идеи, которые у него были в теории информации, они сейчас довольно популярны в математической экономике. Там есть «Универсальный портфель Ковера». Но это тоже все по следам Клода Шеннона.

Слушатель: У вас почти вся лекция была посвящена кодам для исправления ошибок и для обнаружения ошибок. Что известно о попытках исправления и обнаружения вставки символа и потери символа?

Г.К.: Этим занимается мой старший коллега и товарищ Владимир Иосифович Левенштейн, он придумал в 1965 году то, что теперь называется метрикой (расстоянием) Левенштейна. Оно определяется как минимальное число вставок и-или выпадений символов, которые переводят одну последовательность в другую. То есть это такой аналог метрики Хэмминга для исправления как раз ошибок вставок, выпадений, но она изучена гораздо хуже, потому что сама метрика само по себе гораздо хитрее.

Объясню простую вещь, по которой сразу станет понятно, почему она хитрее. Там шары одинакового радиуса в разных точках имеют совершенно разный объем. Это понятно, вот у вас есть вектор из всех нулей, и пусть будет у вас выпадать пять символов в каких-то позициях. Что вы получите? Каждый раз один и тот же вектор из нулей. А вот если у вас есть вектор, в котором половина нулей и половина единичек, и они довольно хаотично разбросаны, то выбрасывая пять символов, вы получите кучу разных векторов. Там такая тяжелая для исследования метрика, и хотя, как всегда, есть границы существования хороших кодов, но явных конструкций, за исключением кодов, исправляющих одну вставку, одно выпадение (а это сделал еще Левенштейн), реальных конструкций нет.

Борис Долгин: Спасибо большое! (аплодисменты)

Смотрите также: Публичные лекции «Полит.ру». Г. Кабатянский о кодах и кодировании. Видео Максим Руссо Информация с точки зрения математики Лекция «Коды – от Клода Шеннона до наших дней». Фоторепортаж Григорий Кабатянский расскажет о кодах и кодировании Коды – от Клода Шеннона до наших дней