Одно из (специфических)
Различные материальные формы представления информации называются сообщениями, содержащими данную информацию. Различные сообщения могут содержать одну и ту же информацию. В качестве примера на рис.6.1 показаны различные представления числа 4: в виде разноформатных начертаний арабской цифры 4, римской цифры, слова "четыре", записи числа 4 в
(рис 6.1) Различные формы представления числа 4
Еще одним подобным примером является возможность записи чисел в различных системах счисления. Следует заметить, что информация может быть облечена не только в графическую форму. Произнесенное человеком слово "четыре" также является сообщением, представляющим число 4. Нетрудно привести множество других примеров такой "многоликости" информации.
Следует заметить, что практический интерес представляют только такие материальные формы представления информации, которые могут быть восприняты человеком и другими живыми существами. Предполагается, что человек воспринимает сообщения непосредственно своими органами чувств или с использованием специальных приборов или средств. Органы чувств человека можно рассматривать как естественные (созданные природой) регистрирующие и измерительные средства (датчики).
Можно выделить несколько основных форм сообщений (в порядке возрастания их сложности).
Сигналы представляют собой некоторые физические величины или свойства физической среды, изменяющиеся во времени. Чаще всего такими величинами являются: напряженность электрического поля, величина электрического тока, интенсивность светового потока, давление газа и т.п.
Сигналы воспринимаются органами чувств человека или других животных, а также специально предназначенными для регистрации сигналов техническими устройствами - датчиками. Принятые сигналы, как правило, преобразуются в другую форму. Например, микрофон преобразует звуковые колебания (периодические изменения давления атмосферы) в переменный электрический ток, а световые или звуковые сигналы преобразуются органами чувств высших животных в импульсы (т. е. тоже сигналы) электрохимической природы. На рис.6.2 показан график звуковых колебаний, возникающих при произнесении слова "четыре".
(рис 6.2) График звуковых колебаний
Чаше всего информация в виде сигналов используется в системах управления техническими объектами для описания изменения состояния объектов с течением времени. Отклонение этих сигналов от требуемых по условиям эксплуатации значений приводит к выработке системой управления сигналов, представляющих управляющую информацию. Получение, обработка и анализ сигналов о состоянии управляемого объекта и внешней среды, а также генерация управляющих сигналов рассматриваются в теории управления.
Изображения можно рассматривать как многомерные и пространственные сигналы (фотографии, карты, графики и т.п.), в которых регистрируемые параметры физической среды зависят не от времени, а от пространственного положения. Для черно-белой фотографии таким параметром является степень почернения фотоматериала (фотопленки или
Физические величины, изменения которых рассматриваются как сигналы или изображения, называются параметрами сигналов. Если параметры сигналов принимают конечное число значений, то такой сигнал называется дискретным.
Некоторые повторяющиеся образцы (фрагменты) сигналов (изменяющихся во времени или в пространстве) в процессе общественной практики человека обособляются, выделяются и трактуются как некоторые новые сущности, а не просто как произвольные фрагменты сигнала. Таким образом возникают фонемы (акустические сигналы) и графемы. Эти новые сущности являются элементами, на основе которых формируется речь и письмо. Число этих элементов конечно. Графемы и фонемы являются частными случаями более общего понятия - знака. Знаком можно считать любую сущность, отличную от других сущностей. Примерами знаков являются буквы различных естественных языков, всевозможные условные обозначения на картах, схемах и других документах, дорожные знаки и многое другое. Разнообразные примеры наборов знаков приведены в 27.
Последовательность знаков, сменяющих друг друга во времени, можно рассматривать как дискретный сигнал. Например, последовательность фонем представляет собой речевое сообщение. Аналогичным образом расположение графем может восприниматься как письменное сообщение. Таким образом, представление информации в виде знаков является основой речи, письменности, а также способов хранения, передачи и обработки информации.
Условно можно выделить научные дисциплины, которые преимущественно занимаются изучением рассмотренных трех форм представления информации. Это анализ и
Учитывая вышеизложенное, можно сказать, что информатика занимается изучением сбора (получения), хранения, поиска, обработки и выдачи информации, представленной в знаковой форме. Знаки - это всего лишь одна из материальных форм информации. Но помимо формы представления информация может характеризоваться содержанием или смыслом, который приписывается человеком.
Следует отметить, что наряду с термином "информация" используется термин "данные" (иногда как синонимы). В [28]предлагается различать эти два термина и считать, что данные суть факты, идеи, сведения, которые представлены в знаковой (символьной) форме, позволяющей производить их передачу, обработку и интерпретацию (т.е. толкование, объяснение, раскрытие смысла), а информация - это смысл, который человек приписывает данным на основании известных ему правил представления в них фактов, идей, сообщений.
Полезно сделать еще одно замечание относительно терминов "знак" и "символ". Некоторые знаки приобретают определенное значение. К примеру, буквы свидетельствуют об алфавите, в который они входят, и о языке, который использует эти буквы. Но некоторые буквы (знаки) имеет для людей более глубокий смысл. Например, знак $$\pi$$, помимо того, что он является буквой греческого алфавита, означает для людей, знакомых с математикой, отношение длины окружности к длине ее диаметра. Поэтому символом целесообразно называть знак, который имеет специальный смысл (значение), связанный с определенной областью человеческой деятельности. Примерами символов являются следующие знаки: ©, @, $, §, ∞.
Число исходных для представления информации знаков, как правило, невелико (несколько десятков), а потребность в знаках, представляющих информацию о реальном мире, существенно превышает это количество и постоянно возрастает с развитием человечества, усложнением производственных отношений. Неограниченный запас новых языковых сообщений может быть получен из конечного множества знаков путем их комбинирования или составления из них последовательностей первичных знаков. Именно такой принцип лежит в основе большинства естественных языков. Несмотря на особенности каждого естественного языка, они имеют много общего. Для изучения общих принципов постро-ения языков разработаны формальные (математические) модели, которые так и называются -
Алфавитом называется конечное непустое множество знаков. Обычно подразумевается, что это множество линейно упорядочено. Условимся обозначать алфавиты символом $$\sum$$. Наиболее часто используются следующие алфавиты.
ASCII-символов или множество всех печатных ASCII-символов.Следует отметить, что алфавит $$H$$ содержит 10 десятичных цифр т. е. $$B \bigcup D \bigcup H$$ .
Слово или цепочка - это конечная последовательность знаков некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите $$B = \{0,1\}$$. Цепочки 15903 и 15df10 являются цепочками в алфавите $$D$$ и $$H$$ соответственно.
Пустая цепочка - это цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую е, можно рассматривать как цепочку в любом алфавите.
Часто бывает необходимо или удобно классифицировать слова по их длине, т.е. по числу позиций, которые занимают знаки в слове. Например, слово 01101 имеет длину 5. Обычно говорят, что
Длину некоторой цепочки $$\omega$$ обычно обозначают $$|\omega|$$. Например, $$|011| = |101| = |f50| = 3$$, а $$|\varepsilon| = 0$$.
Степени алфавита. Для множества всех цепочек определенной длины, состоящих из символов некоторого алфавита , удобно использовать, по аналогии с
Рассмотрим примеры такой записи $$A^0=\{\varepsilon\}$$ независимо от алфавита $$A$$, т.е. $$\varepsilon$$ - единственное слово длины 0. Для $$A=\{0, 1\} A^1=\{0, 1\}, A^2=\{00, 01, 10, 11\}, A^3=\{000, 001, 010, 011, 100, 101, 110, 111\}$$ и так далее. Отметим, что между $$A$$ и $$A^1$$ есть небольшое различие. Дело в том, что $$A$$ есть алфавит, и его элементы 0 и 1 являются символами, а $$A^1$$ является множеством слов, и его элементы - это слова 1 и 0, каждое длиной 1. Мы не будем вводить разные обозначения для этих множеств, полагая, что из контекста будет понятно, является {0,1} или подобное ему множество алфавитом или же множеством цепочек.
Множество всех слов над алфавитом $$A$$ принято обозначать $$A^*$$. Так, например $$\{0,1\}^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \dots\}$$. По-другому это множество можно записать в виде $$А^*= A^0 \bigcup A^1 \bigcup A^2 \bigcup \dots$$
Множество всех непустых слов в алфавите $$A$$ обозначают через $$A^+$$. Таким образом, имеют место следующие равенства:
$$А^+=А^1 \bigcup А^2 \bigcup А^3 \bigcup \dots\\ A^* =A^+\bigcup \{\varepsilon\}$$Конкатенация слов. Пусть $$\alpha$$ и $$\beta$$ - слова. Тогда $$\alpha \cdot \beta$$ обозначает их конкатенацию (соединение), т.е. слово, в котором последовательно записаны слова $$\alpha$$ и $$\beta$$. Более строго, если $$\alpha$$ - слово из $$i$$ символов: $$\alpha = a_1 a_2 \dots a_j$$, а $$\beta$$ - слово из $$j$$ символов $$\beta = b_1 b_2 \dots b_j$$, то $$\alpha \beta$$ - это слово длины $$i+j$$, $$\alpha \cdot \beta =a_{1a2} \dots a_{ib1b2} \dots b_J$$.
Конкатенацию можно рассматривать как алгебраическую операцию на множестве всех слов в алфавите $$A^*$$, которая любым словам $$\alpha$$ и $$\beta$$ из $$A^*$$ сопоставляет слово из $$A^*$$. Эта операция обладает некоторыми привычными свойствами алгебраических операций. Так, конкатенация является ассоциативной операцией, то есть для любых слов $$\alpha, \beta, \gamma$$ справедливо равенство $$(\alpha \cdot \beta) \cdot \gamma= \alpha \cdot (\beta \cdot \gamma)$$. Скобки в этом выражении определяют порядок выполнения
Пусть $$\alpha = 10010$$ и $$\beta = 001$$. Тогда $$\alpha \cdot \beta = 10010001$$, а $$\beta \cdot \alpha = 00110010$$ и, следовательно, $$\alpha \cdot \beta \ne \beta \cdot \alpha$$.
Для пустого слова $$\varepsilon$$ и любого слова $$\omega$$ справедливы равенства $$\omega \cdot \varepsilon = \omega$$. Таким образом, $$\varepsilon$$ является единицей (нейтральным элементом) относительно
Если $$\alpha-\beta \delta$$, то $$\delta$$ называется началом, или префиксом, слова $$\alpha$$, а $$\beta$$ - окончанием, или постфиксом, слова $$\alpha$$.
Множество всех слов можно представить графически в виде помеченного
На рис.6.3 изображен фрагмент словарного
(рис 6.3) Фрагмент словарного дерева (универсума) для алфавита {0, 1)
Опишем процедуру построения словарного дерева. Построение начинается с вершины, которая является корнем дерева и которая соответствует пустому слову $$\varepsilon$$. Эта (единственная) вершина образует нулевой ярус (уровень) дерева. Первый ярус дерева состоит из $$m$$ вершин ($$m$$ - число букв в алфавите $$A$$), которые соединены с корнем ребрами, помеченными буквами алфавита $$A$$. Вершины первого уровня соответствуют всем однобуквенным словам, которые получаются конкатенацией букв, помечающих ребра, с пустым словом.
Дальнейшее построение дерева выполняется аналогичным образом. Если $$k$$-й уровень дерева сформирован, то есть в дереве уже имеется $$m^k$$ вершин, соответствующих всем словам длины $$k$$, к каждой вершине $$k$$-го уровня присоединяется $$k$$ вершин $$(k+1)$$ -го уровня посредством ребер, помеченных буквами алфавита $$A$$. Любой вершине $$(k+1)$$-го уровня соответствует слово, которое получается конкатенацией некоторого $$k$$-буквенного слова и буквы, помечающей ребро между этими словами.
Таким образом, из процедуры построения дерева следует, что ребром в дереве соединяются только те вершины, которым соответствуют слова, отличающиеся по длине на 1. При этом более длинное слово является конкатенацией более короткого слова и буквы, помечающей ребро. Ясно также, что любое слово $$\beta$$, соответствующее вершине, которая лежит на пути из корня дерева к вершине, соответствующей слову $$\alpha$$, является пре-фиксом слова $$\alpha$$, то есть $$\alpha=\beta \cdot \gamma$$, $$\gamma \in A^*$$.
Рассмотренные выше понятия и примеры позволяют сформулировать точное определение
Однако оправданием использования термина "язык" для множества $$L \subset A^*$$ может служить то, что и обычные языки можно рассматривать как множества цепочек (слов). Возьмем в качестве примера русский язык, где набор всех литературных русских слов есть множество цепочек в алфавите (русских же букв). Еще один пример - язык программирования $$С$$ или любой другой язык программирования, в котором правильно написанные программы представляют собой подмножество множества всех возможных цепочек, а цепочки состоят из ASCII. Алфавиты для разных языков программирования могут быть различными, хотя обычно они состоят из прописных и строчных букв, цифр, знаков пунктуации и математических символов.
Существует, однако, множество других языков. Приведем несколько примеров.
Язык, состоящий из всех цепочек, в которых $$n$$ единиц следуют за $$n$$ нулями для некоторого $$n > 0: \{\varepsilon, 01, 0011, 000111, \dots\}$$.
Множество цепочек, состоящих из 0 и 1 и содержащих поровну тех и других: $$\{\varepsilon, 01, 10, 0011, 1001, \dots\}$$.
Множество двоичных записей простых чисел: $$\{10, 11, 101, 111, 1011, \dots \}$$.
Множество $$L_B$$ всех правильных скобочных выражений, $$A = \{(, )\}. ((()())())\in L_B, (()())) \notin L_B$$.
$$А^*$$ - язык для любого алфавита $$A$$.
$$\varnothing$$ - пустой язык в любом алфавите.
\{\varepsilon\} - язык, содержащий одну лишь пустую цепочку. Он также является языком в любом алфавите. Заметим, что $$\varnothing ne \{\varepsilon\}$$; первый не содержит вообще никаких цепочек, а второй состоит из одной цепочки.
Единственное существенное ограничение для множеств, которые могут быть языками, состоит в том, что все алфавиты конечны.
Некоторые из приведенных выше языков содержат конечное число слов. В этом случае язык, в принципе, может быть задан перечислением входящих в него слов.
Однако некоторые языки и могут содержать бесконечное число цепочек, но эти цепочки должны быть составлены из символов некоторого фиксированного конечного алфавита. В общем случае язык - это
Большинство информационных процессов связано не с отдельными сообщениями, а с последовательностями (потоками) сообщений. Например, при чтении человек анализирует последовательность букв, образующих слова и текст в целом; данные, поступающие от измерительных устройств или передающиеся по каналам связи, представляют собой последовательности сообщений. Для описания (моделирования) подобных ситуаций удобно ввести формальное понятие конечного (комбинаторного)
Конечным (комбинаторным) источником называется произвольное множество $$S$$. Элементы множества $$S$$ обычно называются сообщениями. Источник может породить любое из этих сообщений.
В некоторых случаях бывает известно, что в последовательностях сообщений одни сообщения встречаются чаще, чем другие. Например, в текстах на русском языке буквы "о", "е" встречаются более чем в 10 раз чаще букв "щ", "э", "ф" [30]. В других естественных языках наблюдается аналогичная ситуация. Использование дополнительной информации о частотах появления сообщений вероятностного источника может повысить эффективность обработки данных.
Формализацией понятия частоты появления того или иного события в математике является его вероятность. Вероятность события $$A$$ обозначают обычно символом $$P(A)$$. Вероятность некоторого события (сообщения) можно представлять себе как долю тех случаев, в которых оно появляется, от общего числа появившихся событий (сообщений).
Так, если заданы четыре сообщения $$A_1, A_2, A_3, A_4$$ с вероятностями $$P(A_1)=1/2, P(A_2)=3/8, P(A_3) = P(A_4)=1/16$$, то это означает, что среди, например, 10000 переданных сообщений около 5000 раз появляется сообщение $$A_1$$, около 3750 - сообщение $$A_2$$ и примерно по 625 раз - каждое из сообщений $$A_3$$ и $$A_4$$.
Распределение вероятностей появления отдельных сообщений в последовательности является важной ее характеристикой и существенно влияет на дальнейшие процессы обработки сообщений. Для дальнейшего удобно ввести формальное понятие конечного вероятностного
Вероятностным источником $$S$$ назовем произвольное множество (сообщений) с вероятностями (частотами) появления каждого из них. Удобно представлять вероятностный источник в виде таблицы.
Вероятностный
| Сообщение | $$A_1$$ | $$A_2$$ | $$\dots$$ | $$A_n$$ |
| Вероятность появления сообщения | $$p_1$$ | $$p_2$$ | $$\dots$$ | $$p_n$$ |
С позиций теории вероятностей вероятностный источник представляет собой
Характерной особенностью вероятностного источника является отсутствие полной определенности в поступлении очередного сообщения источника. Степень неопределенности для различных источников может значительно отличаться. Например, если рассматривать в качестве источника номера лотерейных билетов, крайне трудно определить номер оче-редного выигрышного билета. Однако если сообщениями источника считать исходы розыгрыша крупного выигрыша (автомобиля или квартиры) для конкретного билета, то сообщение такого источника предсказать не трудно. Скорее всего, на данный лотерейный билет крупного выигрыша не будет.
Для практики желательно уметь оценивать степень неопределенности различных вероятностных источников. Рассмотрим источник с $$n$$ равновероятными сообщениями. Понятно, что степень неопределенности такого источника зависит от $$n$$. При $$n=1$$ неопределенность отсутствует, т. к. может появиться только одно единственное сообщение. При больших $$n$$ неопределенность больше (трудно предсказать появление какого-то определенного сообщения из $$n$$ возможных). Из рассмотренного примера следует, что функция, описывающая неопределенность источника, должна принимать нулевое значение в случае отсутствия неопределенности (при $$n=1$$), а при увеличении $$n$$ она должна возрастать. Можно показать [31], что, наложив ряд простых и естественных требований на функцию, которая должна характеризовать неопределенность вероятностного источника, можно определить вид такой функции.
Неопределенность вероятностного источника $$S$$ с множеством сообщений $$\{m_1,_2,\dots, m_n\}$$, вероятности появления которых равны $$p_1,p_2,\dots,p_n$$ соответственно, принято описывать функцией (величиной)
$$H(S)=\sum_{i=1}^{n}p_i*\log_2\frac{1}{p_i}$$Величина $$H(S)$$ называется
Неопределенность источника можно трактовать как его информативность. Действительно, если неопределенность источника мала или даже равна 0, то очередное сообщение не несет новой информации, т. к. легко может быть предсказано заранее. И наоборот, очередное сообщение неопределенного источника плохо предсказуемо, скорей всего оно будет новым, отличным от любого ожидаемого сообщения.
Входящее в выражение (6.1) для энтропии выражение $$\log_21/p_i$$ можно рассматривать как информативность (неопределенность) $$i$$-го сообщения источника, поскольку оно вполне соответствует интуитивному представлению о неопределенности.
От вероятностного источника зависит выбор оптимального в среднем способа кодирования сообщений.
Чаще всего информация представляется в виде языковых сообщений (цепочек знаков или слов), причем в процессе ее обработки форма представления может меняться. Например, сообщение, предназначенное для передачи по телеграфу, первоначально может быть представлено в виде рукописного текста. Телеграфист переводит это сообщение в последовательность длинных, коротких импульсов и пауз, передающихся по телеграфному каналу. А на приемном конце такая последовательность может быть преобразована в печатный текст. Рассмотренные преобразования представляют собой пример кодирования сообщений. Еще одним примером кодирования является тайнопись, когда исходное сообщение преобразуется в другую форму, скрывающую содержание исходного сообщения.
Различные задачи кодирования можно формализовать следующим образом. Пусть $$A$$ и $$B$$ алфавиты, $$S \subset A^*$$ некоторое множество слов в алфавите $$A$$. Тогда функция
$$c:S \to B^*$$называется кодированием или кодом. Кодом называется также образ отображения $$c$$, обозначаемый $$Im(c)$$. Если существует
Побуквенное (алфавитное) кодирование. Обычно, кодирование множества слов $$S$$ производится с помощью функции кодирующей отдельные буквы алфавита $$A$$. Для этого случая определение кода будет следующим.
Кодом называется отображение
$$c:A \to B^*$$сопоставляющее каждому знаку из алфавита $$A$$ некоторое слово, которое составлено из знаков, входящих в $$B$$. Слова, входящие в $$Im(c)$$, называются кодовыми словами. Отображение (6.2) может задаваться любым из известных в математике способов. Для конечного множества $$A$$ чаще всего используется табличный способ, задающий код (6.2) таблицей.
| Кодируемая буква алфавита А | Кодовое слово |
|---|---|
| $$a_1$$ | $$c(a_1)$$ |
| $$a_2$$ | $$c(a_2)$$ |
| $$\dots$$ | $$\dots$$ |
| $$a_n$$ | $$c(a_N)$$ |
Такая таблица называется кодовой таблицей. В качестве примера можно привести таблицу кодирования алфавита $$\{0, 1, 2, 3, 4, 5, 6, 7\}$$ из цифр
| Кодируемый знак | Кодовое слово |
|---|---|
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
Еще одним примером является так называемый код ASCII, фрагмент которого показан в следующей таблице.
| Знак | Кодовое слово (в десятичной системе счисления) | Кодовое слово (в шестнадцатеричной системе счисления) |
|---|---|---|
| … | … | |
| a | 97 | 61 |
| b | 98 | 62 |
| c | 99 | 63 |
| d | 100 | 64 |
| e | 101 | 65 |
| f | 102 | 66 |
| g | 103 | 67 |
| h | 104 | 68 |
| i | 105 | 69 |
| j | 106 | 6A |
| … | … |
Кодирование слов. Отображение (6.2) позволяет перейти от кодирования отдельных знаков (букв конечного алфавита) к кодированию слов. Если $$\alpha = a_1, a_2, \dots, a_k$$ - слово, состоящее из знаков (полученное конкатенацией знаков) $$a_1, a_2, \dots, a_k \in A$$, то кодом $$c(\alpha)$$ слова $$\alpha$$ (по определению) является конкатенация кодов $$c(a_i)$$ знаков $$a_i$$, образующих слово, т. е. $$с(\alpha) = с(а_1)\cdot с(а_2)\cdot \dots \cdot c(a_k) \in B^*$$. Например, с применением таблицы ASCII кода (см. последнюю таблицу) слово head будет закодировано последовательностью 10410197100 при использовании десятичной системы счисления или последовательностью 68656164 - в шестнадцатеричной.
Условие (необходимое) однозначной декодируемости заключается в инъективности отображения (6.2). Инъективность обеспечивает однозначную декодируемость отдельных знаков из алфавита $$A$$. Однако однозначной декодируемости слов из $$Im(c)$$ это условие не обеспечивает, если коды отдельных знаков, входящих в слово, следуют один за другим и не разделяются специальным символом. Подробнее проблема однозначной декодируемости будет рассмотрена позже.
В частном случае, когда знаки из $$A$$ кодируются однобуквенными словами, отображение (6.2) имеет вид $$c:A \to B$$ и представляет собой простую замену (подстановку) знаков. Однако чаще всего, в основном из-за использования в большинстве технических устройств обработки информации двоичного алфавита $$B =\{0, 1\}$$, каждый знак из $$A$$ кодируется последовательностью знаков (словом) из B.
Недостаточность количества знаков в алфавите $$B$$ является препятствием применения простой замены для кодирования (не обеспечивается инъективность и, следовательно, однозначность декодируемости при $$|A|>|B|$$). Для устранения этой проблемы используются множества новых, "составных" объектов из степеней $$B^2, B^3, \dots $$ алфавита $$B$$. Множество $$B^k$$ состоит из упорядоченных последовательностей элементов из $$B$$ (векторов) длины $$k$$. Число элементов $$|B^k|$$ множества $$B^k$$ равно $$m^k$$. Например, для двоичного алфавита $$B =\{0, 1\}$$ имеем $$|B^k|=2^k$$. Таким образом, взяв достаточно большую степень $$k$$, можно получить нужное количество элементов вторичного алфавита.
Если каждый знак алфавита $$A$$ отображается при кодировании $$c:A\to B^k$$ в слово одинаковой длины $$k$$, то говорят, что код является кодом постоянной длины. Такие коды широко распространены, поскольку для обработки сообщений используются вычислительные машины, коммуникацион-ные устройства и другое оборудование, имеющее регистры фиксированного размера.
Процедуру кодирования слова $$\alpha = a_{i1} a_{i2} \dots a_{ik}$$ в алфавите $$A$$ можно представить следующим образом. Имеется кодовая таблица, в левом столбце которой находятся кодируемые буквы алфавита $$A$$, а в правом столбце - соответствующие кодовые слова (кодовые слова могут иметь различную длину).
(рис 6.4) Процедура кодировании слов с использованием кодовой таблицы
Для каждого знака слова $$\alpha = a_{i1} a_{i2} \dots a_{ik}$$, начиная с первого знака, в кодовой таблице находится строка, в которой в левом поле располагается кодируемый знак (буква), и из правого поля этой строки берется соответствующее кодовое слово в алфавите $$B$$. Найденное кодовое слово приписывается слева (конкатенируется) к уже сформированной части кода слова $$\alpha$$. Кодовое слово первой буквы слова $$\alpha$$ приписывается к пустому слову е. Эта процедура схематически показана на рис.6.4.
В приведенных выше примерах кодирования все кодовые слова имели одинаковую длину. Однако это не является обязательным требованием. Более того, если вероятности появления сообщений заметно отличаются друг от друга, то сообщения с большой вероятностью появления лучше кодировать короткими словами, а более длинными словами кодировать редкие сообщений. В результате кодовый текст при определенных условиях станет в среднем короче.
Показателем экономичности или эффективности неравномерного кода является не длина отдельных кодовых слов, а "средняя" их длина, определяемая равенством:
$$L(S,c)=\sum_{i=1}^{n}p_i*|c(a_i)|$$где $$c(a_i)$$ - кодовое слово, которым закодировано сообщение $$a_i$$, а $$|c(a_i)|$$ - его длина, $$p_i$$ - вероятность сообщения $$a_i$$ ,$$ n $$- общее число сообщений источника $$S$$. Для краткости записи формул далее могут использоваться обозначения $$l_i =|c(a_i)|$$ и $$L=L(S,c)$$. Заметим, что обозначение средней длины кодирования через $$L(S,c)$$ подчеркивает тот факт, что эта величина зависит как от
Наиболее экономным является код с наименьшей средней длиной $$L(S,c)$$. Сравним на примерах экономичность различных способов кодирования одного и того же источника.
Пусть источник содержит 4 сообщения $$A_1, A_2, A_3, A_4$$ с вероятностями $$P(A_1)=1/2, P(A_2)=3/8, P(A_3) = P(A_4)=1/16$$. Эти сообщения можно закодировать кодовыми словами постоянной длины, состоящими из двух знаков, в алфавите $$B =\{0, 1\}$$ в соответствии с кодовой таблицей.
| $$A_1$$ | 00 |
| $$A_2$$ | 01 |
| A_3 | 10 |
| A_4 | 11 |
Очевидно, что для представления (передачи) любой последовательности в среднем потребуется 2 знака на одно сообщение. Сравним эффективность такого кодирования с описанным выше кодированием словами переменной длины. Кодовая таблица для данного случая может иметь следующий вид.
| $$A_1$$ | 0 |
| $$A_2$$ | 1 |
| $$A_3$$ | 10 |
| $$A_4$$ | 11 |
В этой таблице, в отличие от предыдущей, наиболее частые сообщения $$A_1$$ и $$A_2$$ кодируются одним двоичным знаком. Для последнего варианта кодирования имеем
$$L =1 \times 0,5 + 1 \times 0,375 + 2 \times 0,0625 + 2 \times 0,0625 = 1,125$$в то время как для равномерного кода средняя длина $$L=2$$ (она совпадает с общей длиной кодовых слов). Из рассмотренного примера видно, что кодирование сообщений словами различной длины может дать суще-ственное (почти в два раза) увеличение экономичности кодирования.
При использовании неравномерных кодов появляется проблема, которую поясним на примере последней кодовой таблицы. Пусть при помощи этой таблицы кодируется последовательность сообщений $$A_1A_3A_2A_3$$, в результате чего она преобразуется в следующий двоичный текст: 010110. Первый знак исходного сообщения декодируется однозначно - это $$A_1$$. Однако дальше начинается неопределенность: $$A_1A_2A_1A_4A_1, A_1A_3A_2A_3$$ или $$A_1A_3A_4A_1$$. Это лишь некоторые из возможных вариантов декодирования исходной последовательности знаков.
Необходимо отметить, что неоднозначность декодирования слова появилась несмотря на то, что условие однозначности декодирования знаков (инъективность кодового отображения) выполняется.
Существо проблемы - в невозможности однозначного выделения кодовых слов. Для ее решения следовало бы отделить одно кодовое слово от другого. Разумеется, это можно сделать, но лишь используя либо паузу между словами, либо специальный разделительный знак, для которого необходимо особое кодовое обозначение. И тот, и другой путь, во-первых, противоречат описанному выше способу кодирования слов путем конкатенации кодов $$с(а_i)$$ знаков $$a_i$$, образующих слово, и, во-вторых, приведет к значительному удлинению кодового текста, сводя на нет преимущества использования кодов переменной длины.
Решение данной проблемы заключается в том, чтобы иметь возможность в любом кодовом тексте выделять отдельные кодовые слова без использования специальных разделительных знаков. Иначе говоря, необходимо, чтобы код удовлетворял следующему требованию: всякая последовательность кодовых знаков может быть единственным образом разбита на кодовые слова. Коды, для которых последнее требование выполнено, называются однозначно декодируемыми (иногда их называют кодами без запятой).
Рассмотрим код (схему алфавитного кодирования) $$c:A \to В^*$$, заданный кодовой таблицей
$$a_1 \to \beta_1\\ A_2 \to \beta_2\\ \vdots\\ A_k \to \beta_k$$и различные слова, составленные из элементарных кодов.
Определение. Код $$с$$ называется однозначно декодируемым, если
$$\beta_{i_1}, \beta_{i_2}, \dots, \beta_{i_k}=\beta_{j_1}, \beta_{j_2}, \dots, \beta_{i_m} \Rightarrow k=m$$и
$$\forall_t=1,2, \dots, k\\ i_1=j_1$$то есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
Если таблица кодов содержит одинаковые кодовые слова, то есть если
$$\exists_{i,j}, I \ne j\\ \beta_i= \beta_j$$то код заведомо не является однозначно декодируемым (схема не является разделимой). Такие коды далее не рассматриваются.
Наиболее простыми и часто используемыми кодами без специального разделителя кодовых слов являются так называемые префиксные коды [29].
Определение. Код, обладающий тем свойством, что никакое кодовое слово не является началом (префиксом) другого кодового слова, называется префиксным.
Теорема 1.
Доказательство. Предположим противное. Тогда существует слово $$\beta$$ которое можно представить двумя разными способами $$\beta_i=\beta_{i1} \beta_{i2} \dots \beta_{ik}=\beta_{j1} \beta_{j2} \dots \beta_{jm}$$, причем до номера $$t$$ все подслова в обоих представлениях (разложениях) совпадают, а слова $$\beta_{i_t}$$ и $$\beta_{j_t}$$ различны. Отбросив одинаковые префиксы двух равных слов (представлений), получим совпадающие окончания $$\beta_{i_t} \beta_{i_{t+1}} \dots \beta_{i_k}=\beta_{j_t} \beta_{j_{t+1}} \dots \beta_{j_m}$$, начинающиеся с различных слов. Из-за равенства окончаний первые буквы слов $$\beta_{i_t}$$ и $$\beta_{j_t}$$ должны совпадать. По аналогичной причине должны совпадать и вторые буквы этих слов и т.д. Это означает, что неравенство слов $$\beta_{i_t}$$ и $$\beta_{j_t}$$ может заключаться только в том, что они имеют разную длину и, следовательно, одно из них является префиксом другого. Это противоречит префиксности кода.
Множество кодовых слов можно графически изобразить как поддерево словарного дерева (рис.6.5). Для этого из всего словарного дерева следует показать только вершины, соответствующие кодовым словам, и пути, ведущие от этих вершин к корню дерева. Такое поддерево называют деревом кода или кодовым деревом.
На рис.6.5 а) - дерево, соответствующие коду, у которого все слова имеют одинаковую длину. Кружками помечены те вершины, которые соответствуют кодовым словам. В данном случае это 4 двухбуквенных слова, составляющих второй уровень словарного дерева (
(рис 6.5) Деревья различных кодов
Замечание. Свойство префиксности является достаточным, но не является необходимым для однозначной декодируемости.
Пример. Код, состоящий из двоичных кодовых слов 1, 10, - не префиксный, но может быть однозначно декодирован. Появление символа 1 означает начало нового кодового слова. Последнее остается справедливым для кода, каждое слово которого есть единица с последующими нулями. Разумеется, подобные коды далеко не самые экономные.
Если код префиксный, то, читая кодовую запись подряд от начала, мы всегда сможем разобраться, где кончается одно кодовое слово и начинается следующее. Если, например, в кодовой записи встретилось кодовое обозначение 110, то разночтений быть не может, так как в силу префиксности наш код не содержит кодовых обозначений 1, 11 или, скажем, 1101. Именно так обстояло дело для рассмотренного выше кода, который очевидно является префиксным.
Для применения кода на практике желательно, чтобы кодовые слова были как можно короче. Однако чем слова короче, тем их запас меньше. В этом легко убедиться, посмотрев на изображение словарного
Теорема (необходимые условия). Пусть $$C=\{c_1, c_2, \dots, c_n\}$$ - префиксный двоичный код с длинами кодовых слов $$l_1, l_2, \dots, l_n$$. Тогда выполняется
Доказательство. Рассмотрим, сколько слов длины $$k$$ может быть в префиксном коде. Максимальное число таких слов равно $$2^k$$. В этом случае все $$2^k$$ кодовых слова имеют длину $$k$$.
Для каждого кодового слова длины $$k-i$$ имеется $$2^i$$ слов длины $$k$$, для которых данное слово является префиксом и по этой причине не является кодовым. Это следует из структуры словарного дерева (см. рис. 6.3). Множества $$T_{ci}$$ и $$T_{cj}$$ слов длины $$k$$, для которых кодовые слова $$c_i$$ и $$c_j$$ являются префиксами, не пересекаются, так как в противном случае более короткое из этих слов было бы префиксом более длинного. Значит, если в префиксном коде имеется $$n_{k-1}$$ слов длины $$k-1, n_{k-2}$$ слов длины $$k-2,\dots , n_1$$ слов длины 1, то число $$n_k$$ слов длины $$k$$ удовлетворяет неравенству
$$n_k \le 2^k-2^{k-1}n_1-2^{k-2}n_2- \dots - 2n_{k-1}$$Это неравенство верно для любого $$k$$, в том числе и для $$k$$, равного максимальной длине кодовых слов. После деления на $$2^k$$ обеих частей неравенства (6.4) его можно преобразовать к виду
$$\frac{n_k}{2^k}+\frac{n_{k-1}}{2^{k-1}}+\dots +\frac{n_2}{2^2}+\frac{n_1}{2} \le 1$$Слагаемое вида $$\frac{n_m}{2^m}$$, представляющее в неравенстве (6.5) $$п_т$$ кодовых слов длины $$т$$, можно записать в виде суммы
$$\frac{n_m}{2^m}=\overbrace{\frac{1}{2^m}+\frac{1}{2^m}+\dots+\frac{1}{2^m}}^{n_m}$$С учетом такого представления неравенство (6.5) можно переписать следующим образом:
$$\frac{1}{2^{l_1}}+\frac{1}{2^{l_2}}+\dots+\frac{1}{2^{l_N}} \le 1$$где $$N$$ - общее число слов
Выполнение
Можно также доказать, что если
Теорема (достаточные условия). Если положительные целые числа $$l_1, l_2, \dots, l_n$$ удовлетворяют
то существует
Доказательство. Если среди чисел $$l_1, l_2, \dots, l_N$$ имеется ровно $$n_i$$ чисел, равных $$i$$, то
где $$M$$ - максимальное из данных чисел. Из справедливости этого неравенства следует, что верны неравенства (6.5) для всех $$k \le M$$, а следовательно, и неравенство (6.4).
Для построения нужного
Из неравенства (6.4) при $$k=1$$ получаем $$n_1\le 2$$, т. е. требуемое число не превосходит общего числа вершин первого яруса. Значит, на этом ярусе можно выбрать какие-то $$n_1$$ вершин в качестве концевых ($$n_1$$ равно 0, 1 или 2). Если это сделано, то из общего числа вершин второго яруса (их $$2^2=4$$) для построения кода можно использовать лишь $$4-2n_1$$. Однако и этого числа вершин хватит, так как из неравенства (6.4) при $$k=2$$ вытекает
$$п_2 <4-2n_1$$Аналогично, при $$k=3$$ имеем неравенство:
$$n_3 \le 2^3-4n_1-2n_2$$Правая часть его вновь совпадает с допустимым для построения
Докажем, что если для длин $$l_1, l_2, \dots, l_n$$ кодовых слов выполняется равен - равенство $$\frac{1}{2^{l_1}}+\frac{1}{2^{l_2}}+\dots+\frac{1}{2^{l_n}}=1$$,то код является полным. Предположим противное, то есть, что код не полный. Тогда к нему можно добавить, по крайней мере, одно кодовое слово (длины $$l_{n+1}$$) и получить новый
Теоремы Крафта доказаны для случая, когда рассматриваются коды в алфавите $$\{0,1\}$$. Если кодовый алфавит содержит $$d$$ символов, то аналогичным образом можно доказать, что необходимым и достаточным условием для существования
Оказывается, этому неравенству обязаны удовлетворять и длины кодовых слов произвольного однозначно декодируемого кода. Поэтому, если существует однозначно декодируемый код с длинами слов $$l_1, l_2, \dots, l_N$$, то существует и
Один из методов алфавитного кодирования был предложен Фано. Схема кодирования по методу Фано заключается в следующем. Предположим, что кодируемые сообщения источника (знаки исходного алфавита) располагаются в последовательности $$A_1, A_2, \dots, A_N$$ так, что соответствующие им вероятности не возрастают, т. е. $$P(A_1) \ge P(A_2) \ge \dots \ge P(A_N) $$. Рассмотрим разбиения последовательности A 1, A2, …, AN на две подпоследовательности $$A_1, A_2 \dots , A_m$$ и $$A_{m+1}, A_{m+2}, \dots, A_N$$ Каждое такое разбиение определяется числом $$m, 1 \le m \le N-1$$, которое определяет, сколько элементов исходной последовательности входит в первую и вторую части разбиения. Среди $$N-1$$ разбиения выберем такое, чтобы модуль разности $$|\sum_{i=1}^{m}P(A_i)-\sum_{m+1}^{N}P(A_i)|$$ был минимальным. Всем сообщениям из первой части разбиения в качестве первого знака кодового слова приписываем 0, а сообщениям из второй части 1. По тому же принципу каждая из полученных подпоследовательностей снова разбивается на две части, и это раз-биение определяет значение второго символа кодового слова. Процедура продолжается до тех пор, пока все множество не будет разбито на отдельные сообщения. В результате каждому из сообщений будет сопоставлено кодовое слово из нулей и единиц.
Описанную процедуру построения кода Фано на примере из пяти сообщений иллюстрирует следующая таблица.
| Сообщения | Вероятности сообщений | Знаки кодовых слов | Кодовое слово | ||
|---|---|---|---|---|---|
| 1-й знак | 2-й знак | 3-й знак | |||
| $$A_i$$ | 0.4 | 0 | 0 | 00 | |
| $$A_2$$ | 0.15 | 1 | 01 | ||
| $$A_3$$ | 0.15 | 1 | 0 | 10 | |
| $$A_4$$ | 0.15 | 1 | 0 | 110 | |
| $$A_5$$ | 0.15 | 1 | 111 | ||
Понятно, что чем более вероятно сообщение, тем быстрее оно образует "самостоятельную" группу и тем более коротким словом оно будет закодировано. Это обстоятельство и обеспечивает высокую экономность кода Фано. Код, построенный для данного источника методом Фано, имеет среднюю длину кодового слова равную 2,3.
Код, построенный методом Фано, всегда является префиксным. Действительно, на первом шаге построения кода методом Фано множество сообщений источника разбивается на два подмножества. Все кодовые слова, соответствующие первому подмножеству, имеют однобуквенный префикс, состоящий из 0, а все слова, соответствующие второму подмножеству, имеют однобуквенный префикс, состоящий из 1 (или наоборот). Поэтому ни одно слово, соответствующее какому-нибудь из сообщений из первого подмножества, не может быть префиксом ни для какого слова, соответствующего сообщению из второго подмножества. Аналогичная процедура разбиения применяется к каждому подмножеству сообщений с одинаковыми префиксами при добавлении нового знака к формируемым кодовым словам. При этом число подмножеств, на которые разбивается исходное множество сообщений источника (блоков разбиения), увеличивается. Важным свойством разбиений является то, что для кодовых слов, соответствующих сообщениям из разных блоков разбиения, имеются различные префиксы. Построение кода завершается
Описанный метод кодирования можно применять и в случае произвольного алфавита из $$d$$ символов, с той лишь разницей, что на каждом шаге следует производить разбиение на $$d$$ равновероятных групп.
Рассмотренные ранее примеры показывают, что использование кодов переменной длины позволяет эффективнее кодировать сообщения по сравнению с равномерным кодированием. Для получения оценки минимально достижимой средней длины кодового слова рассмотрим избыточность кодирования $$R(c,S)$$, представляющую собой разность $$R(c,S) = L(c,S)-H(S)$$ между средней длиной кодового слова при кодировании источника S кодом c и
Для доказательства первой теоремы напомним одно свойство логарифма, которое заключается в том, что
Теорема. Для произвольного источника $$S$$ и
(рис 6.6) График функции log2(x) и касательной к ней в точке x=1
Доказательство.
$$-R(c,S)=H(S)-L(c,S)=\sum_{i=1}^{k}P(A_i)log \left (\frac{1}{P(A_i)2^{|c(A_i)|}}\right )$$С учетом отмеченного выше неравенства для функции $$log_2$$ каждое слагаемое можно оценить сверху следующим образом:
$$P(A_i)log \left (\frac{1}{P(A_i)*2^{|c(A_i)|}} \right ) \le \frac{P(A_i)}{ln2} \left (\frac{1}{P(A_i)*2^{|c(A_i)|}-1}\right ) \le \frac{1}{ln2} \left (\frac{1}{2^{|c(A_i)|}}-P(A_i) \right )$$После суммирования получим
$$-R(c,S) \le \frac{1}{ln2} \left (\sum_{i=1}^{k}\frac{1}{2^{|c(A_i)|}}-\sum_{i=1}^{k}P(A_i) \right ) \le 0$$причем последнее неравенство следует из
Из доказанной теоремы следует, что энтропия источника является нижней границей средней длины кодирования. Для источников, у которых вероятности являются целыми отрицательными степенями 2, эта граница достижима. Легко проверить, что для источника с распределением вероятностей $$p_1 = 0,5 = 2^{-1}, p_2 = 0,25 = 2^{-2}, p_3 = p_4 = 0,125=2^{-3}$$ средняя длина кодирования равна 1,75 и совпадает с
Для доказательства второй теоремы потребуется функция $$[x]$$, которая называется "потолок" и определяется выражением $$[x]=min\{n|n \ge x, n - целое\}$$. Необходимые для доказательства свойства этой функции легко следуют из ее графика, показанного на рис.6.7, и заключаются в выполнении неравенств $$0 \le [x]-x<1$$.
(рис 6.7) График функции [x]
Теорема. Для каждого источника $$S$$ найдется
Пусть $$l_i=\left [log\frac{1}{P(A_i)} \right ]$$, где $$[х]$$ функция "потолок". Тогда
$$\sum_{i=1}^{k}2^{-i_i} \le \sum{i=1}{k}2^{-log\frac{1}{P(A_i)}}=\sum_{i=1}^{k}P(A_i)=1$$Это означает, что числа $$l_i$$ удовлетворяют
Теорема доказана.
Данная теорема гарантирует, что для любого источника найдется
Для практических целей представляет интерес нахождение для каждого источника
Определение. Префиксное кодирование $$c_0$$ называется оптимальным для источника $$S$$, если для каждого префиксного кодирования c источника $$S$$ справедливо неравенство $$R(c_0,S) \le R(c,S)$$.
Для каждого источника существует оптимальный код, поскольку множество префиксных кодов источника с избыточностью, меньшей либо равной 1, не пусто и конечно. Один источник может иметь несколько оптимальных кодов с разными наборами длин кодовых слов.
Пусть буквы алфавита $$\{a_1, a_2, \dots, a_n\}$$ источника $$S$$ имеют вероятности появления $$p_1 p_2 \dots p_n$$ , длины кодовых слов $$c(a_1), c(a_2), \dots, c(a_n)$$ при использовании кода $$c$$ равны $$l_1, l_2, \dots, l_n$$. Рассмотрим некоторые свойства оптимального кодирования, для того чтобы, опираясь на эти свойства, сформулировать процедуру нахождения оптимального кода.
Свойство 1. Для оптимального кода из $$p_i > p_j$$ следует, что $$l_i \le l_j$$.
Для доказательства предположим противное, т. е. что для оптимального кода существуют $$p_i$$ и $$p_j$$, такие что $$p_i > p_j$$ и $$l_i > l_j$$. Построим новый код, поменяв местами кодовые слова рассматриваемого оптимального кода для $$i$$-ой и $$j$$-ой букв алфавита. Разность между средней длиной $$L_0$$ кодирования оптимальным кодом и средний длиной $$L$$ построенного кода имеет вид
$$L_0-L=p_il_i+p_jl_j-p_il_i-p_jl_j=(p_i-p_j)(l_i-l_j) >0$$что противоречит оптимальности рассматриваемого кода.
Свойство 2. Существует оптимальный код источника $$S$$, для которого
$$l_1\lel_2\le \dots \le l_{n-l}=l_n$$причем два последних слова имеют максимальную длину и отличаются только в последнем знаке.
Предположим, что в оптимальном коде не существует двух слов максимальной длины. Это значит, существует только одно слово максимальной длины. Если это самое длинное слово сократить на один последний знак, а другие кодовые слова оставить неизменными, то получится новый код, который, во-первых, будет префиксным (нет второго слова, которое отличается в последнем знаке), и, во-вторых, средняя длина кодирования будет меньше. Это противоречит предположению о существовании в оптимальном коде только одного слова максимальной длины. Таким образом, в оптимальном коде существует, по крайней мере, два кодовых слова максимальной длины.
Докажем, что какие-то два слова максимальной длины отличаются только в последнем знаке. Опять предположим противное, то есть любые два слова максимальной длины отличаются не только в последнем знаке. В этой ситуации можно повторить описанную выше процедуру укорачивания одного из слов максимальной длины и получить в результате новый
Опираясь на рассмотренные свойства, можно построить оптимальный для заданного источника $$S$$ код с использованием двух процедур: сжатия источника и расщепления кода. Смысл первой процедуры заключается в том, что исходный источник последовательно заменяется на более простой (содержащий на 1 меньше знаков) источник. Применение процедуры сжатия заканчивается, когда будет получен простейший источник с двумя знаками, оптимальное кодирование которого очевидно. Процедура расщепления кода предназначена для построения из оптимального кода более простого источника оптимального кода того источника, из которого процедурой сжатия был получен простой источник.
Процедура сжатия источника заключается в переходе от источника $$S$$ с алфавитом из n знаков $$а_1, а_2, \dots, а_п$$ упорядоченных в порядке невозрастания соответствующих им вероятностей $$р(а_1)\ge р(а_2)\ge \dots \ge р(а_n)$$, к источнику $$S'$$ с алфавитом из $$n-1$$ знака $$а'_1, а'_2, \dots,а'_{n-1}$$ и вероятностями $$p(a'_i)=p(a_i)$$ при $$i < n-1$$ и $$p(a'_{n-l} =p(a_{k-l})+p(a_k)$$.
Операцию сжатия источника $$S$$ будем обозначать через $$S'$$ Фактически, при сжатии первые $$n-2$$ знака остаются неизменными, а два последних, наименее вероятных знака заменяются на некоторый новый знак с вероятностью, равной сумме вероятностей двух заменяемых знаков.
$$\overbrace{ \begin{matrix} a_1 a_2 \ldots a_{n-1} a_n\\ p_1 \ge p_2 \ge \ldots \ge p_{n-1} \ge p_n \end{matrix}}^{\mbox{Источник S из n букв}} \xrightarrow{Сжатие} \overbrace{ \begin{matrix} a_1 a_2 \ldots a_{n-2} \hat a\\ p_1 \ge p_2 \ge \ldots \ge p_{n-2} \ge p_{n-1}+p_n \end{matrix}}^{\mbox{Источник S' из n-1 букв}} \xrightarrow{\mbox{Сортировка по p}}$$Применяя сжатие к источнику $$S$$, получим новый источник $$S^{(1)}=S'$$, применяя затем процедуру сжатия к $$S^{(1)}$$ получим $$S^{(2)}=(S^{(1)})'$$. Действуя подобным образом $$n-2$$ раза, построим последовательность источников $$S$$, $$S^{(1)}, \dots, S^{(n-2)}$$.
Алфавит источника $$S^{(n-2)}$$ состоит только из двух знаков, поэтому найти оптимальный код для этого источника не составляет труда. Одно из слов кодируется знаком 0, а другое - знаком 1. Это особенно важно потому, что, используя оптимальный код для источника $$S^{(n-2)}$$ и последовательность кодов $$S, S^{(1)}, \dots, S^{(n-2)}$$, можно найти оптимальный код для исходного источника $$S$$.
Для построения оптимального кода источника $$S^{(i)}$$, содержащего на один знак больше, чем источник $$S^{(i+1)}$$, необходимо выполнить процедуру расщепления кода.
Пусть имеем источник
$$S^{(i+1)}=\begin{cases} a_1^{i+1}, a_2^{i+1}, \dots, \hat a_j^{i+1}, \dots a_{n-i-1}^{i+1}\\ p(a_1^{i+1}), p(a_2^{i+1}),\dots, p(\hat a_j^{i+1}), \dots p(a_{n-i-1}^{i+1})\\ c_0(a_1^{i+1}), c_0(a_2^{i+1}), \dots, c_0(\hat a_j^{i+1}),\dots c_0(a_{n-i-1}^{i+1}) \end{cases} $$И оптимальный код $$p(\hat a_j^{i+1})=p(a_{n-i-1}^i)+p(a_{n-i}^i)$$
Через $$\hat a_j$$ обозначен тот знак алфавита источника $$S^{(i+1)} $$, который заменил два знака с минимальными вероятностями источника $$S^{(i) $$ при его сжатии.
Процедура расщепления заключается в использовании оптимального кода $$c_o^{(i+1)}$$ источника $$S^{(i+1)}$$ для построения оптимального кода для источника $$S^{(i)}$$. Она заключается в следующем: знакам алфавита источника $$S^{(i)}$$, перешедшим в $$S^{(i+1)}$$ без изменения, назначаются кодовые слова совпадающих с ними знаков источника $$S^{(i+1)}$$; двум наименее вероятным знакам алфавита источника $$S^{(i+1)}$$, замененным в процессе сжатия на знак $$\hat a_j$$, сопоставляют кодовые слова $$с_0^{i+1}(\hat a_j^{i+1})0$$ и $$c_0^{i+1}(\hat a_j^{i+1})l$$.
Слово $$c_o^{i+1}(\hat a_0^{i+1})$$ в оптимальном коде источника $$S^{(i+1)}$$, содержащем $$n-i-1$$ знаков, "расщепляется", путем добавления (конкатенации) знаков 0 и 1, на 2 слова в кодовом множестве для источника $$S^{(i)}$$, содержащем $$n-i$$ знаков.
Средняя длина $$l'$$ кода источника $$S^{(i+1)}$$ и средняя длина $$l$$ кода, полученного из него расщеплением, связаны соотношением $$l=l'+p$$. Действительно,
$$l=l_1p(a_1^{i+1})+\dots+(l_j+1)p(a_{n-i-1}^i)+(l_j+1)p(a_{n-i}^i)+\dots l_{n-i-1}p(a_{n-i-1}^{i+1})=\\ =l_1p(a_1^{i+1})+\dots +l_j(p(a_{j-i-1}^i)+p(a_{n-i}^i))+(p(a_{n-i-1}^i)+p(a_{n-i}^i))+\dots l_{n-i-1}p(a_{n-i-1}^{i+1})=\ =l_1p(a_1^{i+1})+\dots +l_j(p(a_j^i)+\dots l_{n-i-1}p(a_{n-i-1}^{i+1})+(p(a_{n-i-1}^i)+p(a_{n-i}^i))=l'+p$$Докажем, что получающийся в результате расщепления код является оптимальным для источника $$S^{(i)} $$.
Предположим противное, т. е. что существует другой оптимальный код $$c''$$ для того же источника $$S^{(i)}$$ со средней длиной кодирования $$l''$$, меньшей, чем $$l$$, т. е. $$l''<l$$. В соответствии со свойством 2 оптимальный код содержит два слова максимальной длины, отличающиеся в последнем знаке и соответствующие двум наименьшим вероятностям источника $$S^{(i)}$$. Обозначим эти два слова через $$c''(a_{n-i})$$ и $$c''(a_{n-i-1})$$. Из этого кода для источника $$S^{(i)} $$ можно построить код $$c'''$$ для источника $$S^{(i+1)} $$, в котором последнее кодовое слово получается отбрасыванием последнего знаки из слов $$c''(a_{n-i})$$ и $$c''(a_{n-i-1})$$. Средняя длина $$l'''$$ кода $$c'''$$ связана со средней длиной $$l''$$ кода $$c''$$ соотношением $$l''=l'''+p$$. Из этого соотношения, из соотношения $$l=l'+p$$ и из предположения, что $$l''<l$$, следует, что $$l'''<l'$$. Это противоречит оптимальности кода для источника $$S^{(i+1)} $$.
Таким образом, используя процедуру расщепления, строится оптимальный код для источника, который ранее был преобразован процедурой сжатия в более простой источник. Повторяя эту процедуру необходимое количество раз, можно будет найти оптимальный код для исходного источника $$S$$.
Описанный метод оптимального кодирования был предложен в 1952 г. Д. Хафменом и называется его именем. В общем случае, когда для кодирования используется алфавит из более чем двух букв, метод Хафмена рассмотрен в [32].
Рассмотрим процесс построения оптимального кода на примере источника из пяти сообщений с вероятностями $$p_1 = 0,4, p_2 = 0,15, p_3 = 0,15, p_4 = 0,15, p_5 = 0,15$$. Построение кода показано на следующем рисунке.
Стрелками показаны шаги сжатия источника. В левой части каждого столбца показано распределение вероятностей источника. В правой части каждого столбца, соответствующего одному из источников, показаны кодовые слова. Построение кода начинается с простейшего источника $$S(3) $$, который кодируется двумя однобуквенными словами 0 и 1.
В данном случае средняя длина кодирования для оптимального кода, построенного методом Хафмена, составляет 2,2. Это меньше, чем средняя длина кода, построенного ранее методом Фано для того же источника.
Одно из (специфических)
Различные материальные формы представления информации называются сообщениями, содержащими данную информацию. Различные сообщения могут содержать одну и ту же информацию. В качестве примера на рис.6.1 показаны различные представления числа 4: в виде разноформатных начертаний арабской цифры 4, римской цифры, слова "четыре", записи числа 4 в
(рис 6.1) Различные формы представления числа 4
Еще одним подобным примером является возможность записи чисел в различных системах счисления. Следует заметить, что информация может быть облечена не только в графическую форму. Произнесенное человеком слово "четыре" также является сообщением, представляющим число 4. Нетрудно привести множество других примеров такой "многоликости" информации.
Следует заметить, что практический интерес представляют только такие материальные формы представления информации, которые могут быть восприняты человеком и другими живыми существами. Предполагается, что человек воспринимает сообщения непосредственно своими органами чувств или с использованием специальных приборов или средств. Органы чувств человека можно рассматривать как естественные (созданные природой) регистрирующие и измерительные средства (датчики).
Можно выделить несколько основных форм сообщений (в порядке возрастания их сложности).
Сигналы представляют собой некоторые физические величины или свойства физической среды, изменяющиеся во времени. Чаще всего такими величинами являются: напряженность электрического поля, величина электрического тока, интенсивность светового потока, давление газа и т.п.
Сигналы воспринимаются органами чувств человека или других животных, а также специально предназначенными для регистрации сигналов техническими устройствами - датчиками. Принятые сигналы, как правило, преобразуются в другую форму. Например, микрофон преобразует звуковые колебания (периодические изменения давления атмосферы) в переменный электрический ток, а световые или звуковые сигналы преобразуются органами чувств высших животных в импульсы (т. е. тоже сигналы) электрохимической природы. На рис.6.2 показан график звуковых колебаний, возникающих при произнесении слова "четыре".
(рис 6.2) График звуковых колебаний
Чаше всего информация в виде сигналов используется в системах управления техническими объектами для описания изменения состояния объектов с течением времени. Отклонение этих сигналов от требуемых по условиям эксплуатации значений приводит к выработке системой управления сигналов, представляющих управляющую информацию. Получение, обработка и анализ сигналов о состоянии управляемого объекта и внешней среды, а также генерация управляющих сигналов рассматриваются в теории управления.
Изображения можно рассматривать как многомерные и пространственные сигналы (фотографии, карты, графики и т.п.), в которых регистрируемые параметры физической среды зависят не от времени, а от пространственного положения. Для черно-белой фотографии таким параметром является степень почернения фотоматериала (фотопленки или
Физические величины, изменения которых рассматриваются как сигналы или изображения, называются параметрами сигналов. Если параметры сигналов принимают конечное число значений, то такой сигнал называется дискретным.
Некоторые повторяющиеся образцы (фрагменты) сигналов (изменяющихся во времени или в пространстве) в процессе общественной практики человека обособляются, выделяются и трактуются как некоторые новые сущности, а не просто как произвольные фрагменты сигнала. Таким образом возникают фонемы (акустические сигналы) и графемы. Эти новые сущности являются элементами, на основе которых формируется речь и письмо. Число этих элементов конечно. Графемы и фонемы являются частными случаями более общего понятия - знака. Знаком можно считать любую сущность, отличную от других сущностей. Примерами знаков являются буквы различных естественных языков, всевозможные условные обозначения на картах, схемах и других документах, дорожные знаки и многое другое. Разнообразные примеры наборов знаков приведены в 27.
Последовательность знаков, сменяющих друг друга во времени, можно рассматривать как дискретный сигнал. Например, последовательность фонем представляет собой речевое сообщение. Аналогичным образом расположение графем может восприниматься как письменное сообщение. Таким образом, представление информации в виде знаков является основой речи, письменности, а также способов хранения, передачи и обработки информации.
Условно можно выделить научные дисциплины, которые преимущественно занимаются изучением рассмотренных трех форм представления информации. Это анализ и
Учитывая вышеизложенное, можно сказать, что информатика занимается изучением сбора (получения), хранения, поиска, обработки и выдачи информации, представленной в знаковой форме. Знаки - это всего лишь одна из материальных форм информации. Но помимо формы представления информация может характеризоваться содержанием или смыслом, который приписывается человеком.
Следует отметить, что наряду с термином "информация" используется термин "данные" (иногда как синонимы). В [28]предлагается различать эти два термина и считать, что данные суть факты, идеи, сведения, которые представлены в знаковой (символьной) форме, позволяющей производить их передачу, обработку и интерпретацию (т.е. толкование, объяснение, раскрытие смысла), а информация - это смысл, который человек приписывает данным на основании известных ему правил представления в них фактов, идей, сообщений.
Полезно сделать еще одно замечание относительно терминов "знак" и "символ". Некоторые знаки приобретают определенное значение. К примеру, буквы свидетельствуют об алфавите, в который они входят, и о языке, который использует эти буквы. Но некоторые буквы (знаки) имеет для людей более глубокий смысл. Например, знак $$\pi$$, помимо того, что он является буквой греческого алфавита, означает для людей, знакомых с математикой, отношение длины окружности к длине ее диаметра. Поэтому символом целесообразно называть знак, который имеет специальный смысл (значение), связанный с определенной областью человеческой деятельности. Примерами символов являются следующие знаки: ©, @, $, §, ∞.
Число исходных для представления информации знаков, как правило, невелико (несколько десятков), а потребность в знаках, представляющих информацию о реальном мире, существенно превышает это количество и постоянно возрастает с развитием человечества, усложнением производственных отношений. Неограниченный запас новых языковых сообщений может быть получен из конечного множества знаков путем их комбинирования или составления из них последовательностей первичных знаков. Именно такой принцип лежит в основе большинства естественных языков. Несмотря на особенности каждого естественного языка, они имеют много общего. Для изучения общих принципов постро-ения языков разработаны формальные (математические) модели, которые так и называются -
Алфавитом называется конечное непустое множество знаков. Обычно подразумевается, что это множество линейно упорядочено. Условимся обозначать алфавиты символом $$\sum$$. Наиболее часто используются следующие алфавиты.
ASCII-символов или множество всех печатных ASCII-символов.Следует отметить, что алфавит $$H$$ содержит 10 десятичных цифр т. е. $$B \bigcup D \bigcup H$$ .
Слово или цепочка - это конечная последовательность знаков некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите $$B = \{0,1\}$$. Цепочки 15903 и 15df10 являются цепочками в алфавите $$D$$ и $$H$$ соответственно.
Пустая цепочка - это цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую е, можно рассматривать как цепочку в любом алфавите.
Часто бывает необходимо или удобно классифицировать слова по их длине, т.е. по числу позиций, которые занимают знаки в слове. Например, слово 01101 имеет длину 5. Обычно говорят, что
Длину некоторой цепочки $$\omega$$ обычно обозначают $$|\omega|$$. Например, $$|011| = |101| = |f50| = 3$$, а $$|\varepsilon| = 0$$.
Степени алфавита. Для множества всех цепочек определенной длины, состоящих из символов некоторого алфавита , удобно использовать, по аналогии с
Рассмотрим примеры такой записи $$A^0=\{\varepsilon\}$$ независимо от алфавита $$A$$, т.е. $$\varepsilon$$ - единственное слово длины 0. Для $$A=\{0, 1\} A^1=\{0, 1\}, A^2=\{00, 01, 10, 11\}, A^3=\{000, 001, 010, 011, 100, 101, 110, 111\}$$ и так далее. Отметим, что между $$A$$ и $$A^1$$ есть небольшое различие. Дело в том, что $$A$$ есть алфавит, и его элементы 0 и 1 являются символами, а $$A^1$$ является множеством слов, и его элементы - это слова 1 и 0, каждое длиной 1. Мы не будем вводить разные обозначения для этих множеств, полагая, что из контекста будет понятно, является {0,1} или подобное ему множество алфавитом или же множеством цепочек.
Множество всех слов над алфавитом $$A$$ принято обозначать $$A^*$$. Так, например $$\{0,1\}^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \dots\}$$. По-другому это множество можно записать в виде $$А^*= A^0 \bigcup A^1 \bigcup A^2 \bigcup \dots$$
Множество всех непустых слов в алфавите $$A$$ обозначают через $$A^+$$. Таким образом, имеют место следующие равенства:
$$А^+=А^1 \bigcup А^2 \bigcup А^3 \bigcup \dots\\ A^* =A^+\bigcup \{\varepsilon\}$$Конкатенация слов. Пусть $$\alpha$$ и $$\beta$$ - слова. Тогда $$\alpha \cdot \beta$$ обозначает их конкатенацию (соединение), т.е. слово, в котором последовательно записаны слова $$\alpha$$ и $$\beta$$. Более строго, если $$\alpha$$ - слово из $$i$$ символов: $$\alpha = a_1 a_2 \dots a_j$$, а $$\beta$$ - слово из $$j$$ символов $$\beta = b_1 b_2 \dots b_j$$, то $$\alpha \beta$$ - это слово длины $$i+j$$, $$\alpha \cdot \beta =a_{1a2} \dots a_{ib1b2} \dots b_J$$.
Конкатенацию можно рассматривать как алгебраическую операцию на множестве всех слов в алфавите $$A^*$$, которая любым словам $$\alpha$$ и $$\beta$$ из $$A^*$$ сопоставляет слово из $$A^*$$. Эта операция обладает некоторыми привычными свойствами алгебраических операций. Так, конкатенация является ассоциативной операцией, то есть для любых слов $$\alpha, \beta, \gamma$$ справедливо равенство $$(\alpha \cdot \beta) \cdot \gamma= \alpha \cdot (\beta \cdot \gamma)$$. Скобки в этом выражении определяют порядок выполнения
Пусть $$\alpha = 10010$$ и $$\beta = 001$$. Тогда $$\alpha \cdot \beta = 10010001$$, а $$\beta \cdot \alpha = 00110010$$ и, следовательно, $$\alpha \cdot \beta \ne \beta \cdot \alpha$$.
Для пустого слова $$\varepsilon$$ и любого слова $$\omega$$ справедливы равенства $$\omega \cdot \varepsilon = \omega$$. Таким образом, $$\varepsilon$$ является единицей (нейтральным элементом) относительно
Если $$\alpha-\beta \delta$$, то $$\delta$$ называется началом, или префиксом, слова $$\alpha$$, а $$\beta$$ - окончанием, или постфиксом, слова $$\alpha$$.
Множество всех слов можно представить графически в виде помеченного
На рис.6.3 изображен фрагмент словарного
(рис 6.3) Фрагмент словарного дерева (универсума) для алфавита {0, 1)
Опишем процедуру построения словарного дерева. Построение начинается с вершины, которая является корнем дерева и которая соответствует пустому слову $$\varepsilon$$. Эта (единственная) вершина образует нулевой ярус (уровень) дерева. Первый ярус дерева состоит из $$m$$ вершин ($$m$$ - число букв в алфавите $$A$$), которые соединены с корнем ребрами, помеченными буквами алфавита $$A$$. Вершины первого уровня соответствуют всем однобуквенным словам, которые получаются конкатенацией букв, помечающих ребра, с пустым словом.
Дальнейшее построение дерева выполняется аналогичным образом. Если $$k$$-й уровень дерева сформирован, то есть в дереве уже имеется $$m^k$$ вершин, соответствующих всем словам длины $$k$$, к каждой вершине $$k$$-го уровня присоединяется $$k$$ вершин $$(k+1)$$ -го уровня посредством ребер, помеченных буквами алфавита $$A$$. Любой вершине $$(k+1)$$-го уровня соответствует слово, которое получается конкатенацией некоторого $$k$$-буквенного слова и буквы, помечающей ребро между этими словами.
Таким образом, из процедуры построения дерева следует, что ребром в дереве соединяются только те вершины, которым соответствуют слова, отличающиеся по длине на 1. При этом более длинное слово является конкатенацией более короткого слова и буквы, помечающей ребро. Ясно также, что любое слово $$\beta$$, соответствующее вершине, которая лежит на пути из корня дерева к вершине, соответствующей слову $$\alpha$$, является пре-фиксом слова $$\alpha$$, то есть $$\alpha=\beta \cdot \gamma$$, $$\gamma \in A^*$$.
Рассмотренные выше понятия и примеры позволяют сформулировать точное определение
Однако оправданием использования термина "язык" для множества $$L \subset A^*$$ может служить то, что и обычные языки можно рассматривать как множества цепочек (слов). Возьмем в качестве примера русский язык, где набор всех литературных русских слов есть множество цепочек в алфавите (русских же букв). Еще один пример - язык программирования $$С$$ или любой другой язык программирования, в котором правильно написанные программы представляют собой подмножество множества всех возможных цепочек, а цепочки состоят из ASCII. Алфавиты для разных языков программирования могут быть различными, хотя обычно они состоят из прописных и строчных букв, цифр, знаков пунктуации и математических символов.
Существует, однако, множество других языков. Приведем несколько примеров.
Язык, состоящий из всех цепочек, в которых $$n$$ единиц следуют за $$n$$ нулями для некоторого $$n > 0: \{\varepsilon, 01, 0011, 000111, \dots\}$$.
Множество цепочек, состоящих из 0 и 1 и содержащих поровну тех и других: $$\{\varepsilon, 01, 10, 0011, 1001, \dots\}$$.
Множество двоичных записей простых чисел: $$\{10, 11, 101, 111, 1011, \dots \}$$.
Множество $$L_B$$ всех правильных скобочных выражений, $$A = \{(, )\}. ((()())())\in L_B, (()())) \notin L_B$$.
$$А^*$$ - язык для любого алфавита $$A$$.
$$\varnothing$$ - пустой язык в любом алфавите.
\{\varepsilon\} - язык, содержащий одну лишь пустую цепочку. Он также является языком в любом алфавите. Заметим, что $$\varnothing ne \{\varepsilon\}$$; первый не содержит вообще никаких цепочек, а второй состоит из одной цепочки.
Единственное существенное ограничение для множеств, которые могут быть языками, состоит в том, что все алфавиты конечны.
Некоторые из приведенных выше языков содержат конечное число слов. В этом случае язык, в принципе, может быть задан перечислением входящих в него слов.
Однако некоторые языки и могут содержать бесконечное число цепочек, но эти цепочки должны быть составлены из символов некоторого фиксированного конечного алфавита. В общем случае язык - это
Большинство информационных процессов связано не с отдельными сообщениями, а с последовательностями (потоками) сообщений. Например, при чтении человек анализирует последовательность букв, образующих слова и текст в целом; данные, поступающие от измерительных устройств или передающиеся по каналам связи, представляют собой последовательности сообщений. Для описания (моделирования) подобных ситуаций удобно ввести формальное понятие конечного (комбинаторного)
Конечным (комбинаторным) источником называется произвольное множество $$S$$. Элементы множества $$S$$ обычно называются сообщениями. Источник может породить любое из этих сообщений.
В некоторых случаях бывает известно, что в последовательностях сообщений одни сообщения встречаются чаще, чем другие. Например, в текстах на русском языке буквы "о", "е" встречаются более чем в 10 раз чаще букв "щ", "э", "ф" [30]. В других естественных языках наблюдается аналогичная ситуация. Использование дополнительной информации о частотах появления сообщений вероятностного источника может повысить эффективность обработки данных.
Формализацией понятия частоты появления того или иного события в математике является его вероятность. Вероятность события $$A$$ обозначают обычно символом $$P(A)$$. Вероятность некоторого события (сообщения) можно представлять себе как долю тех случаев, в которых оно появляется, от общего числа появившихся событий (сообщений).
Так, если заданы четыре сообщения $$A_1, A_2, A_3, A_4$$ с вероятностями $$P(A_1)=1/2, P(A_2)=3/8, P(A_3) = P(A_4)=1/16$$, то это означает, что среди, например, 10000 переданных сообщений около 5000 раз появляется сообщение $$A_1$$, около 3750 - сообщение $$A_2$$ и примерно по 625 раз - каждое из сообщений $$A_3$$ и $$A_4$$.
Распределение вероятностей появления отдельных сообщений в последовательности является важной ее характеристикой и существенно влияет на дальнейшие процессы обработки сообщений. Для дальнейшего удобно ввести формальное понятие конечного вероятностного
Вероятностным источником $$S$$ назовем произвольное множество (сообщений) с вероятностями (частотами) появления каждого из них. Удобно представлять вероятностный источник в виде таблицы.
Вероятностный
| Сообщение | $$A_1$$ | $$A_2$$ | $$\dots$$ | $$A_n$$ |
| Вероятность появления сообщения | $$p_1$$ | $$p_2$$ | $$\dots$$ | $$p_n$$ |
С позиций теории вероятностей вероятностный источник представляет собой
Характерной особенностью вероятностного источника является отсутствие полной определенности в поступлении очередного сообщения источника. Степень неопределенности для различных источников может значительно отличаться. Например, если рассматривать в качестве источника номера лотерейных билетов, крайне трудно определить номер оче-редного выигрышного билета. Однако если сообщениями источника считать исходы розыгрыша крупного выигрыша (автомобиля или квартиры) для конкретного билета, то сообщение такого источника предсказать не трудно. Скорее всего, на данный лотерейный билет крупного выигрыша не будет.
Для практики желательно уметь оценивать степень неопределенности различных вероятностных источников. Рассмотрим источник с $$n$$ равновероятными сообщениями. Понятно, что степень неопределенности такого источника зависит от $$n$$. При $$n=1$$ неопределенность отсутствует, т. к. может появиться только одно единственное сообщение. При больших $$n$$ неопределенность больше (трудно предсказать появление какого-то определенного сообщения из $$n$$ возможных). Из рассмотренного примера следует, что функция, описывающая неопределенность источника, должна принимать нулевое значение в случае отсутствия неопределенности (при $$n=1$$), а при увеличении $$n$$ она должна возрастать. Можно показать [31], что, наложив ряд простых и естественных требований на функцию, которая должна характеризовать неопределенность вероятностного источника, можно определить вид такой функции.
Неопределенность вероятностного источника $$S$$ с множеством сообщений $$\{m_1,_2,\dots, m_n\}$$, вероятности появления которых равны $$p_1,p_2,\dots,p_n$$ соответственно, принято описывать функцией (величиной)
$$H(S)=\sum_{i=1}^{n}p_i*\log_2\frac{1}{p_i}$$Величина $$H(S)$$ называется
Неопределенность источника можно трактовать как его информативность. Действительно, если неопределенность источника мала или даже равна 0, то очередное сообщение не несет новой информации, т. к. легко может быть предсказано заранее. И наоборот, очередное сообщение неопределенного источника плохо предсказуемо, скорей всего оно будет новым, отличным от любого ожидаемого сообщения.
Входящее в выражение (6.1) для энтропии выражение $$\log_21/p_i$$ можно рассматривать как информативность (неопределенность) $$i$$-го сообщения источника, поскольку оно вполне соответствует интуитивному представлению о неопределенности.
От вероятностного источника зависит выбор оптимального в среднем способа кодирования сообщений.
Чаще всего информация представляется в виде языковых сообщений (цепочек знаков или слов), причем в процессе ее обработки форма представления может меняться. Например, сообщение, предназначенное для передачи по телеграфу, первоначально может быть представлено в виде рукописного текста. Телеграфист переводит это сообщение в последовательность длинных, коротких импульсов и пауз, передающихся по телеграфному каналу. А на приемном конце такая последовательность может быть преобразована в печатный текст. Рассмотренные преобразования представляют собой пример кодирования сообщений. Еще одним примером кодирования является тайнопись, когда исходное сообщение преобразуется в другую форму, скрывающую содержание исходного сообщения.
Различные задачи кодирования можно формализовать следующим образом. Пусть $$A$$ и $$B$$ алфавиты, $$S \subset A^*$$ некоторое множество слов в алфавите $$A$$. Тогда функция
$$c:S \to B^*$$называется кодированием или кодом. Кодом называется также образ отображения $$c$$, обозначаемый $$Im(c)$$. Если существует
Побуквенное (алфавитное) кодирование. Обычно, кодирование множества слов $$S$$ производится с помощью функции кодирующей отдельные буквы алфавита $$A$$. Для этого случая определение кода будет следующим.
Кодом называется отображение
$$c:A \to B^*$$сопоставляющее каждому знаку из алфавита $$A$$ некоторое слово, которое составлено из знаков, входящих в $$B$$. Слова, входящие в $$Im(c)$$, называются кодовыми словами. Отображение (6.2) может задаваться любым из известных в математике способов. Для конечного множества $$A$$ чаще всего используется табличный способ, задающий код (6.2) таблицей.
| Кодируемая буква алфавита А | Кодовое слово |
|---|---|
| $$a_1$$ | $$c(a_1)$$ |
| $$a_2$$ | $$c(a_2)$$ |
| $$\dots$$ | $$\dots$$ |
| $$a_n$$ | $$c(a_N)$$ |
Такая таблица называется кодовой таблицей. В качестве примера можно привести таблицу кодирования алфавита $$\{0, 1, 2, 3, 4, 5, 6, 7\}$$ из цифр
| Кодируемый знак | Кодовое слово |
|---|---|
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
Еще одним примером является так называемый код ASCII, фрагмент которого показан в следующей таблице.
| Знак | Кодовое слово (в десятичной системе счисления) | Кодовое слово (в шестнадцатеричной системе счисления) |
|---|---|---|
| … | … | |
| a | 97 | 61 |
| b | 98 | 62 |
| c | 99 | 63 |
| d | 100 | 64 |
| e | 101 | 65 |
| f | 102 | 66 |
| g | 103 | 67 |
| h | 104 | 68 |
| i | 105 | 69 |
| j | 106 | 6A |
| … | … |
Кодирование слов. Отображение (6.2) позволяет перейти от кодирования отдельных знаков (букв конечного алфавита) к кодированию слов. Если $$\alpha = a_1, a_2, \dots, a_k$$ - слово, состоящее из знаков (полученное конкатенацией знаков) $$a_1, a_2, \dots, a_k \in A$$, то кодом $$c(\alpha)$$ слова $$\alpha$$ (по определению) является конкатенация кодов $$c(a_i)$$ знаков $$a_i$$, образующих слово, т. е. $$с(\alpha) = с(а_1)\cdot с(а_2)\cdot \dots \cdot c(a_k) \in B^*$$. Например, с применением таблицы ASCII кода (см. последнюю таблицу) слово head будет закодировано последовательностью 10410197100 при использовании десятичной системы счисления или последовательностью 68656164 - в шестнадцатеричной.
Условие (необходимое) однозначной декодируемости заключается в инъективности отображения (6.2). Инъективность обеспечивает однозначную декодируемость отдельных знаков из алфавита $$A$$. Однако однозначной декодируемости слов из $$Im(c)$$ это условие не обеспечивает, если коды отдельных знаков, входящих в слово, следуют один за другим и не разделяются специальным символом. Подробнее проблема однозначной декодируемости будет рассмотрена позже.
В частном случае, когда знаки из $$A$$ кодируются однобуквенными словами, отображение (6.2) имеет вид $$c:A \to B$$ и представляет собой простую замену (подстановку) знаков. Однако чаще всего, в основном из-за использования в большинстве технических устройств обработки информации двоичного алфавита $$B =\{0, 1\}$$, каждый знак из $$A$$ кодируется последовательностью знаков (словом) из B.
Недостаточность количества знаков в алфавите $$B$$ является препятствием применения простой замены для кодирования (не обеспечивается инъективность и, следовательно, однозначность декодируемости при $$|A|>|B|$$). Для устранения этой проблемы используются множества новых, "составных" объектов из степеней $$B^2, B^3, \dots $$ алфавита $$B$$. Множество $$B^k$$ состоит из упорядоченных последовательностей элементов из $$B$$ (векторов) длины $$k$$. Число элементов $$|B^k|$$ множества $$B^k$$ равно $$m^k$$. Например, для двоичного алфавита $$B =\{0, 1\}$$ имеем $$|B^k|=2^k$$. Таким образом, взяв достаточно большую степень $$k$$, можно получить нужное количество элементов вторичного алфавита.
Если каждый знак алфавита $$A$$ отображается при кодировании $$c:A\to B^k$$ в слово одинаковой длины $$k$$, то говорят, что код является кодом постоянной длины. Такие коды широко распространены, поскольку для обработки сообщений используются вычислительные машины, коммуникацион-ные устройства и другое оборудование, имеющее регистры фиксированного размера.
Процедуру кодирования слова $$\alpha = a_{i1} a_{i2} \dots a_{ik}$$ в алфавите $$A$$ можно представить следующим образом. Имеется кодовая таблица, в левом столбце которой находятся кодируемые буквы алфавита $$A$$, а в правом столбце - соответствующие кодовые слова (кодовые слова могут иметь различную длину).
(рис 6.4) Процедура кодировании слов с использованием кодовой таблицы
Для каждого знака слова $$\alpha = a_{i1} a_{i2} \dots a_{ik}$$, начиная с первого знака, в кодовой таблице находится строка, в которой в левом поле располагается кодируемый знак (буква), и из правого поля этой строки берется соответствующее кодовое слово в алфавите $$B$$. Найденное кодовое слово приписывается слева (конкатенируется) к уже сформированной части кода слова $$\alpha$$. Кодовое слово первой буквы слова $$\alpha$$ приписывается к пустому слову е. Эта процедура схематически показана на рис.6.4.
В приведенных выше примерах кодирования все кодовые слова имели одинаковую длину. Однако это не является обязательным требованием. Более того, если вероятности появления сообщений заметно отличаются друг от друга, то сообщения с большой вероятностью появления лучше кодировать короткими словами, а более длинными словами кодировать редкие сообщений. В результате кодовый текст при определенных условиях станет в среднем короче.
Показателем экономичности или эффективности неравномерного кода является не длина отдельных кодовых слов, а "средняя" их длина, определяемая равенством:
$$L(S,c)=\sum_{i=1}^{n}p_i*|c(a_i)|$$где $$c(a_i)$$ - кодовое слово, которым закодировано сообщение $$a_i$$, а $$|c(a_i)|$$ - его длина, $$p_i$$ - вероятность сообщения $$a_i$$ ,$$ n $$- общее число сообщений источника $$S$$. Для краткости записи формул далее могут использоваться обозначения $$l_i =|c(a_i)|$$ и $$L=L(S,c)$$. Заметим, что обозначение средней длины кодирования через $$L(S,c)$$ подчеркивает тот факт, что эта величина зависит как от
Наиболее экономным является код с наименьшей средней длиной $$L(S,c)$$. Сравним на примерах экономичность различных способов кодирования одного и того же источника.
Пусть источник содержит 4 сообщения $$A_1, A_2, A_3, A_4$$ с вероятностями $$P(A_1)=1/2, P(A_2)=3/8, P(A_3) = P(A_4)=1/16$$. Эти сообщения можно закодировать кодовыми словами постоянной длины, состоящими из двух знаков, в алфавите $$B =\{0, 1\}$$ в соответствии с кодовой таблицей.
| $$A_1$$ | 00 |
| $$A_2$$ | 01 |
| A_3 | 10 |
| A_4 | 11 |
Очевидно, что для представления (передачи) любой последовательности в среднем потребуется 2 знака на одно сообщение. Сравним эффективность такого кодирования с описанным выше кодированием словами переменной длины. Кодовая таблица для данного случая может иметь следующий вид.
| $$A_1$$ | 0 |
| $$A_2$$ | 1 |
| $$A_3$$ | 10 |
| $$A_4$$ | 11 |
В этой таблице, в отличие от предыдущей, наиболее частые сообщения $$A_1$$ и $$A_2$$ кодируются одним двоичным знаком. Для последнего варианта кодирования имеем
$$L =1 \times 0,5 + 1 \times 0,375 + 2 \times 0,0625 + 2 \times 0,0625 = 1,125$$в то время как для равномерного кода средняя длина $$L=2$$ (она совпадает с общей длиной кодовых слов). Из рассмотренного примера видно, что кодирование сообщений словами различной длины может дать суще-ственное (почти в два раза) увеличение экономичности кодирования.
При использовании неравномерных кодов появляется проблема, которую поясним на примере последней кодовой таблицы. Пусть при помощи этой таблицы кодируется последовательность сообщений $$A_1A_3A_2A_3$$, в результате чего она преобразуется в следующий двоичный текст: 010110. Первый знак исходного сообщения декодируется однозначно - это $$A_1$$. Однако дальше начинается неопределенность: $$A_1A_2A_1A_4A_1, A_1A_3A_2A_3$$ или $$A_1A_3A_4A_1$$. Это лишь некоторые из возможных вариантов декодирования исходной последовательности знаков.
Необходимо отметить, что неоднозначность декодирования слова появилась несмотря на то, что условие однозначности декодирования знаков (инъективность кодового отображения) выполняется.
Существо проблемы - в невозможности однозначного выделения кодовых слов. Для ее решения следовало бы отделить одно кодовое слово от другого. Разумеется, это можно сделать, но лишь используя либо паузу между словами, либо специальный разделительный знак, для которого необходимо особое кодовое обозначение. И тот, и другой путь, во-первых, противоречат описанному выше способу кодирования слов путем конкатенации кодов $$с(а_i)$$ знаков $$a_i$$, образующих слово, и, во-вторых, приведет к значительному удлинению кодового текста, сводя на нет преимущества использования кодов переменной длины.
Решение данной проблемы заключается в том, чтобы иметь возможность в любом кодовом тексте выделять отдельные кодовые слова без использования специальных разделительных знаков. Иначе говоря, необходимо, чтобы код удовлетворял следующему требованию: всякая последовательность кодовых знаков может быть единственным образом разбита на кодовые слова. Коды, для которых последнее требование выполнено, называются однозначно декодируемыми (иногда их называют кодами без запятой).
Рассмотрим код (схему алфавитного кодирования) $$c:A \to В^*$$, заданный кодовой таблицей
$$a_1 \to \beta_1\\ A_2 \to \beta_2\\ \vdots\\ A_k \to \beta_k$$и различные слова, составленные из элементарных кодов.
Определение. Код $$с$$ называется однозначно декодируемым, если
$$\beta_{i_1}, \beta_{i_2}, \dots, \beta_{i_k}=\beta_{j_1}, \beta_{j_2}, \dots, \beta_{i_m} \Rightarrow k=m$$и
$$\forall_t=1,2, \dots, k\\ i_1=j_1$$то есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
Если таблица кодов содержит одинаковые кодовые слова, то есть если
$$\exists_{i,j}, I \ne j\\ \beta_i= \beta_j$$то код заведомо не является однозначно декодируемым (схема не является разделимой). Такие коды далее не рассматриваются.
Наиболее простыми и часто используемыми кодами без специального разделителя кодовых слов являются так называемые префиксные коды [29].
Определение. Код, обладающий тем свойством, что никакое кодовое слово не является началом (префиксом) другого кодового слова, называется префиксным.
Теорема 1.
Доказательство. Предположим противное. Тогда существует слово $$\beta$$ которое можно представить двумя разными способами $$\beta_i=\beta_{i1} \beta_{i2} \dots \beta_{ik}=\beta_{j1} \beta_{j2} \dots \beta_{jm}$$, причем до номера $$t$$ все подслова в обоих представлениях (разложениях) совпадают, а слова $$\beta_{i_t}$$ и $$\beta_{j_t}$$ различны. Отбросив одинаковые префиксы двух равных слов (представлений), получим совпадающие окончания $$\beta_{i_t} \beta_{i_{t+1}} \dots \beta_{i_k}=\beta_{j_t} \beta_{j_{t+1}} \dots \beta_{j_m}$$, начинающиеся с различных слов. Из-за равенства окончаний первые буквы слов $$\beta_{i_t}$$ и $$\beta_{j_t}$$ должны совпадать. По аналогичной причине должны совпадать и вторые буквы этих слов и т.д. Это означает, что неравенство слов $$\beta_{i_t}$$ и $$\beta_{j_t}$$ может заключаться только в том, что они имеют разную длину и, следовательно, одно из них является префиксом другого. Это противоречит префиксности кода.
Множество кодовых слов можно графически изобразить как поддерево словарного дерева (рис.6.5). Для этого из всего словарного дерева следует показать только вершины, соответствующие кодовым словам, и пути, ведущие от этих вершин к корню дерева. Такое поддерево называют деревом кода или кодовым деревом.
На рис.6.5 а) - дерево, соответствующие коду, у которого все слова имеют одинаковую длину. Кружками помечены те вершины, которые соответствуют кодовым словам. В данном случае это 4 двухбуквенных слова, составляющих второй уровень словарного дерева (
(рис 6.5) Деревья различных кодов
Замечание. Свойство префиксности является достаточным, но не является необходимым для однозначной декодируемости.
Пример. Код, состоящий из двоичных кодовых слов 1, 10, - не префиксный, но может быть однозначно декодирован. Появление символа 1 означает начало нового кодового слова. Последнее остается справедливым для кода, каждое слово которого есть единица с последующими нулями. Разумеется, подобные коды далеко не самые экономные.
Если код префиксный, то, читая кодовую запись подряд от начала, мы всегда сможем разобраться, где кончается одно кодовое слово и начинается следующее. Если, например, в кодовой записи встретилось кодовое обозначение 110, то разночтений быть не может, так как в силу префиксности наш код не содержит кодовых обозначений 1, 11 или, скажем, 1101. Именно так обстояло дело для рассмотренного выше кода, который очевидно является префиксным.
Для применения кода на практике желательно, чтобы кодовые слова были как можно короче. Однако чем слова короче, тем их запас меньше. В этом легко убедиться, посмотрев на изображение словарного
Теорема (необходимые условия). Пусть $$C=\{c_1, c_2, \dots, c_n\}$$ - префиксный двоичный код с длинами кодовых слов $$l_1, l_2, \dots, l_n$$. Тогда выполняется
Доказательство. Рассмотрим, сколько слов длины $$k$$ может быть в префиксном коде. Максимальное число таких слов равно $$2^k$$. В этом случае все $$2^k$$ кодовых слова имеют длину $$k$$.
Для каждого кодового слова длины $$k-i$$ имеется $$2^i$$ слов длины $$k$$, для которых данное слово является префиксом и по этой причине не является кодовым. Это следует из структуры словарного дерева (см. рис. 6.3). Множества $$T_{ci}$$ и $$T_{cj}$$ слов длины $$k$$, для которых кодовые слова $$c_i$$ и $$c_j$$ являются префиксами, не пересекаются, так как в противном случае более короткое из этих слов было бы префиксом более длинного. Значит, если в префиксном коде имеется $$n_{k-1}$$ слов длины $$k-1, n_{k-2}$$ слов длины $$k-2,\dots , n_1$$ слов длины 1, то число $$n_k$$ слов длины $$k$$ удовлетворяет неравенству
$$n_k \le 2^k-2^{k-1}n_1-2^{k-2}n_2- \dots - 2n_{k-1}$$Это неравенство верно для любого $$k$$, в том числе и для $$k$$, равного максимальной длине кодовых слов. После деления на $$2^k$$ обеих частей неравенства (6.4) его можно преобразовать к виду
$$\frac{n_k}{2^k}+\frac{n_{k-1}}{2^{k-1}}+\dots +\frac{n_2}{2^2}+\frac{n_1}{2} \le 1$$Слагаемое вида $$\frac{n_m}{2^m}$$, представляющее в неравенстве (6.5) $$п_т$$ кодовых слов длины $$т$$, можно записать в виде суммы
$$\frac{n_m}{2^m}=\overbrace{\frac{1}{2^m}+\frac{1}{2^m}+\dots+\frac{1}{2^m}}^{n_m}$$С учетом такого представления неравенство (6.5) можно переписать следующим образом:
$$\frac{1}{2^{l_1}}+\frac{1}{2^{l_2}}+\dots+\frac{1}{2^{l_N}} \le 1$$где $$N$$ - общее число слов
Выполнение
Можно также доказать, что если
Теорема (достаточные условия). Если положительные целые числа $$l_1, l_2, \dots, l_n$$ удовлетворяют
то существует
Доказательство. Если среди чисел $$l_1, l_2, \dots, l_N$$ имеется ровно $$n_i$$ чисел, равных $$i$$, то
где $$M$$ - максимальное из данных чисел. Из справедливости этого неравенства следует, что верны неравенства (6.5) для всех $$k \le M$$, а следовательно, и неравенство (6.4).
Для построения нужного
Из неравенства (6.4) при $$k=1$$ получаем $$n_1\le 2$$, т. е. требуемое число не превосходит общего числа вершин первого яруса. Значит, на этом ярусе можно выбрать какие-то $$n_1$$ вершин в качестве концевых ($$n_1$$ равно 0, 1 или 2). Если это сделано, то из общего числа вершин второго яруса (их $$2^2=4$$) для построения кода можно использовать лишь $$4-2n_1$$. Однако и этого числа вершин хватит, так как из неравенства (6.4) при $$k=2$$ вытекает
$$п_2 <4-2n_1$$Аналогично, при $$k=3$$ имеем неравенство:
$$n_3 \le 2^3-4n_1-2n_2$$Правая часть его вновь совпадает с допустимым для построения
Докажем, что если для длин $$l_1, l_2, \dots, l_n$$ кодовых слов выполняется равен - равенство $$\frac{1}{2^{l_1}}+\frac{1}{2^{l_2}}+\dots+\frac{1}{2^{l_n}}=1$$,то код является полным. Предположим противное, то есть, что код не полный. Тогда к нему можно добавить, по крайней мере, одно кодовое слово (длины $$l_{n+1}$$) и получить новый
Теоремы Крафта доказаны для случая, когда рассматриваются коды в алфавите $$\{0,1\}$$. Если кодовый алфавит содержит $$d$$ символов, то аналогичным образом можно доказать, что необходимым и достаточным условием для существования
Оказывается, этому неравенству обязаны удовлетворять и длины кодовых слов произвольного однозначно декодируемого кода. Поэтому, если существует однозначно декодируемый код с длинами слов $$l_1, l_2, \dots, l_N$$, то существует и
Один из методов алфавитного кодирования был предложен Фано. Схема кодирования по методу Фано заключается в следующем. Предположим, что кодируемые сообщения источника (знаки исходного алфавита) располагаются в последовательности $$A_1, A_2, \dots, A_N$$ так, что соответствующие им вероятности не возрастают, т. е. $$P(A_1) \ge P(A_2) \ge \dots \ge P(A_N) $$. Рассмотрим разбиения последовательности A 1, A2, …, AN на две подпоследовательности $$A_1, A_2 \dots , A_m$$ и $$A_{m+1}, A_{m+2}, \dots, A_N$$ Каждое такое разбиение определяется числом $$m, 1 \le m \le N-1$$, которое определяет, сколько элементов исходной последовательности входит в первую и вторую части разбиения. Среди $$N-1$$ разбиения выберем такое, чтобы модуль разности $$|\sum_{i=1}^{m}P(A_i)-\sum_{m+1}^{N}P(A_i)|$$ был минимальным. Всем сообщениям из первой части разбиения в качестве первого знака кодового слова приписываем 0, а сообщениям из второй части 1. По тому же принципу каждая из полученных подпоследовательностей снова разбивается на две части, и это раз-биение определяет значение второго символа кодового слова. Процедура продолжается до тех пор, пока все множество не будет разбито на отдельные сообщения. В результате каждому из сообщений будет сопоставлено кодовое слово из нулей и единиц.
Описанную процедуру построения кода Фано на примере из пяти сообщений иллюстрирует следующая таблица.
| Сообщения | Вероятности сообщений | Знаки кодовых слов | Кодовое слово | ||
|---|---|---|---|---|---|
| 1-й знак | 2-й знак | 3-й знак | |||
| $$A_i$$ | 0.4 | 0 | 0 | 00 | |
| $$A_2$$ | 0.15 | 1 | 01 | ||
| $$A_3$$ | 0.15 | 1 | 0 | 10 | |
| $$A_4$$ | 0.15 | 1 | 0 | 110 | |
| $$A_5$$ | 0.15 | 1 | 111 | ||
Понятно, что чем более вероятно сообщение, тем быстрее оно образует "самостоятельную" группу и тем более коротким словом оно будет закодировано. Это обстоятельство и обеспечивает высокую экономность кода Фано. Код, построенный для данного источника методом Фано, имеет среднюю длину кодового слова равную 2,3.
Код, построенный методом Фано, всегда является префиксным. Действительно, на первом шаге построения кода методом Фано множество сообщений источника разбивается на два подмножества. Все кодовые слова, соответствующие первому подмножеству, имеют однобуквенный префикс, состоящий из 0, а все слова, соответствующие второму подмножеству, имеют однобуквенный префикс, состоящий из 1 (или наоборот). Поэтому ни одно слово, соответствующее какому-нибудь из сообщений из первого подмножества, не может быть префиксом ни для какого слова, соответствующего сообщению из второго подмножества. Аналогичная процедура разбиения применяется к каждому подмножеству сообщений с одинаковыми префиксами при добавлении нового знака к формируемым кодовым словам. При этом число подмножеств, на которые разбивается исходное множество сообщений источника (блоков разбиения), увеличивается. Важным свойством разбиений является то, что для кодовых слов, соответствующих сообщениям из разных блоков разбиения, имеются различные префиксы. Построение кода завершается
Описанный метод кодирования можно применять и в случае произвольного алфавита из $$d$$ символов, с той лишь разницей, что на каждом шаге следует производить разбиение на $$d$$ равновероятных групп.
Рассмотренные ранее примеры показывают, что использование кодов переменной длины позволяет эффективнее кодировать сообщения по сравнению с равномерным кодированием. Для получения оценки минимально достижимой средней длины кодового слова рассмотрим избыточность кодирования $$R(c,S)$$, представляющую собой разность $$R(c,S) = L(c,S)-H(S)$$ между средней длиной кодового слова при кодировании источника S кодом c и
Для доказательства первой теоремы напомним одно свойство логарифма, которое заключается в том, что
Теорема. Для произвольного источника $$S$$ и
(рис 6.6) График функции log2(x) и касательной к ней в точке x=1
Доказательство.
$$-R(c,S)=H(S)-L(c,S)=\sum_{i=1}^{k}P(A_i)log \left (\frac{1}{P(A_i)2^{|c(A_i)|}}\right )$$С учетом отмеченного выше неравенства для функции $$log_2$$ каждое слагаемое можно оценить сверху следующим образом:
$$P(A_i)log \left (\frac{1}{P(A_i)*2^{|c(A_i)|}} \right ) \le \frac{P(A_i)}{ln2} \left (\frac{1}{P(A_i)*2^{|c(A_i)|}-1}\right ) \le \frac{1}{ln2} \left (\frac{1}{2^{|c(A_i)|}}-P(A_i) \right )$$После суммирования получим
$$-R(c,S) \le \frac{1}{ln2} \left (\sum_{i=1}^{k}\frac{1}{2^{|c(A_i)|}}-\sum_{i=1}^{k}P(A_i) \right ) \le 0$$причем последнее неравенство следует из
Из доказанной теоремы следует, что энтропия источника является нижней границей средней длины кодирования. Для источников, у которых вероятности являются целыми отрицательными степенями 2, эта граница достижима. Легко проверить, что для источника с распределением вероятностей $$p_1 = 0,5 = 2^{-1}, p_2 = 0,25 = 2^{-2}, p_3 = p_4 = 0,125=2^{-3}$$ средняя длина кодирования равна 1,75 и совпадает с
Для доказательства второй теоремы потребуется функция $$[x]$$, которая называется "потолок" и определяется выражением $$[x]=min\{n|n \ge x, n - целое\}$$. Необходимые для доказательства свойства этой функции легко следуют из ее графика, показанного на рис.6.7, и заключаются в выполнении неравенств $$0 \le [x]-x<1$$.
(рис 6.7) График функции [x]
Теорема. Для каждого источника $$S$$ найдется
Пусть $$l_i=\left [log\frac{1}{P(A_i)} \right ]$$, где $$[х]$$ функция "потолок". Тогда
$$\sum_{i=1}^{k}2^{-i_i} \le \sum{i=1}{k}2^{-log\frac{1}{P(A_i)}}=\sum_{i=1}^{k}P(A_i)=1$$Это означает, что числа $$l_i$$ удовлетворяют
Теорема доказана.
Данная теорема гарантирует, что для любого источника найдется
Для практических целей представляет интерес нахождение для каждого источника
Определение. Префиксное кодирование $$c_0$$ называется оптимальным для источника $$S$$, если для каждого префиксного кодирования c источника $$S$$ справедливо неравенство $$R(c_0,S) \le R(c,S)$$.
Для каждого источника существует оптимальный код, поскольку множество префиксных кодов источника с избыточностью, меньшей либо равной 1, не пусто и конечно. Один источник может иметь несколько оптимальных кодов с разными наборами длин кодовых слов.
Пусть буквы алфавита $$\{a_1, a_2, \dots, a_n\}$$ источника $$S$$ имеют вероятности появления $$p_1 p_2 \dots p_n$$ , длины кодовых слов $$c(a_1), c(a_2), \dots, c(a_n)$$ при использовании кода $$c$$ равны $$l_1, l_2, \dots, l_n$$. Рассмотрим некоторые свойства оптимального кодирования, для того чтобы, опираясь на эти свойства, сформулировать процедуру нахождения оптимального кода.
Свойство 1. Для оптимального кода из $$p_i > p_j$$ следует, что $$l_i \le l_j$$.
Для доказательства предположим противное, т. е. что для оптимального кода существуют $$p_i$$ и $$p_j$$, такие что $$p_i > p_j$$ и $$l_i > l_j$$. Построим новый код, поменяв местами кодовые слова рассматриваемого оптимального кода для $$i$$-ой и $$j$$-ой букв алфавита. Разность между средней длиной $$L_0$$ кодирования оптимальным кодом и средний длиной $$L$$ построенного кода имеет вид
$$L_0-L=p_il_i+p_jl_j-p_il_i-p_jl_j=(p_i-p_j)(l_i-l_j) >0$$что противоречит оптимальности рассматриваемого кода.
Свойство 2. Существует оптимальный код источника $$S$$, для которого
$$l_1\lel_2\le \dots \le l_{n-l}=l_n$$причем два последних слова имеют максимальную длину и отличаются только в последнем знаке.
Предположим, что в оптимальном коде не существует двух слов максимальной длины. Это значит, существует только одно слово максимальной длины. Если это самое длинное слово сократить на один последний знак, а другие кодовые слова оставить неизменными, то получится новый код, который, во-первых, будет префиксным (нет второго слова, которое отличается в последнем знаке), и, во-вторых, средняя длина кодирования будет меньше. Это противоречит предположению о существовании в оптимальном коде только одного слова максимальной длины. Таким образом, в оптимальном коде существует, по крайней мере, два кодовых слова максимальной длины.
Докажем, что какие-то два слова максимальной длины отличаются только в последнем знаке. Опять предположим противное, то есть любые два слова максимальной длины отличаются не только в последнем знаке. В этой ситуации можно повторить описанную выше процедуру укорачивания одного из слов максимальной длины и получить в результате новый
Опираясь на рассмотренные свойства, можно построить оптимальный для заданного источника $$S$$ код с использованием двух процедур: сжатия источника и расщепления кода. Смысл первой процедуры заключается в том, что исходный источник последовательно заменяется на более простой (содержащий на 1 меньше знаков) источник. Применение процедуры сжатия заканчивается, когда будет получен простейший источник с двумя знаками, оптимальное кодирование которого очевидно. Процедура расщепления кода предназначена для построения из оптимального кода более простого источника оптимального кода того источника, из которого процедурой сжатия был получен простой источник.
Процедура сжатия источника заключается в переходе от источника $$S$$ с алфавитом из n знаков $$а_1, а_2, \dots, а_п$$ упорядоченных в порядке невозрастания соответствующих им вероятностей $$р(а_1)\ge р(а_2)\ge \dots \ge р(а_n)$$, к источнику $$S'$$ с алфавитом из $$n-1$$ знака $$а'_1, а'_2, \dots,а'_{n-1}$$ и вероятностями $$p(a'_i)=p(a_i)$$ при $$i < n-1$$ и $$p(a'_{n-l} =p(a_{k-l})+p(a_k)$$.
Операцию сжатия источника $$S$$ будем обозначать через $$S'$$ Фактически, при сжатии первые $$n-2$$ знака остаются неизменными, а два последних, наименее вероятных знака заменяются на некоторый новый знак с вероятностью, равной сумме вероятностей двух заменяемых знаков.
$$\overbrace{ \begin{matrix} a_1 a_2 \ldots a_{n-1} a_n\\ p_1 \ge p_2 \ge \ldots \ge p_{n-1} \ge p_n \end{matrix}}^{\mbox{Источник S из n букв}} \xrightarrow{Сжатие} \overbrace{ \begin{matrix} a_1 a_2 \ldots a_{n-2} \hat a\\ p_1 \ge p_2 \ge \ldots \ge p_{n-2} \ge p_{n-1}+p_n \end{matrix}}^{\mbox{Источник S' из n-1 букв}} \xrightarrow{\mbox{Сортировка по p}}$$Применяя сжатие к источнику $$S$$, получим новый источник $$S^{(1)}=S'$$, применяя затем процедуру сжатия к $$S^{(1)}$$ получим $$S^{(2)}=(S^{(1)})'$$. Действуя подобным образом $$n-2$$ раза, построим последовательность источников $$S$$, $$S^{(1)}, \dots, S^{(n-2)}$$.
Алфавит источника $$S^{(n-2)}$$ состоит только из двух знаков, поэтому найти оптимальный код для этого источника не составляет труда. Одно из слов кодируется знаком 0, а другое - знаком 1. Это особенно важно потому, что, используя оптимальный код для источника $$S^{(n-2)}$$ и последовательность кодов $$S, S^{(1)}, \dots, S^{(n-2)}$$, можно найти оптимальный код для исходного источника $$S$$.
Для построения оптимального кода источника $$S^{(i)}$$, содержащего на один знак больше, чем источник $$S^{(i+1)}$$, необходимо выполнить процедуру расщепления кода.
Пусть имеем источник
$$S^{(i+1)}=\begin{cases} a_1^{i+1}, a_2^{i+1}, \dots, \hat a_j^{i+1}, \dots a_{n-i-1}^{i+1}\\ p(a_1^{i+1}), p(a_2^{i+1}),\dots, p(\hat a_j^{i+1}), \dots p(a_{n-i-1}^{i+1})\\ c_0(a_1^{i+1}), c_0(a_2^{i+1}), \dots, c_0(\hat a_j^{i+1}),\dots c_0(a_{n-i-1}^{i+1}) \end{cases} $$И оптимальный код $$p(\hat a_j^{i+1})=p(a_{n-i-1}^i)+p(a_{n-i}^i)$$
Через $$\hat a_j$$ обозначен тот знак алфавита источника $$S^{(i+1)} $$, который заменил два знака с минимальными вероятностями источника $$S^{(i) $$ при его сжатии.
Процедура расщепления заключается в использовании оптимального кода $$c_o^{(i+1)}$$ источника $$S^{(i+1)}$$ для построения оптимального кода для источника $$S^{(i)}$$. Она заключается в следующем: знакам алфавита источника $$S^{(i)}$$, перешедшим в $$S^{(i+1)}$$ без изменения, назначаются кодовые слова совпадающих с ними знаков источника $$S^{(i+1)}$$; двум наименее вероятным знакам алфавита источника $$S^{(i+1)}$$, замененным в процессе сжатия на знак $$\hat a_j$$, сопоставляют кодовые слова $$с_0^{i+1}(\hat a_j^{i+1})0$$ и $$c_0^{i+1}(\hat a_j^{i+1})l$$.
Слово $$c_o^{i+1}(\hat a_0^{i+1})$$ в оптимальном коде источника $$S^{(i+1)}$$, содержащем $$n-i-1$$ знаков, "расщепляется", путем добавления (конкатенации) знаков 0 и 1, на 2 слова в кодовом множестве для источника $$S^{(i)}$$, содержащем $$n-i$$ знаков.
Средняя длина $$l'$$ кода источника $$S^{(i+1)}$$ и средняя длина $$l$$ кода, полученного из него расщеплением, связаны соотношением $$l=l'+p$$. Действительно,
$$l=l_1p(a_1^{i+1})+\dots+(l_j+1)p(a_{n-i-1}^i)+(l_j+1)p(a_{n-i}^i)+\dots l_{n-i-1}p(a_{n-i-1}^{i+1})=\\ =l_1p(a_1^{i+1})+\dots +l_j(p(a_{j-i-1}^i)+p(a_{n-i}^i))+(p(a_{n-i-1}^i)+p(a_{n-i}^i))+\dots l_{n-i-1}p(a_{n-i-1}^{i+1})=\ =l_1p(a_1^{i+1})+\dots +l_j(p(a_j^i)+\dots l_{n-i-1}p(a_{n-i-1}^{i+1})+(p(a_{n-i-1}^i)+p(a_{n-i}^i))=l'+p$$Докажем, что получающийся в результате расщепления код является оптимальным для источника $$S^{(i)} $$.
Предположим противное, т. е. что существует другой оптимальный код $$c''$$ для того же источника $$S^{(i)}$$ со средней длиной кодирования $$l''$$, меньшей, чем $$l$$, т. е. $$l''<l$$. В соответствии со свойством 2 оптимальный код содержит два слова максимальной длины, отличающиеся в последнем знаке и соответствующие двум наименьшим вероятностям источника $$S^{(i)}$$. Обозначим эти два слова через $$c''(a_{n-i})$$ и $$c''(a_{n-i-1})$$. Из этого кода для источника $$S^{(i)} $$ можно построить код $$c'''$$ для источника $$S^{(i+1)} $$, в котором последнее кодовое слово получается отбрасыванием последнего знаки из слов $$c''(a_{n-i})$$ и $$c''(a_{n-i-1})$$. Средняя длина $$l'''$$ кода $$c'''$$ связана со средней длиной $$l''$$ кода $$c''$$ соотношением $$l''=l'''+p$$. Из этого соотношения, из соотношения $$l=l'+p$$ и из предположения, что $$l''<l$$, следует, что $$l'''<l'$$. Это противоречит оптимальности кода для источника $$S^{(i+1)} $$.
Таким образом, используя процедуру расщепления, строится оптимальный код для источника, который ранее был преобразован процедурой сжатия в более простой источник. Повторяя эту процедуру необходимое количество раз, можно будет найти оптимальный код для исходного источника $$S$$.
Описанный метод оптимального кодирования был предложен в 1952 г. Д. Хафменом и называется его именем. В общем случае, когда для кодирования используется алфавит из более чем двух букв, метод Хафмена рассмотрен в [32].
Рассмотрим процесс построения оптимального кода на примере источника из пяти сообщений с вероятностями $$p_1 = 0,4, p_2 = 0,15, p_3 = 0,15, p_4 = 0,15, p_5 = 0,15$$. Построение кода показано на следующем рисунке.
Стрелками показаны шаги сжатия источника. В левой части каждого столбца показано распределение вероятностей источника. В правой части каждого столбца, соответствующего одному из источников, показаны кодовые слова. Построение кода начинается с простейшего источника $$S(3) $$, который кодируется двумя однобуквенными словами 0 и 1.
В данном случае средняя длина кодирования для оптимального кода, построенного методом Хафмена, составляет 2,2. Это меньше, чем средняя длина кода, построенного ранее методом Фано для того же источника.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.