Рассмотрим ансамбль из сообщений им с соответствующими вероятностями Каждое сообщение должно быть представлено посредством кодового слова, состоящего из последовательных символов, принадлежащих заданному алфавиту. Обозначим через число различных символов в алфавите, через число символов в кодовом слове, соответствующем сообщению Среднее число символов на одно сообщение равно по определению

Нашей первой задачей является нахождение нижней границы для

В разд. 2.8 мы видели, что энтропия ансамбля сообщений представляет собой среднее количество информации, необходимое для однозначного определения сообщения из этого ансамбля. В том же разделе мы видели, что символы несут в среднем максимальное количество информации, когда они равновероятны. Эта максимальная величина, а именно есть пропускная способность кодового алфавита. Кроме того, равенства (2.100) и (2.105) показывают, что статистическая зависимость некоторого символа от предыдущих не может увеличить среднее количество информации на этот символ. На этом основании мы можем заключить, что

Откуда получаем

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

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

символов в каждой позиции кодового слова должны не зависеть от всех предыдущих символов. Если в точности следовать этим правилам, то средняя длина образуемых кодовых слов будет равна минимальной величине, определяемой формулой (3.3). Мы увидим, однако, что только в специальных случаях символы могут использоваться с равными вероятностями и быть сделаны независимыми от всех предыдущих символов. Эти правила конструирования множеств кодовых слов лучше всего пояснить на следующих частных примерах. Используемая процедура кодирования подобна процедуре, впервые предложенной Шенноном .

Сообщения алфавита источника выписывают в порядке убывания вероятностей их появления. Далее разделяют их на две части так, чтобы суммарные вероятности сообщений в каждой из этих частей были по возможности почти одинаковыми. Сообщениям первой части приписывается в качестве первого символа 0, а сообщениям второй части – 1 (можно и наоборот). Затем каждая из этих частей (если она содержит более одного сообщения) делится на две по возможности равновероятные части и в качестве второго символа для первой из них берется 0 , а для второй – 1. Этот процесс повторяется, пока в каждой из полученных частей не останется по одному сообщению. Для примера, приведенного в табл. 1 на первом этапе разделения первой части окажется одно сообщение а 1 с вероятностью P (а 1)=0,4, во второй части - остальные сообщения с суммарной вероятностью P Σ (а 2 -а 6)=0.6. Припишем сообщению а 1 символ 0, а остальным сообщениям в качестве первого символа – 1.

Таблица 1. Произвольное кодирование сообщений

На втором этапе разделим сообщения (а 2 ,а 3 ,а 4 ,а 5 ,а 6) на две равновероятные части, включив в первую часть сообщения а 2, а во вторую часть – сообщения (а 3 ,а 4 ,а 5 ,а 6). Припишем сообщению а 2 в качестве второго символа 0, а остальным сообщениям – 1 и т.д. В результате приходим к коду К 2, приведенному в табл. 2.

Таблица 2. Кодирование сообщений кодом Шеннона-Фано

Код по своему построению удовлетворяет свойству префикса. Поэтому вышеприведенная после последовательность двоичных символов “L ” декодируется однозначно: (а 1 ,а 1 ,а 4 ,а 1 ,а 1 ,а 1 ,а 6 ,а 1). Среднее число символов на одно сообщение с учетом их вероятностей =0,4*1+0,3*2+0,3*4=2,2 , т.е. незначительно превышает энтропию источника сообщений.

2.4. Средняя длина кодового слова

Процедура Шеннона-Фано не обязательно минимизирует , так как достижение большого значения средней собственной информации на одной кодовой букве может привести к обедненному выбору для последующих кодовых букв. Если это разбиение может быть вычислено так, что группы будут в точности равновероятны на каждом этапе разбиения, то вероятности букв источника и длины кодовых слов будут связаны равенством

(2)

Ограничения на длины кодовых слов префиксного кода задаются неравенством Крафта и теоремой кодирования для источника.

Теорема 1. (Неравенство Крафта). Если целые числа (
) удовлетворяют неравенству

(3)

