ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 311
Скачиваний: 7
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
90
????(????|????
1
) = ????(????|????
2
) = ????
????????????
.
Замечание. Если известны априорные вероятности двоичного источника ????
(входа ДСК канала), условная энтропия
????(????|????) источника ???? (выхода ДСК ка- нала) может вычислятьcя по определению энтропии
????(????|????) = ∑
????(????|????
????
)
????
????
∈????
( )
i
P x ,
(????|????) = ????(????|????
1
)
1
( )
P x
+ ????(????|????
2
)
2
(
)
P x .
С учетом ????(????|????
1
) = ????(????|????
2
) = ????
????????????
,
????(????|????) = ????
????????????
((
1
( )
P x
+
2
(
)
P x
) = ????
????????????
Вывод. При связи двух источников по ДСК условная энтропия на выходе не зависит характеристик источника входа.
Возвращаясь к решению примера 5.2, определяем количество информации передаваемой по ДСК. Применяя (5.21) и (5.22), получаем
????(????|0) = ????(????|1) = ????
????????????
= − ???? log
2
???? − (1 − ????) log
2
(1 − ????) =
= −
1 8
log
2 1
8
−
7 8
log
2 4
8
= 0,54 бит/символ.
Таким образом, количество информации ????(????|0), приходящееся на один символ источника ???? при наличии (наблюдении) символа ????
1
= 0 источника ???? равно ????
????????????
= 0,54 бит/символ. Соответсвенно, количество информации ????(????|1) также равно ????
????????????
= 0,54 бит/символ.
Как видно, наличие статистической зависимости источника ???? от источника
????, которая отражается переходными вероятностями ДСК, приводит к уменьше- нию информации, выдаваемой источником ????. Полученное значение условной эн- тропии ????(????|????) указывает на определенные информационные проблемы, связан- ные с уменьшеним количества принимаемой информации в ДСК с шумом.
Выводы:
1. Условная энтропия ДСК определяется функцией Шеннона (2.23).
Напомним, функция Шеннона характеризует дискретный источник двух незави- симых событий ???? = {0, 1} с вероятностями ???? и (1 − ????).
2. Условная энтропия ДСК не зависит от вероятностей символов входа ка- нала, а зависит от уровня шумов в канале.
Замечание. В примере 5.2 источники ???? и ???? связаны между собой каналом.
В этом случае входные символы источника ???? позволяют делать некоторое пред- положение о символах источника ????. Эта заранее получаемая информация сни- жает степень неопределенности источника ????, и, следовательно, уменьшает сред- нее ожидаемое количество полученной информации – энтропию.
91
1 ... 4 5 6 7 8 9 10 11 ... 17
5.5. Соотношение между совместной и условной энтропией
Вновь обратимся к определению совместной энтропии комбинированного источника как математическое ожидание информации, приходящееся на любую пару (????
????
, ????
????
) событий этих источников. Не теряя общего представления о комби- нированном источнике, ограничимся рассмотрением двух источников ???? =
{????
1
, ????
2
, … , ????
????
} и ???? = {????
1
, ????
2
, … , ????
????
}. Совместное событие (????, ????) ∈ (????, ????) характе- ризуется совместной вероятностью ????
????
, ????
????
. Из определения понятия энтропии можно записать для комбинированного источника (????, ????), ???? = {????
1
, ????
2
}, ???? =
{????
1
, ????
2
} следующее выражение:
????(????, ????) = − ∑
∑
????(????
????
,
2
????=1 2
????=1
????
????
) log
2
????(????
????
, ????
????
). (5.23)
Заменяя в (5.23) совместную вероятность ????(????
????
, ????
????
) на выражение
????(????
????
)????(????
????
|????
????
) = ????(????
????
)????(????
????
|????
????
), (см. формулу (2.10)), получим
????(????, ????) = − ∑
∑
????(????
????
)????(
2
????=1 2
????=1
????
????
|????
????
) log
2
((????(????
????
) ????( ????
????
|????
????
)).
Раскрывая логарифм произведения, преобразуем последнее выражение к виду
????(????, ????) = − ∑ ∑ ????(????
????
)????(
2
????=1 2
????=1
????
????
|????
????
)((log
2
????(????
????
) + log
2
????( ????
????
|????
????
)) =
= − ∑ ∑ ????(
2
????=1 2
????=1
????
????
|????
????
)(????(????
????
) log
2
????(????
????
) + ????(????
????
|????
????
)????(????
????
)log
2
????( ????
????
|????
????
)) =
= − ∑ (∑(????(????
????
|????
????
)????(????
????
)log
2
????(????
????
) + ∑ ????(????
????
|????
????
)????(????
????
)log
2
????(????
????
|????
????
)
2
????=1 2
????=1
)
2
????=1
Далее вынесем за знак суммирования по индексу ???? вероятности с индексом суммирования по индексу ????:
????(????, ????) = − ∑ (????(????
????
)log
2
????(????
????
) ∑ ????(????
????
|????
????
) + ????(????
????
) ∑ ????(????
????
|????
????
)log
2
????(????
????
|????
????
)
2
????=1 2
????=1
)
2
????=1
Последнее выражение запишем в виде суммы двух слагаемых:
92
????(????, ????) = − ∑ ????(????
????
)log
2
????(????
????
) ∑ ????(
2
????=1 2
????=1
????
????
|????
????
) − ∑ ????(????
????
)
2
????=1
∑ ????(????
????
|????
????
)log
2
????(????
????
|????
????
)
2
????=1
Так как
∑
????(
2
????=1
????
????
|????
????
) = 1 и ∑
????(????
????
)
2
????=1
= 1, получаем
????(????, ????) = − ∑
????(????
????
)log
2
????(????
????
)
2
????=1
− ∑
????(????
????
|????
????
)log
2
????(????
????
|????
????
)
2
????=1
,
????(????, ????) = ????(????) + ????(????|????). (5.24)
Аналогично, можно записать формулу
????(????, ????) = ????(????) + ????(????|????). (5.25)
Совместная энтропия комбинированного источника представляется сум- мой энтропии одного источника и частью энтропии другого источника.
Вывод. Если между источниками имеется статистическая зависимость, априорные знания свойств одного источника приводят к уменьшению среднего количества информации на выходе этого источника.
5.6. Пропускная способность канала
Ранее была рассмотрена математическая модель передачи информации по каналу с шумами, рис. 2.2. Модель описывает передачу информацию источника
???? = {????
1
, … , ????
????
} с вероятностями {????(????
1
), … , ????(????
????
)} получателю этой информации на выход канала ???? = {????
1
, … , ????
????
} с вероятностями {????(????
1
), … , ????(????
????
)}. Каналы с шумами характеризуются условными вероятностями ????(????|????) для всех ???? ∈ ???? и ???? ∈
????. Напомним, вероятность ????(????
????
|????
????
) – это вероятность получения на приемной стороне символа ????
????
при передаче символа
????
????
Если при передаче информации не было ошибок – это свидетельствует о том, что алфавиты источников ???? и ???? полностью совпадают. Достоверный прием, т. е. без ошибок, соответствует условию
????(????
????
|????
????
) = 1 при ???? = ???? и ????(????
????
, ????
????
) = 0 при ???? ≠ ????.
Событие ????
????
одного источника определяет событие
????
????
другого источника
(шумов в канале нет). Тогда условная энтропия (5.14)
????(????|????) = − ∑
∑
????(????
????
, ????
????
) log
2
????(????
????
|????
????
????
????
∈????
)
????
????
∈????
= 0.
93
Используя понятия теории информации, можно утверждать, что величина условной энтропии равная ????(????|????) = 0, говорит о том, что среднее количество информации которое несет каждый символ источника ???? равно нулю из-за полной статистической связи с источником ????. Источник ???? находится в полной зависи- мости от ???? (и наоборот).
5.6.1. Средняя взаимная информация
Ранее были получены выражения (5.4, 5.5) оценки количества информаци пары отдельных совместных событий (????
????
, ????
????
) источника произведения (????, ????). т. е.
????(????
????
, ????
????
) = −????
????
+ ????(????
????
) + ????(????
????
), (5.26) где ????
????
= log
2
????(
????
????|
????
???? )
????(????
????
)
= log
2
????(
????
???? |
????
????)
????(????
????
)
– взаимная информация совместных одиноч- ных событий (????
????
, ????
????
),
????(????
????
) = −log
2
????(????
????
) – количество информации о событии ????
????
источника
????,
????(????
????
) = −log
2
????(????
????
) – количество информации о событии ????
????
источника
????.
Напомним, для связанных событий ????
????
и
????
????
????
????
≠ 0.
Из (5.26) следует, что количество информации ????(????
????
, ????
????
) о событии (????
????
, ????
????
) снижается на величину взаимной информации ????
????
из-за связи источников, напри- мер, по каналу.
Используя (5.26), определим значение взаимной информации
????
????
= ????(????
????
) + ????(????
????
) − ????(????
????
, ????
????
). (5.27)
На практике представляет интерес среднее количество взаимной информа- ции источника произведения (????, ????) (всей принятой информации). Используя форму выражения (5.27), усредненное количество взаимной информации (через энтропии), получим
????(????; ????) = ????(????) + ????(????) − ????(????, ????), (5.28) где ????(????) и ????(????), соответственно, энтропии источников ???? и ????,
????(????, ????) = − ∑
∑
????(????
????
,
????
????=1
????
????=1
????
????
) log
2
????(????
????
, ????
????
) – совместная энтропия источника
(????, ????).
Формула (5.28) определяет среднею взаимную информацию как разность между суммой средних количеств информации источников ???? и ???? и средним ко- личеством информации источника произведения ????, ????.
С использование терминологии теории информации среднее количество взаимной информации ????(????; ????) характеризует степень статистической связи между источниками ???? и ????.
94
Для независимых источников ???? и ???? взаимная информация ????(????; ????) = 0 (см. подраздел 5.2). Тогда из (5.28)
????(????, ????) = ????(????) + ????(????).
Как видно, полученное выражение совпадает с определением совместной энтропии (см подраз. 5.3), как максимальной средней величины количества ин- формации для всех пар (????
????
, ????
????
) независимых событий источника произведения
(????, ????).
Учитывая соотношения между совместной и условной энтропией (5.24 и
5.25):
????(????, ????) = ????(????) + ????(????|????),
????(????, ????) = ????(????) + ????(????|????), дважды преобразуем формулу взаимной информации (5.28).
????(????; ????) = ????(????) + ????(????) − ????(????, ????) = ????(????) + ????(????) − ????(????) − ????(????|????).
????(????; ????) = ????(????) − ????(????|????).
????(????; ????) = ????(????) + ????(????) − ????(????, ????) = ????(????) + ????(????) − ????(????) − ????(????|????),
????(????; ????) = ????(????) − ????(????|????).
Определение 5.6. Средняя взаимная информация событий источника ???? при условии наличия событий источника ???? (на выходе канала) равна
????(????; ????) = ????(????) − ????(????|????), (5.29) где ????(????) = − ∑
????(????
????
) log
2
????(????
????
)
????
????
∈????
,
????(????|????) = − ∑
∑
????(????
????
, ????
????
) log
2
????(????
????
|????
????
????
????
∈????
)
????
????
∈????
, (см. (5.15)).
Формула (5.29) определяет среднее количество информации об источнике
???? с учетом информации выдаваемой источником ????. Формула (5.29) позволяет дать следующую интерпретацию передачи информации в канале с шумом. Сред- няя взаимная информация ????(????; ????) равна разности среднего количества информа- ции источника ???? (на входе канала) и среднего количества информации на выходе канала, т. е. после приема ????. Величина ????(????|????) определяет среднее количество потеренной информации из-за воздействия помех. Тогда ????(????; ????) определяет среднее количество принятой информации.
Апостериорная информация источника ???? об источнике ???? уменьшает не- определенность источника ???? – энтропию ????(????). В терминах теории информации среднее количество информации, приходящееся на один символ источника ????, но
95 после получения апостериорных знаний о событиях источника ???? (на выходе ка- нала) – это условная энтропия ????(????|????). Величина ????(????|????) характеризует неопре- деленность источника, которая остается после приема ????.
По аналогии, cредняя взаимная информация событий источника ???? при условии наличия событий источника ???? (на входе канала) равна
????(????; ????) = ????(????) − ????(????|????), (5.30) где ????(????) = − ∑
????(????
????
) log
2
????(????
????
)
????
????
∈????
,
????(????|????) = − ∑
∑
????(????
????
, ????
????
) log
2
????(????
????
|????
????
????
????
∈????
)
????
????
∈????
, (см. (5.14)).
Формула (5.30) определяет среднее количество информации об источнике
???? с учетом информации, выдаваемой источником ????.
Вернемся к анализу выражения (5.29) ????(????; ????) = ????(????) − ????(????|????). Получе- ние апостериорных знаний о событиях источника ???? (на выходе канала) приводит к уменьшению среднего количества информации, приходящей на символ источ- ника ???? на выходе канала. Подставляя в (5.29) выражения ????(????) и ????(????|????), полу- чаем формулу средней взаимной информации (среднего количества информа- ции) на выходе канала
????(????; ????) = ∑
????(????
????
)
1
log
2
????(????
????
)
????
????
∈????
− (∑
∑
????(????
????
, ????
????
)
1
log
2
????(????
????
|????
????
????
????
∈????
)
????
????
∈????
. (5.31)
Формула (5.31) позволяет осуществлять анализ системы передачи инфор- мации (источник – канал – источник). Из формулы следует, что среднее количе- ство информации, получаемое при наблюдении источника ???? (выхода канала), за- висит:
– от статистических характеристических источника ????, т. е. от распределе- ния вероятностей ????(????
????
) символов источника ????;
– от статистических характеристических канала, т. е. от переходных харак- теристик (условных вероятностей ????(????
????
|????
????
) канала) – матрицы канала.
Рассмотрим характераные свойства канала.
1. В канале без шумов вероятность ошибки
???? = 0. Совместная вероятность
????(????
????
, ????
????
) = 0 при ???? ≠ ????. В этом случае компонента
????(????|????) = ( ∑ ∑ ????(????
????
, ????
????
)
1
log
2
????(????
????
|????
????
)
????
????
∈????
????
????
∈????
) выражений (5.29, 5.31) равна нулю.
2. В канале без шумов вероятность ошибки
???? = 0. Совместная вероят- ность ????(????
????
, ????
????
) = 1 при ???? = ????. Вероятность ????(????
????
|????
????
) = 1 при ???? = ???? . Тогда значе- ние компоненты
96 1
log
2
????(????
????
|????
????
)
= − log
2
????(????
????
|????
????
) = − log
2 1 = 0 выражений (5.29, 5.31) равно нулю . Компонента ????(????|????) также становится ну- левой.
Отсюда следуют фундаментальные выводы теории информации:
1. Среднее количество информации, выдаваемое источником ???? в канале без шумов достигает максимума:
????(????; ????)
max
= ????(????).
2. В канале без шумов вся информация источника
???? передается на выход канала достоверно.
3. При увеличении вероятности ошибки
???? в канале среднее количество до- стоверно передаваемой информации ????(????; ????) снижается.
Используя соотношения между совместной и условной энтропией в форме
(5.24)
????(????, ????) = ????(????) + ????(????|????), выражая безусловную энтропию в виде
????(????) = ????(????, ????) − ????(????|????) получаем другое выражение взаимной информации (5.29)
????(????; ????) = ????(????) − ????(????|????) = ????(????, ????) − ????(????|????) − ????(????|????). (5.32)
5.6.2. Пропускная способность канала с матрицей переходных
Вероятностей
Определение 5.7. Пропускная способность ???? канала – это максимальная средняя взаимная информация ????(????; ????)
max
, которая может быть получена в канале с матрицей ???? переходных вероятностей.
Замечание. Пропускная способность канала определяет максимальную скорость передачи информации, при которой она может передаваться без оши- бок.
5.6.3. Пропускная способность двоичного симметричного канала
97
Рассмотрим ДСК с источником ???? = {????
1
= 0, ????
2
= 1}. Вероятности симво- лов источника ???? обозначим ????(????
1
) и ????(????
2
). Канал характеризуется вероятностью ошибок ???? и матрицей канала
???? = [
1 − ????
????
????
1 − ????
].
Для определения пропускной способности ДСК необходимо вычислить среднею взаимную информации ????(????; ????) на выходе канала
????(????; ????) = ????(????) − ????(????|????).
В примере 5.2 для ДСК была найдена условная энтропия
????(????|????) = ????
????????????
= −[(1 − ????) log
2
(1 − ????) + ????log
2
????].
Взаимная информация равна
????(????; ????)= ????(????) − ????
????????????
Пропускная способность ДСК определяется как
???? = ????(????; ????)
max
= max {????(????) − ????
????????????
)}.
Когда шумов в канале нет, ????
1
= ????
1
, ????
2
= ????
2
. Энтропия ????(????) достигает своего максимального значения в случае равенства ????(????
1
) = ????(????
2
) вероятностей символов источника ????. Тогда максимальное значение энтропии равно (см. рис.
2.8)
????(????) = ????(????) = 1 бит символ
⁄
Пропускная способность ДСК характеризуется величиной
???? = ????(????; ????)
max
= max {1 − ????
????????????
)}.
Рассмотрим ситуации возможные при передаче информации по ДСК.
1. Если ошибки не возникают, ???? = 0, условная энтропия (формула Шен- нона) равна
????(????|????) = ????
????????????
= −[???? log
2
???? + (1 − ????) log
2
(1 − ????)] = 0.
Обеспечивается максимальная пропускная способность
???? = ????(????; ????)
max
= 1 бит символ
⁄
98
Осуществляется достоверная (надежная) передача всей информации.
2. Если
???? = 1, условная энтропия равна
????(????|????) = ????
????????????
= −[???? log
2
???? + (1 − ????) log
2
(1 − ????)] = 0.
В этом случае пропускная способность также равна
???? = ????(????; ????)
max
= (1 − ????
????????????
) = 1 бит символ
⁄
Среднее количество передаваемой информации также оказывается равным
1 бит/символ. Но в этом случае с вероятностью «единица» принятый символ не равен переданному символу. Процент ошибок достигает 100 %. Невозможно определить, какой символ передавался 0 или 1.
3. Если ???? = 0,5, условная энтропия равна
????(????|????) = ????
????????????
= −[???? log
2
???? + (1 − ????) log
2
(1 − ????)] = 1.
Пропускная способность ДСК
???? = ????(????; ????)
max
= (1 − ????
????????????
) = 0 бит символ
⁄
Передача информации по ДСК становится невозможной.
На рис. 5.2 показана зависимость пропускной способности ДСК от вероят- ности ошибочного приема.
Рис. 5.2. Пропускная способность ДСК
При наличии шумов пропускная способность ???? в канале всегда меньше од- ного бита на символ. Из рисунка видно, что с ростом ???? от 0 до 0,5 пропускная способность C убывает от своего максимального значения, равного 1 до 0. Сред- нее количество передаваемой информации оказывается равным нулю.
Пример 5 .3 . Пусть в среднем один из каждых 100 символов принимается неправильно, т. е. ???? = 0,01. Определить пропускную способность ДСК.
Решение. ???? = [1 + 0,01 log
2 0,01 + 0,99 log
2 0,99] = 0,98 бит символ
⁄
C
p
1 8
,
0 6
,
0 4
,
0 2
,
0 2
,
0 4
,
0 6
,
0 8
,
0 1