Вернер М. Основы кодирования (2004), страница 3

Энтропия и избыточностьТаблица 2.2. Дискретный источник без памяти с символамиXi алфавита X = {а, Ь, с, d, е, /} с вероятностьюр; и информацией I[pi).X,аЬсdеfPi0,050,150,050,40,20,15I(pi)4,32 бит 2,74 бит 4,32 бит1,32 бит 2,32 бит 2,74 битДля того, чтобы конкретизировать проведенные выше рассуждения, рассмотрим численный пример.

В таблице 2.2 задан дискретныйисточник без памяти X с соответствующими алфавитом и вероятностями событий. Следуя (2.3), подсчитаем информацию каждогособытия и дополним таблицу значениями.Энтропия источника равнаН(Х) = 2,25 бит.(2.28)Значение Но для событий равноНо - log2 б бит = 2,585 бит,(2.29)R = (log2 6-2,25) бит = 0,335 бит(2.30)тогда избыточностьи, соответственно, относительная избыточность составляет2,25г = 1 - Iog 6 = 0,130 ^ 13%.2(2.31)Особое значение имеют дискретные двоичные источники без памяти, так как в большинстве случаев с их помощью можно описатьпроцесс передачи данных.Пусть задан двоичный источник без памяти с алфавитом X ={0,1} и с вероятностями для символов «0» и «1» - ро = V и Pi =1-ро соответственно.

Выбор символов производится независимо. Егоэнтропия, называемая также функцией Шеннона, зависит только отвероятности р.Энтропия двоичного источника (функция Шеннона)Нь{р)= -plog 2 p - (1 - р) Iog2(l - р).бит(2.32)Глава 2. Информация, энтропия и избыточностьНа рис. 2.6 показано поведение функции Шеннона. Энтропия двоичного источника всюду положительна и симметрична относительнор = 1/2 и имеет максимум при одинаковой вероятности символов «О»и «1». Максимальная энтропия равная 1 бит соответствует двоичному решению, т.е. на вопрос о значении символа это ответ: либо «да»либо «нет».0,5р —iРис. 2.6.

Энтропия двоичного источника.ГЛАВА 3КОДИРОВАНИЕДЛЯ ДИСКРЕТНЫХИСТОЧНИКОВ БЕЗ ПАМЯТИ3.1. Теорема кодирования источников IВ разделе 2.2 было введено понятие энтропии как средней информации дискретного источника без памяти. Более того, было показано,что любое событие, содержащееся в источнике, может быть разложено на последовательности двоичных решений с исходами «да» или«нет» без потери информации. Таким образом, каждому событию,содержащемуся в алфавите, может быть приписана некоторая последовательность двоичных символов «О» или «1» (в дальнейшем такуюпоследовательность будем называть кодовым словом события). Приэтом не происходит потери информации, так как каждое событие может быть непосредственно восстановлено по соответствующему кодовому слову.

