Информационные характеристики источника дискретных сообщений

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

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

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

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

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

На практике, однако чаще встречаются источники, у которых вероятность выбора одного знака сообщения зависит от того, какие знаки были выбраны источником до этого (источники с памятью). Поскольку такая связь, как правило, распространяется на ограниченное число предыдущих знаков, для описания функционирования источника целесообразно использовать цепи Маркова.

Цепь Маркова порядка  характеризует последовательность событий, вероятности которых зависят от того, какие  событий предшествовали данному. Эти  конкретных событий определяют состояние источника, в котором он находится при выдаче очередного знака. При объёме алфавита знаков  число  различных состояний источника не превышает . Обозначим эти состояния через , а вероятности выбора в состоянии  знака через . При определении вероятности  естественно предположить, что к моменту выдачи источником очередного знака известны все знаки, созданные им ранее, а следовательно, и то, в каком состоянии находится источник.

Если источник находится в состоянии , его частная энтропия  определяется соотношением

.

Усредняя случайную величину  по всем возможным состояниям , получаем энтропию источника сообщений:

,

где вероятность того, что источник сообщений находится в состоянии .

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

Определим энтропию источника сообщений для нескольких частных случаев.

Если статистические связи между знаками полностью отсутствуют, то после выбора источником знака , его состояние не меняется . Следовательно, , и для энтропии источника сообщений справедливо выражение:

.

Когда корреляционные связи наблюдаются только между двумя знаками (простая цепь Маркова), максимальное число различных состояний источника равно объему алфавита. Следовательно,

 

 и , где . При этом выражение (44.2) принимает вид

.

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

Тогда

и

   .

Подставляя эти значения в (44.2), находим

.

Аналогично можно получить выражения для энтропии источника сообщений и при протяженной корреляционной связи между знаками.

Свойства эргодических последовательностей знаков. Характер последовательностей, формируемых реальным источником сообщений, зависит от существующих ограничений на выбор знаков. Они выражаются в том, что вероятности реализации знаков различны и между ними существуют корреляционные связи. Эти ограничения приводят к тому, что вероятности формируемых последовательностей существенно различаются.

Пусть, например эргодический источник без памяти последовательно выдает знаки  в соответствии с вероятностью 0.1; 0,3; 0,6. Тогда в образованной им достаточно длинной последовательности знаков мы ожидаем встретить в среднем на один знак  три знака  и шесть знаков . Однако при ограниченном числе знаков в последовательности существуют вероятности того, что она будет содержать:

только знаки  (либо , либо );

только знаки  и один знак  или ;

только знаки  и один знак  или ;

только знаки  и один знак  или ;

только знаки  и два знака  или  и т.д.

С увеличением числа знаков вероятности появления таких последовательностей уменьшаются.

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

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

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

,

где энтропия источника сообщений.

Соотношение (44.5) называют также свойством асимптотической равномерности длинных последовательностей. Рассмотрим его подробнее.

Так как при  источник сообщений с вероятностью, сколь угодно близкой к единице, выдаёт только типичные последовательности, принимаемое число последовательностей равно  . Неопределенность создания такой последовательности с учётом их равновероятности составляет . Тогда величина  представляет собой неопределенность, которая приходится в среднем на один знак. Конечно, эта величина практически не должна отличаться от энтропии источника, что и констатируется соотношение (44.5).

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

Тогда вероятность  реализации любой типичной последовательности близка к величине

.

Логарифмируя правую и левую части выражения (44.6), получаем

  ,

откуда (при очень больших )

      .

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

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

При объёме алфавита источника  и количестве знаков в последовательности  число всех возможных последовательностей

.

Принимая во внимание соотношение (44.5), число типичных последовательностей  можно записать в виде

.

Тогда

   .

Так как , то  и неравенство усиливается с увеличением .

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

Избыточность. Следствием ограничений на выбор источником знаков является также недоиспользование их как переносчиков информации. Известная априорная информация о вероятностях выбора отдельных знаков и их сочетаний приводит к уменьшению средней неопределенности выбора источником знака, а следовательно, и переносимого им количества информации. При равновероятном и некоррелированном выборе ту же информационную нагрузку на знак можно обеспечить используя алфавит меньшего объёма. В связи с этим говорят об избыточности алфавита   источника сообщений или просто об избыточности источника.

Мерой избыточности служит величина , показывающая, насколько хорошо используются знаки данного источника:

,

где максимально возможная энтропия, равная ; энтропия источника.

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

знаков.

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

.

Поэтому говорят также об избыточности знаков в сообщении или просто об избыточности сообщения, характеризуя её тем же параметром :

   .

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

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

Однако при обмене информацией в автоматических системах естественная избыточность подлежит устранению. Это объясняется тем, что алгоритмы обнаружения и исправления ошибок, базирующихся на статистических закономерностях функционирования источника, оказываются слишком сложными для реализации их техническими средствами. В случае необходимости для повышения помехоустойчивости затем вводится "рациональная" избыточность, позволяющая обеспечить обнаружение и исправление наиболее вероятных и опасных по последствиям ошибок простыми техническими средствами. При низком уровне помех в канале связи устранение избыточности приводит к увеличению скорости передачи информации и может дать значительный экономический эффект.

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

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

.

Производительность источника  теперь можно выразить формулой

.

Как следует из (44.10), повышение производительности источника возможно не только за счёт увеличения энтропии, но и за счёт снижения средней длительности формирования знака. Длительность знаков желательно выбирать обратно пропорциональными вероятностями их появления.

Если длительность выдачи знака не зависит от состояния источника, для всех знаков одинакова и равна , то . Выражение для  принимает вид

.

Наибольшая производительность источника в этом случае достигается при максимальной энтропии.