Теория информации

Размещено на http://www.allbest.ru/

Теория информации

Теория информации тесно связана с такими разделами математики как теория вероятности и математическая статистика, а так же прикладная алгебра, которая представляет для неё математический аппарат. С другой стороны, теория информации исторически и практически представляет собой математический аппарат теории связи. Часто теорию информации рассматривают как одну из ветвей теории вероятности или как часть теории связи. Таким образом, этот предмет весьма узок, то есть он зажат между «чистой» математикой и прикладными аспектами теории связи. Теория связи представляет собой математическую теорию, посвященную измерению информации, её потока, «размеров» каналов связи и т.д. Первоначально теория была посвящена каналу связи, определённому длинной волны и частоты, реализация которого была связана с колебаниями воздуха и электромагнитных излучений. Обычно соответственный процесс был непрерывным, но и мог быть дисперсным, это когда информация кодировалась и декодировалась. Кроме того, теория информации изучает методы построения кодов обладающих полезными свойствами.

Информация и сообщение.

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

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

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

Пример: Сообщение о падении самолёта для близких родственников погибших несёт иную информацию, чем для авиакомпании.

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

Абстрактно можно сказать, что решающим для связи между сообщением N и информацией I является некоторое отображение X представляющее собой результат договоренности между отправляющим сообщение и получающим его, или предписанное им и называемое правилом интерпретации. Правилом интерпретации Q для данного сообщения часто получается как частный случай некоторого общего правила применимого к целому множеству сообщений, которые построены по одинаковому закону.

Если мы формулируем сообщение на некотором языке, то высказывание: «Х понимает этот язык» выражает тот факт, что лицо Х знает правило интерпретации для всех, или, по крайней мере, для большинства сообщений формулируемых на данном языке. Иногда правило интерпретации известно лишь одному кругу лиц. К ним относятся правила интерпретации для специальных языков, в частности для профессиональных, научных и различных других. Особенно чётко видна связь между сообщением и информацией в криптографии. Здесь никто из посторонних не должен извлечь информацию из передаваемого сообщения. Часто встречаются такие сообщения, которые могут интерпретироваться по-разному, причём различные интерпретации основываются одна на другой.

Пример: Сообщение «Идёт дождь» несёт дополнительную информацию о том, что нужно взять зонт. В этом случае говорят об информации различной степени отвлечённости.

Рассмотрим таблицу примеров возможных связей между сообщением и информацией:

1. Добро пожаловать / Welcome

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

2. Ла 2 - С2 / Дезоксирибонуклеиновая кислота

В этом примере сообщение даётся на специальных языках шахмат и химии.

3. Видел морских львов.

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

4. Momerg \ JDOOLD HVW PRQLV GLYLVD

Имеем зашифрованное сообщение. В левой части коммерческий шифр для указания цены в варианте, который в течении многих лет использовался в Германии для обозначения даты упаковки масла (MIL CHPROBE) даёт цену (181067), а в правой части - метод шифровки, который применялся Юлием Цезарем, когда вместо нужной буквы пишется 3 следующая за ней буква в алфавите.

ПР. Gallia est omnisdivisa (Галлия вся разделена)

В данном случае идёт кодирование методом подстановки.

5. ьлерпа

Простейший случай кодирования с помощью обращения (Апрель)

6. ТЁТЯ АНЯ ГРОБУ ТЧК БУДЕМ УСТРАИВАТЬ 13 НОЯБРЯ ДНЁМ ЕВГЕНИЯ СОМОЙЛОВА

Речь идёт об открытом сообщении, в котором скрыто секретное сообщение.

7. Казнить, нельзя помиловать. \ Казнить нельзя, помиловать.

Данный пример показывает, как незначительное изменение текста может существенно изменить весь текст.

8. Родшильд обращался с ним очень фамильонно. \ Матч века машин.

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

Устройство связи.

Письмо и газета относятся к самым старым и до сих пор не устаревшим примером случайной и регулярной передачи сообщений посредством записи на достоверном носители.

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

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

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

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

Два или более устройства связи можно соединить друг с другом таким образом, что результирующее устройство снова будет устройство связи.

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

Канал связи - это среда передачи информации, которая характеризуется, в первую очередь, максимально возможной для неё скоростью передачи данных (ёмкостью канала связи).

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

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

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

Кодирующее устройство

Преобразователь «коды - сигналы» Линия связи

Шумы (помехи) Канал связи Защита от помех (воздух, провода и т.д.)

Преобразователь «сигнал - коды»

Декодирующее устройство

