LEKTsIYa_3
.pdf
ЛЕКЦИЯ № 3.
2. ДИСКРЕТНЫЙ ИСТОЧНИК ИНФОРМАЦИИ (ДИ).
ДИ
ДИ без памяти (ДИБП) |
Стационарный источник |
|
Дискретный источник X |
с алфавитом |
A из L символов {a1 ,...., aL } выдает |
последовательность букв |
(символов) xi |
A (i 1,2,....) выбираемых из этого |
алфавита. Здесь i - дискретное время. Например, двоичный источник выдает двоичную последовательность 01100010100011110…… . Причем алфавит состоит из L 2 символов A {a1 , a2} {0,1}. Пусть каждый символ алфавита имеет заданную вероятность выбора pk p(ak ) P{X ak } , k 1,2,...L , где
L
pk 1. Рассмотрим две математические модели для ДИ.
k 1
1)Если символы выходной последовательности источника статистически независимы, то такой источник называется источником без памяти (ДИБП).
2)Если символы источника взаимозависимы, то можно создать модель на основе статистической стационарности. ДИ называется стационарным, если
совместные вероятности двух последовательностей |
длины n x1 ,...., xn и |
x1 m ,...., xn m одинаковы для всех n 1 и при всех сдвигах |
m : |
p(x1 ,.....xn ) p(x1 m ,...., xn m ) .
Т.е. совместные вероятности двух последовательностей инвариантны по отношению к произвольному сдвигу.
|
2.1. Мера информации ДИ. |
Рассмотрим две |
случайные величины X ,Y с возможными значениями |
X {ak , k 1,2,..., L} |
и Y {bl , l 1,2,..., M }. Пусть мы наблюдаем некоторый выход |
Y bl и желаем количественно определить величину информации, которая содержится в выборке Y относительно события X ak . Замечание: если X и Y статистически независимы, тогда выбор Y не дает информации о событии X . С другой стороны, если Y однозначно определяется X , то информационное содержание у них одинаковое. Взаимная информация определяется как
I (a |
, b ) log |
|
( |
p(ak / bl ) |
) (бит), |
|
|
|
|
(2.1) |
||
2 |
|
|
|
|
|
|||||||
k |
l |
|
p(ak ) |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||
где p(ak / bl ) P{X ak / Y bl } - вероятность наступления события |
X ak при |
|||||||||||
условии, что Y bl . |
|
|
|
|
|
|
|
|
|
|
|
|
1) Если X ,Y независимы, тогда |
|
p(ak , bl ) p(ak ) p(bl |
) , а p(ak / bl ) |
p(ak |
, bl |
) |
p(ak ) . |
|||||
|
p(bl ) |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
||
Тогда по формуле (2.1) I (ak , bl ) log 2 (1) 0 . |
|
|
|
|
|
|||||||
2) Если X ,Y полностью зависимы, тогда p(ak / bl ) 1 |
|
|
|
|
||||||||
I (ak , bl ) log |
1 |
|
log 2 ( p(ak )) I (ak ) (бит) |
|
|
(2.2.) |
||||||
2 ( |
|
) |
|
|
||||||||
p(ak ) |
|
|
||||||||||
Выражение (2.2.) определяет информацию о X |
и называется собственной |
|||||||||||
информацией. Она является информационной мерой Шеннона. |
|
|
|
|||||||||
Свойства собственной информации.
1.Пусть p(ak ) 1 , тогда I (ak ) 0 , т.е. достоверное событие информации не несет. Собственная информация является меройнеопределенности.
2.Пусть ak , aq независимы, тогда I (ak , aq ) log 2 ( p(ak , aq )) log 2 ( p(ak ) p(aq ))
log 2 ( p(ak )) log 2 ( p(aq )) I (ak ) I (aq ), k 1,2,..., L, q 1,2,...., L.
3.Если источник выдает за s секунд цифру «0» или «1» ( L 2 ) с равными
вероятностями p(ak ) 0.5 , то |
I (ak ) log 2 (0.5) 1 бит. |
|
|
|
|||||||
4. |
Пусть имеется |
блок |
a |
символов |
источника из n |
двоичных цифр |
|||||
|
|
|
|
k |
|
|
|
|
|
|
|
a |
10110100 ...1 |
. |
Тогда |
существует 2n |
|
возможных |
|
n - |
битовых блоков, |
||
k |
1 n |
|
|
|
|
|
|
|
|
|
|
появляющихся с одинаковыми вероятностями p(a ) 2 n |
. Средняя собственная |
||||||||||
|
|
|
|
|
|
|
|
k |
|
|
|
информация такого блока равна I (a ) log |
2 |
( p(a )) log |
2 |
(2 n ) n бит. |
|||||||
|
|
|
|
|
k |
|
k |
|
|
||
Зная взаимную информацию (2.1), связанную с парой событий (ak , bl ) , которые являются возможной реализацией двух случайных величин X ,Y , можно получить среднее значение взаимной информации следующим образом:
L M |
L M |
|
|
p(ak , bl |
) |
|
|
||
I ( X ,Y ) p(ak , bl |
)I (ak , bl ) p(ak , bl ) log |
|
( |
) I (Y , X ) |
(2.3) |
||||
2 |
p(a |
|
) p(b ) |
||||||
k 1 l 1 |
k 1 l 1 |
|
|
k |
|
|
|||
|
|
|
|
l |
|
|
|||
среднюю собственную информацию источника:
L |
L |
|
H ( X ) p(ak )I (ak ) p(ak ) log 2 ( p(ak )) |
(2.4) |
|
k 1 |
k 1 |
|
Выражение (2.4) называют энтропией ДИ.
Свойства энтропии ДИ.
1.H(X ) 0 , т.е. энтропия – величина неотрицательная.
2.H ( X ) H max , если p(ak ) p L1 , k 1,2,..., L . Энтропия ДИ максимальна, когда
символы на его выходе равновероятны.
L |
1 |
|
|
1 |
|
|
|
|
H max |
log |
2 ( |
) log |
2 (L) |
(2.5) |
|||
|
|
|||||||
k 1 |
L |
|
L |
|
|
|||
Энтропия является мерой неопределенности источника. Чем больше энтропия, тем больше неопределенность.
3. Энтропия наступления независимых событий X1 , X 2 ,..., X m :
4. Если сообщения энтропии:
m |
|
H ( X1 ,..., X m ) H ( X i ) |
(2.6) |
i 1 |
|
X i , i 1,2,..., m зависимы, то |
вводят понятие условной |
|
L |
L |
|
|
H ( X i / X i 1 ) p(ak , aq ) log 2 ( p(ak / aq ) , |
(2.7) |
|
|
k 1 q 1 |
|
|
где |
Xi {ak }, Xi 1 {aq } . |
Формула (2.7) – |
информационная мера |
неопределенности, содержащаяся в X i после наблюдения X i 1 . Тогда энтропия совместного наступления событий X i , X i 1 определяется следующим образом:
H ( X i , X i 1 ) H ( X i 1 ) H ( X i / X i 1 )
Формулы (2.7) и (2.8) описывают дискретный марковский Оставшаяся или условная неопределенность всегда меньше (безусловной): H ( X i / X i 1 ) X ( X i ) .
(2.8)
источник. исходной
Вывод: Энтропия ДИ тем больше, чем меньше взаимосвязи между символами, чем более равномерно распределены вероятности появления этих символов и чем больше алфавит источника L .
2.2. Производительность, информационная насыщенность и избыточность источника.
Производительность источника – количество средней собственной информации, вырабатываемое в единицу времени:
I ( X ) |
|
H ( X ) |
|
(бит/с) , |
(2.9) |
||||||
|
|
TH |
|||||||||
|
|
|
|
|
|
|
|
|
|||
где TH - интервал наблюдений. |
|
|
|
|
|
|
|
|
|
|
|
Информационная насыщенность определяется как |
|
||||||||||
I H ( X ) |
|
H ( X ) |
|
I ( X ) |
. |
(2.10) |
|||||
|
H |
|
|
|
|
||||||
|
|
|
max |
|
I |
|
|||||
|
|
|
|
|
|
max |
|
||||
Если H (X ) 0, то и I H ( X ) 0 . Если H ( X ) H max , то I H ( X ) 1. |
|
||||||||||
Избыточность источника: |
|
|
|
|
|
|
|
|
|
|
|
r( X ) 1 I H ( X ) 1 |
H ( X ) |
. |
(2.11) |
||||||||
|
|||||||||||
|
|
|
|
|
|
|
|
H max |
|
||
Формула (2.11) показывает недоиспользованность предельных возможностей источника. Чем больше избыточность, тем меньше насыщенность и тем менее эффективно используется канал связи, по которому передается сообщение.
Реальные источники информации обладают большой избыточностью. Поэтому для ее уменьшения прибегают к эффективному кодированию.
2.3. Эффективное кодирование.
Кодирование ДИБП.
Пусть ДИБП выдает буквы или символы каждые s секунд. Каждый символ выбирается из конечного алфавита A {ak }, k 1,2,..., L с вероятностью p(ak ) . Энтропия такого источника определяется по формуле (2.4) и ограничивается сверху значением, вычисляемым по (2.5), т.е. H ( X ) log 2 (L) . Как говорилось выше, знак «=» выполняется, если вероятности символов на выходе источника одинаковы и равны p L1 .
1. Кодовые слова фиксированной длины.
Рассмотрим блоковое кодирование, которое состоит в сопоставлении уникального ряда из K двоичных символов, каждому символу источника. Так
как существует L возможных символов ДИБП, то число двоичных символов кодера на один символ источника при уникальном кодировании определяется
как |
K |
log |
|
(L), L 2Q |
, |
где |
Q |
- целое положительное |
число, |
|
- |
||||||||
|
2 |
|
|
|
|
|
|||||||||||||
|
|
|
|
2 |
|
|
|
|
2Q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(L) |
1, L |
|
|
|
|
|
|
|
|
|
|||||
|
|
log |
|
|
|
|
|
|
|
|
|
|
|
||||||
наибольшее |
|
целое, меньшее, |
чем |
log 2 (L) . |
K - скорость |
кодирования. |
|||||||||||||
Поскольку |
H ( X ) log 2 (L) , |
то |
K H(X ) . |
Эффективность |
кодирования |
||||||||||||||
определяется отношением |
|
H (x) |
. |
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
K |
|
|
|
|
|
|
|
|
А) |
Если |
L 2Q |
|
|
и |
символы |
источника |
равновероятны, |
то |
K H (X ) |
и |
||||||||
эффективность кодирования равна 1 (100%). |
|
|
|
|
|
||||||||||||||
Б) Если |
L 2Q , |
но символы источника равновероятны, то K отличается от |
|||||||||||||||||
H (X ) самое большее на 1 бит на символ. |
|
|
|
|
|
||||||||||||||
В) Если log 2 (L) 1, то эффективность кодирования высокая. |
|
|
|
|
|||||||||||||||
Г) |
Если |
L |
|
|
мало, тогда эффективность кода можно повысить путем |
||||||||||||||
кодирования блока из J символов источника за время J s . |
Для этого надо |
||||||||||||||||||
выбрать |
LJ |
уникальных |
кодовых |
слов. |
|
Используя |
|
кодовую |
|||||||
последовательность из K J |
|
двоичных |
символов, |
можно |
образовать 2K J |
||||||||||
возможных кодовых слов, |
причем K J |
J log 2 (L) . Следовательно, |
требуется |
||||||||||||
минимальное целое значение для K J : |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
K J |
J log 2 (L) 1 . |
|
|
|
|
|
|
|
|
|
|
||
Теперь среднее число символов кода на один символ источника K |
K J |
. При |
|||||||||||||
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
J |
|
эффективность кодирования увеличивается в |
J раз: |
H ( X ) |
|
|
H ( X )J |
. Взяв J |
|||||||||
|
|
||||||||||||||
|
|
|
|
|
|
|
|
K |
|
K J |
|
|
|
|
|
достаточно большим, можно эффективность приблизить к 1.
Такие методы кодирования не приводят к искажениям, т.к. кодирование символов источника или блоков символов в кодовые слова выполняется однозначно (уникально). Эти коды называются бесшумными.
Теперь рассмотрим ситуацию, когда только часть LJ блоков символов источника кодируется однозначно. Например, 2K J 1 наиболее вероятных J символьных блоков кодируется однозначно. Остальные LJ (2KJ 1) блоков длины J представляются одним оставшимся кодовым словом. Такая процедура кодирования вызывает ошибку декодирования каждый раз, когда
источник выдает маловероятный блок. Обозначим через pe вероятность ошибки декодирования. Шеннон в 1948 г. доказал теорему кодирования источника.
Теорема Шеннона кодирования ДИБП. Пусть X - ансамбль символов ДИБП с конечной энтропией H (X ) . Блоки из J символов источника кодируются в
двоичные кодовые слова длины K J |
. Тогда для любого 0 |
pe можно сделать |
|||
сколь угодно малой, если выполняется неравенство |
|
||||
K |
K J |
|
H ( X ) |
(2.12) |
|
J |
|||||
|
|
|
|||
и J достаточно велико.