Полiт.ua Государственная сеть Государственные люди Войти
3 декабря 2016, суббота, 20:40
Facebook Twitter LiveJournal VK.com RSS

НОВОСТИ

СТАТЬИ

АВТОРЫ

ЛЕКЦИИ

PRO SCIENCE

ТЕАТР

РЕГИОНЫ

Информация с точки зрения математики

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

ошибка в первом символе

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

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

Обсудите в соцсетях

Система Orphus
Подпишитесь
чтобы вовремя узнавать о новых спектаклях и других мероприятиях ProScience театра!
3D Apple Facebook Google GPS IBM iPhone PRO SCIENCE видео ProScience Театр Wi-Fi альтернативная энергетика «Ангара» античность археология архитектура астероиды астрофизика Байконур бактерии библиотека онлайн библиотеки биология биомедицина биомеханика бионика биоразнообразие биотехнологии блогосфера бозон Хиггса визуальная антропология вирусы Вольное историческое общество Вселенная вулканология Выбор редакции гаджеты генетика география геология глобальное потепление грибы грипп демография дети динозавры ДНК Древний Египет естественные и точные науки животные жизнь вне Земли Западная Африка защита диссертаций землетрясение зоопарк Иерусалим изобретения иммунология инновации интернет инфекции информационные технологии искусственный интеллект ислам историческая политика история история искусства история России история цивилизаций История человека. История институтов исчезающие языки карикатура католицизм квантовая физика квантовые технологии КГИ киты климатология комета кометы компаративистика компьютерная безопасность компьютерные технологии коронавирус космос криминалистика культура культурная антропология лазер Латинская Америка лженаука лингвистика Луна мамонты Марс математика материаловедение МГУ медицина междисциплинарные исследования местное самоуправление метеориты микробиология Минобрнауки мифология млекопитающие мобильные приложения мозг Монголия музеи НАСА насекомые неандертальцы нейробиология неолит Нобелевская премия НПО им.Лавочкина обезьяны обучение общество О.Г.И. открытия палеолит палеонтология память педагогика планетология погода подготовка космонавтов популяризация науки право преподавание истории происхождение человека Протон-М психология психофизиология птицы ракета растения РБК РВК регионоведение религиоведение рептилии РКК «Энергия» робототехника Роскосмос Роспатент русский язык рыбы Сингапур смертность Солнце сон социология спутники старообрядцы стартапы статистика технологии тигры торнадо транспорт ураган урбанистика фармакология Фестиваль публичных лекций физика физиология физическая антропология фольклор химия христианство Центр им.Хруничева школа эволюция эволюция человека экология эпидемии этнические конфликты этология ядерная физика язык

Редакция

Электронная почта: politru.edit1@gmail.com
Адрес: 129343, Москва, проезд Серебрякова, д.2, корп.1, 9 этаж.
Телефоны: +7 495 980 1893, +7 495 980 1894.
Стоимость услуг Полит.ру
Свидетельство о регистрации средства массовой информации
Эл. № 77-8425 от 1 декабря 2003г. Выдано министерством
Российской Федерации по делам печати, телерадиовещания и
средств массовой информации. Выходит с 21 февраля 1998 года.
При любом использовании материалов веб-сайта ссылка на Полит.ру обязательна.
При перепечатке в Интернете обязательна гиперссылка polit.ru.
Все права защищены и охраняются законом.
© Полит.ру, 1998–2014.