Получатель информации

Современная техника в качестве носителей при передаче сообщений по каналам связи чаще всего используют:

1. Механическое движение;

2. Механическое давление жидкостей и газов; (гидравлика и пневматика)

3. Волны давления в жидкостях и газах;

4. Электрическое напряжение и токи;

5. Свободные электромагнитные волны, в том числе и световые волны.

6. Пучки электромагнитных волн;

Канал связи	Среда обитания	Носитель сообщения	Процесс, используемый для передачи сообщения
1. Почта, курьер	человека	Бумага	Механическое перемещение человека
2.Телефон, комп. сети	Проводник	Электрический ток	Передача электрических волн
3. Радио, телевидение	Эл.- магнитное поле	Эл.- магнитные волны	Распространение эл.- магнитных волн.
4. Зрение	Эл.- магнитное поле	Световые волны	Распространение световых волн.
5. Слух	Воздух	Звуковые волны	Распространение звуковых волн
6. Обоняние, вкус	Воздух, пища	Химические эл-ты	Химические реакции
7. Осязание	Поверхность	Объект, воздействующий на органы осязания	Теплопередача, давление

Сигналы. Параметры сигналов.

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

1. Колебания носителя.

2. Переносимые колебания.

3. Модулированные колебания с амплитудой (слева) и частотой (справа) в качестве параметра сигнала

На рисунке слева - амплитудная модульная

На рисунке справа - частотная модульная

Если для передачи сообщения используются импульсы, то параметром сигнала может быть либо амплитуда импульса, либо интервал между импульсами (амплитудно-импульсная и частотно-импульсная модуляции).

Дискретные сообщения.

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

Знаки, наборы знаков, алфавиты.

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

Знак - элемент некоторого конечного множества, отличающегося друг от друга.

Набор знаков может образовать множество.

Набор знаков, в котором определён линейный порядок знаков, называется - алфавитом.

Примеры алфавитов: 1. Алфавит десятичных цифр (0 1 2 3 4 5 6 7 8 9)

2. Алфавит заглавных латинских букв (23)

3. Алфавит строчных греческих букв

4. Алфавит заглавных кириллических букв (33)

5. Алфавит 12 знаков зодиака

6. Алфавит японского катана.

Некоторые наборы знаков не имеют общепринятого порядка знаков. Пример: Набор знаков клавиатуры, набор знаков азбуки Брайля, набор китайских диаграмм, набор знаков планет, набор знаков игральных карт, набор шерлокхолмских пляшущих человечков, набор знаков генетического кода состоящий из четырёх букв ACGT, обозначающих соответствующие химические соединения (аденин, цитазин, гуанин, тимин).

Дискретизация.

В сообщении, которое не является дискретным, часть приблизительно представляют дискретизациями. После чего с ними можно работать как с дискретными. Применяются 2 метода приближения - развёртка и квантование.

Развёртка.

В случае, когда параметр сигнала принимает последовательное во времени конечное число значений (при ютом они все могут быть пронумерованы), сигнал называется дискретным. А сообщение, передаваемое с помощью таких сигналов - дискретным сообщением. Информация, передаваемая источником, в этом случае, называется дискретной. Если источник вырабатывает непрерывное сообщение (соответствующий параметр сигнала является непрерывная функция от времени), соответствующая информация называется непрерывной. Пример дискретного сообщения - чтение книги, в которой информация представлена текстом, то есть дискретной последовательностью отдельных знаков (букв). Примером непрерывного сообщения является человеческая речь, передаваемая моделированной звуковой волной; параметром сигнала в этом случае является давление, создаваемое этой волной в точке нахождения приёмника - человеческого уха.

Непрерывное сообщение может быть представлено непрерывной функцией, заданной на некотором отрезке [a, b]. Непрерывное сообщение можно преобразовывать в дискретное (такая процедура называется дискретизацией). Для этого из бесконечного множества значений этой функции (параметра сигнала) выбирается их определённое число, которое приближённо может характеризовать остальные значения. Один из способов такого выбора состоит в следующем (иногда этот способ называется развёрткой): область определения функции разбивается точками х1, х2, … , xn. на отрезки равной длинны и на каждом из этих отрезков значение функции принимается постоянным и равным. Например, среднему значению на этом отрезке (считывание); полученная на этом этапе функция в математики называется ступенчатой. Получившийся при этом график называют пульсом.

Следующий шаг - проецирование значений («ступенек») на ось значений функции (ось ординат). Полученная таким образом последовательность значений функции у1, у2, …, уn. является дискретным представлением непрерывной функции, точность которого можно неограниченно улучшать путём уменьшения длин отрезков разбиения области значения аргументов.

