Марковские источники сообщений

Рассмотренная модель дискретного источника сообщений имеет сравнительно узкую область применения, поскольку реальные источники вырабатывают слова при наличии статистической зависимости между буквами. В реальных источниках вероятность выбора какой-либо очередной буквы зависит от всех предшествующих букв. Многие реальные источники достаточно хорошо описываются марковскими моделями источника сообщений. Согласно указанной модели условная вероятность выбора источником очередной буквы зависит только от предшествующих. Математической моделью сообщений, вырабатываемых таким источником, являются цепи Маркова -гo порядка. В рамках указанной модели условная вероятность выбора i_k -й буквы

Если последнее равенство не зависит от времени, то есть справедливо при любом значении k, источник называется однородным. Однородный марковский источник называется стационарным, если безусловная вероятность выбора очередной буквы не зависит от k (p (x_i,k)= p (x_i)). В дальнейшем будем иметь дело только со стационарными источниками. Вычислим производительность источника для простой цепи Маркова ( =l).

В этом случае вероятность

Прологарифмировав последнее равенство, получим

.

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

Усредняя равенство по всем словам, получим количество информации, которое в среднем несет каждое слово: .

Поскольку источник стационарный, то энтропия не зависит от k и равна .

Подставляя полученный результат в (4.6) и учитывая, что всегда , имеем .

В случае Марковской цепи -го порядка H_и вычисляется аналогично и равна H_и .

Таким образом, производительность марковского источника равна неопределенности выбора очередной буквы при условии, что известны предшествующих.

Для производительности марковского источника всегда справедливо неравенство H_и .

Максимального значения, равного log m_x, производительность источника достигает, когда отсутствует статистическая зависимость между буквами в слове и когда все буквы алфавита вырабатываются с равными вероятностями. Очевидно, максимальная производительность источника полностью определяется размером алфавита m_х.

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

Для передачи заданного количества информации, равного I, требуется n = I /H_и букв, если производительность источника равна Н_и. В случае, когда производительность источника достигает своего максимального значения, равного , для передачи того же количества информации I тре­буется минимальное количество букв, равное .

Отсюда I = nН_и = n_о Н_mах или . Учитывая последнее равенство, выражение для избыточности можно записать в виде

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

Пример 1. Определить избыточность источника, если он вырабатывает статистически независимую последовательность из единиц и нулей соответственно с вероятностями, равными р =0,3 и q =0,7.

Решение. Поскольку символы в последовательности стати­стически независимы, то производительность источника

Н_и = бит.

Максимально возможная производительность источника , поскольку m_х =2. При этом символы 1 и 0 должны вырабатываться с равными вероятностями (p = q =0.5). Отсюда

Пример 2. Определить избыточность стационарного марковского источника, алфавит которого состоит из двух символов: 0 и 1. Вырабатываемая источником последовательность представляет собой простую цепь Маркова. Заданы следующие значения условных вероятностей

р (x_ik+1 | x_ik) (i_k+1 = , i_k = ):

р (0|0)=0.3; р (1|0)=0.7; р (0|1)=0.1; р (1|1)=0.9.

Решение. Безусловную вероятность того, что (k+1)-м символом последовательности будет нуль, по формуле полной вероятности можно представить в виде p_k+1 (0)= p_k (0)p(0|0) + [1- p_k (0)] p (0|l).

В правую часть неравенства входит вероятность p_k (0) того, что k -м символом последовательности будет нуль. В силу стационарности источника p_k+1 (0)= p_k (0)= p (0). Подставив в равенство значения р (0|0) и р (0|1), получим

р (0) =0.125, p (1) = 1- р (0) =0.875.

Производительность источника Н_и= р (0) Н (Х_k+1 |0)+ р (1) Н (Х_k+1 |1)=-0.125∙(0.3 log0.3+0.7 log 0.7)-0.875*(0.1log0.1 +0.9log0.9) 0.51, а избыточность источника ,

где Н_mах (Х) = 1.

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