<< Предыдущая

стр. 3
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

что после упрощений соответствует энтропии без разложения про-
цесса выбора событий

= - P l ( o ) lo g 2 ( P l (a)) - р(Ь) log2(p(6)) - р(с) Iog2(p(c)). (2.17)

В рассмотренном примере было использовано свойство логариф-
мической функции, переводящее произведение в сумму. Определение
(2.4) является единственным, при котором аксиома 3 имеет силу.
Заметим также, что рассмотренное разложение процесса выбора со-
бытий может быть сведено к последовательности бинарных решений
«да» и «нет». Максимальной неопределенности соответствует макси-
мальная энтропия источника. Сформулируем следующую теорему:
2.2. Энтропия и избыточность 19)

Теорема 2.2.1. Энтропия простейшего дискретного источника без
памяти максимальна, если все события, в нем содержащиеся, име-
ют одинаковую вероятность, В этом случае энтропия просто равна
логарифму числа событий

#о = Ьит. (2.18)

Замечание. Последующее доказательство теоремы является ти-
пичным в теории информации. В таких доказательствах использу-
ются оценки и предельные переходы, которые ранее были известны,
но не находили практического применения.




Рис. 2.5. Верхняя оценка логарифмической функции.

Доказательство. Для доказательства рассмотрим два дискретных
источника без памяти Р и Q, каждый из которых содержит N со-
бытий с вероятностями р{ и < соответственно. Далее воспользуемся
&
известной верхней оценкой логарифмической функции ( рис. 2.5)

lnx < x — .1. (2.19)

Используя эту оценку, получаем

(2.20)
Ing; —In pj
Pi Pi


Умножив обе части неравенства на pi и просуммировав по всем со-
бытиям 1 < i < N, имеем


(2.21)
,20 Глава 2. Информация, энтропия и избыточность

После упрощения получаем

ад " " " •'
1п < =о

нат + 2 - л 1 п * ^ | ^ А ?
1 1

и, следовательно
N
(2.23)
: -S^Pilnqi.
нам " ^—'
г=1
Предположим, что источник Q содержит только равновероятные со-
бытия. Тогда


(2.24)
L J
г=1 " г=1
1

Так как в процессе доказательства на источник Р не было наложено
никаких ограничений, то данное неравенство имеет место для любого
дискретного источника без памяти, содержащего J событий
V

(2.25)
H(X)<\og2N6nT.

Максимум достигается, когда все события имеют одинаковые веро-
ятности. •
Любой источник, содержащий T событий, не все из которых име-
V
ют одинаковую вероятность, обладает энтропией, меньшей Iog2./V.
Рассмотрим источник емкостью Щ = log2 N как резервуар для хра-
нения информации, который никогда не переполняется.

Разность между максимальной емкостью # о и энтропией источ-
ника X, содержащего N событий, называется избыточностью ис-
точника
R = Но - Н(Х). (2.26)

Относительная избыточность определяется как




Пример: Энтропия дискретного источника без памяти, содержа-
щего 6 событий.
2.2. Энтропия и избыточность

Таблица 2.2. Дискретный источник без памяти с символами
Xi алфавита X = {а, Ь, с, d, е, /} с вероятностью
р; и информацией I[pi).

f
Ь d
а е
с
X,

0,05 0,15 0,05 04
, 02
, 0,15
Pi
4,32 бит 2,74 бит 4,32 бит 1,32 бит 2,32 бит 2,74 бит
I(pi)




Для того, чтобы конкретизировать проведенные выше рассужде-
ния, рассмотрим численный пример. В таблице 2.2 задан дискретный
источник без памяти X с соответствующими алфавитом и вероят-
ностями событий. Следуя (2.3), подсчитаем информацию каждого
события и дополним таблицу значениями.
Энтропия источника равна

Н(Х) = 2,25 бит. (2.28)

Значение Но для событий равно

Но - log2 б бит = 2,585 бит, (2.29)

тогда избыточность

(2.30)
R = (log2 6-2,25) бит = 0,335 бит

и, соответственно, относительная избыточность составляет
2,25
(2.31)
г = 1 - Iog 6 = 0,130 ^ 13%.
2


Особое значение имеют дискретные двоичные источники без па-
мяти, так как в большинстве случаев с их помощью можно описать
процесс передачи данных.
Пусть задан двоичный источник без памяти с алфавитом X =
{0,1} и с вероятностями для символов «0» и «1» - ро = V и Pi =
1-ро соответственно. Выбор символов производится независимо. Его
энтропия, называемая также функцией Шеннона, зависит только от
вероятности р.
Энтропия двоичного источника (функция Шеннона)

Нь{р) (2.32)
= -plog 2 p - (1 - р) Iog2(l - р).
бит
Глава 2. Информация, энтропия и избыточность

На рис. 2.6 показано поведение функции Шеннона. Энтропия дво-
ичного источника всюду положительна и симметрична относительно
р = 1/2 и имеет максимум при одинаковой вероятности символов «О»
и «1». Максимальная энтропия равная 1 бит соответствует двоично-
му решению, т.е. на вопрос о значении символа это ответ: либо «да»
либо «нет».




0,5 р —i


Рис. 2.6. Энтропия двоичного источника.
ГЛАВА 3
КОДИРОВАНИЕ
ДЛЯ ДИСКРЕТНЫХ
ИСТОЧНИКОВ БЕЗ ПАМЯТИ


3.1. Теорема кодирования источников I
В разделе 2.2 было введено понятие энтропии как средней информа-
ции дискретного источника без памяти. Более того, было показано,
что любое событие, содержащееся в источнике, может быть разложе-
но на последовательности двоичных решений с исходами «да» или
«нет» без потери информации. Таким образом, каждому событию,
содержащемуся в алфавите, может быть приписана некоторая после-
довательность двоичных символов «О» или «1» (в дальнейшем такую
последовательность будем называть кодовым словом события). При
этом не происходит потери информации, так как каждое событие мо-
жет быть непосредственно восстановлено по соответствующему ко-
довому слову. Такой процесс называется кодированием источника, а
совокупность кодовых слов всех событий - кодом источника.

Уровень ЧИСЛО
корень
дерева 0
0
ребро 2
1
1/




кА л
узел - - *
\о 4
2
1 Г№
0 1 До 1/
{
А 8
3
Л Д -Д 1˜лО
оконечный J \ j
16
' -4
узел — О О С
Кодовое слово 0110


Р и с . 3 . 1 . Кодовое дерево.


Возникает вопрос: какое среднее число бит надо затратить при
кодировании источника? Попутно возникают вопросы: сколько мест
на плате займут переключательные элементы при реализации кода
источника и каковы длительности кодовых слов при передачи ин-
формации?
Глава 3. Кодирование для дискретных источников без памяти

Ответы на эти вопросы дает теорема Шеннона о кодировании
источников. Перед тем, как приступить к рассмотрению этой тео-
ремы, возьмем в качестве примера двоичного кодирования кодовую
конструкцию, изображенную на рис. 3.1.
Начиная от корня кодового дерева число ребер на каждом уровне
удваивается, причем, слева располагаются ребра, соответствующие
единицам, а справа - нулям кодовых слов. Кодовые слова образу-
ются при прохождении соответствующих ребер, ведущих от корня к
оконечным узлам. В качестве примера будем рассматривать кодовое
слово ОНО.
Если мы пройдем N уровней, то получим 2N оконечных узлов, ко-
торые соответствуют кодовым словам с длиной log22'v6HT = N бит и
можно закодировать 2N событий. Предположим далее, что этим око-
нечным узлам соответствуют 2^ равновероятных событий из всего
алфавита источника. Тогда, на кодирование каждого события затра-
чивается ровно N бит, что равно энтропии источника. Связь между
средней длиной кодового слова и энтропией источника обобщает тео-
рема кодирования источников.

Теорема 3.1.1. Теорема кодирования источников I.
Для любого дискретного источника без памяти X с конечным алфа-
витом и энтропией Н(х) существует D- ичный префиксный код, в
котором средняя длина кодового слова п удовлетворяет неравенству

ШВД (3.1)
< <+1.
и
log?> - ˜\ogD
Термин префиксный код означает, что никакое начало кодового
слова не может быть другим кодовым словом. Это значит, что поток
событий может быть закодирован без специального разделения этих
событий. В случае D = 2 используется двоичный код. Если энтропия

<< Предыдущая

стр. 3
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>