 |
|
Лекция: Смысл энтропии Шеннона
Вводится понятие энтропии. На нескольких примерах показывается, как вычисляется энтропия дискретной случайной величины. Вводится понятие префиксного кодирования. Задачи на самостоятельную работу улучшают восприятие материала. Также много различных математических исследований
Энтропия д.с.в. - это минимум среднего количества бит, которое нужно передавать по каналу связи о текущем значении данной д.с.в.
Рассмотрим пример (скачки). В заезде участвуют 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 Про д.с.в. известно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений , результат которых - "ТЕОРИЯИНФОРМАЦИИ". Составить на основании этого результата приблизительный закон распределения вероятностей этой д.с.в. и оценить минимальную среднюю длину кодов для .