ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 64
Скачиваний: 0
Подставляя выражения (2.6) и (2.7) в (2.3), получаем
п |
п |
P(xtfxk) log Р(х,/хк)= |
|
ЩХ) = — 2 |
Р(хк) V |
||
*=1 |
/=і |
|
|
п |
п |
|
|
- — 2 2 Р (Хк' |
Хі) |0§ P(xt/Xk), |
|
|
Л’=1 /=1 |
|
|
|
так как число переходов в фиксированное |
состояние 5 / |
||
может осуществиться /і различными способами. |
|||
В случае б), как следует из равенства |
|
||
Р(лу,'41), |
х(р) |
= P(xj/Xi, л-,,), |
(2.8) |
у источника столько характерных состоянии, сколько име ется различных пар (xit х п). Таких пар, очевидно, /г2. Ве роятность состояния
|
P{S,;,) = Р(а'ь а'л). |
(2.9) |
причем V |
V P(Sii,) = 1. |
|
/= 1 |
/1 = 1 |
|
Вероятность перехода в фиксированное состояние S ltj |
||
из состояния S Ul |
|
|
|
P(puJs i,j) = P(xj;xi, |
xi,)- |
Число таких переходов равно п. Подставляя в (2.3) вы ражения (2.8) и (2.9), будем иметь
ЩХ) = - |
V V |
Р(хи х„) V Р(хjfXi, х„) log- P(Xj/Xn x b) = |
|
/= 1//=1 |
;=1 |
|
П П П |
|
= |
— 2 2 |
2 р (хі' хі>’ Лу) log P(xj/xi, х„у |
|
i=l h=r1;=1 |
|
В случае в) может быть получена энтропия эргодического источника третьего порядка:
|
|
п |
п |
п |
п |
Щ Х )= |
- 2 |
|
2 |
2 ХР х»)2 РК Х^ хг х>!)l ogр (хі/хі> |
|
|
|
/= 1 j —1 ii= 1 |
q— 1 |
||
4' |
n |
n |
n |
n |
p (x i> Xj, x,„ xg) log P(xg/xh Xj, xh). |
■„)■=2 2 |
2 |
2 |
|||
|
1=1y= l /1=1 £=1 |
||||
Задача 5. Источник сообщений вырабатывает три раз личных символа X\t Хо, х3 с соответственными вероятно стями 0,4; 0,5; 0,1.
50
Вероятности появления пар заданы табл. 6. Опреде лить энтропию и сравнить ее с энтропией источника, у ко торого отсутствуют вероятностные связи.
Т â б л и ц а б
*/*/ |
*і'Т |
Л \х2 *1*3 |
*2*1 |
|
Р(Х „ Xj) |
0,1 |
0,2 |
0,1 |
0,2 |
*2*2
О СО
*2*3 |
*3*1 |
*3*2 |
*3*3 |
0 |
0,1 |
0 |
0 |
Р е ш е н и е. Энтропию найдем по формуле
|
|
я |
я |
|
|
|
|
|
|
б |
|
|
|
|
|
|
|
|
|
||
Н{Х) = |
- 2 |
2 |
Xj) log P(xi!xj). |
(2.10) |
||||||
|
|
|
1У=1 |
|
|
|
|
|
|
|
Для этого вычислим условные |
вероятности по |
формуле |
||||||||
|
|
Р(хі/х -) = P-Xh хр |
• |
|
|
|
|
|||
|
|
|
|
|
p(X/) |
|
|
|
|
|
Результаты расчета сведены в табл. |
7. |
|
|
|
||||||
|
|
|
|
|
|
|
|
Т а б л и ц а |
7 |
|
XilXj |
Xj/Xi |
*l/*2 |
*i/*3 |
*o/*i |
* 2/*2 |
*2 |
/ * 3 |
X3/XI |
XS/X-2 *з/*з |
|
P(XilXj) |
0,25 i |
0,4 |
1 |
0,5 |
0,6 |
|
0 |
0,25 |
0 |
0 |
Подставляя полученные значения вероятностей Р(хі, xj)
и P(xjx}) в (2.10), получаем Н\(Х) = 1,086 (бит).
Энтропия источника, у которого вероятностные связи между символами отсутствуют,
Щ Х ) = - 2 р (хі) 1оь р (хі) = 1,36 (бит).
Энтропия источника с независимым появлением равно вероятных символов, очевидно, равна
Н з ( Х ) = lo g 3 = 1,58 (бит).
Сравнивая энтропии Н\(Х), Н2(Х) и Н3(Х), заключа ем, что при одинаковом числе различных символов коли чество информации, приходящееся на один символ источ ника, существенно зависит от его вероятностных характе ристик: энтропия источника , максимальна и равна 1,58 бит, если вероятности символов одинаковы; неопре деленность в получении того или иного символа падает до 1,36 бит, если* известно, что символы Х\ и х2 выраба
51
тываются чаще, чем символ л'3; и, наконец, энтропия упа ла до 1,086 бит, если известно, что символы х2 и л:3, напри мер, никогда не появляются за символом х3 (см. табл. 7). Если вероятностную связь распространить на большее число символов, энтропия станет еще меньше.-Однако ее уменьшение необходимо имеет предел, на что указывает фундаментальное свойство энтропии эргодических источ ников, к рассмотрению которого мы перейдем.
§ 2. Фундаментальное свойство энтропии дискретных эргодических источников
Теорема 1. Для любых s > 0 и о > 0 можно найти такое М0, при котором эргодические последовательности С длиной М>М'о распадаются на два класса: 1) нетипич ные, сумма вероятностей которых меньше, б ; 2) типич
ные, вероятности которых удовлетворяют следующему неравенству:
(2. 11)
где Н(Х) — энтропия эргодического источника.
Д о к а з а т е л ь с т в о . Согласно теореме Бернулли, выбрав М достаточно большим, можно получить суммар ную вероятность нетипичных последовательностей, мень шую, чем заданное число е.
Так как в типичной последовательности содержится вся информация о вероятностных закономерностях, при сущих источнику, количество случаев нахождения источ ника в состоянии Sk в последовательности длиной М рав но Mp(Sk). Число переходов из состояния Sk в состояние St пропорционально количеству случаев нахождения ис точника в состоянии Sk и вероятности перехода из состо яния Sk в состояние S/:
щ т о р ( З Д ) ' ± ^ ] -
Вероятность того, что в последовательности длиной п произойдет M[P(SkjP(SjSk) ± Д]] таких переходов, рав на по теореме умножения вероятностей
P(S;/Sfe)/WlP(5*) Р(5і/5а)±’і,<
52
Вероятность конкретной последовательности С определим как вероятность всевозможных переходов:*
Р(с) = п П P{S,/Skyv'lP{S!‘] P{Sl,Sn)- r‘1.
к=\ 1,к
Логарифмируя последнее равенство, получаем
log |
1 |
' |
т |
|
Р(с)
М =•• - 2 , 2 Я(5/ - )1о§ ± Л’=11 Пк
тгп
±- n % y i \ogP{Slisly].
l' Ilk
Первая сумма в правой части равенства есть энтропия эргодического источника (см. 2.3) приМ -^со, л/)-»0. Поэтому
lim |
м |
П - оо |
что и требовалось доказать.
Следствие 1. Типичные последовательности приблизи тельно равновероятны.
Для доказательства из (2.11) найдем Р(С) |
|
2-лт(я-ьм < Р(С) < 2“ Ѵ,(Я~ 6) . |
|
При М—> со о —>0. Поэтому при достаточно |
большом М |
можно положить |
|
VIЯ |
(2.12) |
Р(С) |
Из (2.12) видно, что все последовательности С равнове
МЩХ)
роятны и число ІІХ
Следствие 2. При больших М множество типичных по следовательностей охнатынает ничтожную долю всех воз можных последовательностей, вырабатываемых эргодическим источником. Исключение составляет случай эрго дического источника с равновероятными и независимыми символами.
Общее число всевозможных последовательностей дли ны М, вырабатываемых источником,
П/Wlog п
53
откуда при М оо Nr/N -> 0, так как Н(Х) — log /г
Однако хотя типичных последовательностей мало, но только они в основном вырабатываются источником, как то следует из теоремы.
Следствие 3. Чтобы экспериментально определить эн тропию эргодического источника, у которого вероятност ные связи распространяются .на очень большое число сим волов, нам необходимо располагать последовательностью еще большей длины (М^>г); при этом вычисленная энтро
пия |
будет |
как |
угодно |
близка к своему |
пределу |
log!/ Р ( С ) = Н ( Х ) |
(см. предыдущий параграф). |
|
|||
Задача 1. Эргод^ический источник с энтропией Н(Х) = |
|||||
= 1,9 |
(бит) |
вырабатывает |
четыре различных |
символа. |
|
Найти отношение числа типичных к общему числу всевоз можных последовательностей длиной Л4=100 (симво лов).
Р е ш е н и е. Число типичных последовательностей
Nr = 2МН{Х) =
а всех возможных N—n.VI = 4100— 22СОЛI, наконец,
N T |
2l 9 { > |
|
0, 001. |
|
~JT |
2К> |
1024 |
||
|
Таким образом, типичные составляют одну тысячную часть всех возможных последовательностей.
Задача 2. Источник вырабатывает с одинаковой веро ятностью два символа А и В. Определить количество воз можных последовательностей, содержащих а Асимволов А, причем пЛА-пв= М . Определить вероятность события,
которое заключается в том, что в выработанной источни ком последовательности длиной М содержится пА симво
лов А. |
|
Р е ш е н и е. Число всевозможных |
последовательно |
стей, которое можно составить из двух |
букв, по М букв |
в каждой, уѴ= 2 w. Число последовательностей, у которых из М мест пА мест предоставлено букве А, равно числу
сочетаний из М элементов по пА:
Вероятность того, что в выработанной источником после довательности длиной М содержится п Лсимволов А, опре
делится из биномиального закона
Р |
1 \м |
М, пл |
так как по условию задачи Р ( А ) —р = 1/2 и Р(В) = q —
= 1/ 2.
Рассмотрим подробнее работу данного источника, про анализировав механизм появления последовательностей
в двух случаях. |
Пусть М = 4 . |
• |
1-й с л у ч а й . |
Тогда уѴ = 16. Выпишем |
|
эти 16 возможных |
последовательностей, вычислив для |
|
каждой из них значения С '^А и |
Рлѵ пА . |
|
Возможные последова тельности
АЛ Л А
АА А В
АА В А
АВ А А
ВА А А
АА В В
A B B A
ВВ А А
АВ А В
ВА В А
ВА А В
ВВ В А
ВВ А В
ВА В В
АВ В В
ВВ В В
|
|
|
Таблица 8 |
пА |
"в |
с 11А |
. РМ> "А |
|
|
см |
|
4 |
0 |
1 |
1/16 |
3 |
1 |
4 • |
4/ Гб |
|
|
- |
|
2 |
2 |
6 |
6/16 |
1 |
3 |
|
4 |
4/16 |
0 |
4 |
• |
1 |
1/16 |
Из табл. 8 видно, что источник чаще вырабатывает последовательности, содержащие одинаковое число сим волов А и В.
2-й с л у ч а й . М = 20. Тогда УѴ=220,= 1048476 и'вы писывание возможных сообщений бессмысленно. Поэтому приведем табл. 9.
Г5