Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
18 Модели источника дискретных сообщений.
На практике, однако, нас чаще всего интересует не одно конкретное состояние источника, а дискретные или непрерывные последовательности состояний, реализуемых источником за длительный промежуток времени, например телеграммы, видеосюжеты и т. п. Для описания таких сообщений используются математические модели в виде дискретных и непрерывных случайных процессов.
Для построения модели необходимо знать объем l алфавита знаков (), из которых источником формируются сообщения, и вероятности создания им отдельных знаков с учетом возможной взаимосвязи между ними.
При доказательстве основных положений теории информации Шенноном использовалась модель, называемая эргодическим источником сообщений. Предполагается, что создаваемые им сообщения математически можно представить в виде эргодической случайной последовательности. Такая последовательность, как известно, удовлетворяет условиям стационарности и эргодичности. Первое означает, что вероятности отдельных знаков и их сочетаний не зависят от расположения последних по длине сообщения. Из второго следует, что статистические закономерности, полученные при исследовании одного достаточно длинного сообщения с вероятностью, близкой к единице, справедливы для всех сообщений, создаваемых источником. Из статистических характеристик в данном случае нас интересует средняя неопределенность в расчете на один знак последовательности.
Стационарный источник сообщений, выбирающий каждый знак формируемой последовательности независимо от других знаков, всегда является эргодическим. Его также называют источником без памяти.
На практике, однако, чаще встречаются источники, у которых вероятность выбора одного знака сообщения зависит от того, какие знаки были выбраны источником до этого (источники с памятью). Поскольку такая связь, как правило, распространяется на ограниченное число предыдущих знаков, для описания функционирования источника целесообразно использовать цепи Маркова.
Цепь Маркова порядка n характеризует последовательность событий, вероятности которых зависят от того, какие n событий предшествовали данному. Эти n конкретных событий определяют состояние источника, в котором он находится при выдаче очередного знака. При объеме алфавита знаков l число R различных состояний источника не превышает . Обозначим эти состояния через , а вероятности выбора в состоянии знака — через . При определении вероятности естественно предположить, что к моменту выдачи источником очередного знака известны все знаки, созданные им ранее, а следовательно, и то, в каком состоянии находится источник.
Если источник находится в состоянии , его частная энтропия H() определяется соотношением
Усредняя случайную величину H() по всем возможным состояниям q = , получаем энтропию источника сообщений:
где p() — вероятность того, что источник сообщений находится в состоянии .
Величина H(Z) характеризует неопределенность, приходящуюся в среднем на один знак, выдаваемый источником сообщений.
Определим энтропию источника сообщений для нескольких частных случаев.
Если статистические связи между знаками полностью отсутствуют, то после выбора источником знака , его состояние не меняется (R = 1). Следовательно, p()= 1, и для энтропии источника сообщений справедливо выражение:
Когда корреляционные связи наблюдаются только между двумя знаками (простая цепь Маркова), максимальное число различных состояний источника равно объему алфавита. Следовательно, R= l и = , где q = . При этом выражение (4.2) принимает вид
При наличии корреляционной связи между тремя знаками состояния источника определяются двумя предшествующими знаками. Поэтому для произвольного состояния источника , удобно дать обозначение с двумя индексами , где k= и h= .
Тогда
Подставляя эти значения в (4.2), находим
Аналогично можно получить выражения для энтропии источника сообщений и при более протяженной корреляционной связи между знаками.
Пример 4.1. Определить, является ли эргодическим стационарный дискретный источник сообщений, алфавит которого состоит из четырех знаков и , причем безусловные вероятности выбора знаков одинаковы [], a условные вероятности заданы табл 4.1.
Таблица 4.1.
Анализ табл. 4.1 показывает, что источник имеет два режима работы. С вероятностью, равной ¾, первым будет выбран один из знаков или и источник начнет формировать последовательность с равновероятным появлением знаков. Если же первым будет выбран знак (вероятность такого случая равна ), то генерируется последовательность, содержащая только знаки .
Усреднение по ансамблю предполагает наличие множества однотипных источников, примерно три четверти из которых будет работать в первом режиме, а остальные — во втором. При этом в соответствии с (4.3) энтропия источника
Среднее по последовательности (времени) вычисляется с использованием конкретной последовательности и поэтому зависит от режима функционирования источника. В первом режиме неопределенность, приходящаяся на один знак достаточно длинной последовательности (энтропия последовательности), равна 1,586 дв. ед., а во втором — нулю.
Поскольку энтропии формируемых последовательностей не совпадают с энтропией источника, он не является эргодическим.
Отметим, однако, что любой стационарный источник сообщений может быть представлен совокупностью нескольких эргодических источников, различающихся режимами работы.
PAGE \* MERGEFORMAT 3