Такой процесс называется кодированием источника, асовокупность кодовых слов всех событий - кодом источника.Уровенькореньдеревареброузел - - *А01 ДоЛДоконечный J \jузел — О О С01 /122438-416кА л1 /\о-Д 1~лО1 Г№{'Кодовое слово 0110ЧИСЛО0Р и с . 3 . 1 . Кодовое дерево.Возникает вопрос: какое среднее число бит надо затратить прикодировании источника? Попутно возникают вопросы: сколько местна плате займут переключательные элементы при реализации кодаисточника и каковы длительности кодовых слов при передачи информации?Глава 3.

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

Предположим далее, что этим оконечным узлам соответствуют 2^ равновероятных событий из всегоалфавита источника. Тогда, на кодирование каждого события затрачивается ровно N бит, что равно энтропии источника. Связь междусредней длиной кодового слова и энтропией источника обобщает теорема кодирования источников.Теорема 3.1.1. Теорема кодирования источников I.Для любого дискретного источника без памяти X с конечным алфавитом и энтропией Н(х) существует D- ичный префиксный код, вкотором средняя длина кодового слова п удовлетворяет неравенствуШВД<log£> -и< + 1 .~\ogD(3.1)Термин префиксный код означает, что никакое начало кодовогослова не может быть другим кодовым словом.

Это значит, что потоксобытий может быть закодирован без специального разделения этихсобытий. В случае D = 2 используется двоичный код. Если энтропиязадана в битах, то средняя длина п также выражается в битах, чтопрямо указывает на использование двоичного кода.Теорема кодирования источников указывает на то, что средняядлина кодового слова не может быть меньше энтропии. Однако, какбудет показано в разделах 5.2 и 5.5, при блоковом кодировании источников, средняя длина кодового слова может приближаться к энтропии как угодно близко. Это обстоятельство еще раз подчеркивает важность понятия энтропии.

Энтропия - есть мера минимальных средних затрат. Примером практической реализации неравенства (3.1) является код Хаффмана, рассматриваемый в следующемразделе.3.1. Теорема кодирования источников IЗамечание. Доказательство теоремы, 3.1.1 сводится к использованию неравенства Крафта и не несет в себе каких-либо консщрукгпивиых соображений для построения оптимальных, с точки зрения затрат, кодов. Доказательство довольно объемно, но дает хорошее представление о методах теории информации.

Тем не менее,оно может быть пропущено без ущерба для понимания последующих ра,чделов.Доказательство.Ш а г 1. Неравенство Крафта.Для существования однозначно декодируемого D-ичного кода,содержащего К кодовых слов с длинами П1,П2,.-.,щ,необходимои достаточно, чтобы выполнялось неравенство Крафтак(3.2)it=iДля доказательства этого утверждения воспользуемся кодовойконструкцией, изображенной на рис. 3.2.УровеньОЧисловозможныхузловоконечный узел(кодовое слово)Рис. 3.2. Кодовое дерево для D = 2 и п = 4.Мы видим 3 характерных свойства этой конструкции:1.

Существует D1 узлов г-го порядка (г-го уровня);n %2. Каждый узел г-го порядка порождает точно D "п-го уровня;3. Кодовая конструкция соответствует префиксному коду, т.е. никакое кодовое слово не является началом другого кодового слова, так как кодовые слова однозначно определяются конечнымиузлами.Глава 3. Кодирование для дискретных источников без памятиДля простоты упорядочим длины кодовых словп1 ^ п2 ^ ' ' ' nk=п-(3.3)Теперь начнем отсчет. Кодовое слово с\ длины п\ запрещает в точности Dn~ni возможных конечных узлов на последнем п-ом уровне.Так как кодовые слова префиксного кода не сливаются, в совокупности получимК££>»-»*(3.4)fc=iзапрещенных узлов на п-ом уровне.

Общее число возможных узловна п-ом уровне равно Dn , следовательноКn nkY^D -n<D .(3.5)fc=iРазделив обе части неравенства на Dn, получим неравенство Крафта.Ш а г 2. Утверждение Мак-Миллана.Каждый однозначно декодируемый код удовлетворяет неравенству Крафта.При выводе неравенства Крафта были использованы особенностипрефиксных кодов. Но это условие не является необходимым.

Какбудет показано далее, необходимым условием является однозначнаядекодируемость кода. Возведем сумму в неравенстве Крафта в степень LкiLкккОбозначив через Ai число комбинаций, содержащих L кодовыхслов с суммарной длиной г, запишем (3.6) в компактной формек=у*где L n m a xмаксимальная длина сообщения, содержащего L кодовых слов.Если код является однозначно декодируемый, то все последовательности из L кодовых слов суммарной длины г различны. Так какимеется всего D1 возможных последовательностей, тоAt < Dl(3.8)3.1. Теорема кодирования источников I 27Jи, таким образом,5]fc=l(3.9)JИзвлекая L-ичный корень, получим оценку сверху для суммы внеравенстве КрафтаК£ > - » * < (£n,max)1/2(ЗЛО)для всех натуральных L.Обсудим значение числа L.

Это число независимых кодовых слов,которые выбираются из {1,2, ...,К} и используются для построения всех возможных последовательностей длины, не превышающейL n m a x . Поэтому, при L —> оо, мы приходим к неравенству КрафтакY,D~Hk < П М ^ т а х ) 1 ^ = 1fc=l~^°°(З.П)Приведенные выше рассуждения справедливы для каждого однозначно декодируемого кода. Поэтому, каждый однозначно декодируемый код удовлетворяет неравенству Крафта.Ш а г 3.Запишем левую часть неравенства (3.1) в виде(3.12)H(x)-n\ogD<0.Используя вероятность событий рь и соответствующие длины кодовых слов Пк , имеемкH(x)-nlogDк= Vpfclogfc=lVpfc7ifclogi3=^(3.13)fc=lD~nkPkКак и при доказательстве утверждения (2.1), оценим сверху ло-, 28Глава 3.

Кодирование для дискретных источников без памятигарифмическую функцию при помощи (2.19) и получимYVlogf-fPk<loge [y^PkV*-fL Pk1 I =\ I^D'nk-^\= logel^fc=l(3.14)k = lкЗдесь было использовано неравенство Крафта и условие £ pjt = 1.fc=iТаким образом, левая часть неравенства (3.1) теоремы о кодировании источников доказана.Шаг 4.Правая часть неравенства (3.1)(ЗЛ5)logDПри доказательстве используем неравенство Крафта, условие существования кода с соответствующими длинами кодовых слов п& иусловие 2_,(.=i Pk = 1Неравенство Крафта можно записать в видеккDY, ~nk<X>-(3-16)fc=i fc=iПока имеет силу неравенство Крафта, мы свободны в выборедлин кодовых слов n/t G Л/*. Выберем для каждого слагаемого такое наименьшее п^, при котором£Г"* < рк.(3.17)Неравенство Крафта при таком выборе будет выполняться, следовательно, используя конструкцию рис.

3.2, мы можем построитьтакой префиксный код. Так как п/, наименьшее целое, при которомимеет место (3.17), то для nk — 1 справедливорк < D-{nk~l).Остальная часть доказательства лишь формальна.(3.18)3.2. Коды Хаффмана29)Используя свойства логарифмической функции, получаемPfclogPfc < Pit log D~(nk~^ = pk(—Пк + l)logi).(3.19)Суммируя по всем К, имеемк(3.20)-H(X)Разделив обе части неравенства на \ogD и переставляя члены сдомножением на —1 (что меняет знак неравенства), получаем искомое доказательство. •3.2. Коды ХаффманаКоды Хаффмана1 принадлежат к семейству кодов с переменной длиной кодовых слов. Самый известный код неременной длины - азбукаМорзе2 (табл. 3.1).