Информация и алфавит

со временем, называют шенноновскими, а порождающий его отправитель – шенноновским

источником.

Если сообщение является шенноновским, то набор знаков и связанная с каждым знаком информация известны заранее.

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

одним из разделов теоретической информатики. К основным задачам, решаемым в

данном разделе, необходимо отнести следующие:

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

обеспечивает возврат к исходной информации без каких-либо ее потерь.
Наиболее

удобным способом задания кода является табличный способ. Например: пусть имеется алфавит с конечным числом букв: А={a1, a2, a3, a4}. Тогда код для А:

Определения:

модели возможно благодаря тому, что кодовые комбинации n-значного кода могут

рассматриваться как определенные точки n-мерного пространства

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

кода в виде кодового дерева — давно известный и широко

распространенный в теории релейно контактных схем способ.
В общем виде кодовое дерево может быть представлено как граф, состоящий из узлов и ветвей, соединяющих узлы, расположенные на разных уровнях. Истоком графа является корень. Каждый уровень содержит mn узлов, где n — номер уровня, а m — значность кода. Для равномерного двоичного кода число узлов на каждом уровне равно 2n.

Кодовые деревья

корень

1

0

1

0

1

1

1

1

1

1

0

0

0

0

0

0

11

10

01

00

111

110

101

100

011

010

001

000

Кодовое дерево двоичного кода

или префиксные коды, т. е. коды, которые могут быть получены

путем последовательного вычеркивания последнего знака кодовой комбинации (ни одна из комбинаций такого кода не может быть префиксом комбинации того же кода). Например, префиксами кодовой комбинации 11101101 будут: 1, 11, 111,1110, 111011, 1110110, 11101101.

То есть для однозначного декодирования кодовой комбинации 11101101 ни один из передаваемых кодов не может быть представлен комбинациями 1, 11, 111, 1110, 111011, 1110110, 11101101.

Если число узлов на каждом уровне кодового дерева равно mn, то дерево называют полным.
Величина D = mk, где k указывает порядок наивысшего уровня кодового дерева, называется объемом дерева.

Объем дерева характеризует число кодовых комбинаций, которое может быть построено при помощи данного дерева.

ее начальной части, включая саму комбинацию Аi

Та часть кодовой комбинации,

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

Имея кодовое дерево, легко определить, обладает ли данный код свойством префикса. Если ни один узел кодового дерева не является вершиной данного кода, то он обладает свойством префикса. Для заданного кода кодовое дерево всегда одно и то же.

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

Если добавление к комбинациям заданного кода некоторой новой комбинации ведет к нарушению свойства префикса, то такой код называется полным.

Свойство префикса широко используют при построении неравномерных кодов с минимальной длиной кодовых слов, в частности кодовых деревьев по методу Хаффмена

со средней информацией на знак, определенной с учетом вероятностей их

появления, I(A). Вторичный алфавит B – M знаков со средней информационной емкостью I(B). Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение – m знаков. Если исходное сообщение содержит Ist(A) информации, а закодированное – Ifin(B), то условие обратимости кодирования, т.е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом:
Ist(A) ≤Ifin(B)

(1)

(2)

теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При

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

Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения.

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

(3)

(4)

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

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

При этом приемное устройство фиксирует интенсивность и длительность сигналов.

Применение формулы (4) для двоичных сообщений источника без памяти при кодировании знаками равной вероятности даёт:

(5)

Определение количества переданной информации при двоичном кодировании сводится к простому подсчету числа импульсов (единиц) и пауз (нулей).

иметь одинаковые или разные длительности.
Их количество в коде (длина

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

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

чтобы суммарная длительность кодов при передаче (или суммарное число кодов

при хранении) данного сообщения была бы наименьшей

00100010000111010101110000110

Использовать специальную комбинацию элементарных сигналов, которая интерпретируется декодером как разделитель знаков
Применение префиксных кодов

конца слова
код признака конца знака может быть включен в код

буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);
коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);
код буквы (кроме пробела) всегда должен начинаться с 1;
разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация …000 или …0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

составляет:
Q(r) = 4,356/4,964 - 1 0,122
Это означает, что при

данном способе кодирования будет передаваться приблизительно на 12% больше информации, чем содержит исходное сообщение. Аналогичные вычисления для английского языка дают значение K(e, 2) = 4,716, что при I1(e) = 4,036 бит приводят к избыточности кода Q(e,2)= 0,168.

алфавита т: в кодовые слова во вторичном алфавите m1, при

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

Основные свойства оптимальных кодов:
минимальная средняя длина кодового слова оптимального кода обеспечивается в том случае, когда избыточность каждого кодового слова сведена к минимуму (в идеальном случае — к нулю);
кодовые слова оптимального кода должны строиться из равновероятных и взаимонезависимых символов.

не совпадает с началом (префиксом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.

Префиксные коды

Условие Фано:

левый символ, присоединить к рабочему кодовому слову.
Сравнить рабочее кодовое

слово с кодовой таблицей; если совпадения нет, перейти к (1).
Декодировать рабочее кодовое слово, очистить его.
Проверить, имеются ли еще знаки в сообщении; если "да", перейти к (1).

Применение данного алгоритма даёт:

сводится к следующей процедуре:

множество из М сообщений располагают в порядке

убывания вероятностей;
первоначальный ансамбль кодируемых сигналов разбивают на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны;
первой группе присваивают символ 0, второй группе — символ 1;
каждую из подгрупп делят на две группы так, чтобы их суммарные вероятности были по возможности равны;
первым подгруппам каждой из групп вновь присваивают О, а вторым — 1, в результате чего получают вторые цифры кода. Затем каждую из четырех подгрупп вновь делят на равные (с точки зрения суммарной вероятности) части и т. д. до тех пор, пока в каждой из подгрупп останется по одной букве.

Избыточность кода Q(A,2) = 0,0249, т.е. около 2,5%

объединив два знака с наименьшими вероятностями (a5 и a6) и

заменив их одним знаком (например, a(1));

Вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15;

Остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном.

Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что число таких шагов будет равно N – 2, где N – число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей.

кода Q(r) = 0,00887, т.е. менее 1%.
 
Таким образом, можно

заключить, что существует метод построения оптимального неравномерного алфавитного кода.

Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах

код первичного алфавита строится цепочками равной длины, т.е. со всеми

знаками связано одинаковое количество информации равное I0.

Передавать признак конца знака не требуется, поэтому для определения длины кодовой цепочки можно воспользоваться формулой: K(2) = log2N.

Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует).

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

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

на смену азбуке Морзе.

Замечания:
Исходный алфавит должен содержать не более

32-х символов;

I = log232 = 5, т.е. каждый знак содержит 5 бит информации.

Условие N = 32, очевидно, выполняется для языков, основанных на латинском алфавите (N = 27 = 26 + «пробел»), однако в русском алфавите 34 буквы (с пробелом) – именно по этой причине пришлось «сжать» алфавит (как в коде Хаффмана) и объединить в один знак «е» и «ё», а также «ь» и «ъ».

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

Избыточность кода Бодо для русского языка Q(r) = 0,129, для английского Q(e) = 0,193.

Телеграфный код Бодо