Энтропия дискретного источника с зависимыми

Сообщениями

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

p(x_i /x_i-₁,x_i-₂, ... x_i-n)= p(x_i /x_i-₁,x_i-₂, ... x_i-n, ... x_i-n-c), (7)

где с - произвольное положительное число.

Если объем алфавита источника равен k, а число связанных букв, которые необходимо учитывать при определении вероятности очередной буквы, равно порядку источника n, то каждой букве может предшествовать M=kⁿ различных сочетаний букв (состояний источника), влияющих на вероятность появления очередной буквы x_i на выходе источника. А вероятность появления в сообщении любой из k возможных букв определяется условной вероятностью (7) с учётом предшествующих букв, т.е. с учётом M возможных состояний. Эти состояния обозначим как q₁,q₂... q_M.

Сказанное поясним двумя простыми примерами.

Пример 1. Пусть имеется двоичный источник (объём алфавита k=2) -например, источник, выдающий только буквы а и б ; порядок источника n=1. Тогда число состояний источника M=kⁿ=2¹=2(назовём их состояния q₁ и q₂). В этом случае вероятности появления букв а и б будут определяться следующими условными вероятностями:

p(à/q₁=а), p(а/q₂=б), p(á/q₁=а), p(á/q₂=б),

ãäå q₁=а - 1-е состояние q₁,

q₂=б - 2-е состояние q₂.

Âåðîÿòíîñòè ñîñòîÿíèé èñòî÷íèêà ðàâíû p(q₁)=p(a), p(q₂)=p(á).

Пример 2. Пусть по-прежнему k=2 (буквы а и б), однако число связанных букв n=2. Тогда M=2²=4 (4 возможных состояния: (а, а)=q₁, (а, б)=q₂, (б,а)=q₃, (б, б)=q₄ .

В этом случае имеем дело со следующими условными вероятностями:

p(а/а,а); p(а/а,б); p(а/б,а); p(а/б,б); p(б/а,а) . . . и т.д.

Вероятности состояний определяются равенствами p(q₁)=p(a,a), p(q₂)=p(a,б), p(q₃)=p(б,a), p(q₄)=p(б,б).

Энтропия эргодического дискретного источника определяется в два этапа.

1. Вычисляется энтропия источника в каждом из M состояний, считая эти состояния известными:

для состояния q₁ ;

для состояния q₂ ;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

для состояния q_M .

2. Далее находим H(x) путём усреднения по всем состояниям q:

Окончательно получаем

. (8)

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

Вопросы к разделу 3

1. Что такое эргодический дискретный источник?

2. Что такое состояние эргодического дискретного источника, как вычислить количество состояний?

3. Как вычисляется энтропия эргодического источника?

4. Когда энтропия эргодического источника максимальна? Чему равен этот максимум?

Избыточность источника

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

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

(9)

или

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

Однако, преднамеренная избыточность в сообщениях иногда используется для повышения достоверности передачи информации — например, при помехоустойчивом кодировании в системах передачи информации с исправлением ошибок. Большую избыточность имеет любой разговорный язык. Например, избыточность русского языка (как и других) - около 50%. Благодаря избыточности облегчается понимание речи при наличии дефектов в произношении или при искажениях речевых сигналов в каналах связи.

Вопросы к разделу 4

1. Что такое избыточность источника?

2. Какие факторы увеличивают избыточность источника?

3. Чему равна избыточность русского языка?

4. Большая избыточность – это хорошо или плохо для систем передачи информации по каналам связи?

Производительность источника

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

. (10)

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

Однако в последней формуле p(t_i) можно заменить на p(x_i) (вероятность i-го сообщения), так как эти вероятности равны. В результате получаем

, (11)

а производительность источника будет равна

. (12)

Mаксимально возможная производительность дискретного источника равна . (13)

Для двоичного источника, имеющего одинаковую длительность элементов сообщения (k=2, ) имеем

бит¤с. (14)

При укрупнении алфавита в слова по n букв, когда k=2ⁿ, , имеем

бит¤с,

что совпадает с формулой (14).

Таким образом, путём укрепления алфавита увеличить производительность источника нельзя, так как в этом случае и энтропия, и длительность сообщения одновременно возрастают в одинаковое число раз (n).

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

Вопросы к разделу 5

1. Что такое производительность дискретного источника, чему она равна?

2. Когда производительность источника максимальна, чему она равна?

3. Можно ли увеличить производительность источника путём укрупнения алфавита?

4.Как можно увеличить производительность источника при заданной длительности элементов сообщения?

6.Совместная энтропия двух источников

Пусть имеется два дискретных источника с энтропиями H(x) и H(y) и объёмами алфавитов k и l (рис. 2).

Объединим оба эти источника в один сложный источник и определим совместную энтропию. Элементарное сообщение на выходе системы содержит элементарное сообщение x_i и сообщение y_j. Алфавит сложной системы будет иметь объём k×l, а энтропия будет равна

, (15)

или

. (16)

По теореме умножения вероятностей

p(x, y)=p(x)×p(y/x)=p(y)×p(x/y).

Подставляя эти соотношения в (15), получим

. (17)

Аналогично можно получить

. (18)

Здесь H(x) и H(y) - собственная энтропия источников x и y;

(19)

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

Если источники независимы, то p(y/x)=p(y) и H(y/x)=H(y). В этом случае H(x, y)=H(x)+H(y).

Если источники частично зависимы, то H(x, y)<H(x)+H(y).

Если источники полностью зависимы (x и y - cодержат одну и ту же информацию), то H(y/x)=0 и H(x, y)=H(x)=H(y).

Вопросы к разделу 6

1. Что такое совместная энтропия двух источников?

2. Что такое условная энтропия, её физический смысл?

3. Чему равна совместная энтропия двух независимых дискретных источников и двух полностью зависимых источников?

Дата добавления: 2018-02-15; просмотров: 1176; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!