Рис.1 процедура дискретизации непрерывного сообщения.

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

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

Возможность дискретизации непрерывного сигнала с любой желаемой точностью (для возрастания точности достаточно уменьшить шаг) принципиально важна с точки зрения информатики. Чем грубее развертка, тем больше свойств исходной кривой теряется. И наоборот чем «тоньше» развёртка, тем точнее она воспроизводит все подробности исходной функции. Это интуитивное высказывание для случая с помощью считывания, уточняется теоремой отсчётов (Уиттекер, 1915; Котельников, 1933; Найквист, 1924), значение которой для передачи сообщений осознано К. Шенноном в 1949 году.

Теорема отсчётов.

Пусть f(t) функция вида: f(t) =

(то есть f(t) как и функция времени “составлена” из колебаний с частотой, не превышающей некоторой критической частоты V_G , называемой шириной полосы пропускания). Тогда если t_s, то f(t) можно представить в следующем виде: f(t) =

(другими словами, функцию можно восстановить в точках отсчёта nt_s , если частота отсчёта не меньше удвоенной критической частоты).

Интерполяционная функция.

имеет предельное значение 1 при t = 0 и обращается в нуль в остальных точках отсчёта nt_{s .} Ниже представлен график этой функции.

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

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

Цветовая развёртка как средство стиля было использовано как в живописи Пуантилистов.

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

Они позволяют “разматывать” функции с многомерными областями определения на функции с областями определения меньшей размерности, в частности на функции одной переменной. Послойную развёртку применяют в рентгеноскопии, в телевидении используется построчная развёртка.

Результатом этой развёртки является функция, дающая зависимость яркости от одной переменной - времени.

Таким образом, развертка, за которой в случае необходимости следует разматывание в последовательность, есть этап, преобразовывающий функцию в последовательность её значений. Значение функции заполняет те значения (в более чем счётном числе), которые может принимать физическая величина - параметр сигнала. В противоположность этому дискретное сообщение - это конечная последовательность знаков, которых в свою очередь имеется конечное число или счётное. Следующий этап квантования осуществляющий переход от функции к дискретным сообщениям.

Квантование.

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

Виды квантования.

Посередине По границе

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

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

Шенноновские сообщения.

Содержащаяся в сообщении информация может существенно зависеть от того момента времени, в который сообщение достигает приёмника. Задержка такого сообщения одновременно изменяет его характер. Примером может служить лотерея или прогноз погоды. Предельным является случай, когда вся информация, которая несёт сообщение, определяется временем прибытия сигнала. Тогда говорят об извещении. Примером служат бой часов, звон колокола, вой сирены. Однако существует такие сообщения, информация которых не зависит от времени. Такие сообщения можно рассматривать часто как последовательности отдельных сообщений, которые посылаются, друг за другом во времени: момент времени t₀ первое сообщение, в момент времени t₁ второе сообщение и т.д. Так как внутренняя структура отдельных сообщений нас не интересует, будем считать их знаками. Эти знаки считаются выбранными с некоторыми независящими от времени вероятностями из заранее заданного конечного или бесконечного набора знаков.

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

В 1948 году Шеннон ввел в связи с этим математическое понятие количества информации. Это в существенном мера тех затрат, которые необходимы для того, чтобы расклассифицировать или разобрать переданные знаки.

Термин информация произошёл от латинского слова Information который означает разъяснение, осведомление. Данное понятие является одним из ключевых понятий кибернетики и понимается как совокупность каких-либо сведений или данных. Наука о свойствах информации и закономерностях информационных процессов называется теорией информации. Содержание понятия информации будем раскрывать на примере двух исторически первых подходов к измерению количества информации: подходов Хартли и Шеннона. Подход Хартли основан на теории множеств и комбинаторики, подход Шеннона на теории вероятности.

В основе всей теории информации лежит открытие, сделанное Хартли в 1928 году и состоящее в том, что информация дополняет количественную оценку. Завершённый и полный вид этой теории придал в 1948 Клод Шеннон.

Подход Хартли.

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

Рассмотрим множество, состоящее из чисел в двоичной системе исчисления длинной i двоичных разрядов, при этом каждый из разрядов может принимать значения 0 или 1. Из таблицы следует, что количество элементов множества будет вычисляться n=2ⁱ. Рассмотрим процесс выбора чисел из рассмотренного множества до выбора вероятность выбрать любое число одинаково. Существует объективная неопределённость в вопросе о том, какое число будет выбрано.