то существует код, обладающий свойством префикса с алфавитом объемом Д, длины кодовых слов в котором равны этим числам. Обратно, длины кодовых слов любого кода, облагающего свойством префикса, удовлетворяет неравенству (3). Теорема не утверждает, что любой код с длинами кодовых слов, удовлетворяющими (3), является префиксным. Так, например, множество двоичных кодовых слов (0; 00; 11) удовлетворяет (3), но не обладает свойством префикса. Теорема утверждает, что существует некоторый префиксный код с такими длинами, например код (0; 10; 11) . Не любой однозначно декодирующий код обладает свойством префикса, например, код К3 табл. 3. В нем каждое кодовое слово является префиксом каждого более длинного кодового слова. Вместе с тем однозначность декодирования является тривиальной, так как символ 0 всегда определяет начало нового кодового слова. Коды, обладающие свойством префикса, отличаются, однако, от других однозначно декодируемых кодов тем, что конец кодового слова всегда может быть опознан, так что декодирование может быть выполнено без задержки наблюдаёмой последовательности кодовых слов (код. К4 табл.3). По этой причине префиксные коды иногда называют мгновенными кодами.

Таблица 3. Однозначно декодируемые коды

Так как длины кодовых слов любого однозначно декодируемого кода удовлетворяют (3) и можно построить префиксный код для любого множества длин, удовлетворяющих (3), то любой однозначно декодируемый код можно заменить на префиксный код без изменения длин кодовых слов. Таким образом, нижеследующая теорема 2 для кодирования источника относительно средней длины кодового слова предложена как к однозначно декодируемым кодам, так и к подклассу префиксных кодов.

Информация - это совокупность сведений, подлежащих хранению, передаче, обработке и использованию в человеческой деятельности.

Изменение характеристики носителя, которое используется для представления информации, называется сигналом , а значение этой характеристики, отнесенное к некоторой шкале измерений, называется параметром сигнала .

Различают два типа сигналов (а значит и два типа сообщений ): непрерывные и дискретные.

Для обеспечения простоты и надежности распознавания сигналов дискретного вида (знаков ), их число целесообразно свести до минимума. Как правило, прибегают к операции представления исходных знаков в другом алфавите с меньшим числом знаков, называемых символами . При обозначении этой операции используется тот же термин – «кодирование ».

Собственная информация

Количество информации, которое несет в себе буква x i алфавита, назовемсобственной информацией , содержащаяся вx i и обозначим
.

.

Формула Шеннона

Усредним собственную информацию, т.е. рассчитаем, какое среднее количество информации несет в себе один символ алфавита
:
.

Среднее количество информации , приходящееся на одну букву , называется энтропией алфавита (или источника) и обозначается H :

- формула Шеннона .

Очевидно, что среднее 1 количество информации в сообщении длины n вычисляется по формуле:

.

Замечание. Количество информации приписывается самому сообщению.

Замечание. Энтропия является характеристикой источника сообщений (алфавита ).

Формула Хартли

При равновероятности знаков алфавита
, из формулы Шеннона получаем: .

- формула Хартли .

Единицы измерения информации

Единицу количества информации на один элемент сообщения (единицу измерения энтропии) называют битом .

Рассмотрим алфавит равновероятных символов, энтропия которого равна 1:
. Так как отсюда следует
, то ясно, что 1 бит - это количество информации, которое содержится в двоичном сообщении (алфавит {0,1}) длины 1.

В дальнейшем в выражениях для I и H всегда будем использовать логарифмы с основанием 2.

Свойства энтропии

1. Энтропия Н - величина

- неотрицательная (Н  0),

- ограниченная , Эти свойства следуют из того, что такими же качествами обладают все ее слагаемые
.

2. Энтропия равна нулю, если вероятность одного из символов равна 1 . В этом случае говорят о полностью детерминированном источнике и об отсутствии неопределенности в нем, так как наблюдатель знает о сообщении источника до момента его наблюдения.

3. Можно также показать, что энтропия максимальна, если все знаки алфавита равновероятны , т.е. Н max = log m . Таким образом, для поиска максимально возможного значения энтропии (для фиксированного числа символов) используется формула Хартли.

