Шеннона теорема

Теорема утверждает, что каким бы зашумленным ни был канал связи, существует такой способ кодирования, который позволит сделать вероятность ошибки при передаче информации по этому каналу сколь-угодно малой, если только скорость передачи информации R не будет превышать пропускную способность C канала связи.

И напротив, если R > C, вероятность ошибки, передаваемой по каналу информации, всегда будет отличной от нуля и будет расти с увеличением скорости передачи R.

Результат Шеннона интересен, прежде всего, очень нестандартным подходом к решению проблемы, сходной с той, которую во время Второй Мировой войны одновременно решали Норберт Винер в США и Андрей Николаевич Колмогоров в СССР.

Проблема состояла в том, как на основании информации с радара, которая искажена помехами, среди множества возможных направлений движения объекта выбрать его истинное направление с наименьшей ошибкой.

Шеннон же решал схожую, но в определенном смысле обратную задачу: каким образом должна быть представлена реально передаваемая информация, чтобы ее можно было максимально достоверно отличить от того, какая информация могла быть передана.

То есть, в первом случае мы имеем дело с данностью и думаем о наилучших способах ее интерпретации, а во втором – о наилучших способах репрезентации данности, с тем чтобы минимизировать ошибки в ее интерпретации.

Claude Elwood Shannon

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

Информационная энтропия – это величина, обратная информации (см. статью про бит) , и служит мерой неопределенности текстового сообщения.

Избыточность – напротив, это мера предсказуемости, связанная с теми или иными языковыми ограничениями: различной частотой употребления различных букв, наиболее вероятным следованием одних букв за другими и т. п.

В соответствии с данными, которые приводит сам Шеннон, при отправке информационных блоков, состоящих не более, чем из восьми букв, энтропия печатного английского языка составляет 2,3 бита, а его избыточность – около 50 процентов. Увеличение длины блоков до 100 букв снижает энтропию языка до 1 бита на букву, и увеличивает его избыточность до 75%!

Избыточность языка D = R − r, где R – это абсолютная энтропия языка, которая равна двоичному логарифму от общего числа букв алфавита, а r – это реальная энтропия языка, которая и имелась в виду выше. Ее можно сосчитать по формуле

r = H(m)/N,

где H(m) – это энтропия сообщения m, а N – это его длина в символах используемого языка.

Типичным примером избыточности языка являются часто используемые в психологии примеры:

или

В результате вместо слова АРБУЗ до получателя дойдет КАРТУЗ.

Оно состоит из двух слогов, и, допустим, что источник сообщения способен произвести 65 536 слогов. Таким образом, чтобы закодировать один слог потребуется 16 бит (65536 = 2¹⁶), и, следовательно, энтропия каждого слога равна 16 бит.

Скорость передачи сообщения – 1 слог в единицу времени (секунда).

Решение состоит в том, чтобы передавать каждый слог избыточное число раз – например, 4 – и выбрать в качестве действительно передаваемого слога тот, который придет наибольшее число раз!

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