Geum.ru

Основы теории информации и криптографии

Вид материалаУчебное пособие

Содержание


Способы измерения информации
Вероятностный подход к измерению дискретной и непрерывной информации
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   17
^

Способы измерения информации


Понятие количества информации естественно возникает, например, в следующих типовых случаях:
  1. Равенство вещественных переменных , заключает в себе информацию о том, что равно . Про равенство можно сказать, что оно несет меньшую информацию, чем первое, т.к. из первого следует второе, но не наоборот. Равенство несет в себе информацию по объему такую же, как и первое;
  2. Пусть происходят некоторые измерения с некоторой погрешностью. Тогда чем больше будет проведено измерений, тем больше информации об измеряемой сущности будет получено;
  3. Математическое ожидание некоторой случайной величины, содержит в себе информацию о самой случайной величине, Для случайной величины, распределенной по нормальному закону, с известной дисперсией знание математического ожидания дает полную информацию о случайной величине;
  4. Рассмотрим схему передачи информации. Пусть передатчик описывается случайной величиной, , тогда из-за помех в канале связи на приемник будет приходить случайная величина, , где - это случайная величина, описывающая помехи. В этой схеме можно говорить о количестве информации, содержащейся в случайной величине, , относительно . Чем ниже уровень помех (дисперсия мала), тем больше информации можно получить из . При отсутствии помех содержит в себе всю информацию об .

В 1865 г. немецкий физик Рудольф Клаузиус ввел в статистическую физику понятие энтропии или меры уравновешенности системы.

В 1921 г. основатель большей части математической статистики, англичанин Роналд Фишер впервые ввел термин "информация" в математику, но полученные им формулы носят очень специальный характер.

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

Упражнение 4 Какое из соотношений несет в себе больше информации или ?
^

Вероятностный подход к измерению дискретной и непрерывной информации


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

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



Для непрерывных случайных величин, и , заданных плотностями распределения вероятностей , и , аналогичная формула имеет вид



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



и, следовательно,



Энтропия дискретной случайной величины в теории информации определяется формулой



Свойства меры информации и энтропии:
  1. , и независимы;
  2. ;
  3. - константа;
  4. , где ;
  5. . Если , то - функция от . Если - инъективная функцияссылка скрыта от , то .
  1. Логарифмированием из очевидного для всех неравенства (равенство устанавливается только при ) получается неравенство или





т.е. только при для всех и , т.е. при независимости и . Если и независимы, то и, следовательно, аргументы логарифмов равны 1 и, следовательно, сами логарифмы равны 0, что означает, что ;
  1. Следует из симметричности формул относительно аргументов;
  2. Если , то все члены суммы, определяющей , должны быть нули, что возможно тогда и только тогда, когда - константа;
  3. Из четырех очевидных соотношений







получается


  1. Нужно доказать или .



но , а значит аргументы у всех логарифмов не больше 1 и, следовательно, значения логарифмов не больше 0, а это и значит, что вся сумма не больше 0.

Если , то для каждого равно либо , либо 0. Но из следует , что возможно только в случае, когда - функция от .

При независимости случайных величин, и одна из них ничем не описывает другую, что и отражается в том, что для таких случайных величин, .

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

Пусть заданы дискретное случайные величины , и . и - количества очков, выпавших соответственно на 1-й и 2-й игральной кости, а . Найти , , .

Законы распределения вероятностей для дискретной случайной величины и совпадают, т.к. кости одинаковые и без изъянов.



Закон распределения вероятностей для дискретной случайной величины ,



вследствие того, что , - независимы и поэтому



будет



Таблицы, определяющие :





Закон совместного распределения вероятностей дискретной случайной величины и будет



например,



В общем случае получится





Тогда

























Здесь , что соответствует свойствам информации.

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

Расчеты можно проводить, используя 4-е свойство информации, через энтропию.





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

