13 марта в рамках проекта «Публичные лекции «Полит.ру» выступил Григорий Анатольевич Кабатянский – доктор физико-математических наук, главный научный сотрудник Института проблем передачи информации РАН, профессор отделения прикладной математики и информатики НИУ-ВШЭ. Тема его лекции: «Коды – от Клода Шеннона до наших дней».
Одним из фундаментальных достижений американского математика и инженера Клода Шеннона (Claude Elwood Shannon; 1916-2001) стало создание теории информации. В помощь слушателям лекции мы сообщим элементарные сведения об этой дисциплине.
Реплика собеседника, бумажное или электронное письмо, красный сигнал светофора, звонок в дверь – всё это передача информации. Любой случай такой передачи можно описать при помощи общей схемы. В ней присутствуют отправитель (источник) информации, получатель (адресат) и канал связи. Канал связи может вносить в передаваемое сообщение случайные помехи, затрудняя прочтение этого сообщения адресатом. Такими помехами могут быть, например, шумы при телефонном разговоре или же морская вода, размывшая буквы в письме капитана Гранта.
Количество переданной или полученной информации можно измерить. В старину объем бумажной переписки можно было измерять в количестве страниц, телеграф приучил людей считать слова и знаки, и, в конце концов, люди пришли к определению минимальной единицы информации. Это бит (от английского binary digit «двоичная цифра»), он равен одному символу в двоичной системе (0 или 1). Термин «бит» предложил Шеннон в статье «Математическая теория связи».
Информацию можно определить и как степень уменьшения неопределенности. Адресат получает информацию, какое из возможных событий произошло. Если число этих возможных событий равно двум, то информацию о произошедшем событии можно передать одним битом. Например, из двух возможных результатов бросания монетки обозначить орел единицей, а решку – нулем.
Что происходит если этих возможных событий больше двух? Сколько битов понадобится для передачи информации? Предположим, нам надо угадать число от 1 до 16, задавая собеседнику вопросы, на которые он будет отвечать «да» или «нет», при этом стараясь, чтобы количество этих вопросов было минимальным. Мы будем разделять множество возможных вариантов на равные части. «Это число от 1 до 8?» – «Нет» – «Это число от 9 до 12?» – «Да» – «Это число от 9 до 10?» – «Нет» – «Это 11?» – «Да». Нам понадобилось четыре вопроса, то есть четыре байта информации, чтобы узнать число. При этом изначально у нас имелось 16 равновероятных событий, то есть наше количество информации равняется log216=4. В целом информация о том, какое из N событий произошло, записывается log2N битами, в случае если N не является степенью двух, то нужен log2N+1 бит (рассмотрите пример с угадыванием числа от 1 до 17).
А что, если вероятности возможных событий не равны? Предположим, существует пруд, в котором живут рыбы четырех видов. Каждый день рыбак идет к пруду и вылавливает одну рыбу. Больше всего в пруду карасей, вероятность того, что на удочку попадется карась, составляет 1/2. На втором месте окуни, вероятность добычи окуня равна 1/4. Вероятности поимки ерша и пескаря равны 1/8. Мы задаем рыбаку вопросы, на которые отвечает «да» или «нет». Наша цель – узнать, кого поймал сегодня рыбак. В этом случае выгоднее не пытаться каждым вопросом делить множество вариантов пополам (например, «Название рыбы начинается на гласную?»), а спрашивать сразу: «Это карась?». С вероятностью 1/2 мы накроем цель первым же вопросом. Правда, если сегодня попался ерш, нам придется задать целых три вопроса. Казалось бы, этот метод хуже. Но если мы будем играть в эту игру с рыбаком на протяжении 200 дней, то в 100 случаях нам будет достаточно одного вопроса, в 50 случаях – двух и в 50 – трех. Используя первый метод, мы каждый раз будем тратить по два вопроса, а если мы учтем вероятности, то в среднем мы затратим по (100×1 + 50×2 + 50×3)/200 = 1,75 вопроса. Экономия налицо!
Пример с рыбами демонстрирует важное понятие теории информации – энтропию. Энтропия определяется формулой:
Н(С) = p1 log2p1+p2 log2p2+…+pn log2pn, где p – это вероятности событий.
Так как вероятности отдельных событий меньше единицы, их логарифмы всегда отрицательны и энтропия тоже отрицательна. Среднее количество информации, необходимое для сообщения об одном из этих событий, определяется как I(С)= –Н(С). В нашем случае с рыбами:
I(С)= –(1/2 log21/2+1/4 log21/4+1/8 log21/8+1/8 log21/8) = 1/2 + 1/2 + 3/8 + 3/8 = 1,75
Среди теорем теории информации, сформулированных и доказанных Клодом Шенноном есть и такая: при кодировании, допускающем однозначное декодирование, средняя длина сообщений не меньше энтропии источника.
Информация передается по каналу связи: при помощи звуковых волн в воздухе, электрическими сигналами по проводам или еще как-то. В идеальном случае информация из источника доставляется адресату без искажений (т.н. «канал без шума»), однако это далеко не всегда так. В теории информации разработаны особые алгоритмы снижения числа ошибок при передаче, их обнаружения и устранения. Наиболее простым способом обнаружения ошибок служит контроль четности. Предположим, нам надо передать двоичное сообщение:
100101011111.
Разобьем его на группы по три символа:
100 101 011 111.
Если в группе число единиц четно, добавим в нее четвертым символом ноль, а если нечетно, добавим единицу:
1001 1010 0110 1111.
Добавленные нами символы позволяют контролировать ошибки. Если при передаче в каждой группе из четырех знаков число единиц четно, то всё нормально. Если же возникла ошибка (а ошибка – это замена нуля на единицу или единицы на ноль), то число единиц в данной группе станет нечетным. Следует помнить, что этот способ не будет работать, когда в группе из четырех символов одновременно произойдут две ошибки.
Коды способны даже помочь нам исправить ошибку, возникшую при передаче информации по каналу связи. Предположим, нам надо передать четыре бита информации 1011. Добавляем к ним еще три проверочных бита. Делаем это так, чтобы четными были три суммы: первого, второго, третьего и пятого битов; первого, второго, четвертого и шестого битов, первого, третьего, четвертого и седьмого битов. В нашем случае проверочные биты должны быть 001. Адресат, получив сообщение, должен посчитать эти три суммы. Если они четные, ошибок не произошло. Если одна нечетная, то ошибка случилось при передаче проверочного символа. Если две из них нечетные, то ошибка в том символе, который входит в обе суммы. Если все три контрольные суммы нечетные, то ошибка в первом символе (он входит в каждую из сумм).
сообщение | контроль |
|
1011 | 001 | ошибок нет |
0011 | 001 | ошибка в первом символе |
Конечно, в реальных системах передачи информации могут использоваться куда более сложные алгоритмы выявления ошибок, чем тот, что здесь описан.
Теоремы Шеннона о передаче информации по каналу с шумами утверждают, что для такого канала всегда можно найти систему кодирования, при которой сообщения будут переданы со сколь угодно большой степенью верности, если только производительность источника не превышает пропускной способности канала. Иными словами, информацию можно передавать со сколь угодно малой вероятностью ошибки и с любой скоростью, если она меньше некоторой критической для данного канала величины.
