Код

Материал из Википедии — свободной энциклопедии

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

[править] Кодирование

Процесс преобразования сообщения в комбинацию символов в соответствии с кодом называется кодированием, процесс восстановления сообщения из комбинации символов называется декодированием.

[править] Алфавиты

Множество символов, при помощи которых записываются исходные сообщения, называется первичным алфавитом, количество его элементов обозначается m₁. Множество символов, из которых могут состоять кодовые слова, называется вторичным алфавитом, количество элементов этого множества обозначается m₂.

[править] Длина кодовых слов

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

[править] Кодовые деревья

Для наглядного описания кодов используются кодовые деревья. Если число узлов на каждом его уровне содержит узлов, где l — номер уровня (корень дерева находится на нулевом уровне), оно называется полным. Очевидно, величина , называемая объёмом дерева, характеризует максимальное число кодовых комбинаций, которое можно построть при помощи данного дерева.

В теории построения трансляторов, такое дерево описывает множество всех возможных цепочек-выводов из формальной грамматики.

[править] Префиксное свойство

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

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

[править] Примеры

Равномерное кодирование: для алфавита с m₁ символами используются кодовые слова с длиной , где up - округление до большего целого. В этом случае неиспользованными остаются кодовых слов, а остальным проставляются в соответствие символы первичного алфавита. Код Бодо имеет фиксированную длину 5 символов.

Префиксные коды: Код Шеннона-Фано — первый алгоритм неравномерного кодирования. Код Хаффмана — известный метод построения оптимального неравномерного кода (ОНК) с использованием деревьев. Арифметическое кодирование — обобщение кода Хаффмана.

[править] Литература

Цымбал В.П. Теория информации и кодирование. — К.:Выща Школа, 1977. — 288 с.