Также по теме

ИНФОРМАЦИИ ТЕОРИЯ

ИНФОРМАЦИИ ТЕОРИЯ – раздел математики, исследующий процессы хранения, преобразования и передачи информации. В основе его лежит определенный способ измерения количества информации. Возникшая из задач теории связи, теория информации иногда рассматривается как математическая теория систем передачи информации. Опираясь на основополагающую работу К.Шеннона (1948), теория информации устанавливает основные границы возможностей систем передачи информации, задает исходные принципы их разработки и практического воплощения. В настоящей статье рассматривается ядро теории информации – свойства информационных мер и их приложения к анализу систем передачи информации.

Основные свойства информации можно описать с помощью математической модели, отражающей многие характерные особенности информационной меры, как она обычно понимается на интуитивном уровне. Источник информации и канал связи, по которому передается информация, можно моделировать, используя вероятностные представления. Энтропия источника информации равна логарифму (эффективного) числа сообщений, которые он порождает. Это – мера сложности описания источника (или, как иногда говорят, мера неопределенности сообщения). Такое понимание энтропии тесно связано с понятием энтропии, используемым в термодинамике (см. также ТЕРМОДИНАМИКА).

Физически передачу информации можно представить как индуцирование в приемном устройстве требуемого физического состояния. Отправитель намерен передать сообщение получателю. Суть передачи заключается в воспроизведении на выходе канала связи переданного сообщения. В момент передачи отправитель выбирает нужное сообщение из списка всех возможных сообщений. Получатель заранее не знает, какое из них будет выбрано. (Если бы он был об этом заранее информирован, то никакой необходимости посылать сообщение не было бы.) Канал связи вносит в процесс передачи информации случайный шум, который искажает сообщение и тем самым затрудняет его прочтение. В начале процесса связи получатель находится в полной неопределенности относительно того, какое сообщение выбрано из списка возможных. К концу связи получателю становится это известно, т.е. становится известно точное описание выбранного сообщения.

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

Трудность передачи сообщения не зависит от его содержания; передавать бессмысленные сообщения не менее трудно, чем осмысленные. Например, число 23 в одном контексте может быть ценой одного барреля нефти, а в другом – номером победителя заезда на скачках. Смысл сообщения зависит от контекста и семантики, а трудность его передачи определяется только перечнем возможных сообщений (и их вероятностей).

Любую систему передачи информации можно считать состоящей из трех частей: источника сообщений, канала связи и приемного устройства (рис. 1). Например, при разговоре по телефону источником является говорящий, сообщением – его речь. Каналом связи служат провода, передающие электрический сигнал от говорящего к слушателю – получателю сообщения.

Между отправителем сообщения и каналом связи могут находиться устройства (обозначенные на рис. 1 как кодирующие), преобразующие сообщение в форму, удобную для передачи по каналу связи. Декодирующее устройство, установленное на другом конце канала, восстанавливает принятое сообщение.

Рис. 1. ПЕРЕДАЧА ИНФОРМАЦИИ

Изучение систем передачи информации мы начнем с источника сообщений. По каналу связи может передаваться самая различная информация: текст, живая речь, музыка или изображения. Для каждого источника можно указать перечень сообщений, которые он может генерировать. Например, источник телеграфных или телексных сообщений передает только буквы и не содержит, скажем, нотных знаков. Если по каналу связи передается живая речь, то сигнал лишается полезного содержания при частоте выше 20 000 Гц, верхнего предела, воспринимаемого человеческим слухом. Этими фактами можно воспользоваться при проектировании входа канала связи.

Кодирование.

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

Трудность передачи информации зависит от числа возможных сообщений, которые должны быть распознаны получателем. Если это число невелико, то процесс передачи менее сложен, чем при большом числе возможных сообщений. Например, чтобы различить десять возможных сообщений, необходимо передать только одну десятичную цифру (0, 1, 2, .., 9), а для различения 100 возможных сообщений понадобятся уже две десятичные цифры (00, 01, 02, .., 99). Каждая дополнительная цифра позволяет увеличить число распознаваемых сообщений в 10 раз. Таким образом, количество информации, необходимой для того, чтобы мы могли различить N сообщений, растет, если говорить на математическом языке, как логарифм числа N, т.е. как log N.

Простейший список возможных сообщений состоит из двух сообщений. Чтобы передать одно из них, необходим символ, принимающий два значения. Количество информации, которую может передать источник, содержащий два равновероятных сообщения, называется битом и служит основной единицей измерения информации. Символ, представляющий такое количество информации, обычно является двоичной цифрой, 0 или 1. Один бит позволяет различать две равновероятные возможности (0, 1), два бита позволяют различать четыре возможности (00, 01, 10, 11), и т.д. Если число равновероятных возможностей равно N, то количество информации, необходимое для представления одной из них, равно log2N битов. Например, чтобы передать одно из 32 возможных сообщений, отправитель мог бы послать получателю последовательность из log232 = 5 битов. Эта последовательность из 5 двоичных знаков сообщит получателю, какое из 32 возможных сообщений было передано.

Другой подход к той же проблеме можно пояснить на примере игры в 20 вопросов. Один из участников игры задумывает нечто, а другой пытается это отгадать с помощью 20 вопросов, допускающих ответы только типа «да – нет». Предположим, например, что первый из участников игры задумывает «Чарлз Диккенс». Второй участник игры может задать вопрос: «Это реальное лицо?», а затем спросить: «Этот человек жив?» и т.д. С каждым вопросом число вариантов отгадки уменьшается до тех пор, пока задуманное не будет идентифицировано. На языке теории информации можно сказать, что второй участник игры (отгадывающий задуманное) с каждым вопросом может получать самое большее один бит информации. С помощью 20 вопросов он может различить самое большее 220 (т.е. приблизительно миллион) различных объектов.

Если второй участник игры задает свои вопросы не слишком задумываясь, то ему скорее всего понадобится их гораздо больше. Например, чтобы идентифицировать один объект из миллиона возможных, может потребоваться миллион вопросов типа «Задуманный объект – это x?» Чтобы максимально использовать задаваемые вопросы, каждый вопрос должен делить множество возможных ответов примерно на две равные части. Тогда после первого вопроса останется только 500 000 возможных ответов, после второго – только 250 000, и т.д., пока, наконец, после 20-го вопроса не останется только один возможный ответ. Таким образом, в случае N равновероятных сообщений для выбора сообщения требуется около log N битов, а в игре в 20 вопросов для идентификации задуманного объекта требуется log N вопросов, допускающих ответы типа «да - нет».