Количество двоичных разрядов i	Количество, которое можно пронумеровать и разрядность двоичных чисел n	СИСТЕМЫ ИСЧИСЛЕНИЙ
		10	16	2
1	2	0 1	0 1	0 1
2	4	0 1 2 3	0 1 2 3	00 01 10 11
3	8	0 1 2 3 4 5 6 7	0 1 2 3 4 5 6 7	000 001 010 011 100 101 110 111
4	16	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	0 1 2 3 4 5 6 7 8 9 A B C D E F	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Эта неопределённость тем больше, чем больше n количества чисел в множестве, а чисел тем больше, чем больше разрядность i этих чисел.

Обозначим количество информации через I. Использовать непосредственно число возможных сообщений N, в качестве меры количество содержащейся в сообщении информации неудобно по следующим причинам:

Если N=1, то сообщение содержит нулевое количество информации I=0;

Если существует два независимых источника сообщений характеризующихся числом сообщений N₁ и N₂, то число сообщений объединяющей оба источника будет равно N=N1*N2. В то время, как количество информации поступающей от двух независимых источников сообщений должно удовлетворять условию аддитивности: I=I₁+I₂.

Вышеперечисленным условиям удовлетворяет функция логарифма ( по основанию 2 числа состояний источника равновероятных сообщений).

Действительно, если в качестве количественной меры информации определить выражение:

I = log₂ (N), (5.3.1)

То нетрудно увидеть, что оно обладает всеми требованиями, предъявленными к количеству информации:

I = log₂(1) = 0

I = log₂(N) = log₂(N₁ * N₂) = log₂(N₁) + log₂(N₂) = I₁ + I₂

Таким образом, количество информации, содержащееся в двоичной системе исчисления равно количеству двоичных разрядов в этом числе. Это выражение и представляет собой формулу Хартли для количества информации.

Отметим, что оно полностью совпадает с выражением для энтропии ( по Эшби), которая рассматривалась им как количественная мера степени неопределённости состояния системы.

При увеличении длинны числа в 2 раза количество информации в нём также должно возрасти в 2 раза, не смотря на то, что количество чисел в множестве возрастает при этом по показательному закону (в квадрате если числа двоичные), то есть если N₂ = (N₁)², то I₂ = 2 * I₁,

log(N₂) = log₂(N₁)² = 2 log₂(N₁).

Второе требование аддитивности.

Таким образом, логарифмическая мера информации, предложенная Хартли одновременно удовлетворяет условиям монотонности и аддитивности.

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

Минимальное количество информации получается при выборе одного из двух равновероятных вариантов. Это количество информации принято за единицу информации и называется - Бит.

Формула (5.3.1) связывает количество равновероятных событий N и количество информации в сообщении, что некоторое из этих событий произошло.

Частным случаем применения формулы (5.3.1) будет случай, когда N=2^K. Подставляя в (5.3.1) получим I = к.

Задача. Случайным образом вынимается карта из колоды в 32 карты. Какое количество информации требуется, чтобы угадать, что это за карта?

Решение. Для данной ситуации n = 2⁵, следует, к = 5, следовательно, и I = 5 бит.

Подход К. Шеннона.

Шеннонавская теория информации, то есть нахождение количества информации исходит из элементарного альтернативного выбора между двумя знаками, например, между двумя двоичными знаками (битами) 0 и 1. Такой выбор соответствует приёму сообщения, состоящего из одного двоичного знака. По определению количество информации принимается за единицу и называется - битом.

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

При заданном выборочном каскаде нас будет интересовать то, сколько потребуется альтернативных выборов для выбора какого-нибудь определённого элемента.

На рисунке приведён пример: чтобы выбрать а или е нужно два альтернативных выбора (количество информации составляет два бита); чтобы выбрать в, с или f необходимы три альтернативных выбора и т.д.

Если некоторое элемент встречается часто, то естественно, количество выборов, требующихся для его опознания стремится сделать возможно меньшим. Соответственно для опознания более редких элементов приходится использовать большее число альтернативных выборов. Другими словами часто встречающиеся элементы содержат малое, а редкие элементы большее количество информации. Поэтому представляется разумным разбивать исходное множество не на равновеликие , а равновероятные подмножества, то есть максимально, чтобы при каждом разбиении на 2 подмножества, суммы вероятностей для элементов одного и для элементов другого подмножества были близки друг к другу, насколько это возможно. Ради простоты, сначала будем считать, что заданные вероятности позволяют получить точное равенство. Тогда если i-й элемент выделяется после K_i альтернативных выборов, то вероятность его появления p_i равна . Обратно, для выбора элемента, который встречается с вероятностью p_i требуется к_i = log₂ альтернативных выборов. Определим количество информации, содержащее в элементе, задаваемое частотой появления такого элемента, как log₂[бит]. Тогда среднее количество информации будет равно:

I = .

Понятие энтропии

Энтропия как мера неопределённости.

Рассмотрим случайные события с несколько иной стороны. То, что событие случайно означает отсутствие полной уверенности в его наступлении, что создаёт неопределённость в исходах опытов, связанных с данным событием. Степень неопределённости различна для разных ситуаций. Например, если опыт состоит в определённости возраста случайно выбранного студента 1-го курса, то с большей долей уверенности можно утверждать, он окажется возраста не более 30 лет. Хотя по положению на дневном обучении могут учиться лица - выпускники школ ближайших лет. Гораздо меньше неопределённость имеет аналогичный опыт, если определяться будет возраст определённого человека меньше 20 лет. Для практики важно иметь возможность произвести численную оценку неопределённости разных опытов. Нам нужно ввести количественную меру неопределённости. Начнём с простой ситуации, когда опыт имеет n-вероятностей исходов. Неопределённость каждого из них зависит от n, то есть неопределённость равна f(n). Укажем свойство этой функции. f(1)=0, так как при n=1 исход опыта не является случайным и из этого следует? Что неопределённость отсутствует. f(n) возрастает с ростом n, так как в виду большого числа возможных исходов предсказание результата опыта становится весьма затруднительным. Для определения явного вида функции рассмотрим 2 независимых опыта Х и У с количеством равновероятных исходов n_x и n_y. Рассмотрим сложный опыт Z, P состоит в одновременном выполнении Х и У. Число возможных исходов опыта Z равняется произведению n_x*n_y, причём они все равновероятны. Очевидно, определённость исхода такого опыта будет больше неопределённости опыта Х, поскольку к ней добавляется неопределённость У. Допустим, что мера неопределённости Z равна сумме неопределённости опытов Х и У, то есть определённость аддитивна:

f(n_xn_y) = f(n)+f(n_y) (1)

Зададимся вопросом каким может быть явный вид функции f(n), чтобы он удовлетворял свойствам 1 и 2 и соотношению (1). Такому набору свойств удовлетворяет функция логарифма. Таким образом, меру неопределённости опыта с n равномерными исходами можно принять число log n.

Выбор основания логарифма в данном случае значения не имеет, поскольку в силу известной формулы перехода от одного основания к другому основанию состоит во введении одинакового для обеих частей формулы (2):

logn = (2) или (2),

постоянного множителя log_ba, что равносильно изменению масштаба, то есть размера единицы неопределённости.

Явный вид функции, описывающей неопределённость опыта и n равновероятных исходов, будет выглядеть следующим образом:f(n) = (3).

