Материал: 1 ИССЛЕДОВАННИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ ИНФОРМАЦИИ

Оказывается, для широкого класса простых цепей Маркова предел в (1.7) не зависит от начального распределения и равен единственному решению уравнения (1.6), то есть = . Такие цепи называют эргодическими.

Как определить по матрице  эргодична ли соответствующая цепь Маркова? Ответ заведомо положительный, если все элементы матрицы  положительны (не равны нулю). Более точное (но и сложнее проверяемое) условие состоит в том, что должна существовать некоторая положительная степень n₀ матрицы  такая, что все элементы матрицы ⁿ положительны при любых n ≥ n₀.

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

Состояние цепи i достижимо из состояния j, если для некоторого n вероятность перехода из состояния j в состояние i за n шагов положительна. Множество состояний C называется замкнутым, если никакое состояние вне C не может быть достигнуто из состояния, входящего в C .

Цепь называется неприводимой, если в ней не больше одного замкнутого множества. Цепь Маркова неприводима, в частности, тогда, когда все ее состояния достижимы друг из друга.

Состояние i называется периодическим, если существует такое m > 1, что вероятность перехода из i в i за n шагов равна нулю при всех n не кратных m. Цепь, не содержащая периодических состояний, называется непериодической.

Непериодическая неприводимая цепь Маркова эргодична.

Энтропия на сообщение дискретного стационарного источника

Рассмотрим произвольный дискретный стационарный источник, порождающий последовательность (x₁, x₂,…x_m,…), x_mX_m=X. Из предположения о стационарности следует, что распределение вероятностей для буквы x_m, порождаемой в момент времени m не зависит от m. Следовательно, величина энтропии этого распределения H(X_n)=H(X) также не зависит от времени. Назовем ее одномерной энтропией источника (или соответствующего случайного процесса). Обозначим ее как H₁(X).

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

Рассмотрим последовательность из n последовательных букв источника . Для стационарного процесса энтропия распределения вероятностей на таких блоках H(X₁X₂…X_n)=H(Xⁿ) не зависит от расположения блока во времени, ее называют n -мерной энтропией источника.

Величина H(Xⁿ) определяет среднее количество информации в последовательности из n букв. Нормированную величину

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

Другой подход к измерению информации, порождаемой произвольным стационарным источником, состоит в том, что при передаче буквы x_n все предыдущие буквы x₁, x₂,…x_n-1 можно считать известными декодеру. Среднее количество подлежащей передаче информации об x_n определяется величиной условной энтропии H(X_n / X₁X₂…X_n-1). В силу стационарности конкретные значения индексов не играют роли, важна лишь длина предыстории. Поэтому используется следующее обозначение:

.

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

Теорема 1.1. Для дискретного стационарного источника

A. H(X / Xⁿ) не возрастает с увеличением n;

B. H_n(X) не возрастает с увеличением n;

C. H_n(X) ≥ H(X / X^n-1);

D. .

Введем обозначения

.

Основной результат теоремы состоит в том, что H_∞(X) = H(X / X^∞). В дальнейшем, при изучении конструктивных методов кодирования, можно убедится в том: что именно эта величина определяет минимально возможные удельные затраты бит на передачу одной буквы стационарного источника.

По сути, мы рассмотрели два подхода к анализу информативности стационарного источника:

- введение расширенного алфавита, буквами которого служат блоки из n символов источника;

- учет зависимости текущей буквы от n предшествующих букв.

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

1.2 Описание лабораторного макета

Лабораторный макет представляет собой программный пакет обладающий следующими функциями:

- проводить оценку статистических и информационных характеристик дискретных источников информации (для источников с наличием и отсутствием зависимости между соседними символами);

- моделирование дискретного постоянного источника информации (ДПИ) и дискретного источника информации с помощью цепи Маркова первого, второго и третьего порядка;

- кодирование и декодирование сообщений источника неравномерным посимвольным кодом Шеннона-Фано, Хафмена

- кодирование и декодирование сообщений источника алгоритмом арифметического кодирования;

- кодирование и декодирование сообщений методами учитывающими взаимозависимость соседних символов («Стопка книг», LZ, LZW).

1.3 Порядок выполнения работы

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

2. Провести исследование дискретного источника с помощью модели ДПИ (не учитывающей взаимозависимость символов).

   1. Загрузите заданный преподавателем анализируемый текстовый файл.

   2. Приняв длину символов источника равной одной букве, оценить вероятности появления символов и информационный характеристики источника. Результат занести в отчет (таблица 1.2).

   3. Повторить эксперимент п.п. 2.2 приняв длину символов источника равной двум, трем, четырем буквам. Результат занести в отчет, таблицу заполнить для 10-ти наиболее чаше встречаемых комбинаций.

   4. Повторить эксперимент п.п. 2.2 приняв длину символов источника равной одному биту. Результат занести в отчет.

   5. Сравнить результаты и сделать выводы.

Таблица 1.2

H(X) =

H₁(X) =

H_max(X) = log(N) =

r= (H_max(X) - H(X))/H_max(X) =

3. Провести исследование дискретного источника с помощью модели учитывающей взаимозависимость символов (цепь Маркова 1-го и выше порядка).

   1. Загрузите заданный преподавателем анализируемый текстовый файл.

   2. Приняв связность цепи Маркова равной единице, оценить условные вероятности появления символов и информационный характеристики источника. Результат занести в отчет (таблица 1.3), таблицу заполнить для двух значений y_j соответствующих наиболее чаше встречающимся символам.

Таблица 1.3

H(X|Y) =

H₁(X|Y) =

H_max(X|Y) = log(N) =

r = (H_max(X|Y) - H(X|Y))/H_max(X|Y) =

3. Повторить эксперимент п.п. 3.2 приняв связность цепи Маркова равной двум, трем. Результат занести в отчет заполнив таблицы 5.4 и 5.5 аналогично предыдущему пункту.

Таблица 1.4

H(X|YZ) =

H₁(X|YZ) =

H_max(X|YZ) = log(N) =

r = (H_max(X|YZ) - H(X|YZ))/H_max(X|YZ) =

Таблица 1.5

H(X|YZW) =

H₁(X|YZW) =

H_max(X|YZW) = log(N) =

r = (H_max(X|YZW) - H(X|YZW))/H_max(X|YZW) =

4. Сравнить результаты и сделать выводы.

1. Моделирование дискретного постоянного источника информации (без учета взаимозависимости символов сообщения).

   1. Загрузите файл с параметрами источника полученный в результате выполнения п.2.2.

   2. Задайте длину сообщения, генерируемую источником равною 1 000 символов.

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

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

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

2. Моделирование дискретного источника информации с учетом взаимозависимости символов сообщения.

   1. Загрузите файл с параметрами источника полученный в результате выполнения п.3.2.

   2. Задайте длину сообщения, генерируемую источником равною 1 000 символов.

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

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

   5. Повторить эксперимент для других значений связности цепи Маркова.

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