В теории информации большое значение имеет решение вопроса о том, при каком распределении обеспечивается максимальная энтропия Н(х).
Можно показать, что при заданной дисперсии:
,
наибольшей информативностью сообщение обладает только тогда, когда состояния его элементов распределены по нормальному закону:
Так как дисперсия определяет среднюю мощность сигнала, то отсюда следуют практически важные выводы.
Передача наибольшего количества информации при заданной мощности сигнала (или наиболее экономичная передача информации) достигается при такой обработке сигнала, которая приближает распределение плотности вероятности его элементов к нормальному распределению.
В то же время, обеспечивая нормальное распределение плотности вероятности элементам помехи, обеспечивают ее наибольшую “ информативность”, т.е наибольшее пагубное воздействие на прохождение сигнала. Найдем значение энтропии, когда состояния элементов источника сообщений распределены по нормальному закону:
.
Найдем значение энтропии, когда состояния элементов распределены внутри интервала их существования а £ х £ b по равномерному закону, т.е
р(х) = 
.
Дисперсия равномерного распределения 
, поэтому (b-a) = 2 
. С учетом этого можно записать
.
Сравнивая между собой сообщения с равномерным и нормальным распределением вероятностей при условии Нн(х) = Нр(х), получаем:
Это значит, что при одинаковой информативности сообщений средняя мощность сигналов для равномерного распределения их амплитуд должна быть на 42% больше, чем при нормальном распределении амплитуд.
Пример 7. Найдите энтропию случайной величины, распределенной по закону с плотностью вероятности
р(х) = 
Пример 8. При организации мешающего воздействия при передаче информации можно использовать источник шума с нормальным распределением плотности и источник, имеющий в некотором интервале равномерную плотность распределения. Определить, какой источник шума применять экономичнее, каков при этом выигрыш в мощности.
Решение. Сравнение источников следует проводить из условия обеспечения равенства энтропий, когда каждый источник вносит одинаковое мешающее воздействие при передаче информации, но, очевидно, затрачивая при этом не одинаковые мощности.
Как было показано выше, значение энтропии, когда состояния элементов распределены по нормальному закону, можно найти по формуле:
,
где Dx = 1 Ом, а 
, т.е. sг2 - дисперсия, характеризующая мощность, выделяемую на резистора с сопротивлением 1Ом.
Для равномерного распределения энтропию можно найти по формуле:
Нр(х) = 
Так как дисперсия равномерного распределения
Так как 
Поэтому следует выбирать источник шума с нормальным распределением плотности распределения амплитуд, т.к. при той же неопределенности, вносимой им в канал связи, можно выиграть в мощности 42%.
Поэтому следует выбирать источник шума с нормальным распределением плотности, т.к. при той же неопределенности, вносимой им в канал связи, можно выиграть в мощности 42%.
Условная энтропия
До сих пор предполагалось, что все элементы сообщения независимы, т.е. появление каждого данного элемента никак не связано с предшествующими элементами.
Рассмотрим теперь два ансамбля
Х = (х1, x2, ... ,xr)
Y = (y1, y2, ..., ys) ,
которые определяются не только собственными вероятностями р(хi) и p(yj), но и условными вероятностями pxi(yj), pyj(xi), где i = 1, 2, ... , r ; j = 1, 2, ... , s.
Систему двух случайных величин (сообщений) Х, Y можно изобразить случайной точкой на плоскости. Событие, состоящее в попадании случайной точки (X, Y) в область D, принято обозначать в виде (X, Y) Ì D.
Закон распределения системы двух случайных дискретных величин может быть задан с помощью табл. 2.5.
Таблица 2.5.
| Y X | y1 | y2 | . . . | ys |
| x1 | Р11 | Р12 | . . . | Р1s |
| x2 | Р21 | Р22 | . . . | Р2s |
| : | : | : | : | : |
| xr | Рr1 | Рr2 | . . . | Рrs |
где Рij - вероятность события, заключающегося в одновременном выполнении равенства Х = xi, Y = yj. При этом
.
Закон распределения системы случайных непрерывных величин (Х, Y) задают при помощи функции плотности вероятности р(x, y).
Вероятность попадания случайной точки (Х,Y) в область D определяется равенством
.
Функция плотности вероятности обладает следующими свойствами:
1) р(x,y) ³ 0
2) 
Если все случайные точки (X,Y) принадлежат области D, то
.
Условным распределением составляющей Х при Y = yj (yj сохраняет одно и то же значение при всех возможных значениях Х) называют совокупность условных вероятностей Pyj(x1), Pyj(x2), ... , Pyj(xr)
Аналогично определяется условное распределение составляющей Y.
Условные вероятности составляющих X и Y вычисляют соответственно по формулам:
Для контроля вычислений целесообразно убедиться, что сумма вероятностей условного распределения равна единице.
Так как условная вероятность события yj при условии выполнения события xi принимается по определению
то вероятность совместного появления совокупности состояний
P(xi,yj) = P(xi) Pxi(yj).
Аналогично, условимся вероятность события xi при условии выполнения события yj:
.
Поэтому общую энтропию зависимых ансамблей X и Y определяют по формуле Шеннона:
С учетом соотношения 
получают
Н(Х,Y) = H(X) + HX(Y), где Н(Х) - энтропия ансамбля Х;
HX(Y) - условная энтропия ансамбля Y при условии, что сообщение ансамбля Х известны:
Для независимых событий Х и Y: Pxi(yj) = P(yj) и поэтому
HX(Y) = Н(Y) и, следовательно, Н(Х,Y) = H(X) + H(Y).
Если Х и Y полностью зависимы, т.е. при появлении xi неизбежно следует yj, то Р(xi,yj) равна единице при i = j и нулю при i ¹ j. Поэтому НX(Y) = 0, и , следовательно, Н(X,Y) = Н(Х), т.е. при полной зависимости двух ансамблей один из них не вносит никакой информации.
Полученное выражение для условной энтропии
можно использовать и как информативную характеристику одного ансамбля Х, элементы которого взаимно зависимы. Положив Y = X, получим
Например, алфавит состоит из двух элементов 0 и 1. Если эти элементы равновероятны, то количество информации, приходящееся на один элемент сообщения: Н0 = log m = log 2 = 1 бит. Если же, например, Р(0)=ѕ, а Р(1) = ј, то
В случае же взаимной зависимости элементов, определяемой, например, условными вероятностями Р0(0) = 2/3; P0(1) = 1/3; P1(0) = 1; P1(1) = 0, то условная энтропия
Энтропия при взаимно зависимых элементах всегда меньше, чем при независимых, т.е. H’<H.
Пример9: Задано распределение вероятностей случайной дискретной двумерной величины:
Таблица 2.6.
| Y X | 4 | 5 |
| 3 | 0,17 | 0,10 |
| 10 | 0,13 | 0,30 |
| 12 | 0,25 | 0,05 |
Найти законы распределения составляющих Х и Y.
Решение: 1) Сложив вероятности “по строкам”, получим вероятности возможных значений Х:
Р(3) = 0,17 + 0,10 = 0,27
P(10) = 0,13 +0,30 = 0,43
P(12) = 0,25 + 0,05 = 0,30.
Запишем закон распределения составляющей Х:
Таблица 2.7.
| Х | 3 | 10 | 12 |
| P(xi) | 0,27 | 0,43 | 0,30 |
Контроль: 0,27 + 0,43 + 0,30 = 1
2) Сложив вероятности “по столбцам”, аналогично найдем распределение составляющей Y:
Таблица 2.8.
| Y | 4 | 5 |
| P(yj) | 0,55 | 0,45 |
Контроль: 0,55 + 0,45 = 1
Пример10: Задана случайная дискретная двумерная величина (X,Y):
Таблица 2.9.
| Y X | y1 = 0,4 | y2 = 0,8 |
| x1 = 2 | 0,15 | 0,05 |
| x2 = 5 | 0,30 | 0,12 |
| x3 = 8 | 0,35 | 0,03 |
Найти: безусловные законы распределения составляющих; условный закон распределения составляющей Х при условии, что составляющая Y приняла значение y1 = 0,4; условный закон распределения составляющей Y при условии, что составляющая Х приняла значение х2 = 5
Решение: 1) Сложив вероятности “по строкам”, напишем закон распределения Х.
Таблица 2.10.
| X | 2 | 5 | 8 |
| P(x) | 0,20 | 0,42 | 0,38 |
2) Сложив вероятности “по столбцам”, найдем закон распределения Y.
Таблица 2.11.
| Y | 0,4 | 0,8 |
| P(y) | 0,80 | 0,20 |
3) Найдем условные вероятности возможных значений Х при условии, что составляющая Y приняла значение y1 = 0,4
Напишем искомый условный закон распределения Х:
Таблица 2.12.
| X | 2 | 5 | 8 |
| Py1(xi) | 3/16 | 3/8 | 7/16 |
Контроль: 3/16 + 3/8 + 7/16 = 1
Аналогично найдем условный закон распределения Y:
Таблица 2.13.
| Y | 0,4 | 0,8 |
| Px2(yj) | 5/7 | 2/7 |
Контроль: 5/7 + 2/7 = 1.
Пример11: Закон распределения вероятностей системы, объединяющей зависимые источники информации X и Y, задан с помощью таблицы:
Таблица 2.14.
| Y X | y1 | y2 | y3 |
| x1 | 0,4 | 0,1 | 0 |
| x2 | 0 | 0,2 | 0,1 |
| x3 | 0 | 0 | 0,2 |
Определить энтропии Н(Х), H(Y), HX(Y), H(X,Y).
Решение: 1. Вычислим безусловные вероятности Р(xi) и Р(yj) системы:
а) сложив вероятности “по строкам” , получим вероятности возможных значений Х: P(x1) = 0,5
P(x2) = 0,3
P(x3) = 0,2
б) сложив вероятности “по столбцам”, получим вероятности возможных значений Y:
P(y1) = 0,4
P(y2) = 0,3
P(y3) = 0,3
2. Энтропия источника информации Х:
3. Энтропия источника информации Y:
4. Условная энтропия источника информации Y при условии, что сообщения источника Х известны:
Так как условная вероятность события yj при условии выполнения события хi принимается по определению
поэтому найдем условные вероятности возможных значений Y при условии, что составляющая Х приняла значение x1:
Для х2: 
Для х3: 
Поэтому: HX(Y) = - [0,5 (0,8 log 0,8 + 0,2 log 0,2) +
+0,3 (0,67 log 0,67 + 0,33 log 0,33) + 0,2 (1 log 1)] = 0,635
5. Аналогично, условная энтропия источника информации Х при условии, что сообщения источника Y известны:
Для у1: 
Для у2: 
Для у3: 
6. Общая энтропия зависимых источников информации Х и Y:
Проверим результат по формуле:
Н(Х,Y) = H(X) +HX(Y) = 1,485 + 0,635 = 2,12 бит
Н(Х,Y) = H(Y) +HY(X) = 1,57 + 0,55 = 2,12 бит
Пример12: Известны энтропии двух зависимых источников Н(Х) = 5бит; Н(Y) = 10бит. Определить, в каких пределах будет изменяться условная энтропия НХ(Y) в максимально возможных пределах.
Решение: Уяснению соотношений между рассматриваемыми энтропиями источников информации способствует их графическое отображение.
При отсутствии взаимосвязи между источниками информации:
Рис. 2.5.
Если источники информации независимы, то НХ(Y) = Н(Y) = 10 бит, а НY(X) = H(X) = 5 бит, и, следовательно, Н(X,Y) = H(X) + H(Y) = 5 +10 = 15 бит. Т.е., когда источники независимы НХ(Y) = Н(Y) = 10 бит и поэтому принимают максимальное значение.
По мере увеличения взаимосвязи источников НХ(Y) и НY(X) будут уменьшаться:
Рис. 2.6.
При полной зависимости двух источников один из них не вносит никакой информации, т.к. при появлении xi неизбежно следует уj , т.е. Р(xi, уj) равно единице при i = j и нулю при i ¹ j. Поэтому
НY(X) = 0 и, следовательно, Н(X,Y) = НХ(Y) .
Рис. 2.7.
При этом НХ(Y) = Н(Y) - Н(Х) = 10 - 5 = 5 бит. Поэтому НХ(Y) будет изменяться от 10 бит до 5 бит при максимально возможном изменении Нy(Х) от 5 бит до 0 бит.
Пример13: Определите Н(Х) и НХ(Y), если Р(х1,y1) = 0,3; P(x1,y2) = 0,2;
P(x3,y2) = 0,25; P(x3,y3) = 0,1
Пример14: Определите Н(Х), H(Y), H(X,Y), если Р(х1,y1) = 0,2; P(x2,y1) = 0,4;
P(x2,y2) = 0,25; P(x2,y3) = 0,15
Взаимная энтропия
Пусть ансамбли Х и Y относятся соответственно к передаваемому и принимаемому сообщениям. Различия между Х и Y обуславливаются искажениями в процессе передачи сообщений под воздействием помех.
При отсутствии помех различий между ансамблями Х и Y не будет, а энтропии передаваемого и принимаемого сообщений будут равны: Н(Х) = Н(Y).
Воздействие помех оценивают условной энтропией НY(X). Поэтому получаемое потребителем количество информации на один элемент сообщения равно: Е(Х,Y) = Н(Х) – НY(X)
Величину Е(Х,Y) называют взаимной энтропией.
Если ансамбли Х и Y независимы, то это означает, что помехи в канале привели к полному искажению сообщения, т.е. НY(X) = Н(Х), а получаемое потребителем количество информации на один элемент сообщения:Е(Х,Y)=0.
Если Х и Y полностью зависимы, т.е. помехи в канале отсутствуют, то НY(X) = 0 и Е(Х,Y) = H(Y).
Так как НY(X) = Н(Х,Y) – H(Y), то Е(Х,Y) = H(X) + H(Y) – H(X,Y), или
.
Пример15: Определите Н(Х) и Е(Х,Y), если Р(х1,y1) = 0,3; P(x1,y2) = 0,2;
P(x2,y3) = 0,1; P(x3,y2) = 0,1; P(x3,y3) = 0,25.
Избыточность сообщений
Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения.
Пусть энтропии двух источников сообщений Н1<Н2, а количество информации, получаемое от них одинаковое, т.е. I = n1H1 = n2H2, где n1 и n2 - длина сообщения от первого и второго источников. Обозначим
При передаче одинакового количества информации сообщение тем длиннее, чем меньше его энтропия.
Величина m, называемая коэффициентом сжатия, характеризует степень укорочения сообщения при переходе к кодированию состояний элементов, характеризующихся большей энтропией.
При этом доля излишних элементов оценивается коэффициентом избыточности:
Русский алфавит, включая пропуски между словами, содержит 32 элемента (см. Пример), следовательно, при одинаковых вероятностях появления всех 32 элементов алфавита, неопределенность , приходящаяся на один элемент, составляет Н0 = log 32 = 5 бит
Анализ показывает, что с учетом неравномерного появления различных букв алфавита H = 4,42 бит, а с учетом зависимости двухбуквенных сочетаний H’ = 3,52 бит, т.е. H’< H < H0
Обычно применяют три коэффициента избыточности:
1) частная избыточность, обусловленная взаимосвязью r’ = 1 - H’/H;
2) частная избыточность, зависящая от распределения r’’ = 1 - H/ H0;
3) полная избыточность r0 = 1 - H’/ H0
Эти три величины связаны зависимостью r0 = r’ + r’’ - r’r’’
Вследствие зависимости между сочетаниями, содержащими две и больше букв, а также смысловой зависимости между словами, избыточность русского языка (как и других европейских языков) превышает 50% (r0 =1 - H’/ H0 = 1 - 3,52/5 = 0,30).
Избыточность играет положительную роль, т.к. благодаря ней сообщения защищены от помех. Это используют при помехоустойчивом кодировании.
Вполне нормальный на вид лазерный диск может содержать внутренние (процесс записи сопряжен с появлением различного рода ошибок) и внешние (наличие физических разрушений поверхности диска ) дефекты. Однако даже при наличии физических разрушений поверхности лазерный диск может вполне нормально читаться за счет избыточности хранящихся на нем данных. Корректирующие коды С 1, С 2, Q - и Р - уровней восстанавливают все известные приводы, и их корректирующая способность может достигать двух ошибок на каждый из уровней С 1 и C 2 и до 86 и 52 ошибок на уровни Q и Р соответственно. Но затем, по мере разрастания дефектов, корректирующей способности кодов Рида—Соломона неожиданно перестает хватать, и диск без всяких видимых причин отказывает читаться, а то и вовсе не опознается приводом. Избыточность устраняют построением оптимальных кодов, которые укорачивают сообщения по сравнению с равномерными кодами. Это используют при архивации данных. Действие средств архивации основано на использовании алгоритмов сжатия, имеющих достаточно длинную историю развития, начавшуюся задолго до появления первого компьютера —/еще в 40-х гг. XX века. Группа ученых-математиков, работавших в области электротехники, заинтересовалась возможностью создания технологии хранения данных, обеспечивающей более экономное расходование пространства. Одним из них был Клод Элвуд Шеннон, основоположник современной теории информации. Из разработок того времени позже практическое применение нашли алгоритмы сжатия Хаффмана и Шеннона-Фано. А в 1977 г. математики Якоб Зив и Абрахам Лемпел придумали новый алгоритм сжатия, который позже доработал Терри Велч. Большинство методов данного преобразования имеют сложную теоретическую математическую основу. Суть работы архиваторов: они находят в файлах избыточную информацию (повторяющиеся участки и пробелы), кодируют их, а затем при распаковке восстанавливают исходные файлы по особым отметкам. Основой для архивации послужили алгоритмы сжатия Я. Зива и А. Лемпела. Первым широкое признание получил архиватор Zip. Со временем завоевали популярность и другие программы: RAR , ARJ , АСЕ, TAR , LHA и т. д.В операционной системе Windows достаточно четко обозначились два лидера: WinZip (домашняя страница этой утилиты находится в Internet по адресу http :// www . winzip . com ) и WinRAR, созданный российским программистом Евгением Рошалем (домашняя страница http :// www . rarlab . com ). WinRAR активно вытесняет WinZip так как имеет: удобный и интуитивно понятный интерфейс; мощную и гибкую систему архивации файлов; высокую скорость работы; более плотно сжимает файлы. Обе утилиты обеспечивают совместимость с большим числом архивных форматов. Помимо них к довольно распространенным архиваторам можно причислить WinArj (домашняя страница http :// www . lasoft - oz . com ). Стоит назвать Cabinet Manager (поддерживает формат CAB, разработанный компанией Microsoft для хранения дистрибутивов своих программ) и WinAce (работает с файлами с расширением асе и некоторыми другими). Необходимо упомянуть программы-оболочки Norton Commander, Windows Commander или Far Manager. Они позволяют путем настройки файлов конфигурации подключать внешние DOS-архиваторы командной строки и организовывать прозрачное манипулирование архивами, представляя их на экране в виде обычных каталогов. Благодаря этому с помощью комбинаций функциональных клавиш можно легко просматривать содержимое архивов, извлекать файлы из них и создавать новые архивы. Хотя программы архивации, предназначенные для MS-DOS, умеют работать и под управлением большинства версий Windows (в окне сеанса MS-DOS), применять их в этой операционной системе нецелесообразно. Дело в том, что при обработке файлов DOS-архиваторами их имена урезаются до 8 символов, что далеко не всегда удобно, а в некоторых случаях даже противопоказано.
Выбирая инструмент для работы с архивами, прежде всего, следует учитывать как минимум два фактора: эффективность, т. е. оптимальное соотношение между экономией дискового пространства и производительностью работы, и совместимость, т. е. возможность обмена данными с другими пользователями
Последняя, пожалуй, наиболее значима, так как по достигаемой степени сжатия, конкурирующие форматы и инструменты различаются на проценты, а высокая вычислительная мощность современных компьютеров делает время обработки архивов не столь существенным показателем. Поэтому при выборе программы-архиватора важнейшим критерием становится ее способность "понимать" наиболее распространенные архивные форматы.
При архивации надо иметь в виду, что качество сжатия файлов сильно зависит от степени избыточности хранящихся в них данных, которая определяется их типом. К примеру, степень избыточности у видеоданных обычно в несколько раз больше, чем у графических, а степень избыточности графических данных в несколько раз больше, чем текстовых. На практике это означает, что, скажем, изображения форматов BMP и TIFF , будучи помещенными в архив, как правило, уменьшаются в размере сильнее, чем документы MS Word. А вот рисунки JPEG уже заранее компрессированы, поэтому даже самый лучший архиватор для них будет мало эффективен. Также крайне незначительно сжимаются исполняемые файлы программ и архивы.
Программы-архиваторы можно разделить на три категории.
1. Программы, используемые для сжатия исполняемых файлов, причем все файлы, которые прошли сжатие, свободно запускаются, но изменение их содержимого, например русификация, возможны только после их разархивации.
2. Программы, используемые для сжатия мультимедийных файлов, причем можно после сжатия эти файлы свободно использовать, хотя, как правило, при сжатии изменяется их формат (внутренняя структура), а иногда и ассоциируемая с ними программа, что может привести к проблемам с запуском.
3. 3. Программы, используемые для сжатия любых видов файлов и каталогов, причем в основном использование сжатых файлов возможно только после разархивации. Хотя имеются программы, которые "видят" некоторые типы архивов как самые обычные каталоги, но они имеют ряд неприятных нюансов, например, сильно нагружают центральный процессор, что исключает их использование на "слабых машинах".
Принцип работы архиваторов основан на поиске в файле "избыточной" информации и последующем ее кодировании с целью получения минимального объема. Самым известным методом архивации файлов является сжатие последовательностей одинаковых символов. Например, внутри вашего файла находятся последовательности байтов, которые часто повторяются. Вместо того, чтобы хранить каждый байт, фиксируется количество повторяемых символов и их позиция. Например, архивируемый файл занимает 15 байт и состоит из следующих символов:
В В В В В L L L L L А А А А А
В шестнадцатеричной системе
42 42 42 42 42 4С 4С 4С 4С 4С 41 41 41 41 41
Архиватор может представить этот файл в следующем виде (шестнадцатеричном):
01 05 42 06 05 4С 0А 05 41
Это значит: с первой позиции пять раз повторяется символ "В", с позиции 6 пять раз повторяется символ "L" и с позиции 11 пять раз повторяется символ "А". Для хранения файла в такой форме потребуется всего 9 байт, что на 6 байт меньше исходного.
Описанный метод является простым и очень эффективным способом сжатия файлов. Однако он не обеспечивает большой экономии объема, если обрабатываемый текст содержит небольшое количество последовательностей повторяющихся символов.
Более изощренный метод сжатия данных, используемый в том или ином виде практически любым архиватором, — это так называемый оптимальный префиксный код и, в частности, кодирование символами переменной длины (алгоритм Хаффмана).
Код переменной длины позволяет записывать наиболее часто встречающиеся символы и группы символов всего лишь несколькими битами, в то время как редкие символы и фразы будут записаны более длинными битовыми строками. Например, в любом английском тексте буква Е встречается чаще, чем Z, а X и Q относятся к наименее встречающимся. Таким образом, используя специальную таблицу соответствия, можно закодировать каждую букву Е меньшим числом битов и использовать более длинный код для более редких букв.
Популярные архиваторы ARJ , РАК, PKZIP работают на основе алгоритма Лемпела-Зива. Эти архиваторы классифицируются как адаптивные словарные кодировщики, в которых текстовые строки заменяются указателями на идентичные им строки, встречающиеся ранее в тексте. Например, все слова какой-нибудь книги могут быть представлены в виде номеров страниц и номеров строк некоторого словаря. Важнейшей отличительной чертой этого алгоритма является использование грамматического разбора предшествующего текста с расположением его на фразы, которые записываются в словарь. Указатели позволяют сделать ссылки на любую фразу в окне установленного размера, предшествующего текущей фразе. Если соответствие найдено, текущая фраза заменяется указателем на своего предыдущего двойника.
При архивации, как и при компрессировании, степень сжатия файлов сильно зависит от формата файла. Графические файлы, типа TIF и GIF, уже заранее компрессированы (хотя существует разновидность формата TIFF и без компрессии), и здесь даже самый лучший архиватор мало чего найдет для упаковки. Совсем другая картина наблюдается при архивации текстовых файлов, файлов PostScript, файлов BMP и им подобных.
Дата: 2019-07-30, просмотров: 343.
