Материал: 6593
56
In X (t);Y (t) = Hn X (t) − Hn X (t)
Y (t) ,
а средняя информация, приходящаяся на один отсчет (символ)
I X (t);Y (t) |
= H X (t) |
− H X (t) |
Y (t) . |
(2.4.8) |
||
|
|
|
|
|
|
|
Возможен и другой способ вычисления средней энтропии (условной и безусловной) дискретной стационарной случайной последовательности, приводящий к тем же результатам.
Энтропия последовательности X(t) равна
H X (t ) |
= lim H X (n ) |
X (1) , ,X (n −1) |
(2.4.9) |
||
|
|
n →∞ |
|
|
|
и характеризует среднее количество дополнительной информации, доставляемой одним символом в реализациях бесконечной длины.
Средняя условная энтропия последовательности Х(t) вычисляется по формуле
H X (t) Y (t) |
= |
(2.4.10) |
|
|
|
|
|
lim H X (n) |
X (1) ,…, X (n−1),Y (1),…,Y (n) . |
||
n→∞ |
|
|
|
РЕШЕНИЕ ТИПОВЫХ ПРИМЕРОВ
Пример 2.4.1. Сообщение X есть стационарная последовательность независимых символов, имеющих ряд распределения Сигнал Y является последователь-
xj |
x1 |
x2 |
x3 |
ностью двоичных символов, связанных |
|
p(xj) |
0,2 |
0,1 |
0,7 |
||
с сообщением следующим неудачным |
образом: x1→00, x2→00, x3→1.
Определить: а) средние безусловную и условную энтропии, приходящиеся на 1 символ сообщения;
б) средние безусловную и условную энтропии, приходящиеся на 1 символ сигнала;
в) среднюю взаимную информацию в расчете на 1 символ сообщения.
Решение. Символы в последовательности на выходе источника независимы, поэтому из (2.4.3)
57
HX (t) = H1 X (t) = H [X ]=
−0, 2 log 0, 2 −0,1 log 0,1−0,7 log 0,7 =1,1568 áèò/ñèì â.
Обозначив y1=00, у2=1, вычислим условные и безусловные
вероятности сигнала: |
|
|
p (y1 x1 )= p (y1 |
x2 )=1, |
p (y1 x3 )= 0, |
p (y2 x1 )= p (y2 |
x2 )= 0, |
p (y2 x3 )=1, |
p (y1 )= p (x1 ) p (y1 
x1 )+ p (x2 ) p (y1 
x2 )+ p (x3 ) p (y1 
x3 )= 0,2 +0,1 = 0,3,
p (y2 )= 0,7.
Энтропия случайной величины Y равна
H(Y )= −0,3 log 0,3 −0,7 log 0,7 = 0,8813 áèò,
аусловная энтропия H(Y/X)=0, так как сигнал однозначно определяется сообщением.
Взаимная информация
I (X ;Y )= H (Y )− H (Y
X )= 0,8813 áèò.
Условная энтропия сообщения
H (X 
Y )= H (X )− I (X ;Y )=1,1568 −0,8813 = 0,2755 áèò.
Итак, получаем, что условная энтропия сообщения равна 0,2755 бит/симв, а взаимная информация в расчете на 1 символ сообщения равна 0,8813 бит/симв.
Среднее количество символов сигнала, приходящихся на 1 символ сообщения, равно
3
L = ∑p (xj )lj = 0,2 2 +0,1 2 +0,7 1 =1,3 ñèì â,
j=1
где lj – длина кодового слова, соответствующего xj. Энтропия последовательности Y(t) равна
HY (t) = H (Y )
L = 0,8813
1,3 = 0,6779 áèò/ñèì â,
аусловная энтропия равна нулю.
Таблица 2.4.1
X(k) |
|
X(k-1) |
|
|
x1 |
x2 |
x3 |
x1 |
0,2 |
0,3 |
0,6 |
x2 |
0,4 |
0,5 |
0,1 |
x3 |
0,4 |
0,2 |
0,3 |
Пример 2.4.2. Вычислить энтропию однородной неразложимой марковской последовательности, заданной матрицей
58
вероятностей переходов p (X (k )
X (k −1) ) от символа X (k −1) к
символу X (k ) (табл. 2.4.1).
Решение. Однородность последовательности проявляется в том, что при k → ∞ безусловная вероятность pj того, что k-й символ примет значение xj, не зависит от k и от значения перво-
го символа |
и |
связана с вероятностями переходов |
prj = p (x (jk ) |
xr(k −1) ) |
|
m
уравнением p j = ∑pr prj .
r =1
Записываем это уравнение для каждого j и получаем систему уравнений
p1 = p1 p11 + p2 p21 + p3 p31, p2 = p1 p12 + p2 p22 + p3 p32 ,
p3 = p1 p13 + p2 p23 + p3 p33.
Подставляем численные значения вероятностей переходов и получим
−0,8 p1 +0,3p2 +0,6 p3 = 0, 0,4 p1 −0,5 p2 +0,1p3 = 0,
0,4 p1 +0,2 p2 −0,7 p3 = 0.
Определитель этой системы равен нулю, поэтому вероятности pj определяется с точностью до постоянного множителя. Выбираем его так, чтобы выполнялось условие нормировки
p1 + p2 + p3 =1, и получим
p1 = 0,3548, р2 = 0,3441, р3 = 0,3011.
Энтропия последовательности Н[Х(t)] по смыслу есть средняя дополнительная (условная) информация, приносимая одним символом последовательности, поэтому для марковской последовательности ее можно вычислить по формуле (2.4.9)
59
H X (t) = H (x(k )
X (k −1) )= ∑m pj H (X (k )
X (k −1) )=
|
|
|
|
j=1 |
m |
|
m |
|
= 0,3548 1,5219 +0,3441 1,4855 + |
= ∑pj |
∑pjr log pjr |
|||
j=1 |
r=1 |
|
|
|
0,3011 1,2955 =1,4412 áèò
ñèì â.
ЗАДАЧИ
2.4.1. Периодически, один раз в 5 с, бросают игральную кость, и результат каждого бросания передают при помощи
трехразрядного |
двоичного |
числа. |
Найти: |
|
а) |
энтропию |
шестеричной последовательности на входе, |
||
б) |
энтропию |
двоичной последовательности |
на выходе, |
|
в) среднюю информацию, содержащуюся в отрезке выходного сигнала длительностью 1 мин.
2.4.2. Известно, что энтропия, приходящаяся на 1 букву русского текста, составляет приблизительно 1,2 бит. Каково минимальное среднее количество десятичных символов, необходимых для передачи информации, содержащейся в телеграмме из 100 букв?
2.4.3. Периодически проводятся тиражи лотереи. В каждом тираже участвуют 1024 билета, но выигрывает из них один. Результат каждого тиража передается при помощи 10-разрядного двоичного числа. Из-за наличия помех возможны искажения символов с вероятностью 0,001. Ошибки в отдельных символах
независимы. |
Найти: |
|
а) |
энтропию |
исходной 1024-ичной последовательности, |
б) |
энтропию |
двоичной последовательности на входе, |
в) |
энтропию |
двоичной последовательности на выходе, |
г) |
энтропию |
выходной 1024-ичной последовательности, |
д) среднее количество передаваемой информации в расчете на двоичный символ входной последовательности.
2.4.4. В условиях задачи 2.4.3 для повышения помехоустойчивости каждый двоичный символ передается трехкратно. В месте приема из каждых трех символов формируется один,
60
причем решение выносится простым «большинством голосов». Найти:
а) энтропию двоичной последовательности на выходе, б) среднее количество информации в расчете на передаваемый двоичный символ.
2.4.5. В некотором районе состояние погоды зависит только от того, что было накануне. При ежедневной регистрации погоды различают лишь два состояния: x1 – ясно и x2 – переменно. Вероятности переходов равны
p (x1 |
x1 )= 0.9 |
p (x2 |
x1 )= 0.1 |
p (x1 |
x2 )= 0.7 |
p (x2 |
x2 )= 0.3 |
Вычислить энтропию последовательности сообщений о состоянии погоды.
2.4.6. Найти энтропию последовательности на выходе троичного марковского источника, если вероятности всех переходов равны 1/3.
2.4.7. Буквы в последовательности на выходе источника выбираются из алфавита А, В, С и образуют марковскую последовательность. Совместные вероятности всевозможных пар букв заданы в табл. 2.4.2.
Таблица 2.4.2
X |
X(k+1) |
|
|
(k) |
А |
В |
С |
А |
0 |
0 |
0 |
,2 |
,05 |
|
,15 |
|
0 |
0 |
0 |
,15 |
,05 |
|
,1 |
|
0 |
0 |
0 |
,05 |
,2 |
|
,05 |
Вычислить энтропию последовательности.
2.4.8. Троичная марковская последовательность задана матрицей вероятности переходов P от X(k) (строка) к X(k+1) (столбец)