4. Особый интерес представляют бинарные сообщения , использующие бинарный алфавит {0,1}. Так как при m = 2 вероятности знаков алфавита p 1  1 и p 2  1, то можно положить p 1 = p и p 2 = 1-p . Тогда энтропия определяется соотношением

В приведенных выше примерах кодирования все кодовые слова имели одинаковую длину. Однако это не является обязательным требованием. Более того, если вероятности появления сообщений заметно отличаются друг от друга, то сообщения с большой вероятностью появления лучше кодировать короткими словами, а более длинными словами кодировать редкие сообщений. В результате кодовый текст при определенных условиях станет в среднем короче.

Показателем экономичности или эффективности неравномерного кода является не длина отдельных кодовых слов, а "средняя" их длина, определяемая равенством:

где - кодовое слово, которым закодировано сообщение, а- его длина,- вероятность сообщения,- общее число сообщений источника. Для краткости записи формул далее могут использоваться обозначенияи. Заметим, что обозначение средней длины кодирования черезподчеркивает тот факт, что эта величина зависит как отисточника сообщений , так и от способа кодирования.

Наиболее экономным является код с наименьшей средней длиной . Сравним на примерах экономичность различных способов кодирования одного и того же источника.

Пусть источник содержит 4 сообщения с вероятностями. Эти сообщения можно закодировать кодовыми словами постоянной длины, состоящими из двух знаков, в алфавитев соответствии с кодовой таблицей.

Очевидно, что для представления (передачи) любой последовательности в среднем потребуется 2 знака на одно сообщение. Сравним эффективность такого кодирования с описанным выше кодированием словами переменной длины. Кодовая таблица для данного случая может иметь следующий вид.

В этой таблице, в отличие от предыдущей, наиболее частые сообщения икодируются одним двоичным знаком. Для последнего варианта кодирования имеем

в то время как для равномерного кода средняя длина (она совпадает с общей длиной кодовых слов). Из рассмотренного примера видно, что кодирование сообщений словами различной длины может дать суще-ственное (почти в два раза) увеличение экономичности кодирования.

При использовании неравномерных кодов появляется проблема, которую поясним на примере последней кодовой таблицы. Пусть при помощи этой таблицы кодируется последовательность сообщений , в результате чего она преобразуется в следующий двоичный текст: 010110. Первый знак исходного сообщения декодируется однозначно - это. Однако дальше начинается неопределенность:или. Это лишь некоторые из возможных вариантов декодирования исходной последовательности знаков.

Необходимо отметить, что неоднозначность декодирования слова появилась несмотря на то, что условие однозначности декодирования знаков (инъективность кодового отображения) выполняется.

Существо проблемы - в невозможности однозначного выделения кодовых слов. Для ее решения следовало бы отделить одно кодовое слово от другого. Разумеется, это можно сделать, но лишь используя либо паузу между словами, либо специальный разделительный знак, для которого необходимо особое кодовое обозначение. И тот, и другой путь, во-первых, противоречат описанному выше способу кодирования слов путем конкатенации кодов знаков, образующих слово, и, во-вторых, приведет к значительному удлинению кодового текста, сводя на нет преимущества использования кодов переменной длины.

Решение данной проблемы заключается в том, чтобы иметь возможность в любом кодовом тексте выделять отдельные кодовые слова без использования специальных разделительных знаков. Иначе говоря, необходимо, чтобы код удовлетворял следующему требованию: всякая последовательность кодовых знаков может быть единственным образом разбита на кодовые слова. Коды, для которых последнее требование выполнено, называются однозначно декодируемыми (иногда их называют кодами без запятой).

Рассмотрим код (схему алфавитного кодирования) , заданный кодовой таблицей

и различные слова, составленные из элементарных кодов.

Определение . Код называется однозначно декодируемым, если

то есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.

Если таблица кодов содержит одинаковые кодовые слова, то есть если

то код заведомо не является однозначно декодируемым (схема не является разделимой). Такие коды далее не рассматриваются.