На основании формулы (1) и p( найдём неопределённость, вносимую каждым отдельным исходом в общую, поскольку исходов n и все они равновероятны и, следовательно, равнозначны, а общая неопределённость равна log₂n, из свойства аддитивности неопределённости следует, что неопределённость, вносимая одним исходом составляет:

(4),

где p(.

Таким образом, неопределённость, вносимая каждым из равновероятных исходов равна:

H = -p (5)

Обобщим формулу (5) на ситуацию, когда исходы опытов не равновероятны. Тогда; пусть будет p(x₁), p(x₂)

H₁ = -p(x₁)*log₂p(x₁)

H₂ = -p(x₂)*log₂p(x₂), тогда

Н = Н₁+H₂ = -p(x₁)log₂p(x₁) - p(x₂)log₂p(x₂),

Общая формула Н будет выглядеть следующим образом:

H = - (6)

Эта формула энтропии опыта Х.

Свойства энтропии.

1. Н = 0, тогда и только тогда, когда одна из p(x_j) = 1. Однако, при этом из следует, что все остальные p(x_i) = 0 (), то есть реализуется ситуация, когда один из исходов является достоверным, то есть событие перестаёт быть случайным. Во всех остальных случаях Н>0.

2. H(XY) = H(X)+H(Y) (7)

Доказательство: Процесс получения информации можно интерпретировать как изменение неопределённости в вопросе о том, из какого источника отправлено сообщение в результате приёма сигнала по каналу связи. Формально эту модель можно представить следующим образом. Пусть имеются 2 взаимосвязанных множества:

1. Множество из N- источников {x_i}, вероятности которых равны p(x_i).

2. Множество из М- признаков {y_j}, которые встречаются с вероятностями p(y_j) и условными вероятностями p(x_i/y_j).

Вероятность наблюдения признака - это средняя вероятность его наблюдения при предъявлении определённого из них. До получения информации ситуация характеризуется неопределённостью того, из какого источника она будет направлена, то есть энтропии:

 (8)

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

Пусть, например, p_ij есть вероятность наступления события p(x_iy_j), то есть вероятность того, что если в сообщении был признак y_j, то это сообщение от источника x_i

(9)

В соответствии с определением Шеннона энтропия множества ХУ, являющихся объединением множеств источника и сообщения будет иметь вид:

(10)

Подставив в формулу (10) формулу (8) получим:

(11)

При равных условиях наибольшую энтропию имеет опыт с равновероятными исходами.

Пример. Пусть имеются 2 ящика, в каждом из которых по 12 шаров. В 1-м 3 белых, 3 чёрных и 6 красных.

Во втором каждого цвета по 4 шарика. Опыты состоят в вытаскивании по одному шарику из каждого ящика. Что можно сказать относительно неопределённости этих опытов?

Во втором опыте неопределённость опытов выше, что показывает такую формулу:

что показывает справедливость формулы (11)

Пусть имеются два опыта с одинаковым числом исходов N. В одном случае они равновероятны, а в другом нет. Каково соотношение энтропий опытов. Пусть количество знаков равно N = 2ⁿ. Все знаки равновероятны, то есть Все двоичные слова имеют длину N и Н равно: .

Покажем, что для источника сообщений с n знаками и произвольными значениями p(x_i)

(12)

Равенство (12) достигается в случае равновероятных знаков, но даже в этом случае log₂n не целое число. Это значит, что log₂n не может быть (одинаковым для всех знаков) количество необходимых альтернативных выборов. Тем не менее выбор из n знаков всегда можно осуществить с помощью N альтернативных выборов, где: N-1 < log₂ n N (13)

Для этого достаточно разбивать всякое множество знаков так, чтобы количество знаков в двух получающихся подмножествах различались не более чем на единицу. Таким образом для источника с n знаками всегда существует кодирование словами длинны N, где N-1 < log₂ n N.

Если при некотором кодировании источника сообщения i-й знак имеет длину N_i, то средняя длина слов равна (14)

Условная энтропия.

Энтропия объединения множеств. Если множество представляет собой объединение множеств источников и сообщений, взаимозависимых между собой множеств, то простое сложение их энтропий уже не применимо. Действительно, в силу взаимосвязи между множествами, информация о том, в каком состоянии находится одно множество, позволяет нам более определённо судить, как о состоянии второго множества, так и в состоянии всего объединённого множества в целом. Следовательно, энтропия объединённого множества будет меньше, чем сумма соответственных энтропий множеств. Введём для определения меры неопределённости взаимосвязанных множеств понятие условной энтропии.

Пусть имеются два зависимых множества Х и У, характеризующиеся из N источников {x_i} и из М признаков {y_j} с вероятностями p(x_i) и p(y_j).

Предположим, что множество Х находится в состоянии {x_i}. Обозначим через p(yj / xi) условную вероятность того, что множество У будет находится в состоянии {y_j}.

Если не важно, в каком состоянии находится система Х, то суммируя по всем {x_i} получаем безусловную вероятность нахождения множества в {y_j}. Получается формула:

(1)

Очевидно, что:

Определим условную энтропию системы. У при условии, что система Х будет находится в состоянии {x_i}.

(2)

Она зависит от того, в каком состоянии из состояний {x_i} будет находится множество Х. Поэтому можно найти среднее значение условной энтропии множества У относительно множества Х усреднив по всем {x_i}

Н(У/Х) = (3)

Формула (3) - условная энтропия множества У относительно множества Х. Она характеризует среднюю неопределённость состояния множества У при условии, что состояние множества Х полностью определено.

Н(У/Х) - называется полной условной энтропией , а

Н(У/х_i) - частной условной энтропией множества У относительно состояния {x_i}.

Внося p(x_i) под знак суммы и, учитывая, что p(x_i)*p(y_j/x_i) = p(x_i), условную энтропию можно записать:

Н(У/Х) = - (4)

Аналогично можно определить условную частную энтропию множества Х относительно состояния {y_j}.

Н(X/y_j) = - (5)

А полная условная энтропия Х относительно множества У:

H(X/Y) = - (6)

Формула (6) характеризует степень неопределённости множества Х относительно множества У.

Если рассмотреть множества Х и У как подмножества некоторого объединения множеств, которые характеризуются состояниями {x_i y_j} и соответствующими вероятностями p(x_i y_j), то можно определить меру неопределённости состояние объединения множеств Н(Х, У) которое называется энтропией объединения.

H(X, У) = - (7)

сообщение дискретизация шеннон энтропия

Энтропия объединения может быть выражена через энтропии составляющих её подмножеств, то есть

Н(Х, У) = Н(Х) + Н(У/Х) = Н(У) + Н(Х/У) (8)

Докажем это равенство:

Н(Х, У) =

Таким образом, энтропия двух подмножеств равна безусловной одной из них плюс общая условная энтропия другого подмножества относительно первого. Данное утверждение может быть обобщено на случай объединения произвольного числа взаимозависимых подмножеств {x_i} i = 1,n, тогда , формула будет выглядеть следующим образом:

Н(Х₁, Х₂, . . . Х_N) = Н(Х₁) + Н(Х₂/Х1) + Н(Х₃/Х₁, Х₂) + ….+ Н(Х_N/Х₁, Х₂, . . .,Х_N-1) (9)

В частном случае, когда подмножество Х и У независимы, то есть условная вероятность какого-либо состояния одного множества совпадает с безусловной вероятностью этого состояния

P(x_i/y_j) = p(x_i), тогда

H(X/У) =

= (10)

То есть в этом случае условная энтропия совпадает с безусловной энтропией и энтропия объединения двух подмножеств будет равна сумме безусловных энтропий этих подмножеств.

Н(Х/У) = Н(Х) + Н(У) (11)

Рассмотрим другой случай, когда состояние одного подмножества полностью определяет состояние другого, например, если множество У находится в состоянии {y_k}, то это означает, что мы можем указать только в каком состоянии {x_i} находится множество Х:

p(x_i/y_j) = 1, при j = k

p(x_i/y_j) = 0, при j k ,

тогда условная энтропия одного подмножества относительно другого будет равна нулю.

Н(Х/У) =

= - (12)

А энтропия объединения двух подмножеств в этом случае совпадает с безусловной энтропией каждой из подмножеств:

Н(Х/У) = Н(Х) = Н(У) (13)

Такие подмножества называются эквивалентными.

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

Н(Х/У) Н(Х)

Н(Х/У) Н(У) (14)

А энтропия объединения не превышает суммы энтропий подмножеств

Н(Х/У) Н(Х) + Н(У) (15)

Условная энтропия.

Энтропия объединения.

Понятие условной энтропии используется при определении взаимозависимости (суть взаимозависимости букв алфавита заключается в том, что вероятность появления i-й буквы в существующем месте сообщения зависит от того, какие буквы стоят перед ней и после неё, и будет отличатся от безусловной вероятности p_i известной из статистических свойств данного алфавита) между символами кодирования алфавита, для определения потерь при передаче информации по каналам связи при вычислении энтропии объединения. Пусть при передачи n-сообщений символ А встречается m-раз, В - 1 раз, а АВ - k-раз, то вероятность появления А будет равна:

p(A) =

p(B) =

p(AB) =

Условная вероятность появления символа А относительно В и вычисляется следующим образом:

p(A/B) = (1)

p(B/A) =

p(AB) = p(B) * p(A/B) = p(A) * p(B/A) (2)

От классического выражения

H = -

Условная энтропия

H(b_j/a_i) = - (3)

H(a_i/b_j) = - (4)

Индекс i выбран для характеристики произведённого состояния источника А, j = адресата В.

Формула (3), (4) - частные условные энтропии.

Общая условная энтропия В относительно сообщения А характеризует I содержащуюся в существующем символе алфавита и определяется усреднением по всем символам, то есть по всем состояниям с учётом вероятности появления каждого из состояний и равна сумме вероятностей появления символов алфавита на неопределённость, которая состоится после того, как адресат принял сигнал.

H(B/A) = -

P(b_j/a_i)log₂ p(b_ja_i) (5)

Так как p(a_i) * p(b_j/a_i) = p(a_i, b_j) - вероятности совместного появления, то формулу (5) можно записать следующим образом:

H(B/A) = - (6)

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

A \ B	b1	b2	……	bj	……	bn
a1	p(b1/a1)	p(b2/a1)	……	p(bj/a1)	……	p(bn/ai)
a2	p(b1/a2)	p(b2/a2)	……	p(bj/a2)	……	p(bn/a2)
……	……	……	……	……	……	……
ai	p(b1/ai)	p(b2/ai)	……	p(bj/ai)	……	p(bn/ai)
……	……	……	……	……	……	……
am	p(b1/am)	p(b2/am)	……	p(bj/am)	……	p(bn/am)

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

Если описывать канал связи со стороны источника сообщений, то прохождение данного вида сигнала в данном канале связи описывается распределением условных вероятностей вида p(b_j/a_i).

p(b₁/a₁) + p(b₂/a₂) + …… + p(b_j/a₁) + …… + p(b_n/a₁) (7)

Сумма вероятностей распределения (7) всегда должна равняться единице. Потеря информации, которая приходится на долю сигнала a_i описывается при помощи частной условной энтропии.

p(b₁/a₁) + p(b₂/a₁) + p(b_j/a₁) + p(b_n/a₁) = 1

H(b_j/a₁) = - (8)

Суммирование производится по j, так как i-е состояние остаётся постоянным. Чтобы учесть потери при передаче всех сигналов по данному каналу связи следует учесть все частные условные энтропии, то есть произвести двойное суммирование по i и по j. При этом

1 в случае равновероятных появлениях сигналов на выходе источника сообщения будет равно:

p(B/A) = - (9)

делим на m, так как энтропия - есть неопределённость на 1 символ.

2 в случае не равновероятного появления символов нет. В сообщении следует учесть вероятность появления каждого символа, умножив её на её соответствую частную условную энтропию.

H(B/A) = - (10)

Рассмотрим канал связи со стороны приёмника сообщений, то есть с получением сигнала b_j, предполагая , что был послан какой-то из сигналов а₁, а₂, … ,а_i, … , а_m.

При этом канальная матрица имеет следующий вид:

A \ B	b1	b2	……	bj	……	bn
a1	p(а1/b1)	p(a1/b2)	……	p(a1/bj)	……	p(a1/bn)
a2	p(a2/b1)	p(a2/b2)	……	p(a2/bj)	……	p(a2/bn)
……	……	……	……	……	……	……
ai	p(ai/b1)	p(ai/bj)	……	p(bj/ai)	……	p(ai/bn)
……	……	……	……	……	……	……
am	p(am/b1)	p(am/b2)	……	p(am/bj)	……	p(am/bn)

В этом случае единицы должны равняться сумме условных вероятностей по столбцам канальной матрицы.

p(a₁/b_j) + p(a₂/b_j) + p(a_i/b_j) + p(a_m/b_j) = 1 (11)

Частная условная энтропия:

H(a_i/b_j) = - (12)

Общая условная энтропия:

H(A/B) = - (13)

Так как p(a_i)*p(b_j/a_i) = p(a_i/b_j), то для вычисления общей условной энтропии наравне с формулой (10) может быть использована следующая формула (6).

Если заданная канальная матрица вида p(b_j/a_i) и безусловные вероятности вида p(a_i), то безусловные вероятности приёмника p(b_j) находим как , то есть если заданы безусловные вероятности источника и канальная матрица, то может быть вычислена энтропия источника

H(a_i) = - (14)

H(A) = - (15)

Если взаимозависимость связывает три элемента:

H(A/B,K) = - (16)

Энтропия объединения может быть подсчитана следующей матрицей:

p(a₁ b₁) p(a₁b₂)

P(a_i,b_j) = p(a₂b₁) p(a₂b₂)

p(a_nb₁) p(a_nb₂)

Такая матрица обладает замечательным свойством:

(17)

(18)

Это свойство в свою очередь позволяет вычислять энтропии как источника, так и приёмника сообщения непосредственно по канальной матрице.

H(A) = - (19)

H(B) = - (20)

Условные вероятности вида:

p(a_i,b_j) = (21)

p(b_j,a_i) = (22)

Количество информации на символ сообщения переданного по каналу связи, в котором влияние помех описывается при помощи энтропии объединения, вычисляется по следующей формуле:

I(A,B) = H(A) + H(B) - H(B,A).

Энтропия и информация.

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

У равновесной полностью беспорядочной системы, о состоянии такой системы наша осведомлённость минимальна, будет наибольшая энтропия. Упорядоченность системы связана с получением некоторой дополнительной информации и уменьшением энтропии.

Объективность информации.

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

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

Формула Шеннона приводит ещё к одному выводу. Пусть некоторый опыт имеет два исхода Х₁, Х₂.

Причём p(х₁) = 0,99 p(х₂) = 0,01