ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 308
Скачиваний: 7
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
81
????
????
= log
2
????(????
????
|????
????
)
????(????
????
)
= log
2
????(????
????
, ????
????
)
????(????
????
)????(????
????
)
= log
2
????(????
????
)????(????
????
)
????(????
????
)????(????
????
)
= 0.
Величина ????
????
= 0 говорит о том, между источниками ???? и ???? нет связи. Пе- редача информации между источниками ???? и ???? отсутствует. Передаваемую неза- висимым комбинированным источником (????, ????) информацию можно найти, ис- пользуя (5.4, 5.5)
????
????
????
,????
????
= −log
2
????(
????
???? |
????
????)
????(????
????
)
+ ????(????
????
) + ????(????
????
) = ????(????
????
) + ????(????
????
),
????
????
????
,????
????
= −log
2
????(
????
????|
????
???? )
????(????
????
)
+ ????(????
????
) + ????(????
????
) = ????(????
????
) + ????(????
????
).
2. Пусть источники
???? = {????
1
, ????
2
, … , ????
????
} и ???? = {????
1
, ????
2
, … , ????
????
} являются зави- симыми. В терминах теории информации это означает, что источники ???? и ???? об- мениваются информацией. Событие ????
????
одного источника определяет событие
????
????
другого источника (шумов в канале нет). В этом случае
????(????
????
|????
????
) = ????(????
????
|????
????
) = 1.
Взаимная информация (5.6) относительно источников ???? и ???? равна
????
????
= log
2
????(????
????
|????
????
)
????(????
????
)
= log
2
????(????
????
|????
????
)
????(????
????
)
= log
2 1
????(????
????
)
= log
2 1
????(????
????
)
=
= ????(????
????
) = ????(????
????
). (5.8)
Подставляя (5.8) в ранее полученные оценки количества информации
(5.4 и 5.5) о паре событий
(????
????
, ????
????
), получаем
????
????
????
,????
????
= −log
2
????(
????
???? |
????
????)
????(????
????
)
+ ????(????
????
) + ????(????
????
) = −????(????
????
) + ????(????
????
) + ????(????
????
) = ????(????
????
).
????
????
????
,????
????
= −log
2
????(
????
????|
????
???? )
????(????
????
)
+ ????(????
????
) + ????(????
????
) = −????(????
????
) + ????(????
????
) + ????(????
????
) = ????(????
????
).
Таким образом, количество информации ????
????
????
,????
????
об отдельном событии
(????
????
, ????
????
) зависимых связанных источников определяется количеством информа- ции одного из них, т. е. ????(????
????
) или ????(????
????
).
Вывод. В общем случае количество информации связанных источников о некотором совместном событии (????
????
, ????
????
) определяется суммой информации о каждом независимом событии этих источников с вычетом предсказанной взаим- ной информации.
Далее перейдем к рассмотрению усредненных количественных оценок ин- формации комбинированных источников.
82
1 2 3 4 5 6 7 8 9 10 ... 17
5.3. Совместная энтропия
5.3.1. Суммирующее свойство энтропии комбинированных источни-
ков
Энтропия комбинированного (объединенного) источника или источника произведения (????, ????) определяется с использование знания совместных вероятно- стей ????(????
????
, ????
????
) появления пар событий (символов) (????
????
, ????
????
) для всех ???? = 1, … , ???? и
???? = 1, … , ????. Например, ???? = {????
1
, ????
2
}, ???? = {????
1
, ????
2
}, совместные вероятности источ- ника (????, ????) задаются как
????(????
????
, ????
????
) = (
????(????
1
, ????
1
) ????(????
2
, ????
1
)
????(????
1
, ????
2
)
????(????
2
, ????
2
)
).
Определение 5.3. Совместная энтропия ????(????, ????) – среднее количество ин- формации, приходящееся на два любые события (совместное событие) источни- ков ???? = (????
1
, … , ????
????
) и ???? = (????
1
, … , ????
????
).
Так как ????(????
????
, ????
????
) = ????(????
????
, ????
????
), то ????(????, ????) = ????(????, ????).
Теорема 5.1. Если источники ???? и ???? независимы, то энтропия комбиниро- ванного источника (????, ????) равна сумме энтропий отдельных источников:
????(????, ????) = ????(????) + ????(????).
Доказательствотеоремы. Пусть ???? = {????
1
, ????
2
}, ???? = {????
1
, ????
2
}. Тогда совмест- ное независимое событие (????, ????) ∈ {????, ????} имеет вероятность ????
????
????
????
. Из определения энтропии можно записать для комбинированного источника (????, ????) выражение cовместной энтропии:
????(????, ????) = − ∑
∑
????
????
????
2
????=1 2
????=1
????
????
????
log
2
????
????
????
????
????
????
=
= − ∑
∑
????
????
????
2
????=1 2
????=1
????
????
????
(log
2
????
????
????
+ log
2
????
????
????
)=
= − ∑
????
????
????
∑
????
????
????
2
????=1 2
????=1
(log
2
????
????
????
+ log
2
????
????
????
)=
= − ∑
????
????
????
∑
(????
????
????
2
????=1 2
????=1
log
2
????
????
????
+ ????
????
????
log
2
????
????
????
)=
= − ∑
????
????
????
(∑
????
????
????
2
????=1 2
????=1
log
2
????
????
????
+ ∑
????
????
????
log
2
????
????
????
2
????=1
)=
= − ∑
????
????
????
[(log
2
????
????
????
∑
????
????
????
2
????=1 2
????=1
+ ∑
????
????
????
log
2
????
????
????
2
????=1
)]=
= − ∑
????
????
????
2
????=1
log
2
????
????
????
∑
????
????
????
2
????=1
− ∑
????
????
????
2
????=1
∑
????
????
????
2
????=1
log
2
????
????
????
83
Все вероятности символов одиночных источников в сумме должны давать значение 1, поэтому ∑
????
????
????
2
????=1
= ∑
????
????
????
= 1 2
????=1
. В результате получаем
????(????, ????) = − ∑
????
????
????
2
????=1
log
2
????
????
????
− ∑
????
????
????
2
????=1
log
2
????
????
????
= ????(????) + ????(????). (5.9)
Утверждение 5.1. Если источники ???? и ???? не являются независимыми, все- гда выполняется
????(????, ????) < ????(????) + ????(????).
5.4. Условная энтропия
Пусть имеются источники ???? = {????
1
, … , ????
????
, … , ????
????
} и ???? = {????
1
, … , ????
????
, … , ????
????
}.
Источники могут быть связаны информационным каналом, например ДСК. Ка- нал задается условными вероятностями (переходными вероятностями).
Определение 5.4. Условная энтропия ????(????|????) – это энтропия источника ????, при условии наличия (наблюдения) источника ????.
????(????|????) = ∑
????(????|????
????
)
????
????
∈????
????(????
????
).
Как видно, вычисляется среднее значение случайного процесса.
По аналогии, условная энтропия ????(????|????) – это энтропия источника ????, при условии наличия источника ????.
????(????|????) = ∑
????(????|????
????
)
????
????
∈????
????(????
????
).
Для отдельного события ????
????
∈ ???? в соответствии с определением энтро- пии (см. формулу (2.23) ???? = ∑
−????
????
????
????=1
log ????
????
) условная энтропия ????(????|????
????
) источ- ника ???? записывается в виде
????(????|????
????
) = − ∑
????(????
????
|????
????
) log
2
????(????
????
|????
????
????
????
∈????
), ???? = 1, … , ???? (5.10)
Замечание. Выражение (5.10) называется частной условной энтропией ис- точника ???? для символа (события) ????
????
источника
????.
Частная условная энтропия источника ???? определяет количество информа- ции cодержашееся в одном событии (символе) ????
????
источника
???? при условии, что имеется конкретное событие ????
????
источника
????.
По аналогии определяется частная условная энтропия источника ???? для символа (события) ????
????
источника
????.
Частная условная энтропия источника ???? – это количество информации в одном событии ????
????
источника
???? при условии, что имеется конкретное событие
(наблюдение)
????
????
источника
????.
84
Пусть ???? = {????
1
, ????
2
}, ???? = {????
1
, ????
2
}. Если известно событие ????
1
частная услов- ная энтропия
????(????|????
1
) = − ∑ ????(????
????
|????
1
)
2
????=1
log
2
????(????
????
|????
1
) =
= −????(????
1
|????
1
) log
2
????(????
1
|????
1
) − ???? (????
2
|????
1
) log
2
????(????
2
|????
1
).
Соответственно, если известно событие ????
2
, частная условная энтропия
????(????|????
2
) равна
????(????|????
2
) = − ∑ ????(????
????
|????
2
)
2
????=1
log
2
????(????
????
|????
2
) =
= −????(????
1
|????
2
) log
2
????(????
1
|????
2
) − ????(????
2
|????
2
) log
2
????(????
2
|????
2
).
Средняя величина частных условных энтропий ????(????|????
????
) по всем ????
????
∈ ???? в соответствии с их вероятностями ????(????
????
) определяется по формуле (см. определе- ние 5.4)
????(????|????) = ∑
????(????|????
????
)
????
????
∈????
????(????
????
). (5.11)
Подставив выражение (5.10) в (5.11), получаем
????(????|????) = − ∑
????(????
????
)(∑
????(????
????
|????
????
) log
2
????(????
????
|????
????
))
????
????
∈????
????
????
∈????
. (5.12)
Формулу (5.12) можно записать в виде
????(????|????) = − ∑
(∑
????(????
????
|????
????
)????(????
????
)
????
????
∈????
????
????
∈????
log
2
????(????
????
|????
????
)). (5.13)
Заменяя в (5.13) выражение ????(????
????
|????
????
)????(????
????
) на совместную вероятность
????(????
????
, ????
????
) появления двух событий ????
????
и ????
????
, (см. формулу (2.10)
????(????
????
, ????
????
) =
= ????(????
????
|????
????
)????(????
????
)
), получим
????(????|????) = − ∑
∑
????(????
????
, ????
????
) log
2
????(????
????
|????
????
????
????
∈????
)
????
????
∈????
. (5.14)
По аналогии можно дать определение и записать выражение для условной энтропии ????(????|????).
Определение 5.5. Условная энтропия ????(????|????) – это средняя энтропия ис- точника ????, при условии наличия источника ????.
????(????|????) = − ∑
∑
????(????
????
, ????
????
) log
2
????(????
????
|????
????
????
????
∈????
)
????
????
∈????
. (5.15)
Замечания:
85 1. Выражения (5.14) и (5.15) называются полной условной энтропией.
2. Условная энтропия
????(????|????) – это среднее количество информации, со- держащейся в символе источника ????, при известной его статистической связи с источником ????.
По аналогии, условная энтропия ????(????|????) – это среднее количество инфор- мации, приходящееся на символ источника ????, если известна его статистическая в сязь с источником ????.
5.4.1. Условная энтропия двоичного симметричного канала
Двоичный симметричный канал (ДСК) является моделью передачи инфор- мации по каналу с аддитивным белым гауссовским шумом. ДСК является мате- матической двоичной моделью взаимодействия двух дискретных источников без памяти. Напомним, приемник также можно считать источником информации.
Модель ДСК определяет вероятностные соотношения между источниками в про- цессе передачи информации. В этом случае известны совместная вероятность
????(????
????
, ????
????
) символов источников ???? и ???? и условная вероятность ????(????
????
|????
????
) символа ????
????
на входе канала, если на выходе наблюдается ????
????
Ставится задача определения количества информации, передаваемой по
ДСК. По другому говоря, необходимо найти количество информацию, содержа- щеся в принятом сообщении ????
????
при передаче сообщения
????
????
. Графическое пред- ставление ДСК показано на рис. 5.1.
Рис. 5.1. Модель двоичного симметричного канала передачи информации
Входными символами канала являются символы ????
1
= 0 и ????
2
= 1. Выход- нымисимволами источника являются символы ????
1
= 0 и ????
2
= 1. Если при передаче информации выходные символы канала совпадают с входными
(????
1
= ????
1
и
????
2
= ????
2
), пространство событий отражается подмножеством
{00, 11}.
Из-за воздействия шума возможен неправильный прием символов, когда выход канала не совпадает с входом (????
1
≠ ????
1
и
????
2
≠ ????
2
). В этом случае простран- ство таких событий отражается подмножеством
86
{01, 10}.
Передача информации по модели, показанной на рис. 5.1, может отобра- жаться в виде пространства событий определяемым множеством
{00, 01, 10, 11}.
Это пространство событий описывается вероятностями перехода символов входа ???? в символы выхода ????.
Достоверной передаче символов или пространству событий {00, 11} соот- ветствуют вероятности
????(0|0) и ????(1|1).
Передаче с ошибками или пространству событий {10, 01} соответствуют условные вероятности
????(1|0) и ????(0|1)
Замечанее. Если вероятности искажений ????(0|1) ≅ ????(1|0) = ????, то канал называется двоичным симметричным.
Пусть ???? – вероятность перехода (вероятность ошибки). Тогда достоверная передача информации – это событие, происходящее с вероятностью (1 − ????). Для описания ДСК воспользуемся выражением (2.20). Оно определяет вероятность
????(????
????
) выхода ДСК через распределение вероятностей источника ???? (априорные вероятности ????(????
????
)) и вероятностей перехода ????(????
????
|????
????
) по формуле
????(????
????
) = ∑
????(????
????
|????
????
)????(????
????
)
2
????=1
,
????(????
1
) = ????(????
1
|????
1
)????(????
1
) + ????(????
1
|????
2
)????(????
2
),
????(????
2
) = ????(????
2
|????
1
)????(????
1
) + ????(????
2
|????
2
)????(????
2
).
Легко увидеть, что этим выражениям соответствует матричная форма
[
????(????
1
)
????(????
2
)
] = [
????(????
1
|????
1
)
????(????
1
|????
2
)
????(????
2
|????
1
) ????(????
2
|????
2
)
] [
????(????
1
)
????(????
2
)
]. (5.16)
Двоичный симметричный канал определяется четырьмя вероятностями перехода для значений 0 ≤ ???? ≤ 0,5.
Замечание. Матрица
???? = [
????(????
1
|????
1
)
????(????
1
|????
2
)
????(????
2
|????
1
) ????(????
2
|????
2
)
]
87 называется матрицей переходных вероятностей канала (матрицей канала).
Так как для ДСК справедливо ????(0|1) ≅ ????(1|0) = ????, то
????(????
1
|????
2
) = ????(????
2
|????
1
) = ????, ????(????
1
|????
1
) = ????(????
2
|????
2
) = (1 − ????). (5.17)
Подставляя выражения (5.17) в ????, распределение вероятностей выходных символов ДСК канала записывается в виде
[
????(????
1
)
????(????
2
)
] = [
1 − ????
????
????
1 − ????
] [
????(????
1
)
????(????
2
)
].(5.18)
Вероятность того, что на выходе канала будет символ ????
1
равна
????(????
1
) = (1 − ????)????(????
1
) + ????????(????
2
).
Вероятность того, что на выходе канала будет символ ????
2
равна
????(????
2
) = ????????(????
1
) + (1 − ????)????(????
2
).
Пример 5.1 . Входными символами ДСК являются символы ????
1
= 0 и ????
2
=
1. Пусть канал характеризуется вероятностью ошибки ???? = 0,05. Источник сим- волов описывается вероятностями ????(????
1
) = 0,9 и ????(????
2
) = 0,1. Матрица ДСК имеет вид
???? = [
0,95 0,05 0,05 0,95
].
Вероятность того, что на выходе канала будет символ ????
1
равна
????(????
1
) = (1 − ????)????(????
1
) + ????????(????
2
) = 0,95 ∙ 0,9 + 0,05 ∙ 0,1 = 0,86.
Вероятность того, что на выходе канала будет символ ????
2
, равна
????(????
2
) = ????????(????
1
) + (1 − ????)????(????
2
) = 0,05 ∙ 0,9 + 0,95 ∙ 0,1 = 0,14.
Для того чтобы найти вероятность ????(????|????) достоверного получения симво- лов источника ???? приемной стороной воспользуемся формулой (2.12) из теоремы
Байеса:
????(????
????
|????
????
) =
????(
????
????|
????
????)????(????
????
)
????(????
????
)
88
Вероятность достоверного получения символов источника ???? по ДСК вы- числяется из выражения
????(????
????
|????
????
) =
????(
????
????|
????
????)????(????
????
)
????(????
????
)
С учетом выполнения условий
????(????
1
|????
1
) = ????(????
2
|????
2
) = (1 − ????) для ДСК, получаем:
????(????
1
|????
1
) =
(1 − ????)????(????
1
)
????(????
1
)
=
0,95 ∙ 0,9 0,86
= 0,9941,
????(????
2
|????
2
) =
(1 − ????)????(????
2
)
????(????
2
)
=
0,95 ∙ 0,1 0,14
= 0,678.
Как видно из примера, в условиях воздействия шума (см. также пример
2.2.1, но с другим значением уровня шума) в канале большее значение вероятно- сти правильного приема символа получается, когда он чаще передается. На ос- нове этого фундаментального принципа введения избыточности (повторяемо- сти) строятся все все современные оптимальные алгоритмы обработки сигналов в шумах, помехоустойчивое кодирование и пр.
Пример 5 .2. Вычислим условную энтропию комбинированных источни- ков на примере связи выхода и входа ДСК.
По другому можно сказать, что надо вычислить энтропию ????(????|????) источ- ника ????, при наблюдении источника ????. Входные символы канала (источник ????):
????
1
= 0 и ????
2
= 1. Выходные символы канала (источник ????): ????
1
= 0 и ????
2
= 1. Ве- роятность ошибки в канале ???? =
1 8
Решение. Применяя формулу (5.14) условной энтропии, запишем выраже- ние
????(????|????) = − ∑ ∑ ????(????
????
, ????
????
) log
2
????(????
????
|????
????
) =
2
????=1 2
????=1
= − ∑[????(????
????
, ????
1
) log
2
????(????
1
|????
????
) +
2
????=1
????(????
????
, ????
2
) log
2
????(????
2
|????
????
)] =
− [????(????
1
, ????
1
) log
2
????(????
1
|????
1
) + ????(????
1
, ????
2
) log
2
????(????
2
|????
1
)] −
− [????(????
2
, ????
1
) log
2
????(????
1
|????
2
) + ????(????
2
, ????
2
) log
2
????(????
2
|????
2
).
С учетом ????(????
????
, ????
????
) = ????(????
????
|????
????
)????(????
????
) (см. формулу (2.10), получим
????(????|????) = −[????(????
1
)????(????
1
|????
1
) log
2
????(????
1
|????
1
) + ????(????
1
)????(????
2
|????
1
) log
2
????(????
2
|????
1
)] −
89
− [????(????
2
)????(????
1
|????
2
) log
2
????(????
1
|????
2
) + ????(????
2
)????(????
2
|????
2
) log
2
????(????
2
|????
2
)].
Исходя из свойств переходных вероятностей ДСК:
????(????
????
|????
????
) = ????(????
????
|????
????
) = 1 − ????,
????(????
????
|????
????
) = ????(????
????
|????
????
) = ????,
Получаем
????(????|????) = −[????(????
1
)(1 − ????) log
2
(1 − ????) + ????(????
1
)???? log
2
????] −
− [????(????
2
)???? log
2
???? + ????(????
2
)(1 − ????) log
2
(1 − ????)] =
−[(1 − ????) log
2
(1 − ????)((????(????
1
) + ????(????
2
))] − [(????log
2
????)((????(????
1
) + ????(????
2
))] =
= −[(1 − ????) log
2
(1 − ????) + ???? log
2
????] = ????
????????????
Заметим, что для ДСК выполняются равенства ????(????
????
, ????
????
) = ????(????
????
|????
????
).
Ранее рассматривалось понятие частной условной энтропии источника ????
(5.10)
????(????|????
????
) = − ∑
????(????
????
|????
????
) log
2
????(????
????
|????
????
????
????
∈????
), ???? = 1, … , ????.
Для двоичных источников имеем
????(????|????
1
) = − ∑ ????(????
????
|????
1
)
2
????=1
log
2
????(????
????
|????
1
)
????(????|????
1
) = −[????(????
1
|????
1
) log
2
????(????
1
|????
1
) + ????(????
1
|????
2
) log
2
????(????
2
|????
1
)] и (5.19)
????(????|????
2
) = −[????(????
2
|????
1
) log
2
????(????
1
|????
2
) + ????(????
2
|????
2
) log
2
????(????
2
|????
2
)] (5.20) выражение (5.19) можно записать в виде
????(????|????
1
) = −[????(????
1
|????
1
) log
2
????(????
1
|????
1
) + ????(????
1
|????
2
) log
2
????(????
2
|????
1
)] =
= ????(????|0) = −[(1 − ????) log
2
(1 − ????) + ???? log
2
(????)] = ????
????????????
. (5.21)
Аналогично получаем выражение частной условной энтропии ????(????|????
2
):
????(????|????
2
) = −[????(????
2
|????
1
) log
2
????(????
1
|????
2
) + ????(????
2
|????
2
) log
2
????(????
2
|????
2
)] =
= ????(????|1) = −[(1 − ????) log
2
????(1 − ????) + ????log
2
????] = ????
????????????
. (5.22)
Как видно,