Рассмотрим более простой пример. Пусть дискретная случайная величина равна количеству очков, выпавших на игральной кости, а дискретная случайная величина равна 0, если выпавшее количество очков нечетно, и 1, если выпавшее количество очков четно. Найти и .

Составим законы распределения вероятностей дискретной случайной величины и .



Таким образом, при и, соответственно, при .

Составим также закон совместного распределения вероятностей этих дискретных случайных величин



Таким образом,







Точное количество выпавших очков дает точную информацию о четности, т.е. 1бит. Из бит/сим и 3-го свойства информации следует, что информация об полностью определяет , но не наоборот, т.к. бит/сим. Действительно, функционально зависит от , а от функционально не зависит.

Расчеты через энтропию будут следующими





Упражнение 5 Найти энтропию дискретной случайной величины , заданной распределением



Упражнение 6 Значения дискретной случайной величины и определяются подбрасыванием двух идеальных монет, а дискретная случайная величина равна сумме количества "гербов", выпавших при подбрасывании этих монет. Сколько информации об содержится в ?

Упражнение 7 Сколько информации об содержится в дискретной случайной величине , где независимые дискретные случайные величины и могут с равной вероятностью принимать значение либо 0, либо 1? Найти и . Каков характер зависимости между и ?

Упражнение 8 Дискретные случайные величины , - зависимы и распределены также как и соответствующие дискретные случайные величины из предыдущей задачи. Найти , если совместное распределение вероятностей и описывается законом



Упражнение 9 Дискретные случайные величины и определяются подбрасыванием двух идеальных тетраэдров, грани которых помечены числами от 1 до 4. дискретная случайная величина равна сумме чисел, выпавших при подбрасывании этих тетраэдров, т.е. . Вычислить , и .

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

Упражнение 11 Дискретная случайная величина может принимать три значения , 0 и 1 с равными вероятностями. Дискретная случайная величина с равными вероятностями может принимать значения 0, 1 и 2. и - независимы. . Найти , , , , .

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



3. Лекция: Смысл энтропии Шеннона

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

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

Рассмотрим пример (скачки). В заезде участвуют 4 лошади с равными шансами на победу, т.е. вероятность победы каждой лошади равна 1/4. Введем д.с.в. , равную номеру победившей лошади. Здесь . После каждого заезда по каналам связи достаточно будет передавать два бита информации о номере победившей лошади. Кодируем номер лошади следующим образом: 1-00, 2-01, 3-10, 4-11. Если ввести функцию , которая возвращает длину сообщения, кодирующего заданное значение , то м. о. - это средняя длина сообщения, кодирующего . Можно формально определить через две функции , где каждому значению ставит в соответствие некоторый битовый код, причем, взаимно однозначно, а возвращает длину в битах для любого конкретного кода. В этом примере .

Пусть теперь д.с.в. имеет следующее распределение



т.е. лошадь с номером 1 - это фаворит. Тогда



Закодируем номера лошадей: 1-0, 2-10, 3-110, 4-111, - т.е. так, чтобы каждой код не был префиксом другого кода (подобное кодирование называют префиксным). В среднем в 16 заездах 1-я лошадь должна победить в 12 из них, 2-я - в 2-х, 3-я - в 1-м и 4-я - в 1-м. Таким образом, средняя длина сообщения о победителе равна бит/сим или м. о. . Действительно, сейчас задается следующим распределением вероятностей: , , . Следовательно,



Итак, .

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

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

Упражнение 13 Найти энтропию д.с.в. и среднюю длину каждого из приведенных кодов для этой д.с.в.



Упражнение 14 д.с.в. равна количеству "гербов", выпавших на двух идеальных монетках. Найти энтропию . Придумать минимальный код для , вычислить его среднюю длину и обосновать его минимальность.

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

Упражнение 16 Про д.с.в. известно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений , результат которых - "ТЕОРИЯИНФОРМАЦИИ". Составить на основании этого результата приблизительный закон распределения вероятностей этой д.с.в. и оценить минимальную среднюю длину кодов для .