Формулы Хартли и Шеннона в теории информации

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

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

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

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

Клода Шеннона (1916--2001) называют «отцом теории информации».

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

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

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

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

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

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

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

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

Для оценки кол-ва информации в сообщении в теории информации, используется логарифмическая мера, введённая Р. Хартли, вероятностная интерпретация которой была дана в работах Шеннона. Если вероятность появления сообщения x есть p(x), причем 0 <р ( х)<1, то количество информации - I(x), содержащееся в сообщении, определяется формулой:

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

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

2. Формулы Хартли и Шеннона

1928 год американский инженер Ральф Хартли рассматривает процесс получения информации как выбор одного сообщения из конечного заданного множества N равновероятных событий.

Формула Хартли:

K=log2 N,

где К - количество информации, N -число равновероятных событий.

Формула Хартли может быть записана и так: N=2k

Так как наступление каждого из N событий имеет одинаковую вероятность P, то:

Р=1/N,

где P- вероятность наступления события.

Тогда, формулу можно записать иначе:

K= - log2 P.

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

Формула Шеннона:

K = - (p1 *log2 p1+ p2 *log 2p 2 + p 3 *log 2p 3 +…+ pi * log2 pi),

где pi вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Также эту формулу записывают:

.

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

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

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

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

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

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

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

Объемный подход.

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

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

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

Энтропийный (вероятностный) подход.

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

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

Подход Р. Хартли основан на фундаментальных теоретико-множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

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

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

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

Чем больше элементов в множестве, тем больше неопределенность выбора, тем больше информации.

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

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

Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

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

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

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

Поэтому функция энтропии должна удовлетворять условиям:

определена и непрерывна для всех ,

где для всех и . (Нетрудно видеть, что эта функция зависит только от распределения вероятностей, но не от алфавита).

Для целых положительных , должно выполняться следующее неравенство:

.

Для целых положительных , где , должно выполняться равенство:

.

информационный пропускной энтропийный

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

Размещено на Allbest.ru