Идея экономии числа символов при неравномерном кодировании состоит в закреплении более коротких слов за более вероятными (чаще повторяющимися) сообщениями и, наоборот, более длинных – за менее вероятными (частыми). Тем самым достигается малое среднее число символов на сообщение. Необходимо, однако, одновременно позаботиться об однозначности декодирования . Последняя обеспечивается, в частности, для префиксных кодов, в которых ни одно слово не является начальным фрагментом (префиксом ) другого.

Пример 1.3.1 Код представленный ниже (M =4) не является однозначно декодируемым:

Действительно, если на выходе кодера появится комбинация 00111111, она может быть прочитана как x 1 , x 2 , x 3 , x 4 , или x 1 , x 2 , x 4 , x 3 , или x 1 , x 1 , x 4 , x 4 , или x 1 , x 1 , x 3 , x 3 , x 3 .

Пример 1.3.2 В отличие от предыдущего, код, представленный ниже (M =4) является префиксным, и, следовательно, однозначно декодируемым:

Так, если последовательность на выходе кодера имеет вид 0011010111110, ее можно декодировать единственным образом: x 1 , x 1 , x 3 , x 2 , x 4 , x 3 .

Любой префиксный код является мгновенно декодируемым. Это означает, что любое его слово можно распознать сразу по появлении последнего из его символов.

Теорема 1.3.1 (Неравенство Крафта). Код, содержащий M кодовых слов, может быть префиксным тогда и только тогда, когда длины его кодовых слов n 1 , n 2 , …, n M подчиняются неравенству

Средняя длина неравномерного кода определяется равенством

Теорема 1.3.2 Средняя длина лучших префиксных кодов лежит в границах

Код Шеннона-Фано

На первом шаге рассматриваемого алгоритма ансамбль источника разбивается на два подмножества, совокупные вероятности которых максимально близки друг к другу, т.е. к 1/2. Всем сообщениям первого из подмножеств присваивается первый символ кодового слова 0, а второго –первый символ 1. На втором шаге каждое из подмножеств вновь разбивается на два с максимально близкими совокупными вероятностями и кодовые слова первого из полученных подмножеств получают в качестве второго символа 0, а второго – 1 и т. д. Как только сообщение оказывается единственным в подмножестве, его кодирование заверено. Процедура повторяется до исчерпания всех сообщений ансамбля.

Нетрудно показать, что средняя длина кода Шеннона-Фано удовлетворяет правому неравенству Теоремы 1.3.2:

Пример 1.3.3 Закодируем дискретный источник M= 8 сообщений, имеющих вероятности, перечисленные в таблице.

В данном случае logM =3, энтропия источника H (X )»2.44 бит, асредняя длина кодового слова:

Код Хаффмена

Этот код оптимален в том смысле, что ни один префиксный код не может обладать меньшей средней длиной слова. На первом шаге кодирования по Хаффмену два наименее вероятных сообщения объединяются в одно суммарное, вероятность которого равна сумме вероятностей исходных. При этом одному из исходных сообщений присваивается кодовый символ 0, а другому – 1. На втором шаге повторяется то же самое с новым ансамблем из M -1 сообщений и вновь два наименее вероятных сообщения объединяются в одно с присвоением символа 0 одному из них и 1 – другому. Процедура повторяется M -1 раз, т. е. вплоть до шага, когда одному из двух оставшихся сообщений присваивается символ 0, а другому - 1. В результате получается кодовое дерево , чтением которого справа налево формируются кодовые слова для всех сообщений кодируемого ансамбля.

Удобнее, приступая к процедуре кодирования, записать все сообщения в порядке убывания их вероятностей. Следует также отметить, что, в противоположность алгоритму Шеннона-Фано, в ходе кодирования по Хаффмену любое кодовое слово появляется в обратном порядке.

Пример, приведенный ниже иллюстрирует процесс кодирования и демонстрирует сравнительное преимущество кода Хаффмена.

Пример 1.3.4 Закодируем по Хаффмену ансамбль из Примера 1.3.3:

Средняя длина: